Skip graphs
Top Cited Papers
- 1 November 2007
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 3 (4) , 37
- https://doi.org/10.1145/1290672.1290674
Abstract
Skip graphs are a novel distributed data structure, based on skip lists, that provide the full functionality of a balanced tree in a distributed system where resources are stored in separate nodes that may fail at any time. They are designed for use in searching peer-to-peer systems, and by providing the ability to perform queries based on key ordering, they improve on existing search tools that provide only hash table functionality. Unlike skip lists or other tree data structures, skip graphs are highly resilient, tolerating a large fraction of failed nodes without losing connectivity. In addition, simple and straightforward algorithms can be used to construct a skip graph, insert new nodes into it, search it, and detect and repair errors within it introduced due to node failures.Keywords
This publication has 20 references indexed in Scilit:
- Skip B-TreesPublished by Springer Nature ,2006
- Chord: a scalable peer-to-peer lookup protocol for internet applicationsIEEE/ACM Transactions on Networking, 2003
- Accessing Nearby Copies of Replicated Objects in a Distributed EnvironmentTheory of Computing Systems, 1999
- A design of a parallel dictionary using skip listsTheoretical Computer Science, 1996
- Analysis of an optimized search algorithm for skip listsTheoretical Computer Science, 1995
- A DISTRIBUTED, REPLICATED, DATA-BALANCED SEARCH STRUCTUREInternational Journal of High Speed Computing, 1994
- A Limit Theory for Random Skip ListsThe Annals of Applied Probability, 1992
- Skip lists: a probabilistic alternative to balanced treesCommunications of the ACM, 1990
- Fault tolerance and storage reduction in binary search treesInformation and Control, 1984
- Trie memoryCommunications of the ACM, 1960