Concepedia

Skip Lists

Skip Lists is a probabilistic hierarchical linked‑list-based data structure for ordered dictionaries in which elements are stored in multiple levels of forward-pointer lists formed by random promotion, thereby enabling expected \(O(\log n)\) search, insertion, and deletion while maintaining structural simplicity relative to balanced search trees.

92

Publications

8K

Citations

210

Authors

100

Institutions

Publications per year

2017–2026

16

Variants

Skip List

Parents

Children

Publications

92

Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs

Yu. A. Malkov, D. A. Yashunin · IEEE Transactions on Pattern Analysis and Machine Intelligence · 2018 · 1.6K citations

, , +14

Skip lists: a probabilistic alternative to balanced trees

William Pugh · Communications of the ACM · 1990 · 1.2K citations · Full text

, , +7

Recent directions in netlist partitioning: a survey

Charles J. Alpert, Andrew B. Kahng · Integration · 1995 · 646 citations

, , +14

Skip graphs

James Aspnes, Gauri Shah · Symposium on Discrete Algorithms · 2003 · 333 citations

, , +12

Skip graphs

James Aspnes, Gauri Shah · ACM Transactions on Algorithms · 2007 · 326 citations

, , +12

1–5 of 92

Authors

210

  1. NS
    Nir Shavit

    Tel Aviv University, Israel

    5 publications · 279 citations

    5

    h-index

  2. TP
    Thomas Papadakis

    University of Waterloo, Canada

    3 publications · 152 citations

    3

    h-index

  3. MT
    Michael T. Goodrich

    Johns Hopkins University, United States

    3 publications · 295 citations

    3

    h-index

  4. EP
    Erez Petrank

    Technion – Israel Institute of Technology, Israel

    3 publications · 76 citations

    3

    h-index

  5. WP
    William Pugh

    University of Maryland, College Park, United States

    3 publications · 1.3K citations

    3

    h-index

1–5 of 210

Institutions

100

  1. University of Waterloo

    Waterloo, Canada

    5 h-index

    8 publications

    487 citations

  2. Microsoft Research (United Kingdom)

    Cambridge, United Kingdom

    4 h-index

    6 publications

    461 citations

  3. Technion – Israel Institute of Technology

    Haifa, Israel

    4 h-index

    8 publications

    242 citations

  4. Massachusetts Institute of Technology

    Cambridge, United States

    4 h-index

    8 publications

    388 citations

  5. Stanford University

    Stanford, United States

    3 h-index

    9 publications

    1.2K citations

  6. University of Florida

    Gainesville, United States

    3 h-index

    6 publications

    250 citations

  7. Tel Aviv University

    Tel Aviv, Israel

    3 h-index

    4 publications

    187 citations

  8. Universitat Politècnica de Catalunya

    Barcelona, Spain

    3 h-index

    5 publications

    85 citations

1–8 of 100

Venues

  1. Theoretical Computer Science

    4 publications · 98 citations

    4

    h-index

  2. arXiv (Cornell University)

    Repository · 3 publications · 263 citations

    3

    h-index

  3. Proceedings of the VLDB Endowment

    PVLDB · 3 publications · 140 citations

    3

    h-index

  4. ACM SIGPLAN Notices

    3 publications · 95 citations

    3

    h-index

  5. BIT Numerical Mathematics

    2 publications · 45 citations

    2

    h-index

1–5