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

<p>This solution uses the sketch data structure from <a href="https://arxiv.org/abs/1606.00996" rel="nofollow noreferrer">"A Minimal Variance Estimator for the Cardinality of Big Data Set Intersection", by Cohen et al.</a> It stores $k$ hash values.</p>

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

<p>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$.</p>

CC BY-SA 3.0
2017-06-18T18:47:37.850Z
2017-06-18T18:47:37.850Z
jbapple
<p>Let $U=\{1,\ldots, u\}$ be a <em>universe</em> 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 <em>range queries</em>.</p>

<p>In the <a href="https://en.wikipedia.org/wiki/Range_query_(data_structures)" rel="nofollow noreferrer">Range Query</a> 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])$.</p>

<p>Consider the function $f$ that returns the number of distinct elements in the queried range.</p>

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

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

<p>.</p>

<blockquote>
  <p><strong>If we allow approximation of the number of distinct elements, can we get faster queries?</strong></p>
</blockquote>

<hr>

<p>EDIT: I have found a related problem <a href="https://stackoverflow.com/questions/39787455/is-it-possible-to-query-number-of-distinct-integers-in-a-range-in-olg-n">discussed in stackoverflow</a>. The answer there shows a $O(n\log n\log u)$ bits algorithm that answers queries in $O(\log n)$ time. </p>

<p>Is this optimal?</p>

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

<ds.algorithms><ds.data-structures><space-time-tradeoff>
What is known about computing distinct count range queries?
R B
# What is known about computing distinct count range queries?

(Asked by: username_0 on 2017-06-15)

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](https://en.wikipedia.org/wiki/Range_query_(data_structures)) 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](https://stackoverflow.com/questions/39787455/is-it-possible-to-query-number-of-distinct-integers-in-a-range-in-olg-n). 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?

**Tags:** ds.algorithms, ds.data-structures, space-time-tradeoff


---

## 1 answers

### Answer by username_1 on 2017-06-18. Score: 2

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.](https://arxiv.org/abs/1606.00996) 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$.


---

