Questions tagged [data-streams]
The data-streams tag has no usage guidance.
4
questions
6
votes
2answers
570 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
2answers
581 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
3answers
304 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
6answers
1k 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 ...
