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: 2311
Venue: SIGMOD
Year: 1986
Pagerank: 0.00010696521
Overall Rank: 1,746 | 87.86%
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
3,366	An Adaptive Packed-Memory Array	2006	PODS	7.1726818e-05
10,913	Layered List Labeling	2024	PODS	4.1945683e-05
11,822	Anti-Persistence on Persistent Storage: History-Independent Sparse Tables and Dictionaries	2016	PODS	4.1945683e-05
11,966	Cost-Oblivious Storage Reallocation	2014	PODS	4.1945683e-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,074	Performance Analysis Of Three Related Assignment Problems	1979	SIGMOD	4.1945683e-05
4,993	Dynamic File Allocation in Disk Arrays	1991	SIGMOD	5.7818647e-05
11,440	Frequent Elements with Witnesses in Data Streams	2021	PODS	4.1945683e-05
11,261	Out-of-Order Sliding-Window Aggregation with Efficient Bulk Evictions and Insertions	2023	VLDB	4.1945683e-05
3,434	Efficient Bulk Insertion into a Distributed Ordered Table	2008	SIGMOD	7.0994919e-05
6,218	Reading a Set of Disk Pages	1993	VLDB	5.1528637e-05
1,077	Incremental Organization for Data Recording and Warehousing	1997	VLDB	0.00014247204
255	Interpolation-Based Index Maintenance	1983	PODS	0.00030498284
14,232	Stable Set and Multiset Operations in Optimal Time and Space	1988	PODS	-
6,323	Index Maintenance for Non-Uniform Record Distributions	1984	PODS	5.1114874e-05