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$
5
  • $\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 '20 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 '20 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 '20 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 '20 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 '20 at 1:08
0
$\begingroup$

It looks like there are some known lower bounds (see page two of Sorting Short Keys in Circuits of Size $o(n\log n)$). The relevant section is copied below:

More specifically, Lin, Shi, and Xie [LSX19] showed that any stable compaction circuit that treats the payload as indivisible must have at least $\Omega(n \log n)$ selector gates — here the indivisibility assumptions requires that the circuit only move the payload around through selector gates but not perform boolean computation on the encoding of the payload. The indivisibility restriction in Lin et al.’s lower bound [LSX19] can be removed if one assumes the Li-Li network coding conjecture [LL04] — this is implied by Afshani et al. [AFKL19]’s recent work$^2$.

Given that this is the case, it seems like the best thing to do is to use sorting networks. There seem to be a few new ones which may be competitive (see for example this), but I can't say anything definitive.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.