Sorting networks and their applications

By K. Batcher. 1968

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Optimization & Training

Citations in the corpus

Billion-Scale Similarity Search with GPUs (2017, methodology): “We use a variant of Batcher’s bitonic sorting network [8], which is a set of parallel merges on an array of size 2 k .”
Prochlo: Strong Privacy for Analytics in the Crowd (2017, neutral): “Batcher’s sort is one such algorithm [8].”
Optimal Decision Lists using SAT (2020, background): “Also note that any of the known cardinality encodings that can be used to represent the sum in (1) (Biere et al. 2009, Chapter 2) (also see (As ´ ın et al. 2009; Bailleux and Boufkhad 2003; Batcher 1968; Sinz 2005)).”
Computing Optimal Decision Sets with SAT (2020, background): “oolean formula, which can be clausiﬁed with the use of auxiliary variables [54]. Also note that any of the known cardinality encodings can be used to represent constraint (1) [9, Chapter 2] (also see [1, 5,7,53]). Finally, the size (in terms of the number of literals) of the proposed SAT encoding is”
Efficient implementation of sorting on multi-core SIMD CPU architecture (2008, methodology): “There are two commonly described merging networks [1] that can be implemented with the current set of SIMD instructions: • odd-even network • bitonic merge network Figure 1 depicts the odd-even merge network, while Figure 2 shows the bitonic merge network (both for merging sequences of length 4).”
Improved techniques for preparing eigenstates of fermionic Hamiltonians (2017, background): “Slightly better performance can be obtained using an odd-even mergesort.(40) The asymptotically best sorting networks have depth O(log η) and complexity O(η log η), though there is a large constant which means they are less efficient for realistic η.”
Oblivious Multi-Party Machine Learning on Trusted Processors (2016, background): “As a result, a Batcher’s sorting network [7] with running time of O(n(logn)2) is preferred in practice.”
PROCHLO: Strong Privacy for Analytics in the Crowd (2017, unknown): “Batcher’s sort is one such algorithm [8].”
Deploying Secure Multi-Party Computation for Financial Data Analysis - (Short Paper) (2012, methodology): “Each Sharemind miner has a copy of a SecreC script that loads shares from the miner’s database and uses a secure MPC implementation of an oblivious Batcher’s odd-even merge sorting network [3] to sort the underlying private data vector.”
GPU Computing (2008, background): “Sort: GPUs have come to excel at sorting as the GPU computing community has rediscovered, adapted, and improved seminal sorting algorithms, notably bitonic merge sort [11].”
Observing and Preventing Leakage in MapReduce (2015, background): “Sorting networks [4] provide the security guarantees above: their network traffic is independent of the data.”
Oblivious RAM Revisited (2010, methodology): “Specifically, this primitive was implemented in [9] using a sorting network: either the sorting network of Batcher [5] which performs O(n log 2 n) read operations with a very small constant (approximately 1/2), or the sorting network of AKS [2] which performs only O(n log n) read operations, but who”
Designing efficient sorting algorithms for manycore GPUs (2009, methodology): “Sorting networks, such as Batcher’s bitonic sorting network [28], are among the oldest parallel sorting techniques.”
Fast and approximate stream mining of quantiles and frequencies using graphics processors (2005, methodology): “Using these two functionalities, we can design optimal sorting networks such as bitonic sort [8] and periodic balanced sort [16] efficiently using any traditional GPU.”
Distance makes the types grow stronger: a calculus for differential privacy (2010, background): “We are therefore essentially concerned with sorting networks, [5] with cswp being the comparator.”
Translating Pseudo-Boolean Constraints into SAT (2006, unknown): “MINISAT+ uses odd-even merge sorters [9].”
An Algorithmic Framework For Differentially Private Data Analysis on Trusted Processors (2018, methodology): “Indeed, a simple solution is to do an oblivious sorting [1, 6] of the database elements, and then count the number of distinct elements by making another pass over the database.”