# Questions tagged [streaming-algorithm]

Streaming reads the data once, in sequence.

57 questions
Filter by
Sorted by
Tagged with
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 ...
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),...
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. ...
• 125
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 ...
• 123
1 vote
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$ ...
• 123
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 ...
• 115
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]$...
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 ...
• 127
1 vote
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: ...
• 141
1 vote
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 ...
• 829
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$ ...
• 193
1 vote
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$ ...
• 193
1 vote
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 ...
• 69
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\}$ ...
• 193
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: ...
• 829
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 ...
1 vote
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 ...
• 47
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 ...
• 181
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 ...
• 829
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 ...
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 ...
1 vote
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  \...
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 ...
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,...
• 133
1 vote
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 ...
• 11
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 ...
• 183
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 ...
• 153
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 ...
• 121
1 vote
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 ...
• 1,287
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 ...
• 241
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 &...
1 vote
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 ...
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 ...
• 1,118
1 vote
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 ...
• 401
1 vote
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 ...
1 vote
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 ...
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 ...
• 143
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$ ...
• 205
1 vote
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
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 ...
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 ...
1 vote
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 ...
• 11
1 vote
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 ...
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$) ...
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 ...
• 101
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 ...
• 1,085
962 views