Making data structures persistent

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Making data structures persistent

Full text

Pdf (1.33 MB)

Source

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

Berkeley, California, United States

Pages: 109 - 121

Year of Publication: 1986

ISBN:0-89791-193-8

Authors

J R Driscoll	Comp. Sci. Dept., Carnegie-Mellon Univ., Pittsburgh, PA
N Sarnak	Courant Inst. of Mathematical Sciences, New York University, New York, New York
D D Sleator	Comp. Sci. Dept., Carnegie-Mellon Univ., Pittsburgh, PA
R E Tarjan	Comp. Science Dept., Princeton Univ., Princeton, New Jersey and AT&T Bell Laboratories, Murray Hill, NJ

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): n/a, Downloads (12 Months): n/a, Citation Count: 21

Additional Information:

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

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	R. Bayer and E. MeCreight, "Organization of large ordered indexes," Acta Informatica 1 (1972), 173- 189.
	2	J .L . Bentley and J. B. Saxe, "Decompositional searching problems I: static-to-dynamic transformations," J. Algorithms 1 (1980), 301-358.
	3	N. Blum and K. Mehlhorn, "On the average number of rebalancing operations in weightbalanced trees," Theoretical Computer Science 11 (1980), 303-320.
	4	M.R. Brown and R. E. Tarjan, "Design and analysis of a data structure for representing sorted lists," SIAM J. Comput., 9 (1980), 594-614.
	5	B. Chazelle, "Filtering search: a new approach to query-answering," Proc 24 th Annual IEEE Symp. on Foundations of Computer Science (1983), 122- 132.
	6	Bernard Chazelle, How to search history, Information and Control, v.64 n.1-3, p.77-99, Jan./Feb./March 1985 [doi>10.1016/S0019-9958(85)80045-0]
	7	Bernard Chazelle , Leonidas J. Guibas, Fractional Cascading: A Data Structuring Technique with Geometric Applications, Proceedings of the 12th Colloquium on Automata, Languages and Programming, p.90-100, July 15-19, 1985
	8	B. Chazelle and L. J. Guibas, "Fractional cascading I: a data structuring technique," to appear.
	9	Richard Cole, Searching and sorting similar lists, Journal of Algorithms, v.7 n.2, p.202-220, June 1986 [doi>10.1016/0196-6774(86)90004-0]
	10	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]
	11	D. P. Dobkin and J. I. Munro, "Efficient uses of the past," Proc. 21 n Annual IEEE Symp. on Foundations of Computer Science (1980), 200-206.
	12	L. J. Guibas and R. Sedgewiclq "A dichromatic framework for balanced trees," Proc. 19 th Annual IEEE Syrup. on Foundations of Computer Science (1978), 8-21.
	13	R. Hood and R. Melville, "Real-time queue ol~rations in pure LISP," Inform. Process. Lett. t3 (1981), 50-54.
	14	Scott Huddleston , Kurt Mehlhorn, Robust Balancing in B-Trees, Proceedings of the 5th GI-Conference on Theoretical Computer Science, p.234-244, March 23-25, 1981
	15	S. Huddleston and K. Mehlhorn, "A new data structure for representing sorted lists," Acta Informatica 17 (1982), 157-184.
	16	S. Huddleston, "An efficient scheme for fast local updates in linear lists," Dept. of Information and Computer Science, University of California, irvine, CA, 1981.
	17	S. Rao Kosaraju, Localized search in sorted lists, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.62-69, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802458]
	18	T. Krijnen and L. G. L. T. Meertens, "Making B- trees work for B," IW 219/83, The Mathematical Centre, Amsterdam, The Netherlands, 1983.
	19	D. Maier and S. C. Salveter, "Hysterical B-trees," Inform. Process. Lett. 12 (1981), 199-202.
	20	E. W. Meyers, "AVL dags," TR 82-9, Dept. of Computer Science, The University of Arizona, Tucson, AZ, 1982.
	21	E. W. Myers, "An applicative random-access stack," Inform. Process. Lett. 17 (1983), 241-248.
	22	Eugene W. Myers, Efficient applicative data types, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.66-75, January 15-18, 1984, Salt Lake City, Utah, United States [doi>10.1145/800017.800517]
	23	J. Nievergelt and E. M. Reingold, "Binary search trees of bounded balance," SIAM J. Comput. 2 (1973), 33-43.
	24	M. H. Overmars, "Searching in the past I," Information and Control, to appear.
	25	M.H. Overmars, "Searching in the past II: general transforms," Technical Report RUU-CS-81-9, Department of Computer Science, University of Utrecht, Utrecht, The Netherlands, 1981.
	26	Thomas Reps , Tim Teitelbaum , Alan Demers, Incremental Context-Dependent Analysis for Language-Based Editors, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.3, p.449-477, July 1983 [doi>10.1145/2166.357218]
	27	Neil Ivor Sarnak, Persistent data structures, 1986
	28	Neil Sarnak , Robert E. Tarjan, Planar point location using persistent search trees, Communications of the ACM, v.29 n.7, p.669-679, July 1986 [doi>10.1145/6138.6151]
	29	D.D. Sleator, "An improved method for maintaining order in a list,"to appear.
	30	G. F. Swart, "Efficient algorithms for computing geometric intersections," Technical Report #85- 01-02, Department of Computer Science, University of Washington, Seattle, WA, 1985.
	31	Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
	32	R.E. Tarjan, "Updating a balanced search tree in O(1) rotations," Inform. Process. Lett. 16 (1983), 253-257.
	33	R. E. Tarjan, "Amortized computational complexity," SIAM J. Alg. Disc. Meth. 6 (1985), 306-318.
	34	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]
	35	Athanasios K. Tsakalidis, AVL-Trees for Localized Search, Proceedings of the 11th Colloquium on Automata, Languages and Programming, p.473-485, July 16-20, 1984
	36	A K. Tsakalidis, "An optimal implementation for localized search," A 84/06, Fachbereich Angewandte Mathematik und Informatik, Universit//t des Saarlandes, Saarbriicken, West Germany, 1984.

