Removing duplicates efficiently and with a low memory overhead

Question

I want to filter efficiently a list of integers for duplicates in a way that only the resulting set needs to be stored.

One way this can be seen:

• we have a range of integers $S = \{1, \dots{}, N\}$ with $N$ big (say $2^{40}$)
• we have a function $f : S \to S$ with, supposedly, many collisions (the images are uniformly distributed in $S$)
• we then need to store $f[S]$, that is $\{f(x) | x \in S\}$

I have a quite accurate (probabilistic) estimation of what $|f[S]|$ is, and can therefore allocate data structures in advance (say $|f[S]| \approx 2^{30}$).

I have had a few ideas, but I am not sure what would be the best approach:

• a bitset is out of the question because the input set does not fit into memory.
• a hash table, but (1) it requires some memory overhead, say 150% of $|f[S]|$ and (2) the table has to be explored when built which requires additional time because of the memory overhead.
• an "on the fly" sort, preferably with $O(N)$ complexity (non-comparison sort). Regarding that, I am not sure what is the major difference between bucket sort and flashsort.
• a simple array with a binary search tree, but this requires $O(N \log |f[S]|)$ time.
• maybe using Bloom filters or a similar data structure could be useful in a relaxation (with false positives) of the problem.

Some questions on stackoverflow seem to tackle with this sort of things (http://stackoverflow.com/questions/12240997/sorting-array-in-on-run-time, http://stackoverflow.com/questions/3951547/java-array-finding-duplicates), but none seems to match my requirements.

Answer 1

Why not bin and chain?

The idea is to store positive integers representable by $n = k+m$ bits in an array $A$ of $2^k$ entries representing ranges of values: entry $A[y]$, $y \ge 0$, represents the range $[2^m y, 2^m(y+1)-1]$. For any $1 \le x \lt 2^n$ we may write $x = 2^m y + z$ where $y$ has $k$ bits and $z$ has $m$ bits. Try to store $z$ (not $x$!) at location $y$:

• When $A[y]=z$ already, do nothing: $x$ is a duplicate.

• When $A[y]$ is uninitialized, store $z$ at $A[y]$.

• Otherwise, store an index into a separate array used to chain the $z$'s (which have collided at $y$) in linked lists. You will have to search linearly through the list headed by $A[y]$ and, depending on what the search uncovers, potentially insert $z$ into the list.

At the end, $f(S)$ is easy to recover by looping through the initialized entries of $A$ and--by merely concatenating two bitstrings--reassembling each $z$ found at location $y$ (either directly or within a chain referenced there) into the original value $x = 2^m y + z$.

When the distribution is close to uniform and $2^k$ exceeds $N$, there will not be much chaining (this can be assessed in the usual ways) and the chains will tend to be short. When the distribution is nonuniform, the algorithm still works, but can reach quadratic timing. If that's a possibility, use something more efficient than chains (and pay a little overhead for storage).

The storage needed is at most $2^n$ bits for $A$ and $2^{2k}$ bits for the chains (assuming $m \le k$). This is exactly the space needed to store $2^k$ values of $n$ bits each. If you're confident in the uniformity, you can underallocate the storage for the chains. If nonuniformity is a possibility, you may want to increase $k$ and fully advocate the chain storage.

An alternative way of thinking about this solution is that it is a hash table with a particularly nice hash function (take the $k$ most significant bits) and, because of that, we only need to store the least significant $m=n-k$ bits in the table.

There are ways to overlay storage for the chains with the storage for $A$ but it doesn't seem worth the bother, because it wouldn't save much (assuming $m$ is much smaller than $k$) space and would make the code harder to develop, debug, and maintain.