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

Dan E. Willard: Good Worst-Case Algorithms for Inserting and Deleting Records in Dense Sequential Files. SIGMOD Conference 1986: 251-260

@inproceedings{DBLP:conf/sigmod/Willard86,
  author    = {Dan E. Willard},
  editor    = {Carlo Zaniolo},
  title     = {Good Worst-Case Algorithms for Inserting and Deleting Records
               in Dense Sequential Files},
  booktitle = {Proceedings of the 1986 ACM SIGMOD International Conference on
               Management of Data, Washington, D.C., May 28-30, 1986},
  publisher = {ACM Press},
  year      = {1986},
  pages     = {251-260},
  ee        = {http://doi.acm.org/10.1145/16894.16879, db/conf/sigmod/Willard86.html},
  crossref  = {DBLP:conf/sigmod/86},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

Abstract

Consider a file which arranges records in sequential order, and stores them with possible empty spaces in M consecutive pages of memory. We develop an insertion-deletion algorithm which runs in a worst-case time approximately proportional to log²M divided by the page-size when the set of manipulated records has cardinality O(M).

Copyright © 1986 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/smod7592 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

BibTeX

Printed Edition

Carlo Zaniolo (Ed.): Proceedings of the 1986 ACM SIGMOD International Conference on Management of Data, Washington, D.C., May 28-30, 1986. ACM Press 1986 BibTeX , SIGMOD Record 15(2)
Contents

Online Edition: ACM Digital Library

References

[BCW-85]: Brenda S. Baker, Edward G. Coffman Jr., Dan E. Willard: Algorithms for Resolving Conflicts in Dynamic Storage Allocation. J. ACM 32(2): 327-343(1985) BibTeX
[FR-79]: Wm. Randolph Franklin: Padded Lists: Set Operations in Expected Theta(log log N) Time. Inf. Process. Lett. 9(4): 161-166(1979) BibTeX
[HKW-86]: Micha Hofri, Alan G. Konheim: Padded Lists Revisited. SIAM J. Comput. 16(6): 1073-1114(1987) BibTeX
[IKR-80]: Alon Itai, Alan G. Konheim, Michael Rodeh: A Sparse Table Implementation of Priority Queues. ICALP 1981: 417-431 BibTeX
[MG-78]: ...
[MG-80]: Robert Melville, David Gries: Controlled Density Sorting. Inf. Process. Lett. 10(4/5): 169-172(1980) BibTeX
[Wh-77]: ...
[Wi-81]: ...
[Wi-82]: Dan E. Willard: Maintaining Dense Sequential Files in a Dynamic Environment (Extended Abstract). STOC 1982: 114-121 BibTeX
[Wi-85]: Dan E. Willard: A Density Control Algorithm for Doing Insertions and Deletions in a Sequentially Ordered File in Good Worst-Case Time. Inf. Comput. 97(2): 150-204(1992) BibTeX
[WL-85]: Dan E. Willard, George S. Lueker: Adding Range Restriction Capability to Dynamic Data Structures. J. ACM 32(3): 597-617(1985) BibTeX

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]