# Questions tagged [streaming-algorithm]

Streaming reads the data once, in sequence.

34 questions
Filter by
Sorted by
Tagged with
263 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,...
105 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 ...
222 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 ...
1k 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 ...
85 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 ...
163 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 ...
78 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 ...
1k 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 &...
114 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 ...
407 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 ...
117 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 ...
389 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 ...
268 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 ...
203 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 ...
975 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$ ...
44 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 ...
1k 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 ...
165 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 ...
157 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 ...
1k 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$) ...
223 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 ...
202 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 ...
777 views

804 views

### Is every linear-time algorithm a streaming algorithm?

Over at this question about inversion counting, I found a paper that proves a lower bound on space complexity for all (exact) streaming algorithms. I have claimed that this bound extends to all linear ...
536 views

### Counting with constant space bounded TMs

The problem, coming from an interview question, is: You have a stream of incoming numbers in range 0 to 60000 and you have a function which will take a number from that range and return the ...
### Choosing an element from a set satisfying a predicate uniformly at random in $O(1)$ space
We are given a set of objects, say integers, $S$. In addition, we are given a predicate $P$, for example $P(i): \Leftrightarrow i \geq 0$. We don't know in advance how many elements of $S$ satisfy the ...
Consider an array $X$ of $n$ cells, each containing a number from $\{1,..., n\}$. There is at least one duplicate number, i.e., a number that appears at least twice. I want output some duplicate ...