Good Worst-Case Algorithms for Inserting and Deleting Records in Dense Sequential Files

Summary: Worst-case insertion and deletion for dense sequential files on M pages with gaps. For O(M) changes, runtime ~ log^2 M / page-size, illustrating robust worst-case guarantees for ordered-file data management. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2312
Venue: SIGMOD
Year: 1986
Pagerank: 8.3251971e-05
Overall Rank: 2,681 | 81.37%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Dan E. Willard

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,951	An Adaptive Packed-Memory Array	2006	PODS	7.9796299e-05
10,917	Layered List Labeling	2024	PODS	5.1725247e-05
11,830	Anti-Persistence on Persistent Storage: History-Independent Sparse Tables and Dictionaries	2016	PODS	5.1725247e-05
11,974	Cost-Oblivious Storage Reallocation	2014	PODS	5.1725247e-05

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
13,087	Performance Analysis Of Three Related Assignment Problems	1979	SIGMOD	5.1725247e-05
5,363	Dynamic File Allocation in Disk Arrays	1991	SIGMOD	6.3184365e-05
11,443	Frequent Elements with Witnesses in Data Streams	2021	PODS	5.1725247e-05
11,263	Out-of-Order Sliding-Window Aggregation with Efficient Bulk Evictions and Insertions	2023	VLDB	5.1725247e-05
3,517	Efficient Bulk Insertion into a Distributed Ordered Table	2008	SIGMOD	7.4156011e-05
6,363	Reading a Set of Disk Pages	1993	VLDB	5.963483e-05
971	Incremental Organization for Data Recording and Warehousing	1997	VLDB	0.00012972941
494	Interpolation-Based Index Maintenance	1983	PODS	0.0001757322
14,246	Stable Set and Multiset Operations in Optimal Time and Space	1988	PODS	-
6,410	Index Maintenance for Non-Uniform Record Distributions	1984	PODS	5.9504129e-05