Computing a histogram with the number of extant values not known in advance

Question

(This may be more fitting for CSTheory, I'm not sure.)

I'm looking for an practical or theoretical work (that is, academic papers, online jots, pseudocode or code) regarding efficient algorithms for the following problem:

Unknown-Number-of-Bins Histogram

Inputs:

• An array of integers $a$, of length $n$.

Outputs:

• An array of integers $\text{bins}$ of length $m <= n$.
• An array of unsigned integers $\text{counts}$, also of length $m$.

Output Requirements:

• For every $i \in \{0...m-1\}$ it must be the case that

  $\bigl|\bigl\{ j \in \{0...n-1\} \mid a_j = \text{bins}_i \bigr\}\bigr|$ $ = \text{counts}_i$

  In other words, $\text{bins}$ and $\text{counts}$ constitute a histogram of $a$, with one bin for every unique value in $a$.

• It is not required for $\text{bins}$ or $\text{counts}$ to be sorted.

Other Notes:

• Complexity is considered as a function of both $n$ and $m$.
• Low time complexity is required both asymptotically and for relatively low values of $m$ - but it is not required for low values of $n$.
• No hiding monstrosities in the $\mathop{O}(\cdot)$ constants please! This should be usable in practice.
• A parallel(izable) approach? You are most welcome :-)
• Low space complexity is a plus.
• Deterministic algorithms preferred, and barring that, go easy on those coin flips.

Clearly, there are many way to go about this, some very straightforward, e.g. "sort the input, then build a sorted histogram in a single pass", in $\mathop{O}(n \log{n})$ time. Of course I'm interested in something better....

Answer 1

Often, in order to improve a sorting-based algorithm from $O(n\log n)$ to $O(n)$, one can use hash tables. In this case, you would use a hash table of size $O(n)$. Each entry of the hash table would store an integer and its count. The entire algorithm would now run in expected time $O(n)$.

Answer 2

The problem seems poorly posed. In particular, the following seems to be a trivial solution: choose the bins in advance so that one bin covers the entire array and the remaining $m-1$ bins will not have any elements in them. For instance, you could scan the array once to find the smallest and largest elements of the input array, $\alpha$ and $\beta$; then make one bin cover $[\alpha,\beta]$, and the remaining $m-1$ bins cover other intervals that don't overlap with the input (e.g., $[\beta+1,\beta+2]$, $[\beta+3,\beta+4]$, ...). Now it is easy to output the counts: the bin $[\alpha,\beta]$ has count $n$, and the remaining bins have count 0.

This trivial solution runs in $O(n)$ time. It is parallelizable, deterministic, and has no nasty constants hidden in the big-O notation. The space complexity is $O(1)$. You can even make it a streaming algorithm. However, it's probably not very useful in practice.

If this is not what you wanted, then it looks like your set of requirements were not stated precisely enough.

Answer 3

Not a great solution, but an improvement - it seems - over @YuvalFilmus' approach:

• Gradually guess the value of m, increasing by a constant factor each time (say by 2);
• For every guess m', use an $O(m')$-bucket hash table (perhaps it would need to be $\Omega(m' \log(m'))$ considering the union-bound on the requirement of the hashing going well).
• Start computing the histogram, while also summing up hash bucket sizes; if you get a hash bucket that's too large (say > $c_1 \log(m)$), or the average bucket size is too large ($> c_2$) then clear the hash table and proceed to the next guess.

This should do the trick with a hash table with O(m log(m)) buckets, and average bucket length below $c_2$ - so the time complexity would be $O\left(n + m \log^2(m)\right)$ and the space complexity $O(m \log(m))$. I'm not absolutely sure about te choice of the extra log factor - perhaps we can make do with less than that.

However, I really don't like this solution as something to use in practice. It feels like the artificial construct of a theoretician...