Questions tagged [data-streams]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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 ...