Skip lists: a probabilistic alternative to balanced trees

By William W. Pugh. 1989

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

Nearest-Neighbor Searching and Metric Space Dimensions (2005, methodology): “This description shows that the data structure is similar to a skip list[Pug90], which is a way to accelerate searching in a linear list of ordered values; such searching is the one-dimensional version of nearest-neighbor searching.”
Flat combining and the synchronization-parallelism tradeoff (2010, methodology): “A skiplist [19] is a probabilistic data-structure, representing a multiset of nodes, ordered by their keys.”
Practical lock-freedom (2003, methodology): “Pugh describes a highly-concurrent skip list implementation which uses perpointer mutual-exclusion locks [Pugh90a].”
Defect prediction from static code features: current results, limitations, new approaches (2010, methodology): “This is simple to implement via a linked list structure but a faster alternative would be a binary-search over skip lists (Pugh 1990).”
Cache-oblivious B-trees (2000, background): “Search trees that satisfy Properties 1 and 2 include weight-balanced B-trees [11], deterministic skip lists [37], and skip lists [41] in the expected sense.”
Transactional boosting: a methodology for highly-concurrent transactional objects (2008, background): “Skip List Implementation A skip list [ 23 ] is linked list in which each node has a set of short-cut references to later nodes in the list.”
PebblesDB: Building Key-Value Stores using Fragmented Log-Structured Merge Trees (2017, methodology): “To quickly find keys in each level, FLSM organizes the sstables into guards (inspired from the Skip-List data structure [47, 48]).”
Rank-Based Similarity Search: Reducing the Dimensional Dependence (2015, methodology): “In their method, a randomized structure resembling a skip list [42] is used to retrieve pre-computed samples of elements in the vicinity of points of interest.”
The rainbow skip graph: a fault-tolerant constant-degree distributed data structure (2006, background): “Aspnes and Shah [4] present a distributed data structure, called skip graphs, for searching ordered data in a peer-to-peer network, based on the randomized skip-list data structure [16].”
Vanish: Increasing Data Privacy with Self-Destructing Data (2009, methodology): “Churn (node death and birth) is modeled by a Poisson distribution as in [53].”
Fast k-Nearest Neighbour Search via Prioritized DCI (2017, methodology): “They are implemented using standard data structures that maintain one-dimensional ordered sequences of elements, like self-balancing binary search trees (Bayer, 1972; Guibas & Sedgewick, 1978) or skip lists (Pugh, 1990).”
The Bw-Tree: A B-tree for new hardware platforms (2013, methodology): “We also compare the Bw-tree to a latch-free skip list implementation [14].”
Skip graphs (2003, methodology): “So we can directly apply the skip list search analysis given in [Pug90], to analyze the search in S .”
Survey of research towards robust peer-to-peer networks: Search methods (2006, unknown): “Unlike Skip Lists, Skip Graphs provide multiple lists at each level for redundancy, and every node participates in one of the lists at each level.”
The design and implementation of VAMPIRE (2002, unknown): “In order to speed up the computation of the joins, the relations associated with paths are represented by skip-lists [20].”