The art of computer programming: sorting and searching (volume 3)

By Donald Ervin Knuth. 1973

How researchers see this paper

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

In Algorithms & Complexity

Citations in the corpus

Product Quantization for Nearest Neighbor Search (2011, methodology): “Then we provide a statistical bound on the distance estimation error, and propose a reﬁned estimator for the squared Euclidean distance.”
A Global Analysis of Sentinel-2A, Sentinel-2B and Landsat-8 Data Revisit Intervals and Implications for Terrestrial Monitoring (2017, methodology): “Given the large amount of data, a computationally efficient sort algorithm was used [26].”
Skip graphs (2003, background): “An alternative view of a skip graph is a trie [de la Briandais 1959; Fredkin 1960; Knuth 1973] of skip lists that share their lower levels.”
Estimating Renyi Entropy of Discrete Distributions (2014, background): “In particular, the Rényi entropy of order 2, H2(p), measures the quality of random number generators [19], [30], determines the number of unbiased bits that can be extracted from a physical source of randomness [6], [14], helps test graph expansion [8] and closeness of distributions [5], [34], and c”
Graph-based Isometry Invariant Representation Learning (2017, methodology): “Using the selection algorithm (Knuth, 1998) we can reach the average computational complexity of O ( N ) .”
ChunkStash: Speeding Up Inline Storage Deduplication Using Flash Memory (2010, methodology): “Reducing RAM usage per slot by storing compact key signatures: Traditional hash table designs store the respective key in each entry of the hash table index [25].”
Big Batch SGD: Automated Inference using Adaptive Batch Sizes (2016, methodology): “For efficiency, instead of resampling the batch each time the condition fails, one could also simply add data to the current batch, and update the variance using an online scheme like Welford’s method [16].”
An efficient memory-based morphosyntactic tagger and parser for Dutch (2007, unknown): “It compresses a database of labeled examples into a lossless-compression decision-tree structure that preserves the labeling information of all examples, and technically should be named a trie according to Knuth (1973).”
The algorithmic imaginary: exploring the ordinary affects of Facebook algorithms (2017, unknown): “The algorithmic imaginary is not to be understood as a false belief or fetish of sorts but, rather, as the way in which people imagine, perceive and experience algorithms and what these imaginations make possible.”