The tag has no wiki summary.

learn more… | top users | synonyms

2
votes
0answers
60 views

Which paper to cite when referring to reservoir sampling *with replacement*?

As far as I can tell, the term "reservoir sampling" is commonly used to refer to sampling without replacement and references [1], [2], and [3] are cited while mentioning it. When referring to ...
1
vote
0answers
57 views

Bound the number of rounds in the sampling

Suppose we have a sequence $a_1,a_2,\ldots, a_n$, each $a_i$ is sampled uniformly and independently from $[0,1]$. Define $$ J_1=1,\\ \text{for}~i>1, ~J_i = 1 \iff a_i < \min ...
1
vote
2answers
299 views

What are the algorithms and the data structures for GUIs and input management?

I'm studying how, given: an input from the user ( like a click of the mouse or the input from a key ) a well defined data structure that represent the graphical layout inside a window ( a tree/graph ...
0
votes
1answer
69 views

“Computing on data streams” clarification

In the 1998 technical note "Computing on data streams" by Monika Rauch Henzinger , Prabhakar Raghavan , Sridar Rajagopalan (found here: http://www.eecs.harvard.edu/~michaelm/E210/datastreams.pdf) ...
4
votes
1answer
276 views

Streaming Algorithms: Motivations for estimating frequency moments

The celebrated AMS paper "The space complexity of approximating the frequency moments" defines the problem as following: Let $a_1, a_2,\dotsc, a_m$ be a sequence of integers where each $a_j \in ...
0
votes
1answer
136 views

Functions and Counting Problems in Streaming Computation

I have read a stream computation paper in STOC07(Paul Beame, T. S. Jayram, and Atri Rudra. Lower bounds for randomized read/write stream algorithms.) and FOCS08(Paul Beame and Trinh Huynh. On the ...
9
votes
3answers
221 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 ...
20
votes
5answers
371 views

Reducing space usage of st-connectivity with multiple passes?

Suppose a graph $G$ with $n$ vertices is presented as a stream of $m$ edges, but multiple passes are allowed over the stream. Monika Rauch Henzinger, Prabhakar Raghavan, and Sridar Rajagopalan ...
5
votes
2answers
440 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 ...
8
votes
5answers
2k views

Which is the limit of lossless compression data? (if there exists such a limit)

Lately I've been dealing with compression-related algorithms, and I was wondering which is the best compression ratio that can be achievable by lossless data compression. So far, the only source I ...
1
vote
0answers
185 views

Simple to implement approximate quantile data structure for a stream of integers?

I'm looking for a simple data structure that will let me compute arbitrary approximate quantiles, within a percent or two error, on a stream of 64-bit integers (think of $n$ as being potentially as ...
4
votes
1answer
162 views

Why does deterministic recognition of DYCK(2) languages in the streaming model take linear space?

I was reading the paper "Recognizing Well-Paranthesized Expressions in the Streaming Model" by Magniez, Mathieu and Nayak where they give upper and lower bounds on the space required to recognize ...
17
votes
2answers
360 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 ...
8
votes
2answers
310 views

Lower bound of checking graph connectivity on stream

I would like to check the status of the space lower bound for solving connectivity problem on stream in $p$ passes. The $\Omega(n/p)$ was stated in the literature but it seems to be for a slightly ...
5
votes
3answers
399 views

Best sources on data stream algorithms

I recently got interested in data stream algorithms to the point that I'd like to study the topic and then teach it to someone. I'd be thus grateful for pointers to really good sources on the topic, ...
16
votes
4answers
3k views

Algorithm for 'k'' most frequently occurring numbers

I have been searching for the most efficient (streaming??) algorithm that tells me the 'k' most frequently occurring elements in a data stream at any point in time. This post: ...
10
votes
6answers
962 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 ...
8
votes
4answers
315 views

Continuous Clustering

So I have an issue I'm facing in regards to clustering with live, continuously streaming data. Since I have an ever-growing data set I'm not sure what is the best way to run efficient and effective ...