Cache-oblivious priority queue and graph algorithm applications

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Cache-oblivious priority queue and graph algorithm applications

Full text

Pdf (263 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thiry-fourth annual ACM symposium on Theory of computing table of contents

Montreal, Quebec, Canada

SESSION: Session 5B table of contents

Pages: 268 - 276

Year of Publication: 2002

ISBN:1-58113-495-9

Authors

Lars Arge	Duke University
Michael A. Bender	SUNY Stony Brook
Erik D. Demaine	MIT
Bryan Holland-Minkley	Duke University
J. Ian Munro	University of Waterloo

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 17, Downloads (12 Months): 99, Citation Count: 19

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

ABSTRACT

(MATH) In this paper we develop an optimal cache-oblivious priority queue data structure, supporting insertion, deletion, and deletemin operations in O(¹ \over _B log^M/B^N \over _B) amortized memory transfers, where M and B are the memory and block transfer sizes of any two consecutive levels of a multilevel memory hierarchy. In a cache-oblivious data structure, M and B are not used in the description of the structure. The bounds match the bounds of several previously developed external-memory (cache-aware) priority queue data structures, which all rely crucially on knowledge about M and B. Priority queues are a critical component in many of the best known external- memory graph algorithms, and using our cache-oblivious priority queue we develop several cache- oblivious graph algorithms.

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	James Abello , Adam L. Buchsbaum , Jeffery Westbrook, A Functional Approach to External Graph Algorithms, Proceedings of the 6th Annual European Symposium on Algorithms, p.332-343, August 24-26, 1998
	2	A. Aggarwal , B. Alpern , A. Chandra , M. Snir, A model for hierarchical memory, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.305-314, January 1987, New York, New York, United States [doi>10.1145/28395.28428]
	3	Alok Aggarwal , Ashok Chandra, Virtual memory algorithms, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.173-185, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62227]
	4	A. Aggarwal, A. K. Chandra, and M. Snir. Hierarchical memory with block transfer. In Proc. IEEE Symp. on Foundations of Comp. Sci., pages 204--216, 1987.
	5	Alok Aggarwal , Jeffrey,S. Vitter, The input/output complexity of sorting and related problems, Communications of the ACM, v.31 n.9, p.1116-1127, Sept. 1988 [doi>10.1145/48529.48535]
	6	B. Alpern, L. Carter, E. Feig, and T. Selker. The uniform memory hierarchy model of computation. Algorithmica, 12(2--3),1994.
	7	R. J. Anderson , G. L. Miller, A simple randomized parallel algorithm for list-ranking, Information Processing Letters, v.33 n.5, p.269-273, January 1990 [doi>10.1016/0020-0190(90)90196-5]
	8	Lars Arge, The Buffer Tree: A New Technique for Optimal I/O-Algorithms (Extended Abstract), Proceedings of the 4th International Workshop on Algorithms and Data Structures, p.334-345, August 16-18, 1995
	9	Lars Arge, The I/O - Complexity of Ordered Binary - Decision Diagram Manipulation, Proceedings of the 6th International Symposium on Algorithms and Computation, p.82-91, December 04-06, 1995
	10	Lars Arge, External memory data structures, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
	11	Lars Arge , Gerth Stølting Brodal , Laura Toma, On External-Memory MST, SSSP, and Multi-way Planar Graph Separation, Proceedings of the 7th Scandinavian Workshop on Algorithm Theory, p.433-447, July 05-07, 2000
	12	R. Bayer and E. McCreight. Organization and maintenance of large ordered indexes. Acta Informica, 1:173--189, 1972.
	13	M. A. Bender , E. D. Demaine , M. Farach-Colton, Cache-oblivious B-trees, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.399, November 12-14, 2000
	14	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
	15	Robert D. Blumofe , Matteo Frigo , Christopher F. Joerg , Charles E. Leiserson , Keith H. Randall, An analysis of dag-consistent distributed shared-memory algorithms, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.297-308, June 24-26, 1996, Padua, Italy [doi>10.1145/237502.237574]
	16	Gerth Stølting Brodal , Rolf Fagerberg , Riko Jacob, Cache oblivious search trees via binary trees of small height, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.39-48, January 06-08, 2002, San Francisco, California
	17	Gerth Stølting Brodal , Jyrki Katajainen, Worst-Case External-Memory Priority Queues, Proceedings of the 6th Scandinavian Workshop on Algorithm Theory, p.107-118, July 08-10, 1998
	18	Adam L. Buchsbaum , Michael Goldwasser , Suresh Venkatasubramanian , Jeffery R. Westbrook, On external memory graph traversal, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.859-860, January 09-11, 2000, San Francisco, California, United States
	19	Yi-Jen Chiang , Michael T. Goodrich , Edward F. Grove , Roberto Tamassia , Darren Erik Vengroff , Jeffrey Scott Vitter, External-memory graph algorithms, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.139-149, January 22-24, 1995, San Francisco, California, United States
	20	Francis Y. Chin , John Lam , I-Ngo Chen, Efficient parallel algorithms for some graph problems, Communications of the ACM, v.25 n.9, p.659-665, Sept 1982 [doi>10.1145/358628.358650]
	21	Richard Cole , Uzi Vishkin, Deterministic coin tossing with applications to optimal parallel list ranking, Information and Control, v.70 n.1, p.32-53, July 1986 [doi>10.1016/S0019-9958(86)80023-7]
	22	Richard Cole , Uzi Vishkin, Approximate parallel scheduling. II.: applications to logarithmic-time optimal parallel graph algorithms, Information and Computation, v.92 n.1, p.1-47, May 1991 [doi>10.1016/0890-5401(91)90019-X]
	23	Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979 [doi>10.1145/356770.356776]
	24	R. Fadel , K. V. Jakobsen , J. Katajainen , J. Teuhola, Heaps and heapsort on secondary storage, Theoretical Computer Science, v.220 n.2, p.345-362, June 17, 1999 [doi>10.1016/S0304-3975(99)00006-7]
	25	Matteo Frigo , Charles E. Leiserson , Harald Prokop , Sridhar Ramachandran, Cache-Oblivious Algorithms, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.285, October 17-18, 1999
	26	S. Huddleston and K. Mehlhorn. A new data structure for representing sorted lists. Acta Informica, 17:157--184, 1982.
	27	Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
	28	Vijay Kumar , Eric J. Schwabe, Improved Algorithms and Data Structures for Solving Graph Problems in External Memory, Proceedings of the 8th IEEE Symposium on Parallel and Distributed Processing (SPDP '96), p.169, October 23-26, 1996
	29	Anthony LaMarca , Richard Ladner, The influence of caches on the performance of heaps, Journal of Experimental Algorithmics (JEA), 1, p.4-es, 1996 [doi>10.1145/235141.235145]
	30	Kameshwar Munagala , Abhiram Ranade, I/O-complexity of graph algorithms, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.687-694, January 17-19, 1999, Baltimore, Maryland, United States
	31	R. C. Prim. Shortest connection networks and some generalizations. Bell Syst. Tech. J., 36:1389--1401, 1957.
	32	Naila Rahman , Richard Cole , Rajeev Raman, Optimised Predecessor Data Structures for Internal Memory, Proceedings of the 5th International Workshop on Algorithm Engineering, p.67-78, August 28-31, 2001
	33	John E. Savage, Extending the Hong-Kung Model to Memory Hierarchies, Proceedings of the First Annual International Conference on Computing and Combinatorics, p.270-281, August 24-26, 1995
	34	R. E. Tarjan and U. Vishkin. An efficient parallel biconnectivity algorithm. SIAM Journal of Computing, 14(4):862--874, 1985.
	35	Sivan Toledo, Locality of Reference in LU Decomposition with Partial Pivoting, SIAM Journal on Matrix Analysis and Applications, v.18 n.4, p.1065-1081, Oct. 1997 [doi>10.1137/S0895479896297744]
	36	U. Vishkin. On efficient parallel strong orientation. Information Processing Letters, 20:235--240, 1985.
	37	Jeffrey Scott Vitter, External memory algorithms and data structures: dealing with massive data, ACM Computing Surveys (CSUR), v.33 n.2, p.209-271, June 2001 [doi>10.1145/384192.384193]
	38	J. S. Vitter and E. A. M. Shriver. Algorithms for parallel memory, II: Hierarchical multilevel memories. Algorithmica, 12(2--3):148--169, 1994.

CITED BY 19

	Pankaj K. Agarwal , Lars Arge , Andrew Danner , Bryan Holland-Minkley, Cache-oblivious data structures for orthogonal range searching, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA
	Robert Niewiadomski , José Nelson Amaral , Robert C. Holte, A performance study of data layout techniques for improving data locality in refinement-based pathfinding, Journal of Experimental Algorithmics (JEA), v.9 n.es, 2004
	Gerth Stølting Brodal , Rolf Fagerberg, On the limits of cache-obliviousness, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Gianni Franceschini, Proximity Mergesort: optimal in-place sorting in the cache-oblivious model, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Guy E. Blelloch , Phillip B. Gibbons, Effectively sharing a cache among threads, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain
	Rezaul Alam Chowdhury , Vijaya Ramachandran, Cache-oblivious shortest paths in graphs using buffer heap, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain
	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
	Gerth Stølting Brodal , Rolf Fagerberg, Cache-oblivious string dictionaries, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.581-590, January 22-26, 2006, Miami, Florida
	Rezaul Alam Chowdhury , Vijaya Ramachandran, External-memory exact and approximate all-pairs shortest-paths in undirected graphs, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Lars Arge , Gerth Stølting Brodal , Rolf Fagerberg , Morten Laustsen, Cache-oblivious planar orthogonal range searching and counting, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy
	Lars Arge , Mark de Berg , Herman Haverkort, Cache-oblivious R-trees, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy
	Lars Arge , Norbert Zeh, Simple and semi-dynamic structures for cache-oblivious planar orthogonal range searching, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA
	Luca Allulli , Peter Lichodzijewski , Norbert Zeh, A faster cache-oblivious shortest-path algorithm for undirected graphs with bounded edge lengths, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.910-919, January 07-09, 2007, New Orleans, Louisiana
	Matteo Frigo , Volker Strumpen, The memory behavior of cache oblivious stencil computations, The Journal of Supercomputing, v.39 n.2, p.93-112, February 2007
	Guangming Tan , Shengzhong Feng , Ninghui Sun, Cache oblivious algorithms for nonserial polyadic programming, The Journal of Supercomputing, v.39 n.2, p.227-249, February 2007
	Michael A. Bender , Martin Farach-Colton , Jeremy T. Fineman , Yonatan R. Fogel , Bradley C. Kuszmaul , Jelani Nelson, Cache-oblivious streaming B-trees, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA
	Nikolas Askitis , Ranjan Sinha, HAT-trie: a cache-conscious trie-based data structure for strings, Proceedings of the thirtieth Australasian conference on Computer science, p.97-105, January 30-February 02, 2007, Ballarat, Victoria, Australia
	Haim Kaplan , Robert Endre Tarjan, Thin heaps, thick heaps, ACM Transactions on Algorithms (TALG), v.4 n.1, p.1-14, March 2008
	Zhewei Wei , Ke Yi , Qin Zhang, Dynamic external hashing: the limit of buffering, Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures, August 11-13, 2009, Calgary, AB, Canada