# Practical Data-oblivious Compaction?

Compaction is a particularly weak form of sorting. The problem can be phrased as follows:

Given an array $$A$$ of $$N$$ cells, with at most $$R$$ of the cells distinguished (say by a bit), produce an array $$D$$ of at most size $$O(R)$$ containing all of the marked cells

Compaction is said to be:

• Tight: If the output array $$D$$ is of size exactly $$R$$
• Order-preserving: If the relative ordering of marked elements of $$A$$ is the same as the relative ordering of elements of $$D$$ (i.e. if the compaction is "stable" in the sense of sorting)
• Data-oblivious: If the algorithm which computes the compaction has access patterns independent of the data

One can construct tight, order-preserving, data-oblivious compaction from a sorting network. You have to use non-standard comparison function which:

• Sets all marked elements as greater than unmarked elements
• Within comparisons between marked elements (resp. unmarked elements), breaks ties by the element's initial ordering in the array.

But such a function is easy to specify, and can be computed in $$O(\log N)$$ time. This means that one can construct tight, order-preserving, data-oblivious compaction from the AKS sorting network (giving an $$O(N(\log N)^2)$$ algorithm) or from a more practical sorting network like Batcher Odd-Even Mergesort (giving an $$O(N(\log N)^3)$$ algorithm).

Anyone who has worked for sorting networks before has heard that there are the asymptotically optimal algorithms (namely the AKS sorting network and ZigZag Sort, both using $$O(N\log N)$$ comparisons), and the practically efficient algorithms (Batcher's mentioned above is one example, but there are many which are $$O(N(\log N)^2)$$ comparisons).

I'm essentially curious if there is something similar for compaction --- I have seen papers such as this which give oblivious tight compaction in $$O(N)$$ time <1>. This paper's improvement is lowering the implied constant from $$2^{228}$$ to ~$$9000$$. I imagine that for al "reasonably-sized arrays" it is still more efficient to pair Batcher's sorting network with the aforementioned non-standard comparison function.

So has been research done into practically-efficient compaction algorithms? While I eventually want something which is tight, order-preserving, and data-oblivious, the most important keyword by far is "data-oblivious". I'm willing to tolerate a negligible (meaning $$N^{-\omega(1)}$$) probability of failure, as long as it has "good constants". Moreover the data to be compacted is "random" in a strong sense. In particular, each element of the array is marked/not marked according to the result of an i.i.d. $$\mathsf{Bern}(1/2)$$.

<1> The linked algorithm has a negligible probability of failure, which is fine for my purposes.

• @EmilJeřábek The way to get order-preserving from a sorting network is to, instead of comparing elements $x < y$, you compare "tagged elements" $(x, \mathsf{ind}_x) < (y, \mathsf{ind}_y)$ where $\mathsf{ind}_x$ is the index of $x$ in the array. One defines this comparison in the obvious way --- $(x, \mathsf{ind}_x)$ is less than $(y, \mathsf{ind}_y)$ iff $(x < y) \lor (x == y \land \mathsf{ind}_x < \mathsf{ind}_y)$. The result algorithm is still not technically stable, the underlying ordering is now total, so stability does not matter (as correctness of the sorting algorithm suffices) ... – Mark Jul 16 at 21:07
• Comparing $\mathsf{ind}_x$ and $\mathsf{ind}_y$ costs $O(\log N)$ though, which is typically much greater than simply comparing $x$ and $y$ (which in the case of compaction is $O(1)$). – Mark Jul 16 at 21:08
• Sorry, I was tired yesterday, I see that you already wrote this in the question. Thank you. – Emil Jeřábek Jul 17 at 6:10
• What model of computation do you use? If you count basic operations on indices as $O(\log n)$ many sorting algorithms get extra hidden logarithmic factors. – orlp Jul 26 at 0:01
• @orlp I don't really have a fixed computational model in mind. The point of this post is that I require a stable, tight, data-oblivious compaction algorithm for something I intend to implement and profile. I could (and currently plan to) use the aforementioned transformation from a sorting network, but given that people research data-oblivious compaction algorithms in their own right I thought it was possible that some of them are more practically efficient. Unfortunately the papers I've read haven't made this point obvious, so I thought to ask it here. – Mark Jul 26 at 1:08