# Questions tagged [data-streams]

The tag has no usage guidance.

33 questions
Filter by
Sorted by
Tagged with
120 views

### Counting distinct elements in a stream with expiration

Counting the number of distinct elements in a stream is a well-known and studied problem in computer science, for example Flajolet-Martin algorithm. There are algorithms for calculating the number of ...
64 views

### Sketching order statistics of a stream

Suppose we have a string stream over alphabet $[n]$. At each step, we would like to compute a sketch of the last $k$ elements, such that from the sketch we can approximate their relative order. For ...
118 views

### Sublinear finite-precision sampling in a stream

I am looking to sample a single item from a stream such that each item in the stream has an equal probability of being selected. This is a restricted version of the reservoir sampling problem. On a ...
221 views

### Why is HyperLogLog (near-)optimal?

The original HyperLogLog paper claims that this probabilistic counting algorithm is "near-optimal". The relevant section of the paper reads: Clearly, maintaining $\epsilon$-approximate counts till ...
322 views

### How much memory is needed for counting distinct elements in a stream exactly with high probability

Assume we know a parameter $n\in\mathbb N$, and then get to observe a sequence of elements $x_1,\ldots, x_n$, one at a time. Our goal is to count the number of distinct elements in $x_1,\ldots, x_n$, ...
231 views

### Streaming algorithms for sum

First of all, I am not sure whether this is a research level question. Please let me know if it is not. The question is about streaming algorithms for the sum of the given data stream. From ...
77 views

### Does bisimulation or the approximation lemma work for monadic streams?

For ordinary streams $S_A := \nu X. A \times X$, there is a bisimulation lemma. It says that two streams are equal if there exists a bisimulation between them. A bisimulation is a relation $\sim$ on ...
159 views

### Finding median in a changing array

Consider the problem of needing to support an $n$ integers array structure with two operations: Set(k,v) - set the $k$'th integer to value $v$ (i.e. $A[k]=v$). Median() - return the median value of ...
100 views

### Lower bounds for randomized frequency estimation algorithms

Consider a stream of elements $s_1s_2\ldots s_N$. A counter-based frequency estimation algorithm uses $m$ counters and is required to answer queries of the form "How many times did $x$ appear"? It ...
68 views

### Constructing a bad sequence for counter algorithm

Assume that we want to construct a sequence $s\in\{a,b\}^{N}$ such that $s$ contains exactly $n$ times the letter '$a$'. The sequence is then feed to the following probabilistic algorithm: ...
852 views

### Algorithm for finding heavy hitters in a weighted stream

The problem of finding heavy hitters in a stream is defined as follows: given a $N$ sized stream of elements, return a set $\mathcal D$, such that every item which arrived at least $N\theta$ times ...
240 views

### Integer queue summation

As part of a project I'm working on, we came up with an efficient algorithm for approximating the sum of an integers queue. The setting is as follows: Let $\epsilon>0$. we need to maintain a space-...
143 views

87 views

### Questions on “Improved Sketching of Hamming Distance with Error Correcting” by Porat and Lipsky

What is the proof of lemma 4.3 in this paper? http://u.cs.biu.ac.il/~porately/papers/submission_24.pdf That is, how does it follow from 4.1 and 4.2? Also, why is the constant 8 necessary? How is it ...
154 views

### Functions and Counting Problems in Streaming Computation

I have read a stream computation paper in STOC07(Paul Beame, T. S. Jayram, and Atri Rudra. Lower bounds for randomized read/write stream algorithms.) and FOCS08（Paul Beame and Trinh Huynh. On the ...
304 views

580 views

### Best sources on data stream algorithms

I recently got interested in data stream algorithms to the point that I'd like to study the topic and then teach it to someone. I'd be thus grateful for pointers to really good sources on the topic, ...
6k views

### Algorithm for 'k'' most frequently occurring numbers

I have been searching for the most efficient (streaming??) algorithm that tells me the 'k' most frequently occurring elements in a data stream at any point in time. This post: "Divide and conquer&...