Two algorithms for maintaining order in a list

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Two algorithms for maintaining order in a list

Full text

Pdf (717 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the nineteenth annual ACM symposium on Theory of computing table of contents

New York, New York, United States

Pages: 365 - 372

Year of Publication: 1987

ISBN:0-89791-221-7

Authors

P. Dietz	Schlumberger-Doll Research, Ridgefield, CT
D. Sleator	Carnegie-Mellon University, Pittsburgh, PA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 19, Downloads (12 Months): 104, Citation Count: 68

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/28395.28434 What is a DOI?

ABSTRACT

The order maintenance problem is that of maintaining a list under a sequence of Insert and Delete operations, while answering Order queries (determine which of two elements comes first in the list). We give two new algorithms for this problem. The first algorithm matches the O(1) amortized time per operation of the best previously known algorithm, and is much simpler. The second algorithm permits all operations to be performed in O(1) worst-case time.

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.

	1	Henry G. Baker, Jr., List processing in real time on a serial computer, Communications of the ACM, v.21 n.4, p.280-294, April 1978 [doi>10.1145/359460.359470]
	2	Paul F. Dietz, Maintaining order in a linked list, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.122-127, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802184]
	3	J R Driscoll , N Sarnak , D D Sleator , R E Tarjan, Making data structures persistent, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.109-121, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12142]
	4	Daniel D. Sleator , Robert E. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, v.28 n.2, p.202-208, Feb. 1985 [doi>10.1145/2786.2793]
	5	Tarjan, R. E. Amortized Compu'Lational Complexity. SIAM J. AIg. Disc. Meth. 2(6), April 1985, pages 306- 318.
	6	Athanasios K. Tsakalidis, Maintaining order in a generalized linked list, Acta Informatica, v.21 n.1, p.101-112, May 1984 [doi>10.1007/BF00289142]
	7	Wegbreit, B. Retrieval from Context Trees. {afo. Proc. Lett. 3(4), March 1975, pages 119-120.
	8	Dan E. Willard, Maintaining dense sequential files in a dynamic environment (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.114-121, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802183]
	9	Dan E. Willard, Good worst-case algorithms for inserting and deleting records in dense sequential files, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.251-260, May 28-30, 1986, Washington, D.C., United States

CITED BY 68

	Adam L. Buchsbaum , Robert E. Tarjan, Confluently persistent deques via data structuaral bootstrapping, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.155-164, January 25-27, 1993, Austin, Texas, United States
	Prosenjit Gupta , Ravi Janardan , Michiel Smid, Efficient algorithms for generalized intersection searching on non-iso-oriented objects, Proceedings of the tenth annual symposium on Computational geometry, p.369-378, June 06-08, 1994, Stony Brook, New York, United States
	Magnus Carlsson, Monads for incremental computing, ACM SIGPLAN Notices, v.37 n.9, p.26-35, September 2002
	Ramana M. Idury , Alejandro A. Schäffer, Multiple matching of rectangular patterns, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.81-90, May 16-18, 1993, San Diego, California, United States
	Arne Andersson , Ola Petersson, On-line approximate list indexing with applications, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.20-27, January 22-24, 1995, San Francisco, California, United States
	Paul F. Dietz , Rajeev Raman, Persistence, amortization and randomization, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.78-88, January 28-30, 1991, San Francisco, California, United States
	Bowen Alpern , Roger Hoover , Barry K. Rosen , Peter F. Sweeney , F. Kenneth Zadeck, Incremental evaluation of computational circuits, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.32-42, January 22-24, 1990, San Francisco, California, United States
	Amihood Amir , Martin Farach , Ramana M. Idury , Johannes A. La Poutré , Alejandro A. Schäffer, Improved dynamic dictionary matching, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.392-401, January 25-27, 1993, Austin, Texas, United States
	Amos Fiat , Haim Kaplan, Making data structures confluently persistent, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.537-546, January 07-09, 2001, Washington, D.C., United States
	Bowen Alpern , Anthony Cocchi , Stephen Fink , David Grove, Efficient implementation of Java interfaces: Invokeinterface considered harmless, ACM SIGPLAN Notices, v.36 n.11, p.108-124, 11/01/2001
	Johannes A. La Poutré, Alpha-algorithms for incremental planarity testing (preliminary version), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.706-715, May 23-25, 1994, Montreal, Quebec, Canada
	Yoav Zibin , Joseph Yossi Gil, Fast algorithm for creating space efficient dispatching tables with application to multi-dispatching, ACM SIGPLAN Notices, v.37 n.11, November 2002
	Christian Worm Mortensen, Fully-dynamic two dimensional orthogonal range and line segment intersection reporting in logarithmic time, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Gad M. Landau , Jeanette P. Schmidt , Vassilis J. Tsotras, Historical queries along multiple lines of time evolution, The VLDB Journal — The International Journal on Very Large Data Bases, v.4 n.4, p.703-726, October 1995
	Richard Cole , Ramesh Hariharan, Dynamic LCA queries on trees, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.235-244, January 17-19, 1999, Baltimore, Maryland, United States
	David Eppstein , Zvi Galil , Giuseppe F. Italiano , Amnon Nissenzweig, Sparsification—a technique for speeding up dynamic graph algorithms, Journal of the ACM (JACM), v.44 n.5, p.669-696, Sept. 1997
	Ralf Hinze, Bootstrapping one-sided flexible arrays, ACM SIGPLAN Notices, v.37 n.9, p.2-13, September 2002
	Gianni Franceschini , J. Ian Munro, Implicit dictionaries with O(1) modifications per update and fast search, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.404-413, January 22-26, 2006, Miami, Florida
	Vassilis Christophides , Dimitris Plexousakis , Michel Scholl , Sotirios Tourtounis, On labeling schemes for the semantic web, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary
	Damien K. Fisher , Franky Lam , William M. Shui , Raymond K. Wong, Efficient ordering for XML data, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA
	Torsten Grust , Maurice Van Keulen , Jens Teubner, Accelerating XPath evaluation in any RDBMS, ACM Transactions on Database Systems (TODS), v.29 n.1, p.91-131, March 2004
	Stephen Alstrup , Gerth Stølting Brodal , Theis Rauhe, Pattern matching in dynamic texts, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.819-828, January 09-11, 2000, San Francisco, California, United States
	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
	Gerth Stølting Brodal, Finger search trees with constant insertion time, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.540-549, January 25-27, 1998, San Francisco, California, United States
	Umut A. Acar , Guy E. Blelloch , Robert Harper , Jorge L. Vittes , Shan Leung Maverick Woo, Dynamizing static algorithms, with applications to dynamic trees and history independence, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Prosenjit Bose , Joachim Gudmundsson , Pat Morin, Ordered theta graphs, Computational Geometry: Theory and Applications, v.28 n.1, p.11-18, May 2004
	Therese Biedl , Timothy Chan , Yashar Ganjali , Mohammad Taghi Hajiaghayi , David R. Wood, Balanced vertex-orderings of graphs, Discrete Applied Mathematics, v.148 n.1, p.27-48, 30 April 2005
	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
	Irit Katriel , Hans L. Bodlaender, Online topological ordering, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	David Eppstein , Michael T. Goodrich , Jonathan Z. Sun, The skip quadtree: a simple dynamic data structure for multidimensional data, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy
	Loukas Georgiadis , Robert E. Tarjan , Renato F. Werneck, Design of data structures for mergeable trees, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.394-403, January 22-26, 2006, Miami, Florida
	Torsten Grust, Accelerating XPath location steps, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin
	Amos Fiat , Haim Kaplan, Making data structures confluently persistent, Journal of Algorithms, v.48 n.1, p.16-58, August 2003
	David R. Wood, Optimal three-dimensional orthogonal graph drawing in the general position model, Theoretical Computer Science, v.299 n.1-3, p.151-178, 18 April 2003
	Michael A. Bender , Martin Farach-Colton , Bradley C. Kuszmaul, Cache-oblivious string B-trees, 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, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA
	Damien K. Fisher , Franky Lam , William M. Shui , Raymond K. Wong, Dynamic labeling schemes for ordered XML based on type information, Proceedings of the 17th Australasian Database Conference, p.59-68, January 16-19, 2006, Hobart, Australia
	George Lagogiannis , Yannis Panagis , Spyros Sioutas , Athanasios Tsakalidis, A survey of persistent data structures, Proceedings of the 9th WSEAS International Conference on Computers, p.1-6, July 14-16, 2005, Athens, Greece
	Umut A. Acar , Guy E. Blelloch , Robert Harper, Adaptive functional programming, ACM SIGPLAN Notices, v.37 n.1, p.247-259, Jan. 2002
	Peter Damaschke , Zhen Zhou, On queuing lengths in on-line switching, Theoretical Computer Science, v.339 n.2, p.333-343, 12 June 2005
	Umut A. Acar , Guy E. Blelloch , Matthias Blume , Kanat Tangwongsan, An experimental analysis of self-adjusting computation, ACM SIGPLAN Notices, v.41 n.6, June 2006
	Umut A. Acar , Guy E. Blelloch , Robert Harper, Adaptive functional programming, ACM Transactions on Programming Languages and Systems (TOPLAS), v.28 n.6, p.990-1034, November 2006
	David J. Pearce , Paul H. J. Kelly, A dynamic topological sort algorithm for directed acyclic graphs, Journal of Experimental Algorithmics (JEA), 11, 2006
	Silke Trißl , Ulf Leser, Fast and practical indexing and querying of very large graphs, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China
	Erik D. Demaine , Mihai Patrascu, Tight bounds for dynamic convex hull queries (again), Proceedings of the twenty-third annual symposium on Computational geometry, June 06-08, 2007, Gyeongju, South Korea
	Richard S. Bird , Stefan Sadnicki, Minimal on-line labelling, Information Processing Letters, v.101 n.1, p.41-45, 16 January 2007
	Irit Katriel , Hans L. Bodlaender, Online topological ordering, ACM Transactions on Algorithms (TALG), v.2 n.3, p.364-379, July 2006
	Hsiao-Fei Liu , Kun-Mao Chao, A tight analysis of the Katriel–Bodlaender algorithm for online topological ordering, Theoretical Computer Science, v.389 n.1-2, p.182-189, December, 2007
	Umut A. Acar , Amal Ahmed , Matthias Blume, Imperative self-adjusting computation, ACM SIGPLAN Notices, v.43 n.1, January 2008
	Shu-Yao Chien , Zografoula Vagena , Donghui Zhang , Vassilis J. Tsotras , Carlo Zaniolo, Efficient structural joins on indexed XML documents, Proceedings of the 28th international conference on Very Large Data Bases, p.263-274, August 20-23, 2002, Hong Kong, China
	Kunal Agrawal , Jeremy T. Fineman , Jim Sukha, Nested parallelism in transactional memory, Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, February 20-23, 2008, Salt Lake City, UT, USA
	Matthew Hammer , Umut A. Acar , Mohan Rajagopalan , Anwar Ghuloum, A proposal for parallel self-adjusting computation, Proceedings of the 2007 workshop on Declarative aspects of multicore programming, p.3-9, January 16-16, 2007, Nice, France
	Joseph (Yossi) Gil , Yoav Zibin, Efficient dynamic dispatching with type slicing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.30 n.1, p.5-es, November 2007
	Chouvalit Khancome , Veera Boonjing, Dynamic dictionary matching using inverted lists, Proceedings of the third conference on IASTED International Conference: Advances in Computer Science and Technology, p.397-401, April 02-04, 2007, Phuket, Thailand
	N. A. Aznauryan , S. D. Kuznetsov , L. G. Novak , M. N. Grinev, SLS: A numbering scheme for large XML documents, Programming and Computing Software, v.32 n.1, p.8-18, January 2006
	Mohamed Y. Eltabakh , Wing-Kai Hon , Rahul Shah , Walid G. Aref , Jeffrey S. Vitter, The SBC-tree: an index for run-length compressed sequences, Proceedings of the 11th international conference on Extending database technology: Advances in database technology, March 25-29, 2008, Nantes, France
	Melissa E. O'Neill , F. Warren Burton, A new method for functional arrays, Journal of Functional Programming, v.7 n.5, p.487-513, September 1997
	Matthew A. Hammer , Umut A. Acar, Memory management for self-adjusting computation, Proceedings of the 7th international symposium on Memory management, June 07-08, 2008, Tucson, AZ, USA
	Hamed Seiied Alavi , Seth Gilbert , Rachid Guerraoui, Extensible encoding of type hierarchies, ACM SIGPLAN Notices, v.43 n.1, January 2008
	Badrish Chandramouli , Jeff M. Phillips , Jun Yang, Value-based notification conditions in large-scale publish/subscribe systems?, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
	Guy E. Blelloch, Space-efficient dynamic orthogonal point location, segment intersection, and range reporting, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.894-903, January 20-22, 2008, San Francisco, California
	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
	Amos Korman, Improved compact routing schemes for dynamic trees, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada
	Deepak Ajwani , Tobias Friedrich , Ulrich Meyer, An O(n^2.75) algorithm for incremental topological ordering, ACM Transactions on Algorithms (TALG), v.4 n.4, p.1-14, August 2008
	Janis Voigtländer, Bidirectionalization for free! (Pearl), Proceedings of the 36th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, January 21-23, 2009, Savannah, GA, USA
	Michael A. Bender , Jeremy T. Fineman , Seth Gilbert, A new approach to incremental topological ordering, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.1108-1115, January 04-06, 2009, New York, New York
	Yuval Emek , Amos Korman, Brief announcement: new bounds for the controller problem, Proceedings of the 28th ACM symposium on Principles of distributed computing, August 10-12, 2009, Calgary, AB, Canada
	Yoav Giora , Haim Kaplan, Optimal dynamic vertical ray shooting in rectilinear planar subdivisions, ACM Transactions on Algorithms (TALG), v.5 n.3, p.1-51, July 2009