4
$\begingroup$

Let $U=\{1,\ldots, u\}$ be a universe of elements for some $u\in \mathbb N$. Given some $n\in\mathbb N$, we are interested in computing some function $f:U^{\le n}\to\mathbb R$ over range queries.

In the Range Query problem we get an integer array $A[1,\ldots,n]\in U^n$ and wish to compute queries that takes as input parameters $1\le i\le j\le n$ and return $f(A[i,\ldots,j])$.

Consider the function $f$ that returns the number of distinct elements in the queried range.

The goal is to preprocess the input array $A$ and create a small summary that allows efficient computation of these distinct queries.

What is the best known algorithm for the problem? (given a memory bound $m$, what is the minimal query time that is required).

.

If we allow approximation of the number of distinct elements, can we get faster queries?


EDIT: I have found a related problem discussed in stackoverflow. The answer there shows a $O(n\log n\log u)$ bits algorithm that answers queries in $O(\log n)$ time.

Is this optimal?

Can we get better time/space bounds if we allow approximation?

$\endgroup$
2
$\begingroup$

A sketch data structure is an approximation of a set of elements. Sketches vary in what they store -- some store just hashes, some store elements from the set (a sample), and some store floating-point numbers.

This solution uses the sketch data structure from "A Minimal Variance Estimator for the Cardinality of Big Data Set Intersection", by Cohen et al. It stores $k$ hash values.

Let $I = 2nk/m$. Let $F[t] = \{A[1], A[2], \dots , A[tI]\}$ and $B[t] = \{A[n], A[n-1], \dots, A[n-tI]\}$. Store the sketches for $F[1], F[2], \dots, F[m/2k]$ and $B[1], B[2], \dots, B[m/2k]$. That is a total of $m/k$ sketches, each of size $k$, using a total of $m$ words of space.

Let $r(x)$ denote the value of $x$ rounded to the nearest integer. To estimate the carnality of $\{A[i], \dots, A[j]\}$, estimate the cardinality of $F[r(j/I)] \bigcap B[r((n-i)/I)]$. The Cohen et al. paper describes how to do this in $\text{poly}(k)$ time. The variance of the estimate is a long formula in Corollary 2, combined with the error induced by only using $m/k$ samples, which is at most $4nk/m$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.