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)
Incoming Non-self Citations Over Time
Authors
- 1. Dan E. Willard (Bell Communications Research; State University of New York at Albany)
BibTeX Citation
@inproceedings{willard_sigmod86,
title = {{Good Worst-Case Algorithms for Inserting and Deleting Records in Dense Sequential Files}},
author = {Willard, Dan E.},
series = {{SIGMOD} '86},
booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
publisher = {Association for Computing Machinery},
doi = {10.1145/16894.16879},
url = {https://dl.acm.org/doi/10.1145/16894.16879},
year = {1986}
}
Incoming Citations (Sorted by Pagerank)
Showing 4 of 4 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 2,950 | An Adaptive Packed-Memory Array | 2006 | PODS | 7.9260861e-05 |
| 11,134 | Layered List Labeling | 2024 | PODS | 5.093636e-05 |
| 12,025 | Anti-Persistence on Persistent Storage: History-Independent Sparse Tables and Dictionaries | 2016 | PODS | 5.093636e-05 |
| 12,164 | Cost-Oblivious Storage Reallocation | 2014 | PODS | 5.093636e-05 |
Previous
Page 1 / 1
Next
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 |
|---|
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 13,275 | Performance Analysis Of Three Related Assignment Problems | 1979 | SIGMOD |
| 2 | 5,428 | Dynamic File Allocation in Disk Arrays | 1991 | SIGMOD |
| 3 | 11,638 | Frequent Elements with Witnesses in Data Streams | 2021 | PODS |
| 4 | 11,460 | Out-of-Order Sliding-Window Aggregation with Efficient Bulk Evictions and Insertions | 2023 | VLDB |
| 5 | 3,566 | Efficient Bulk Insertion into a Distributed Ordered Table | 2008 | SIGMOD |
| 6 | 6,460 | Reading a Set of Disk Pages | 1993 | VLDB |
| 7 | 981 | Incremental Organization for Data Recording and Warehousing | 1997 | VLDB |
| 8 | 507 | Interpolation-Based Index Maintenance | 1983 | PODS |
| 9 | 14,432 | Stable Set and Multiset Operations in Optimal Time and Space | 1988 | PODS |
| 10 | 6,497 | Index Maintenance for Non-Uniform Record Distributions | 1984 | PODS |