Skip lists: a probabilistic alternative to balanced trees

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Skip lists: a probabilistic alternative to balanced trees

Full text

Pdf (913 KB)

Source

Communications of the ACM archive
Volume 33 , Issue 6 (June 1990) table of contents

Pages: 668 - 676

Year of Publication: 1990

ISSN:0001-0782

Author

William Pugh

Univ. of Maryland, College Park

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 73, Downloads (12 Months): 417, Citation Count: 100

Additional Information:

abstract references cited by index terms review collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/78973.78977 What is a DOI?

ABSTRACT

Skip lists are data structures that use probabilistic balancing rather than strictly enforced balancing. As a result, the algorithms for insertion and deletion in skip lists are much simpler and significantly faster than equivalent algorithms for balanced trees.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Alfred V. Aho , John E. Hopcroft , Jeffrey Ullman , J. D. Ullman , J. E. Hopcroft, Data Structures and Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
	2	John Allen, Anatomy of LISP, McGraw-Hill, Inc., New York, NY, 1978
	3	Aragon, C.. and Seidel, R. Randomized search trees. In Proceedings of the 30th Ann. IEEE Symposium on Foundations of Computer Science (October 1989), pp. 540-545.
	4	Bentley, J., Leighton, F.T., Lepley, M.F., Stanat, D., and Steele, J.M. A randomized data structure for ordered sets. Tech. Memo MIT/LCS Technical Report Number 297. {May 1986}.
	5	Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
	6	T. Papadakis , J. I. Munro , P. V. Poblete, Analysis of the expected search cost in skip lists, Proceedings of the second Scandinavian workshop on Algorithm theory, p.160-172, July 1990, Bergen, Sweden
	7	William Pugh, Concurrent maintenance of skip lists, University of Maryland at College Park, College Park, MD, 1990
	8	William Pugh, A skip list cookbook, University of Maryland at College Park, College Park, MD, 1990
	9	W. Pugh, Slow optimally balanced search strategies vs. cached fast uniformly balanced search strategies, Information Processing Letters, v.34 n.5, p.251-254, May 1990 [doi>10.1016/0020-0190(90)90130-P]
	10	W. Pugh , T. Teitelbaum, Incremental computation via function caching, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.315-328, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75305]
	11	Daniel Dominic Sleator , Robert Endre Tarjan, Self-adjusting binary search trees, Journal of the ACM (JACM), v.32 n.3, p.652-686, July 1985 [doi>10.1145/3828.3835]
	12	Sprugnoli, R. Randomly Balanced Binary Trees, Calcolo, 17 (1981), 99-118.
	13	Niklaus Wirth, Algorithms + Data Structures = Programs, Prentice Hall PTR, Upper Saddle River, NJ, 1978

