Questions tagged [data-streams]
The data-streams tag has no usage guidance.
33
questions
6
votes
0answers
110 views
Counting distinct elements in a stream with expiration
Counting the number of distinct elements in a stream is a well-known and studied problem in computer science, for example Flajolet-Martin algorithm.
There are algorithms for calculating the number of ...
1
vote
0answers
63 views
Sketching order statistics of a stream
Suppose we have a string stream over alphabet $[n]$. At each step, we would like to compute a sketch of the last $k$ elements, such that from the sketch we can approximate their relative order. For ...
3
votes
1answer
117 views
Sublinear finite-precision sampling in a stream
I am looking to sample a single item from a stream such that each item in the stream has an equal probability of being selected. This is a restricted version of the reservoir sampling problem.
On a ...
5
votes
0answers
221 views
Why is HyperLogLog (near-)optimal?
The original HyperLogLog paper claims that this probabilistic counting algorithm is "near-optimal". The relevant section of the paper reads:
Clearly, maintaining $\epsilon$-approximate counts till ...
6
votes
1answer
316 views
How much memory is needed for counting distinct elements in a stream exactly with high probability
Assume we know a parameter $n\in\mathbb N$, and then get to observe a sequence of elements $x_1,\ldots, x_n$, one at a time.
Our goal is to count the number of distinct elements in $x_1,\ldots, x_n$, ...
2
votes
0answers
225 views
Streaming algorithms for sum
First of all, I am not sure whether this is a research level question. Please let me know if it is not.
The question is about streaming algorithms for the sum of the given data stream. From ...
5
votes
1answer
76 views
Does bisimulation or the approximation lemma work for monadic streams?
For ordinary streams $S_A := \nu X. A \times X$, there is a bisimulation lemma. It says that two streams are equal if there exists a bisimulation between them. A bisimulation is a relation $\sim$ on ...
3
votes
0answers
154 views
Finding median in a changing array
Consider the problem of needing to support an $n$ integers array structure with two operations:
Set(k,v) - set the $k$'th integer to value $v$ (i.e. $A[k]=v$).
Median() - return the median value of ...
6
votes
0answers
100 views
Lower bounds for randomized frequency estimation algorithms
Consider a stream of elements $s_1s_2\ldots s_N$.
A counter-based frequency estimation algorithm uses $m$ counters and is required to answer queries of the form "How many times did $x$ appear"?
It ...
4
votes
0answers
66 views
Constructing a bad sequence for counter algorithm
Assume that we want to construct a sequence $s\in\{a,b\}^{N}$ such that $s$ contains exactly $n$ times the letter '$a$'.
The sequence is then feed to the following probabilistic algorithm:
...
6
votes
3answers
824 views
Algorithm for finding heavy hitters in a weighted stream
The problem of finding heavy hitters in a stream is defined as follows: given a $N$ sized stream of elements, return a set $\mathcal D$, such that every item which arrived at least $N\theta$ times ...
7
votes
0answers
233 views
Integer queue summation
As part of a project I'm working on, we came up with an efficient algorithm for approximating the sum of an integers queue.
The setting is as follows: Let $\epsilon>0$. we need to maintain a space-...
5
votes
1answer
140 views
Single-pass streaming quantile estimation using moments
Is it possible to estimate within $\epsilon$ the quantiles of a set of integers $\{x_1, x_2, \dots, x_n\}$ given only the values $\sum x_i^0,\sum x_i^1, \sum x_i^2, \dots, \sum x_i^{f(n)}$ where $f \...
1
vote
1answer
143 views
Are the `ArrowApply` and `Monad` typeclasses equivalent?
It is stated e.g. on Hackage, that the ArrowApply and the Monad typeclasses are equivalent. I have my doubts about this.
It is ...
2
votes
0answers
104 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
66 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 \{a_1,a_2,...
2
votes
2answers
3k 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
83 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)
...
7
votes
1answer
874 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 \{1,2,...
0
votes
0answers
87 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
154 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 ...
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
$\...
20
votes
5answers
446 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 ...
6
votes
2answers
571 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 ...
15
votes
5answers
19k 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 ...
2
votes
0answers
304 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
246 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 DYCK(...
18
votes
2answers
596 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:...
8
votes
2answers
968 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 ...
7
votes
3answers
564 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, ...
20
votes
2answers
6k 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: "Divide and conquer&...
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 ...
9
votes
4answers
448 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 ...
