1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @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) ... $\endgroup$ – Mark Jul 16 at 21:07
  • $\begingroup$ 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)$). $\endgroup$ – Mark Jul 16 at 21:08
  • $\begingroup$ Sorry, I was tired yesterday, I see that you already wrote this in the question. Thank you. $\endgroup$ – Emil Jeřábek Jul 17 at 6:10
  • $\begingroup$ 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. $\endgroup$ – orlp Jul 26 at 0:01
  • $\begingroup$ @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. $\endgroup$ – Mark Jul 26 at 1:08

Your Answer

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

Browse other questions tagged or ask your own question.