<p>To achieve order-preserving, you may use the <span class="math-container">$O(n \log n)$</span> by <a href="https://arxiv.org/abs/1103.5102" rel="nofollow noreferrer">Goodrich, Figure 1, Data-Oblivious External-Memory Algorithms for the Compaction, Selection, and Sorting of Outsourced Data</a>. The algorithm is simple and the constant is &lt; 10.</p>

CC BY-SA 4.0
2023-12-20T18:11:04.857Z
2023-12-20T18:11:04.857Z
xacid
<p>It looks like there are some known lower bounds (see page two of <a href="https://arxiv.org/pdf/2010.09884.pdf" rel="nofollow noreferrer"><em>Sorting Short Keys in Circuits of Size <span class="math-container">$o(n\log n)$</span></em></a>). The relevant section is copied below:</p>
<blockquote>
<p>More specifically, Lin, Shi, and Xie [LSX19] showed that any stable compaction circuit that treats the payload as <em>indivisible</em> must have at least <span class="math-container">$\Omega(n \log n)$</span> 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<span class="math-container">$^2$</span>.</p>
</blockquote>
<p>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 <a href="https://arxiv.org/pdf/2008.01765.pdf" rel="nofollow noreferrer">this</a>), but I can't say anything definitive.</p>

CC BY-SA 4.0
2021-03-27T01:17:53.197Z
2021-03-27T01:17:53.197Z
Mark Schultz-Wu
<p><em>Compaction</em> is a particularly weak form of sorting. The problem can be phrased as follows:</p>
<blockquote>
<p>Given an array <span class="math-container">$A$</span> of <span class="math-container">$N$</span> cells, with at most <span class="math-container">$R$</span> of the cells distinguished (say by a bit), produce an array <span class="math-container">$D$</span> of at most size <span class="math-container">$O(R)$</span> containing all of the marked cells</p>
</blockquote>
<p>Compaction is said to be:</p>
<ul>
<li><strong>Tight</strong>: If the output array <span class="math-container">$D$</span> is of size exactly <span class="math-container">$R$</span></li>
<li><strong>Order-preserving</strong>: If the relative ordering of marked elements of <span class="math-container">$A$</span> is the same as the relative ordering of elements of <span class="math-container">$D$</span> (i.e. if the compaction is &quot;stable&quot; in the sense of sorting)</li>
<li><strong>Data-oblivious</strong>: If the algorithm which computes the compaction has access patterns independent of the data</li>
</ul>
<p>One can construct tight, order-preserving, data-oblivious compaction from a sorting network. You have to use non-standard comparison function which:</p>
<ul>
<li>Sets all marked elements as greater than unmarked elements</li>
<li>Within comparisons between marked elements (resp. unmarked elements), breaks ties by the element's initial ordering in the array.</li>
</ul>
<p>But such a function is easy to specify, and can be computed in <span class="math-container">$O(\log N)$</span> time.
This means that one can construct tight, order-preserving, data-oblivious compaction from the AKS sorting network (giving an <span class="math-container">$O(N(\log N)^2)$</span> algorithm) or from a more practical sorting network like Batcher Odd-Even Mergesort (giving an <span class="math-container">$O(N(\log N)^3)$</span> algorithm).</p>
<p>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 <span class="math-container">$O(N\log N)$</span> comparisons), and the practically efficient algorithms (Batcher's mentioned above is one example, but there are many which are <span class="math-container">$O(N(\log N)^2)$</span> comparisons).</p>
<p>I'm essentially curious if there is something similar for compaction --- I have seen papers such as <a href="https://eprint.iacr.org/2020/377.pdf" rel="nofollow noreferrer">this</a> which give oblivious tight compaction in <span class="math-container">$O(N)$</span> time &lt;1&gt;.
This paper's improvement is lowering the implied constant from <span class="math-container">$2^{228}$</span> to ~<span class="math-container">$9000$</span>. I imagine that for al &quot;reasonably-sized arrays&quot; it is still more efficient to pair Batcher's sorting network with the aforementioned non-standard comparison function.</p>
<p>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 &quot;data-oblivious&quot;. I'm willing to tolerate a negligible (meaning <span class="math-container">$N^{-\omega(1)}$</span>) probability of failure, as long as it has &quot;good constants&quot;.
Moreover the data to be compacted is &quot;random&quot; in a strong sense. In particular, each element of the array is marked/not marked according to the result of an i.i.d. <span class="math-container">$\mathsf{Bern}(1/2)$</span>.</p>
<p>&lt;1&gt; The linked algorithm has a negligible probability of failure, which is fine for my purposes.</p>

CC BY-SA 4.0
2020-07-26T00:01:50.730Z
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
CC BY-SA 4.0
2020-07-26T01:08:10.550Z
@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 Schultz-Wu
<sorting-network><cache-oblivious>
Practical Data-oblivious Compaction?
Mark Schultz-Wu
# Practical Data-oblivious Compaction?

(Asked by: username_0 on 2020-07-16)

*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](https://eprint.iacr.org/2020/377.pdf) 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.

**Tags:** sorting-network, cache-oblivious
> **Comments:**
> **username_1**: 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.  
> **username_0**: @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.  

---

## 2 answers

### Answer by username_2 on 2023-12-20. Score: 3

To achieve order-preserving, you may use the $O(n \log n)$ by [Goodrich, Figure 1, Data-Oblivious External-Memory Algorithms for the Compaction, Selection, and Sorting of Outsourced Data](https://arxiv.org/abs/1103.5102). The algorithm is simple and the constant is < 10.


---

### Answer by username_0 on 2021-03-27. Score: 2

It looks like there are some known lower bounds (see page two of [*Sorting Short Keys in Circuits of Size $o(n\log n)$*](https://arxiv.org/pdf/2010.09884.pdf)). 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](https://arxiv.org/pdf/2008.01765.pdf)), but I can't say anything definitive.


---