CITED BY 100

	Amir Roth , Gurindar S. Sohi, Effective jump-pointer prefetching for linked data structures, ACM SIGARCH Computer Architecture News, v.27 n.2, p.111-121, May 1999
	Jihad El-Sana , Elvir Azanli , Amitabh Varshney, Skip strips: maintaining triangle strips for view-dependent rendering, Proceedings of the conference on Visualization '99: celebrating ten years, p.131-138, October 1999, San Francisco, California, United States
	Leonidas Guibas , John Hershberger , Subhash Suri , Li Zhang, Kinetic connectivity for unit disks, Proceedings of the sixteenth annual symposium on Computational geometry, p.331-340, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong
	Pascal Fradet , Daniel Le Métayer, Shape types, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.27-39, January 15-17, 1997, Paris, France
	Sanjeev Khanna , Shiyu Zhou, On indexed data broadcast, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.463-472, May 24-26, 1998, Dallas, Texas, United States
	William Pugh, Compressing Java class files, ACM SIGPLAN Notices, v.34 n.5, p.247-258, May 1999
	F. Cazals, Effective nearest neighbors searching on the hyper-cube, with applications to molecular clustering, Proceedings of the fourteenth annual symposium on Computational geometry, p.222-230, June 07-10, 1998, Minneapolis, Minnesota, United States
	Joseph Hummel , Laurie J. Hendren , Alexandru Nicolau, Abstract description of pointer data structures: an approach for improving the analysis and optimization of imperative programs, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.3, p.243-260, Sept. 1992
	Narendra V. Shenoy , William Nicholls, An efficient routing database, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA
	Hae Don Chon , Divyakant Agrawal , Amr El Abbadi, Using space-time grid for efficient management of moving objects, Proceedings of the 2nd ACM international workshop on Data engineering for wireless and mobile access, p.59-65, May 2001, Santa Barbara, California, United States
	David S. Wise , Joshua Walgenbach, Static and dynamic partitioning of pointers as links and threads, ACM SIGPLAN Notices, v.31 n.6, p.42-49, June 15, 1996
	J. Ian Munro , Thomas Papadakis , Robert Sedgewick, Deterministic skip lists, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.367-375, September 1992, Orlando, Florida, United States
	Alois Ferscha , James Johnson, A testbed for parallel simulation performance prediction, Proceedings of the 28th conference on Winter simulation, p.637-644, December 08-11, 1996, Coronado, California, United States
	Michael T. Goodrich , Roberto Tamassia, Using randomization in the teaching of data structures and algorithms, ACM SIGCSE Bulletin, v.31 n.1, p.53-57, March 1999
	Guy E. Blelloch , Margaret Reid-Miller, Fast set operations using treaps, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.16-26, June 28-July 02, 1998, Puerto Vallarta, Mexico
	David Eppstein, Average case analysis of dynamic geometric optimization, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.77-86, January 23-25, 1994, Arlington, Virginia, United States
	Willibald Doeringer , Günter Karjoth , Mehdi Nassehi, Routing on longest-matching prefixes, IEEE/ACM Transactions on Networking (TON), v.4 n.1, p.86-97, Feb. 1996
	Hai Zhou , Narendra Shenoy , William Nicholls, Efficient minimum spanning tree construction without Delaunay triangulation, Proceedings of the 2001 conference on Asia South Pacific design automation, p.192-197, January 2001, Yokohama, Japan
	Rajiv Gupta , Scott A. Smolka , Shaji Bhaskar, On randomization in sequential and distributed algorithms, ACM Computing Surveys (CSUR), v.26 n.1, p.7-86, March 1994
	Funda Ergun , S. Cenk Sahinalp , Jonathan Sharp , Rakesh Sinha, Biased dictionaries with fast insert/deletes, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.483-491, July 2001, Hersonissos, Greece
	Robert Rönngren , Rassul Ayani, A comparative study of parallel and sequential priority queue algorithms, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.7 n.2, p.157-209, April 1997
	Nir Shavit , Asaph Zemach, Scalable concurrent priority queue algorithms, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.113-122, May 04-06, 1999, Atlanta, Georgia, United States
	R. W. Quong, Expected I-cache miss rates via the gap model, ACM SIGARCH Computer Architecture News, v.22 n.2, p.372-383, April 1994
	Timothy M. Chan, Fixed-dimensional linear programming queries made easy, Proceedings of the twelfth annual symposium on Computational geometry, p.284-290, May 24-26, 1996, Philadelphia, Pennsylvania, United States
	Ketan Mulmuley , Sandeep Sen, Dynamic point location in arrangements of hyperplanes, Proceedings of the seventh annual symposium on Computational geometry, p.132-141, June 10-12, 1991, North Conway, New Hampshire, United States
	Kenneth L. Clarkson, An algorithm for approximate closest-point queries, Proceedings of the tenth annual symposium on Computational geometry, p.160-164, June 06-08, 1994, Stony Brook, New York, United States
	Piotr Berman , Zheng Zhang , Yuri I. Wolf , Eugene V. Koonin , Webb Miller, Winnowing sequences from a database search, Proceedings of the third annual international conference on Computational molecular biology, p.50-58, April 11-14, 1999, Lyon, France
	John D. Valois, Lock-free linked lists using compare-and-swap, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.214-222, August 20-23, 1995, Ottowa, Ontario, Canada
	Sunil Arya , David M. Mount, Approximate nearest neighbor queries in fixed dimensions, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.271-280, January 25-27, 1993, Austin, Texas, United States
	Ketan Mulmuley, Randomized multidimensional search trees (extended abstract): dynamic sampling, Proceedings of the seventh annual symposium on Computational geometry, p.121-131, June 10-12, 1991, North Conway, New Hampshire, United States
	Lars Arge , Octavian Procopiuc , Sridhar Ramaswamy , Torsten Suel , Jeffrey Scott Vitter, Theory and practice of I/O-efficient algorithms for multidimensional batched searching problems, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.685-694, January 25-27, 1998, San Francisco, California, United States
	Mike J. Spreitzer , Marvin M. Theimer , Karin Petersen , Alan J. Demers , Douglas B. Terry, Dealing with server corruption in weakly consistent replicated data systems, Wireless Networks, v.5 n.5, p.357-371, Oct. 1999
	Susanne Albers , Marek Karpinski, Randomized splay trees: theoretical and experimental results, Information Processing Letters, v.81 n.4, p.213-221, 28 February 2002
	Hae Don Chon , Divyakant Agrawal , Amr El Abbadi, Range and kNN query processing for moving objects in grid model, Mobile Networks and Applications, v.8 n.4, p.401-412, August 2003
	Daniel J. Polivy , Roberto Tamassia, Authenticating distributed data using Web services and XML signatures, Proceedings of the 2002 ACM workshop on XML security, November 22-22, 2002, Fairfax, VA
	Giri Narasimhan , Martin Zachariasen, Geometric Minimum Spanning Trees via Well-Separated Pair Decompositions, Journal of Experimental Algorithmics (JEA), 6, p.6-es, 2001
	Stephen Tyson , Brennan Williams, Visualization of oil reservoirs over a large range of scales as a catalyst for multi-disciplinary integration, Proceedings of the 4th conference on Visualization '93, October 25-29, 1993, San Jose, California
	Hubert Ka Yau Leung , Hans-Arno Jacobsen, Efficient matching for state-persistent publish/subscribe systems, Proceedings of the 2003 conference of the Centre for Advanced Studies on Collaborative research, p.182-196, October 06-09, 2003, Toronto, Ontario, Canada
	Dahlia Malkhi , Moni Naor , David Ratajczak, Viceroy: a scalable and dynamic emulation of the butterfly, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California
	Vladmir Estivill-Castro , Derick Wood, A survey of adaptive sorting algorithms, ACM Computing Surveys (CSUR), v.24 n.4, p.441-476, Dec. 1992
	Moez Chaabouni , Soon M. Chung, The point-range tree: a data structure for indexing intervals, Proceedings of the 1993 ACM conference on Computer science, p.453-460, February 16-18, 1993, Indianapolis, Indiana, United States
	Mikhail Fomitchev , Eric Ruppert, Lock-free linked lists and skip lists, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
	Jun-ichi Aoe, A compendium of key search references, ACM SIGIR Forum, v.24 n.3, p.26-42, Fall 1990
	Gurmeet Singh Manku , Moni Naor , Udi Wieder, Know thy neighbor's neighbor: the power of lookahead in randomized P2P networks, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Eric N. Hanson, The Design and Implementation of the Ariel Active Database Rule System, IEEE Transactions on Knowledge and Data Engineering, v.8 n.1, p.157-172, February 1996
	Oded Sudarsky , Craig Gotsman, Dynamic Scene Occlusion Culling, IEEE Transactions on Visualization and Computer Graphics, v.5 n.1, p.13-29, January 1999
	Håkan Sundell , Philippas Tsigas, Fast and lock-free concurrent priority queues for multi-thread systems, Journal of Parallel and Distributed Computing, v.65 n.5, p.609-627, May 2005
	Seonghun Cho , Sarataj Sahni, Weight-biased leftist trees and modified skip lists, Journal of Experimental Algorithmics (JEA), 3, p.2-es, 1998
	Aneesh Aggarwal, Software caching vs. prefetching, ACM SIGPLAN Notices, v.38 n.2 supplement, February 2003
	John Hershberger , Subhash Suri, Adaptive sampling for geometric problems over data streams, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France
	Håkan Sundell , Philippas Tsigas, Scalable and lock-free concurrent dictionaries, Proceedings of the 2004 ACM symposium on Applied computing, March 14-17, 2004, Nicosia, Cyprus
	David Eppstein , Michael T. Goodrich , Jonathan Z. Sun, The skip quadtree: a simple dynamic data structure for multidimensional data, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy
	Lars Arge , David Eppstein , Michael T. Goodrich, Skip-webs: efficient distributed data structures for multi-dimensional data sets, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA
	Jan Reutimann , Michele Giugliano , Stefano Fusi, Event-driven simulation of spiking neurons with stochastic dynamics, Neural Computation, v.15 n.4, p.811-830, April 2003
	Michael T. Goodrich , Michael J. Nelson , Jonathan Z. Sun, The rainbow skip graph: a fault-tolerant constant-degree distributed data structure, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.384-393, January 22-26, 2006, Miami, Florida
	Kaouthar Blibech , Alban Gabillon, CHRONOS: an authenticated dictionary based on skip lists for timestamping systems, Proceedings of the 2005 workshop on Secure web services, November 11-11, 2005, Fairfax, VA, USA
	Alexandre Riazanov , Andrei Voronkov, Efficient instance retrieval with standard and relational path indexing, Information and Computation, v.199 n.1-2, p.228-252, 25 May 2005
	Peter Desnoyers , Deepak Ganesan , Prashant Shenoy, TSAR: a two tier sensor storage architecture using interval skip graphs, Proceedings of the 3rd international conference on Embedded networked sensor systems, November 02-04, 2005, San Diego, California, USA
	Peter J. Grabner , Arnold Knopfmacher , Helmut Prodinger, Combinatorics of geometrically distributed random variables: run statistics, Theoretical Computer Science, v.297 n.1-3, p.261-270, 17 March 2003
	James Aspnes , Gauri Shah, Skip graphs, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	David Ginat, On varying perspectives of problem decomposition, ACM SIGCSE Bulletin, v.34 n.1, March 2002
	B. Barla Cambazoglu , Cevdet Aykanat, Performance of query processing implementations in ranking-based text retrieval systems using inverted indices, Information Processing and Management: an International Journal, v.42 n.4, p.875-898, July 2006
	Patricio V. Poblete , J. Ian Munro , Thomas Papadakis, The binomial transform and the analysis of skip lists, Theoretical Computer Science, v.352 n.1, p.136-158, 7 March 2006
	M. F. Khan , Ray Paul , Ishfaq Ahmed , Arif Ghafoor, Intensive Data Management in Parallel Systems: A Survey, Distributed and Parallel Databases, v.7 n.4, p.383-414, Oct. 1999
	Nima Sarshar , Behnam A. Rezaei , Vwani P. Roychowdhury, Low latency wireless ad hoc networking: power and bandwidth challenges and a solution, IEEE/ACM Transactions on Networking (TON), v.16 n.2, p.335-346, April 2008
	Conrado Martínez , Salvador Roura, Randomized binary search trees, Journal of the ACM (JACM), v.45 n.2, p.288-323, March 1998
	Maurice Herlihy , Victor Luchangco , Mark Moir, A flexible framework for implementing software transactional memory, ACM SIGPLAN Notices, v.41 n.10, October 2006
	Amr Elmasry, Deterministic jumplists, Nordic Journal of Computing, v.12 n.1, p.27-39, March 2005
	Rickard E. Faith , Lars S. Nyland , Jan F. Prins, KHEPERA: a system for rapid implementation of domain specific languages, Proceedings of the Conference on Domain-Specific Languages on Conference on Domain-Specific Languages (DSL), 1997, p.19-19, October 15-17, 1997, Santa Barbara, California
	Margaret Archibald , Arnold Knopfmacher , Helmut Prodinger, The number of distinct values in a geometrically distributed sample, European Journal of Combinatorics, v.27 n.7, p.1059-1081, October 2006
	John Risson , Tim Moors, Survey of research towards robust peer-to-peer networks: search methods, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.50 n.17, p.3485-3521, 5 December 2006
	Eduardo Ros , Richard Carrillo , Eva M. Ortigosa , Boris Barbour , Rodrigo Agís, Event-driven simulation scheme for spiking neural networks using lookup tables to characterize neuronal dynamics, Neural Computation, v.18 n.12, p.2959-2993, December 2006
	Mary Ellen Zurko , John Wray , Ian Morrison , Mike Shanzer , Mike Crane , Pat Booth , Ellen McDermott , Warren Macek , Ann Graham , Jim Wade , Tom Sandlin, Jonah: experience implementing PKIX reference freeware, Proceedings of the 8th conference on USENIX Security Symposium, p.15-15, August 23-26, 1999, Washington, D.C.
	Petros Maniatis , Mary Baker, Secure History Preservation Through Timeline Entanglement, Proceedings of the 11th USENIX Security Symposium, p.297-312, August 05-09, 2002
	Edwin H. Jacox , Hanan Samet, Spatial join techniques, ACM Transactions on Database Systems (TODS), v.32 n.1, p.7-es, March 2007
	Thorsten Schütt , Florian Schintke , Alexander Reinefeld, Range queries on structured overlay networks, Computer Communications, v.31 n.2, p.280-291, February, 2008
	Brian C. Dean , Zachary H. Jones, Exploring the duality between skip lists and binary search trees, Proceedings of the 45th annual southeast regional conference, March 23-24, 2007, Winston-Salem, North Carolina
	Prosenjit Bose , Karim Douïeb , Stefan Langerman, Dynamic optimality for skip lists and B-trees, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.1106-1114, January 20-22, 2008, San Francisco, California
	Alexandre Riazanov , Andrei Voronkov, The design and implementation of VAMPIRE, AI Communications, v.15 n.2,3, p.91-110, August 2002
	Lars Arge , Octavian Procopiuc , Sridhar Ramaswamy , Torsten Suel , Jeffrey Scott Vitter, Scalable Sweeping-Based Spatial Join, Proceedings of the 24rd International Conference on Very Large Data Bases, p.570-581, August 24-27, 1998
	Matthias Hopf , Thomas Ertl, Hierarchical Splatting of Scattered Data, Proceedings of the 14th IEEE Visualization 2003 (VIS'03), p.57, October 22-24, 2003
	Jean Cardinal , Sébastien Collette , Stefan Langerman, Local properties of geometric graphs, Computational Geometry: Theory and Applications, v.39 n.1, p.55-64, January, 2008
	Michaela Heyer, Randomness Preserving Deletions on Special Binary Search Trees, Electronic Notes in Theoretical Computer Science (ENTCS), 225, p.99-113, January, 2009
	James Aspnes , Gauri Shah, Skip graphs, ACM Transactions on Algorithms (TALG), v.3 n.4, p.37-es, November 2007
	John Hershberger , Subhash Suri, Adaptive sampling for geometric problems over data streams, Computational Geometry: Theory and Applications, v.39 n.3, p.191-208, April, 2008
	Mirko Zadravec , Andrej Brodnik , Markus Mannila , Merja Wanne , Borut alik, A practical approach to the 2D incremental nearest-point problem suitable for different point distributions, Pattern Recognition, v.41 n.2, p.646-653, February, 2008
	A. González-Beltrán , P. Milligan , P. Sage, Range queries over skip tree graphs, Computer Communications, v.31 n.2, p.358-374, February, 2008
	Flavio Chierichetti , Silvio Lattanzi , Federico Mari , Alessandro Panconesi, On placing skips optimally in expectation, Proceedings of the international conference on Web search and web data mining, February 11-12, 2008, Palo Alto, California, USA
	Ross Shaull , Liuba Shrira , Hao Xu, Skippy: a new snapshot indexing method for time travel in the storage manager, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada
	Alexander Heitzmann , Bernardo Palazzi , Charalampos Papamanthou , Roberto Tamassia, Efficient integrity checking of untrusted network storage, Proceedings of the 4th ACM international workshop on Storage security and survivability, October 31-31, 2008, Alexandria, Virginia, USA
	Ralph Lange , Frank Dürr , Kurt Rothermel, Scalable processing of trajectory-based queries in space-partitioned moving objects databases, Proceedings of the 16th ACM SIGSPATIAL international conference on Advances in geographic information systems, November 05-07, 2008, Irvine, California
	Tingjian Ge , Stan Zdonik, A skip-list approach for efficiently processing forecasting queries, Proceedings of the VLDB Endowment, v.1 n.1, August 2008
	Ragib Hasan , Radu Sion , Marianne Winslett, The case of the fake picasso: preventing history forgery with secure provenance, Proccedings of the 7th conference on File and stroage technologies, p.1-14, February 24-27, 2009, San Francisco, California
	Suman Nath , Phillip B. Gibbons, Online maintenance of very large random samples on flash storage, Proceedings of the VLDB Endowment, v.1 n.1, August 2008
	Li-Pin Chang , Chen-Hui Hsu, Soft lists: a native index structure for NOR-flash-based embedded devices, Proceedings of the 2009 Conference on Asia and South Pacific Design Automation, January 19-22, 2009, Yokohama, Japan
	Nikolas Askitis , Justin Zobel, B-tries for disk-based string management, The VLDB Journal — The International Journal on Very Large Data Bases, v.18 n.1, p.157-179, January 2009
	Shirish Tatikonda , Flavio Junqueira , B. Barla Cambazoglu , Vassilis Plachouras, On efficient posting list intersection with multicore processors, Proceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval, July 19-23, 2009, Boston, MA, USA
	Sorabh Gandhi , Suman Nath , Subhash Suri , Jie Liu, GAMPS: compressing multi sensor data by grouping and amplitude scaling, Proceedings of the 35th SIGMOD international conference on Management of data, June 29-July 02, 2009, Providence, Rhode Island, USA
	Suman Nath, Energy efficient sensor data logging with amnesic flash storage, Proceedings of the 2009 International Conference on Information Processing in Sensor Networks, p.157-168, April 13-16, 2009
	Per Bjesse, Word level bitwidth reduction for unbounded hardware model checking, Formal Methods in System Design, v.35 n.1, p.56-72, August 2009

INDEX TERMS

Primary Classification:
E. Data
E.1 DATA STRUCTURES
Subjects: Lists, stacks, and queues

Additional Classification:
E. Data
E.1 DATA STRUCTURES
Subjects: Trees

F. Theory of Computation
F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
F.2.2 Nonnumerical Algorithms and Problems
Subjects: Sorting and searching

General Terms:
Algorithms, Theory

Keywords:
data structures, searching, trees

REVIEW

"Susan M. Merritt : Reviewer"

A skip list is a new data structure proposed as an alternative to balanced trees. Pugh gives algorithms for search, insert, and delete for the skip list. He analyzes the expected search cost and gives some experimental results comp more...

Collaborative Colleagues:

William Pugh: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player