Questions tagged [streaming-algorithm]
Streaming reads the data once, in sequence.
60
questions
0
votes
0
answers
86
views
How to determine the width and depth of a count-min sketch, depending of the unique elements inside
Follow up this question:
What is the correct way to determine the width and depth of a count-min sketch?
Let suppose, correct way is following:
...
- 101
0
votes
0
answers
10
views
On the definition of multiple-passes random order streaming algorithms
Some problems have better streaming algorithms if we assume that the input arrives in a random order.
I am looking at a paper that discusses multiple-passes random order streaming algorithms and am ...
- 141
0
votes
0
answers
19
views
maximum k- coverage when the universe is streaming
I am studying the maximum k-coverage problem when the universe is streaming (rather than the subsets). Formally, Let $U$ be a universe set which is unknown at the beginning. We have $n$ subsets ...
- 115
-1
votes
1
answer
39
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
-5
votes
1
answer
447
views
Implementing Flajolet–Martin algorithm in Python
I am stuck on what to do.
I am trying to create a simple implementation of the Flajolet–Martin algorithm using Python. The stream will be the contents of a text file and you will produce an ...
3
votes
2
answers
125
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),...
- 623
2
votes
1
answer
1k
views
Applications of the DGIM algorithm
In the field of mining of data streams the algorithm of Datar-Gionis-Indyk-Motwani (DGIM, M. Datar, A. Gionis, P. Indyk, and R. Motwani, “Maintaining stream statistics over sliding windows,” SIAM J. ...
- 125
0
votes
1
answer
56
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
1
vote
0
answers
49
views
Is there a distributed streaming algorithm to verify set cover?
I have $k$ sets of similar sizes, that cover a universe $U$.
e.g. for $k=3$ and $U = \{1, 2, 3, 4, 5, 6\}$:
$S_0 = \{1, 2, 4\}$
$S_1 = \{2, 3, 4\}$
$S_2 = \{4, 5, 6\}$
I have another larger set $C$ ...
- 123
6
votes
1
answer
628
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]$...
- 623
0
votes
1
answer
58
views
Streaming interval cover algorithm
I'm given a target integer range $[x, y]$ which needs to be covered $n$ times, and a stream of integer ranges $[x_i, y_i]$. I need an algorithm which consumes integer ranges from the stream and ...
- 127
1
vote
1
answer
23
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
162
views
A one-pass heavy hitter algorithm
I was shown this problem from a class last year and I am still not sure what the right answer is.
Items that occur with high frequency in a dataset are sometimes called heavy hitters. Accordingly, let ...
- 880
2
votes
1
answer
42
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
1
answer
54
views
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
89
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
2
votes
1
answer
174
views
$\epsilon$-approximation Sub-linear time monotonicity testing
I have the following exercise I have been staring at for several hours to no avail.
Question:
Testing the monotonicity of a function - the case of bits: Given a function $f: [n] \rightarrow \{0,1\}$ ...
- 193
0
votes
1
answer
75
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:
...
- 880
0
votes
1
answer
60
views
Big o notation for sublinear algorithm in streaming algorithm
Excuse me if this is obvious.
At 1:55 of this Coursera video on streaming algorithms (see pasted image below for relevant slide), the professor mentions sublinear storage. I get the $N^{\alpha}$ but I ...
- 659
1
vote
1
answer
79
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 ...
- 47
3
votes
2
answers
64
views
Semi-streaming algorithm for $s$-$t$ connectivity
Let $G=(V,E)$ be an undirected graph. Given a pair of vertices $s,t \in V$, how can we construct a semi-streaming algorithm which determines is $s$ and $t$ are connected? Is there any way to construct ...
- 181
2
votes
1
answer
69
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 ...
- 880
0
votes
0
answers
25
views
Analyzing a counting triangles streaming algorithm which uses $\ell_0$ sampling
I'm trying to analyze the following streaming algorithm for counting triangles (see below). It supposedly works also for dynamic graphs (i.e. "turnstile model", where edge deletions are ...
- 43
2
votes
1
answer
152
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
1
vote
1
answer
87
views
1-sparse recovery algorithm
In the reference below, a 1-sparse recovery algorithm over a vector $a \in R^n$ is defined as follows. My question is why do we need the modulus (i.e. $x \mod p$)?
Algorithm:
Keep track of
$$
\...
- 43
2
votes
1
answer
54
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
3
votes
1
answer
3k
views
Flajolet-Martin Algorithm : question about use of certain hash functions
this is a question given in a PDF about streaming algorithms (this isnt an assignment but im trying to understand)
Exercise 4.4.1 : Suppose our stream consists of the integers 3, 1, 4,
1, 5, 9, 2,...
- 133
2
votes
5
answers
682
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 ...
- 21
3
votes
1
answer
234
views
Matrix element value counting in O(1) space
The question arise from my customer's real-time system (RAM model, off-course), which has very limited resources.
Given an NxM matrix of integer values, we need to verify that the number of non-zero ...
- 237
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
2
votes
0
answers
119
views
What are some of the simplest applications of heavy hitter problem?
I am learning about stream algorithms and am implementing Count-Min sketch data structure. I am also learning to approximately solve the HH problem with sublinear space complexity.
I want to know ...
- 121
1
vote
1
answer
1k
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,331
2
votes
0
answers
88
views
Different properties of Heavy-Hitters and Count-Min Sketch algorithms?
I'm currently using the Heavy-Hitters algorithm as described here and I'm wondering what if any space, time, accuracy, or real-world performance differences I would see if I were to switch to an ...
- 251
2
votes
1
answer
3k
views
Efficient streaming sort
Consider following task: we have an input of N+1 lines, where first line contains N - number of items, and then we have N lines, each one contains one item, which is a tuple (number id, number m), id &...
- 227
1
vote
1
answer
235
views
Proof of Lower Bound for Deterministic Distinct Elements Algorithm
There is a proof in this document (page 8, Section 4, Lemma 3: https://inst.eecs.berkeley.edu/~cs170/fa16/lecture-11-29.pdf) that mirrors a proof my professor gave in my algorithms class. The lemma ...
2
votes
0
answers
829
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,138
1
vote
1
answer
182
views
What does 'buffering' mean?
I read the lecture 4 of CS162 (UC Berkeley: https://inst.eecs.berkeley.edu/~cs162/sp17/static/lectures/4.pdf), but I got little bit confused about the meaning of the keyword "buffered" they used when ...
- 411
1
vote
1
answer
719
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
1
vote
0
answers
303
views
What is the best stream data clustering algorithm that can handle non-static, uncertain data? [closed]
I have gone through many algorithms including streaming k-means, CluStream etc and they all have their pros and cons. What is the best performing algorithm in terms of
Computational Complexity
...
- 11
3
votes
1
answer
224
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
9
votes
2
answers
1k
views
Counting islands in Boolean matrices
Given an $n \times m$ Boolean matrix $\mathrm X$, let $0$ entries represent the sea and $1$ entries represent land. Define an island as vertically or horizontally (but not diagonally) adjacent $1$ ...
- 215
1
vote
0
answers
46
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 ...
- 111
5
votes
3
answers
2k
views
Streaming parsing algorithms
A parser is a procedure which decides if an input belongs to a certain language and produces a witness in the form of a parse tree.
Let a streaming parser be a parser which for any prefix $u$ can ...
- 173
0
votes
1
answer
3k
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
1
vote
0
answers
215
views
What data structure is best suited for nested values and count of values?
I have incoming stream of data which has following values.
Country, City, State
Along with maximum number of unique values to store (e.g. 50,22,12).
I need to design a system which will keep count of ...
- 11
1
vote
1
answer
183
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 ...
- 11
6
votes
0
answers
3k
views
What is the correct way to determine the width and depth of a count-min sketch?
The width (number of registers) and depth (number of hash functions) of a Count-Min sketch determine the accuracy of counts retrieved.
I've found two different methods for calculating the width ($w$) ...
- 161
-1
votes
1
answer
232
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
0
votes
0
answers
213
views
How does hashing achieve sketching?
Given a sequence $x \in \{ 1,2,3...,\vert \Sigma \vert \}^*$ one wants to create a sketch of it say $s(x)$ of size $\frac{2c}{3}k (ln^2 k)$ bits. And that seems to be achieved as follows,
pick at ...
- 1,115
2
votes
1
answer
1k
views
Count-Min sketch: dyadic ranges
Can anyone give me a proof as to why
Any range over a unviverse {1...n} can be reduced to at most $2log_2n$
disjoint dyadic ranges?
Where a dyadic range is a range of the form $[x2^y+1....(x+...
- 143