CITED BY 21

	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
	Arvind , Rishiyur S. Nikhil , Keshav K. Pingali, I-structures: data structures for parallel computing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.4, p.598-632, Oct. 1989
	Marshall Bern , David Dobkin , David Eppstein , Robert Grossman, Visibility with a moving point of view, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.107-117, January 22-24, 1990, San Francisco, California, United States
	George Kollios , Dimitrios Gunopulos , Vassilis J. Tsotras, On indexing mobile objects, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.261-272, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
	Rafail Ostrovsky , Moti Yung, How to withstand mobile virus attacks (extended abstract), Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.51-59, August 19-21, 1991, Montreal, Quebec, Canada
	L. J. Guibas , M. Sharir , S. Sifrony, On the general motion planning problem with two degrees of freedom, Proceedings of the fourth annual symposium on Computational geometry, p.289-298, June 06-08, 1988, Urbana-Champaign, Illinois, United States
	G. F. Johnson , D. Duggan, Stores and partial continuations as first-class objects in a language and its environment, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.158-168, January 10-13, 1988, San Diego, California, United States
	John Turek , Joel L. Wolf , Krishna R. Pattipati , Philip S. Yu, Scheduling parallelizable tasks: putting it all on the shelf, ACM SIGMETRICS Performance Evaluation Review, v.20 n.1, p.225-236, June 1992
	Nicholas Pippenger, Pure versus impure Lisp, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.2, p.223-238, March 1997
	M. Bern, Hidden surface removal for rectangles, Proceedings of the fourth annual symposium on Computational geometry, p.183-192, June 06-08, 1988, Urbana-Champaign, Illinois, United States
	Robert Paige, Future directions in program transformations, ACM Computing Surveys (CSUR), v.28 n.4es, Dec. 1996
	George Kollios , Vassilis J. Tsotras , Dimitrios Gunopulos , Alex Delis , Marios Hadjieleftheriou, Indexing Animated Objects Using Spatiotemporal Access Methods, IEEE Transactions on Knowledge and Data Engineering, v.13 n.5, p.758-777, September 2001
	Leonidas Guibas , John Hershberger , Jack Snoeyink, Compact interval trees: a data structure for convex hulls, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.169-178, January 22-24, 1990, San Francisco, California, United States
	M. Goodrich , M. Ghouse , J. Bright, Generalized sweep methods for parallel computational geometry, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.280-289, July 02-06, 1990, Island of Crete, Greece
	Vijay K. Vaishnavi, Multidimensional Balanced Binary Trees, IEEE Transactions on Computers, v.38 n.7, p.968-985, July 1989
	Marios Hadjieleftheriou , George Kollios , J. Tsotras , Dimitrios Gunopulos, Indexing spatiotemporal archives, The VLDB Journal — The International Journal on Very Large Data Bases, v.15 n.2, p.143-164, June 2006
	Marios Hadjieleftheriou , Erik Hoel , Vassilis J. Tsotras, SaIL: A Spatial Index Library for Efficient Application Integration, Geoinformatica, v.9 n.4, p.367-389, December 2005
	A. A. Diwan , Sanjeeva Rane , S. Seshadri , S. Sudarshan, Clustering Techniques for Minimizing External Path Length, Proceedings of the 22th International Conference on Very Large Data Bases, p.342-353, September 03-06, 1996
	Sergio Cabello , Erin W. Chambers, Multiple source shortest paths in a genus g graph, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.89-97, January 07-09, 2007, New Orleans, Louisiana
	Roly Perera, Programming Languages For Interactive Computing, Electronic Notes in Theoretical Computer Science (ENTCS), v.203 n.3, p.35-52, May, 2008
	Mark Cieliebak , Alexander Hall , Riko Jacob , Marc Nunkesser, Sequential vector packing, Theoretical Computer Science, v.409 n.3, p.351-363, December, 2008