Tagged Questions

The tag has no wiki summary.

learn more… | top users | synonyms

2
votes
0answers
64 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
59 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
315 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
71 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
307 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
0answers
72 views

Questions on “Improved Sketching of Hamming Distance with Error Correcting” by Porat and Lipsky

What is the proof of lemma 4.3 in this paper? http://u.cs.biu.ac.il/~porately/papers/submission_24.pdf That is, how does it follow from 4.1 and 4.2? Also, why is the constant 8 necessary? How is it ...
0
votes
1answer
137 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
224 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
373 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
451 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
194 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
164 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 ...
18
votes
2answers
365 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
318 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 ...
6
votes
3answers
402 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, ...
17
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: ...
11
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 ...
8
votes
4answers
316 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 ...