Questions tagged [data-streams]
The data-streams tag has no usage guidance.
4
questions
6
votes
2
answers
578
views
Incremental drawing of large graphs
I have the following problem:
I'm developing a software for data visualization where I get a graph structure and represent it in 3D space. So far, I've been using force-based algorithms to draw graphs ...
18
votes
2
answers
656
views
Storage requirements for median selection (two passes algorithms)
In a classic paper Munro and Paterson study the problem of how much storage is required for an algorithm to find the median in a randomly sorted array. In particular they focus on the following model:...
11
votes
3
answers
319
views
Bounds on approximating frequency moments
Let $a_1, a_2,\dotsc, a_m$ be a sequence of integers where each $a_j \in \{1,2,\dotsc,n\}$. For $i \in \{1,2,\dotsc,n\}$, let $m_i = |\{j : a_j = i\}|$. The $k$th frequency moment is defined to be
$\...
12
votes
6
answers
2k
views
"Divide and conquer" data stream algorithms
What useful algorithms do there exist that work on huge data streams and also their results are fairly small and one can compute the result for a mixture of two streams by somehow merging their ...