Questions tagged [streaming-algorithm]
Streaming reads the data once, in sequence.
61 questions
0
votes
0
answers
22
views
Questions about decidability and streaming algorithm
I was working on some conceptual parts about the Turing Machine and streaming algorithm, and got a bit stuck. Below is the statement I am trying to prove.
“If L has a streaming algorithm, then L is ...
1
vote
0
answers
268
views
Chernoff bound on the maximum of multinomial distribution
I am reading some heavy hitter (HH) papers
when I run into the following reduction theorem.
The theorem attempts to reduce
an HH problem with a very small tail frequency $\epsilon$
to multiple HH ...
- 61
-1
votes
1
answer
61
views
Compute sum of moduli for a stream of integer numbers
We receive a stream of $n$ integer numbers: $x_1, x_2,\dots, x_n$. Assume that each $x_i$ is a constant and can be stored with $O(1)$ bits.
Whenever a new number $x_i, i \geq 2$ is inputted, we need ...
- 11
3
votes
2
answers
220
views
Sorted degrees and maximal degree in dynamic graphs
Consider a sequence of vertex and edge additions and removals to an initially empty (undirected, simple) graph.
Is it possible to update the ordered list of vertex degrees in constant time (and space),...
- 685
0
votes
1
answer
153
views
Is the equality of Bloom filters analogous to set equivalence?
I have two multisets $A$, $B$ where $A \subseteq B$.
Using these two sets, we construct two Bloom filters $BF(A), BF(B)$; both using bitsets of size $n$ with the same $k$ hash functions.
What's the ...
- 123
6
votes
1
answer
1k
views
Fast and compact data structure for dynamic graphs
A graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ may be represented in central memory as follows:
an associative array (hash table) $V$ gives for any $v\in \mathcal{V}$ the list of its neighbors $V[v]$...
- 685
1
vote
1
answer
68
views
Matching two noisy / lossy versions of the same data stream to each other
Say I have two noisy / lossy streams of symbols of the same data. Essentially, I want to match up the two streams as best as possible. For example, say I have:
...
- 141
2
votes
1
answer
90
views
Understanding contradiction in proof of Algorithm for Testing of Clustering of points in metric space in sub-linear time
I am trying to understand this paper, in which (k, b)-clusterability is defined like so:
A set $X$ of points in a metric space is (k, b)-diameter clusterable if $X$ can be partitioned into $k$ ...
- 193
1
vote
2
answers
254
views
Probability that two specific elements are in uniformly random sample
Consider the sampling algorithm as described here section 2.2 specifically Algorithm 2.4.
Essentially we are given a stream of $N$ elements and wish to maintain a uniformly random sample, $S$, of size ...
- 190
0
votes
1
answer
126
views
What is the right data structure for MST in a stream
In a single pass stream you can compute the minimum spanning tree (MST) in an undirected graph using the following algorithm:
...
- 1,036
1
vote
1
answer
133
views
Solving number of distinct elements in $O(\frac{n\ell}{p})$ space complexity with $2p$ passes over data
Suppose there is an n-element stream with elements from $\{0,1\}^\ell$ which means each element is in set $\{0, \dots , 2^\ell-1\}$. Also may assume $2^\ell >n^2$. How can I with $2p$ passes over ...
- 57
2
votes
1
answer
126
views
Confused by proof of correctness of Majority
I have been studying a streaming algorithm to determine if there is a majority element in a stream. But am confused by a proof for it.
The algorithm works as follows. You keep one counter $c$ and a ...
- 1,036
2
votes
1
answer
280
views
Streaming algorithm for counting triangles in a graph
As described in the reference, the algorithm (see at the bottom) supposes to output an estimator $\hat T$ for the # of triangles in a given graph $G = (V, E)$, denoted $T$. It is written that "it ...
- 43
2
votes
1
answer
99
views
A way to express LTL (varient) to enforce a stream of data to satisfy some linear time logic
Linear Time Logic (LTL) is used for system verification. In my case, I am investing some time, to see the feasibility of using LTL this time to enforce a constraint on a stream of data. Enough of ...
- 195
4
votes
5
answers
1k
views
sliding window maximum
I have a stream of tuples arriving in the following form: (timestamp,price). There is no pattern in the arrival of these data points (number of data points per minute is random). I need to be able to ...
- 41
2
votes
1
answer
4k
views
How to best maintain a sorted list from a stream of integers?
If I have an incoming stream of integers how can I best maintain a sorted list of them? The only way I can think of is to binary search for the position and shifting the remaining elements to the ...
- 153
1
vote
1
answer
2k
views
Is there a fast algorithm for computing the rolling mode of an array of integers?
I was wondering if there exists an efficient algorithm for calculating the "rolling mode of an array of integers.
By rolling mode I mean that we have an array of integers of size $n$ and a sliding ...
- 1,351
3
votes
2
answers
3k
views
Efficient streaming sort
Consider following task:
we have an input of N+1 lines, where first line contains N ≤ 150000 - number of items, and then we have N lines, each one contains one item, which is a tuple (number id, ...
- 237
2
votes
0
answers
952
views
How much better are conservative updates for count-min sketch?
I've been reading about count-min sketch and I'm interested in the performance of this data structure when doing conservative updates. To my understanding from the Wikipedia article, conservative ...
- 1,168
1
vote
1
answer
827
views
Algorithm for finding 2 missing items in a stream of integers
I saw this post and wondered why the approach described in the accepted answer works. The same problem and solution is described a bit nicer here.
So let's say we receive a stream of $n-2$ pairwise ...
- 427
3
votes
1
answer
254
views
Reducing randomness needed by turing machine
I am reading an article related to streaming algorithms named "Turnstile streaming algorithms might as well be linear sketched" by Yi Li, Huy Nguyen and David Woodruff,
At some point they have a ...
- 143
2
votes
0
answers
70
views
What resources are there for students to compute on a data stream?
I teach a randomized algorithms course, and many of the cool applications are to streaming computation. I can have students implement these algorithms in Python or C++, but I feel it would be much ...
- 121
0
votes
1
answer
4k
views
Find pth percentile of a stream of numbers
I want to find the pth percentile of a stream of integers, exactly (not approximately).
If we know the number of integers which will be coming in the stream and the numbers can fit into the memory ...
Astha Gupta
2
votes
1
answer
238
views
Optimal data structure for a time-windowed streaming graph in order to compute fast statistics
I apologize if this is the wrong place or too trivial a question for this community. What is the best data structure to store a time-windowed streaming graph in order to compute fast statistics over ...
- 21
-1
votes
1
answer
269
views
Find the 10 top most occurring strings in a huge array of objects
Find the 10 top most occurring strings in a huge array of Strings.
Since the array is huge, it is not possible to load it in memory completely.
My idea is to parse the arrays one by one and put the ...
- 101