Streaming reads the data once, in sequence.

learn more… | top users | synonyms

0
votes
1answer
29 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
0answers
26 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 ...
1
vote
1answer
97 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 ...
3
votes
0answers
96 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$) ...
-1
votes
1answer
98 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 ...
0
votes
0answers
67 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 ...
2
votes
1answer
179 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....(...
4
votes
0answers
75 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 ...
1
vote
0answers
92 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 ...
3
votes
2answers
46 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 ...
5
votes
4answers
474 views

Space complexity for finding the minimum number outside the list of numbers

We are given an (unsorted) list $L=(a_1,\dots,a_n)$ of numbers of size $n$, where $a_i\in \{ 1,\dots,B\}$. We want to find the minimum number $x$ from $\{ 1,\dots,B\} \backslash L$. What is the ...
1
vote
0answers
338 views

Streaming Knapsack Problem

I want to implement efficiently "streaming Knapsack" problem in java. The problem is I have a stream input of integer data coming continuously for example -1, 2, 9, 5, 5, 11, 1 -3,... The question ...
4
votes
1answer
1k views

Minimum space needed to sort a stream of integers

This question has gotten a lot of attention on SO: Sorting 1 million 8-digit numbers in 1MB of RAM The problem is to sort a stream of 1 million 8-digit numbers (integers in the range $[0,\: 99\...
14
votes
4answers
570 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 ...
2
votes
2answers
345 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 ...
4
votes
1answer
235 views

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 ...
6
votes
1answer
132 views

Streaming algorithm and random access

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 ...