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,976 | An Adaptive Packed-Memory Array | 2006 | PODS | 7.7902411e-05 |
| 11,488 | Layered List Labeling | 2024 | PODS | 4.9769913e-05 |
| 12,326 | Anti-Persistence on Persistent Storage: History-Independent Sparse Tables and Dictionaries | 2016 | PODS | 4.9769913e-05 |
| 12,461 | Cost-Oblivious Storage Reallocation | 2014 | PODS | 4.9769913e-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,571 | Performance Analysis Of Three Related Assignment Problems | 1979 | SIGMOD |
| 2 | 5,565 | Dynamic File Allocation in Disk Arrays | 1991 | SIGMOD |
| 3 | 11,951 | Frequent Elements with Witnesses in Data Streams | 2021 | PODS |
| 4 | 11,778 | Out-of-Order Sliding-Window Aggregation with Efficient Bulk Evictions and Insertions | 2023 | VLDB |
| 5 | 3,641 | Efficient Bulk Insertion into a Distributed Ordered Table | 2008 | SIGMOD |
| 6 | 6,599 | Reading a Set of Disk Pages | 1993 | VLDB |
| 7 | 968 | Incremental Organization for Data Recording and Warehousing | 1997 | VLDB |
| 8 | 522 | Interpolation-Based Index Maintenance | 1983 | PODS |
| 9 | 14,748 | Stable Set and Multiset Operations in Optimal Time and Space | 1988 | PODS |
| 10 | 6,628 | Index Maintenance for Non-Uniform Record Distributions | 1984 | PODS |