Write-Optimized Skip Lists

Summary: External-memory write-optimized skip list with range queries O(log_{B^ε}N + K/B) and updates amortized O((log_{B^ε}N)/B^{1-ε}) I/Os w.h.p., matching B^ε-tree/LSM. Novel proof: extremal-graph coloring decomposes paths into uncorrelated groups so few levels suffice. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1729
Venue: PODS
Year: 2017
Pagerank: 4.1945683e-05
Overall Rank: 11,764 | 18.16%
DOI: 10.1145/3034786.3056117

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
11,562	Timely Reporting of Heavy Hitters using External Memory	2020	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
379	bLSM: A General Purpose Log Structured Merge Tree	2012	SIGMOD	0.0002493527
1,117	Cache-Oblivious String B-trees	2006	PODS	0.00013882205
1,248	Don't Thrash: How to Cache Your Hash on Flash	2012	VLDB	0.00013046661
1,480	Write-Optimized B-Trees	2004	VLDB	0.00011746722
2,396	A Novel Index Supporting High Volume Data Warehouse Insertions	1999	VLDB	8.8997169e-05
2,558	Rose: Compressed, log-structured replication	2008	VLDB	8.5455497e-05
11,822	Anti-Persistence on Persistent Storage: History-Independent Sparse Tables and Dictionaries	2016	PODS	4.1945683e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
11,965	A Dynamic I/O-Efficient Structure for One-Dimensional Top-k Range Reporting	2014	PODS	4.1945683e-05
4,941	Comparing Hierarchical Data in External Memory	1999	VLDB	5.8179899e-05
5,196	Clustering Techniques for Minimizing External Path Length	1996	VLDB	5.6365164e-05
8,767	Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes	2009	PODS	4.456315e-05
12,530	Lower Bounds for Sorting with Few Random Accesses to External Memory	2005	PODS	4.1945683e-05
8,546	I/O-Efficient Planar Range Skyline and Attrition Priority Queues	2013	PODS	4.4937074e-05
1,182	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS	0.00013455963
6,809	Adaptive Data Skipping in Main-Memory Systems	2016	SIGMOD	4.9206606e-05
11,825	Efficient Top-k Indexing via General Reductions	2016	PODS	4.1945683e-05
11,822	Anti-Persistence on Persistent Storage: History-Independent Sparse Tables and Dictionaries	2016	PODS	4.1945683e-05