Good worst-case algorithms for inserting and deleting records in dense sequential files

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Good worst-case algorithms for inserting and deleting records in dense sequential files

Full text

Pdf (1.01 MB)

Source

International Conference on Management of Data archive
Proceedings of the 1986 ACM SIGMOD international conference on Management of data table of contents

Washington, D.C., United States

Pages: 251 - 260

Year of Publication: 1986

ISBN:0-89791-191-1

Also published in ...

Author

Dan E. Willard

SUNY Albany and Consultant, Bell Communications Research

Sponsor

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 27, Citation Count: 7

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/16894.16879 What is a DOI?

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 log2M divided by the page-size when the set of manipulated records has cardinality O(M).

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	BCW-85	Brenda S. Baker , Dan E. Willard, Algorithms for resolving conflicts in dynamic storage allocation, Journal of the ACM (JACM), v.32 n.2, p.327-343, April 1985 [doi>10.1145/3149.335126]
	Fr-79	W R Franklin, "Padded Lists Set Operatlons m Expected 0(log log N) Time," In} Pro~ Letters, 9 4 (1979), pp 161-166
	HKW-86	M Horn, A Konhelm and D Wlllard, "Padded Lists Revisited", forthcoming report
	IKR-80	Alon Itai , Alan G. Konheim , Michael Rodeh, A Sparse Table Implementation of Priority Queues, Proceedings of the 8th Colloquium on Automata, Languages and Programming, p.417-431, July 13-17, 1981
	MG-78	Robert C. Melville , David Gries, Sorting and Searching Using Controlled Density Arrays, Cornell University, Ithaca, NY, 1978
	MG-80	R Melville and D Grins, "Controlled Density Sorting," Int" Proc Letters, 10 4 (1980), pp 169-172
	Wh-77	Gio C. Wiederhold, Database Design, McGraw-Hill, Inc., New York, NY, 1977
	Wi-81	D E Wlllard, "Inserting and Deleting coras m Blocked Sequential Flies," Bell Labs Tech Report TM81-45193-5, 1981
	Wi-82	D E Wlllard, "Maintaining Dense Sequential Flies in a Dynamic Environment," Bell Labs Tech Mem 45413-8212302, 1982
	Wi-85	D E Wlllard, "A Density Control Algorithm or doing insertions and deletmns m a sequentmlly ordered file m good and worst case time" SUNY Albany Technical Report 85-14, 1985
	WL-85	Dan E. Willard , George S. Lueker, Adding range restriction capability to dynamic data structures, Journal of the ACM (JACM), v.32 n.3, p.597-617, July 1985 [doi>10.1145/3828.3839]

CITED BY 7

	P. Dietz , D. Sleator, Two algorithms for maintaining order in a list, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.365-372, January 1987, New York, New York, United States
	Michael A. Bender , Ziyang Duan , John Iacono , Jing Wu, A locality-preserving cache-oblivious dynamic dictionary, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.29-38, January 06-08, 2002, San Francisco, California
	Karni Gilon , David Peleg, Compact deterministic distributed dictionaries (extended abstract), Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.81-94, August 19-21, 1991, Montreal, Quebec, Canada
	Michael A. Bender , Ziyang Duan , John Iacono , Jing Wu, A locality-preserving cache-oblivious dynamic dictionary, Journal of Algorithms, v.53 n.2, p.115-136, November 2004
	Michael A. Bender , Jeremy T. Fineman , Seth Gilbert , Charles E. Leiserson, On-the-fly maintenance of series-parallel relationships in fork-join multithreaded programs, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain
	Michael A. Bender , Haodong Hu, An adaptive packed-memory array, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA
	Michael A. Bender , Haodong Hu, An adaptive packed-memory array, ACM Transactions on Database Systems (TODS), v.32 n.4, p.26-es, November 2007