Questions tagged [data-streams]
The data-streams tag has no usage guidance.
37
questions
0
votes
0
answers
75
views
Finding lightest k elements in data stream using small space
There has been much research and progress devoted towards algorithms for finding approximate $\ell_p$-Heavy Hitters with parameter $\epsilon$ in the streaming setting (For all 3 of the vanilla, ...
- 1
0
votes
1
answer
101
views
Boosting the probability of success(random projections, johnson lindenstrauss)
In the simple proof of the johnson lindenstrauss lemma written by Sanjoy Dasgupta, Anupam Gupta that can be found here they state the following (p.$62$):
Repeating this projection $O(n)$ times can ...
6
votes
2
answers
305
views
How to show that the median cannot be maintained in $O(1)$ time?
Suppose that we have a stream of numbers $x_1,x_2,\ldots$ such that we wish to track the median of the values observed so far.
This task is easy to do with $O(\log n)$ update time (where $n$ is the ...
- 63
0
votes
2
answers
307
views
Finding top-K items in a sliding window
Imagine we have a stream of bank transactions.
Each transaction has a target account and some amount of money.
I'd like to find top K accounts over some period of time (e.g. last 7 days) which ...
- 233
6
votes
0
answers
365
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
0
answers
66
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 ...
- 679
4
votes
1
answer
136
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 ...
- 11.2k
5
votes
0
answers
226
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 ...
- 329
6
votes
1
answer
392
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$, ...
- 9,438
2
votes
0
answers
303
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 ...
- 1,345
4
votes
1
answer
84
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 ...
- 584
3
votes
0
answers
181
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 ...
- 9,438
6
votes
0
answers
118
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 ...
- 9,438
4
votes
0
answers
71
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:
...
- 9,438
6
votes
3
answers
970
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 ...
- 9,438
7
votes
0
answers
277
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-...
- 9,438
5
votes
1
answer
153
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 \...
- 11.2k
1
vote
1
answer
177
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 ...
- 584
2
votes
0
answers
121
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 ...
- 393
1
vote
0
answers
67
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,...
- 13
2
votes
2
answers
4k
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 ...
- 161
0
votes
1
answer
85
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)
...
- 113
7
votes
1
answer
928
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,...
- 395
0
votes
0
answers
93
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 ...
- 11
0
votes
1
answer
164
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 ...
- 317
11
votes
3
answers
326
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
$\...
- 779
20
votes
5
answers
468
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 ...
- 18.9k
6
votes
2
answers
592
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 ...
17
votes
6
answers
23k
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 ...
- 273
2
votes
0
answers
309
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 ...
- 747
5
votes
1
answer
289
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(...
- 1,631
18
votes
2
answers
668
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:...
- 1,831
8
votes
2
answers
1k
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 ...
- 763
7
votes
3
answers
634
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, ...
- 8,911
20
votes
2
answers
7k
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&...
- 460
12
votes
6
answers
2k
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,911
9
votes
4
answers
456
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 ...
brian