EUVIMEDEUVIMED entdecken
Crossref

The Ubiquitous Skiplist: A Survey of What Cannot be Skipped About the Skiplist and its Applications in Data Systems

Lu Xing, Venkata Sai Pavan Kumar Vadrevu, Walid G. Aref

ACM Computing Surveys · 30.11.2025 · 57 (11) · 1-37

DOI: 10.1145/3736754 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Computing Surveys, online erschienen am 11.06.2025. Verfasst von Lu Xing und 2 weiteren Autor:innen. Die Arbeit wurde bisher 4-mal zitiert (Crossref) und nennt 145 Literaturangaben. Gefördert von: NSF.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Skiplists have become prevalent in systems. The main advantages of skiplists are their simplicity and ease of implementation, and the ability to support operations in the same asymptotic complexities as their tree-based counterparts. In this survey, we explore skiplists and their many variants. We highlight many scenarios about how skiplists are useful, and how they fit well in these usage scenarios. We also compare skiplists with other data structures, especially tree-based structures. Extensions to skiplists include structural modifications, as well as algorithmic enhancements and operations. We categorize the existing extensions, and summarize the skiplist variants that belong to each category. We present how data systems incorporate skiplist variants into many different application scenarios to serve various purposes. These data systems cover a wide range of applications, from data indexing to block-chain, from network algorithms to deterministic skiplists, and so on. It illustrates an impactful and diverse applications of skiplists in various domains of data systems.

Förderung

  • NSF

Zitieren

APA

Xing, L., Vadrevu, V. S. P. K., & Aref, W. G. (2025). The Ubiquitous Skiplist: A Survey of What Cannot be Skipped About the Skiplist and its Applications in Data Systems. ACM Computing Surveys, 57(11), 1-37. https://doi.org/10.1145/3736754

Vancouver

Xing L, Vadrevu VSPK, Aref WG. The Ubiquitous Skiplist: A Survey of What Cannot be Skipped About the Skiplist and its Applications in Data Systems. ACM Computing Surveys. 2025;57(11):1-37. doi:10.1145/3736754

BibTeX
@article{Xing2025,
  author = {Xing, Lu and Vadrevu, Venkata Sai Pavan Kumar and Aref, Walid G.},
  title = {The Ubiquitous Skiplist: A Survey of What Cannot be Skipped About the Skiplist and its Applications in Data Systems},
  journal = {ACM Computing Surveys},
  year = {2025},
  volume = {57},
  number = {11},
  pages = {1--37},
  doi = {10.1145/3736754}
}
Kostenlos starten →