Questions tagged [streaming-algorithm]

Streaming reads the data once, in sequence.

Filter by
Sorted by
Tagged with
-5 votes
1 answer
79 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 ...
user avatar
3 votes
2 answers
85 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),...
user avatar
2 votes
1 answer
273 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. ...
user avatar
  • 125
0 votes
1 answer
36 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 ...
user avatar
  • 123
1 vote
0 answers
47 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$ ...
user avatar
  • 123
0 votes
0 answers
25 views

Good sources that treat "sliding window" whiteboarding-style problems?

This is a reference request for algorithms textbooks that address the common "sliding window" problems that come up in whiteboarding. If not textbooks per se, I'm looking for a more ...
user avatar
  • 115
6 votes
1 answer
368 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]$...
user avatar
0 votes
1 answer
49 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 ...
user avatar
  • 127
1 vote
1 answer
22 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: ...
user avatar
  • 141
1 vote
1 answer
77 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 ...
user avatar
  • 829
2 votes
1 answer
30 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$ ...
user avatar
  • 193
1 vote
1 answer
32 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$ ...
user avatar
  • 193
1 vote
2 answers
50 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 ...
user avatar
  • 69
2 votes
1 answer
106 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\}$ ...
user avatar
  • 193
0 votes
1 answer
54 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: ...
user avatar
  • 829
0 votes
1 answer
45 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 ...
user avatar
1 vote
1 answer
67 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 ...
user avatar
  • 47
3 votes
2 answers
55 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 ...
user avatar
2 votes
1 answer
60 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 ...
user avatar
  • 829
0 votes
0 answers
23 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 ...
user avatar
2 votes
1 answer
67 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 ...
user avatar
1 vote
1 answer
74 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 $$ \...
user avatar
2 votes
1 answer
46 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 ...
user avatar
3 votes
1 answer
2k 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,...
user avatar
  • 133
1 vote
5 answers
411 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 ...
user avatar
  • 11
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 ...
user avatar
  • 183
2 votes
1 answer
3k 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 ...
user avatar
2 votes
0 answers
112 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 ...
user avatar
1 vote
1 answer
831 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 ...
user avatar
2 votes
0 answers
85 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 ...
user avatar
  • 241
2 votes
1 answer
2k 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 &...
user avatar
1 vote
1 answer
190 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 ...
user avatar
2 votes
0 answers
686 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 ...
user avatar
  • 1,118
1 vote
1 answer
145 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 ...
user avatar
1 vote
1 answer
633 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 ...
user avatar
1 vote
0 answers
290 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 ...
user avatar
3 votes
1 answer
220 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 ...
user avatar
  • 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$ ...
user avatar
  • 205
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
1 vote
0 answers
204 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 ...
user avatar
  • 11
1 vote
1 answer
167 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 ...
user avatar
6 votes
0 answers
2k 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$) ...
user avatar
-1 votes
1 answer
230 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 ...
user avatar
  • 101
0 votes
0 answers
208 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 ...
user avatar
  • 1,085
2 votes
1 answer
962 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+...
user avatar
  • 143
4 votes
0 answers
162 views

Computing parity of a permutation in a streaming-fashion way

I'm looking for a one-pass algorithm which computes parity of a permutation. I assume that an input permutation is given by stream $\pi[1], \pi[2], \cdots, \pi[n]$. The output should be the parity of ...
user avatar
1 vote
0 answers
201 views

Binary search transition point of a function on stream

Consider an unknown function $f(x,y)$, where $x$ and $y$ are just two scalar numbers in $[0,1]$. $f(x,y)$ is an increasing function of $y$ and is between $0$ and $1$ but is unknown. At each time I ...
user avatar
  • 111
3 votes
2 answers
355 views

Forward Error Correction for streaming data

I am very familiar with error correcting codes. However, it is not obvious how to apply them to adaptive streaming data. There also doesn't seem to be much literature on the problem. The naive ...
user avatar