Efficient external memory algorithms by simulating coarse-grained parallel algorithms

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Efficient external memory algorithms by simulating coarse-grained parallel algorithms

Full text

Pdf (1.33 MB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures table of contents

Newport, Rhode Island, United States

Pages: 106 - 115

Year of Publication: 1997

ISBN:0-89791-890-8

Authors

Frank Dehne	School of Computer Science, Carleton University Ottawa, Canada K1S 5B6
Wolfgang Dittrich	Department of Computer Science, University of Paderborn, 33095 Paderborn, Germany
David Hutchinson	School of Computer Science, Carleton Universitym Ottawa, Canada K1S 5B6

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 17, Citation Count: 14

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/258492.258503 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	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]
	2	B. Alpern, et al. The Uniform Memory Hierarchy Model of Computation. Algorithmica 12:72-109, 1994.
	3	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
	4	Lars Arge , Darren Erik Vengroff , Jeffrey Scott Vitter, External-Memory Algorithms for Processing Line Segments in Geographic Information Systems (Extended Abstract), Proceedings of the Third Annual European Symposium on Algorithms, p.295-310, September 25-27, 1995
	5	L. Arge. Efficient External-Memory Data Structures and Apphcations, Ph.D Thesis, BRICS, University of Aarhus, 1996.
	6	Armin Bäumker , Wolfgang Dittrich, Parallel Algorithms for Image Processing: Practical Algorithms with Experiments, Proceedings of the 10th International Parallel Processing Symposium, p.429-433, April 15-19, 1996
	7	Armin Bäumker , Wolfgang Dittrich , Friedhelm Meyer auf der Heide, Truly efficient parallel algorithms: 1-optimal multisearch for an extension of the BSP model, Selected papers from the third European symposium on Algorithms, p.175-203, August 1998, Courfu, Greece
	8	Armin Bäumker , Wolfgang Dittrich , Andrea Pietracaprina, The Deterministic Complexity of Parallel Multisearch (Extended Abstract), Proceedings of the 5th Scandinavian Workshop on Algorithm Theory, p.404-415, July 03-05, 1996
	9	Paul B. Callahan , Michael T. Goodrich , Kumar Ramaiyer, Topology B-Trees and Their Applications, Proceedings of the 4th International Workshop on Algorithms and Data Structures, p.381-392, August 16-18, 1995
	10	Yi-Jen Chiang, Dynamic and i/o-efficient algorithms for computational geometry and graph problems: theoretical and experimental results, 1996
	11	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
	12	Thomas H. Cormen, Virtual memory for data-parallel computing, Massachusetts Institute of Technology, Cambridge, MA, 1993
	13	Frank Dehne , Andreas Fabri , Andrew Rau-Chaplin, Scalable parallel geometric algorithms for coarse grained multicomputers, Proceedings of the ninth annual symposium on Computational geometry, p.298-307, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161154]
	14	F. Dehne, A. Fabri, and C. Kenyon. Scalable and Architecture Independent Parallel Geometric Algorithms with High Probability Optimal Time. Proc. 6th IEEE Symposium on Parallel and Distributed Processing, pp. 586-593, 1994.
	15	Frank Dehne , Xiaotie Deng , Patrick Dymond , Andreas Fabri , Ashfaq A. Khokhar, A randomized parallel 3D convex hull algorithm for coarse grained multicomputers, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.27-33, June 24-26, 1995, Santa Barbara, California, United States [doi>10.1145/215399.215410]
	16	Alexandros V. Gerbessiotis , Leslie G. Valiant, Direct bulk-synchronous parallel algorithms, Journal of Parallel and Distributed Computing, v.22 n.2, p.251-267, Aug. 1994 [doi>10.1006/jpdc.1994.1085]
	17	M.T. Goodrich, et al. External Memory Computational Geometry. Proc. FOCS, 714-723, 1993.
	18	W. Hoeffding, Probability inequalities for sums of bounded random variables, American Statistical Association Journal, 1963, 13-30.
	19	M.H. Nodine and J.S. Vitter. Paradigms for Optimal Sorting with Multiple Disks. Proc. Hawaii International Conference on System Sciences 1:50-59, 1993.
	20	Mark H. Nodine , Jeffrey Scott Vitter, Greed sort: optimal deterministic sorting on parallel disks, Journal of the ACM (JACM), v.42 n.4, p.919-933, July 1995 [doi>10.1145/210332.210343]
	21	Jop F. Sibeyn , Michael Kaufmann, BSP-Like External-Memory Computation, Proceedings of the Third Italian Conference on Algorithms and Complexity, p.229-240, March 12-14, 1997
	22	Sairam Subramanian , Sridhar Ramaswamy, The P-range tree: a new data structure for range searching in secondary memory, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.378-387, January 22-24, 1995, San Francisco, California, United States
	23	Leslie G. Valiant, A bridging model for parallel computation, Communications of the ACM, v.33 n.8, p.103-111, Aug. 1990 [doi>10.1145/79173.79181]
	24	D.E. Vengroff. TPIE User Manual and Reference. Tech Report 1995.
	25	D. E. Vengroff , J. Scott Vitter, Supporting I/O-efficient scientific computation in TPIE, Proceedings of the 7th IEEE Symposium on Parallel and Distributeed Processing, p.74, October 25-28, 1995
	26	Jeffrey Scott Vitter , Mark H. Nodine, Large-scale sorting in uniform memory hierarchies, Journal of Parallel and Distributed Computing, v.17 n.1-2, p.107-114, Jan./Feb. 1993 [doi>10.1006/jpdc.1993.1008]
	27	J.S. Vitter and E.A.M. Shriver. Algorithms for Parallel Memory, I: Two Level Memories. Algorithmica 12:110- 147, 1994.

CITED BY 14

	Wolfgang Dittrich , David Hutchinson , Anil Maheshwari, Blocking in parallel multisearch problems (extended abstract), Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.98-107, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Jeffrey Scott Vitter, External memory algorithms, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.119-128, June 01-04, 1998, Seattle, Washington, United States
	Jeffrey Scott Vitter , David A. Hutchinson, Distribution sort with randomized cycle, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.77-86, January 07-09, 2001, Washington, D.C., United States
	A. Crauser , P. Ferragina , K. Mehlhorn , U. Meyer , E. Ramos, Randomized external-memory algorithms for some geometric problems, Proceedings of the fourteenth annual symposium on Computational geometry, p.259-268, June 07-10, 1998, Minneapolis, Minnesota, United States
	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
	Peter Sanders , Sebastian Egner , Jan Korst, Fast concurrent access to parallel disks, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.849-858, January 09-11, 2000, San Francisco, California, United States
	Frank Dehne , Todd Eavis , Susanne Hambrusch , Andrew Rau-Chaplin, Parallelizing the Data Cube, Distributed and Parallel Databases, v.11 n.2, p.181-201, March 2002
	Jeffrey Scott Vitter, External memory algorithms, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
	F. Dehne , W. Dittrich , D. Hutchinson , A. Maheshwari, Parallel virtual memory, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.889-890, January 17-19, 1999, Baltimore, Maryland, United States
	David Hutchinson , Anil Maheshwari , Norbert Zeh, An external memory data structure for shortest path queries, Discrete Applied Mathematics, v.126 n.1, p.55-82, March 2003
	Mark W. Goudreau , Kevin Lang , Satish B. Rao , Torsten Suel , Thanasis Tsantilas, Portable and Efficient Parallel Computing Using the BSP Model, IEEE Transactions on Computers, v.48 n.7, p.670-689, July 1999
	Deepak Ajwani , Roman Dementiev , Ulrich Meyer, A computational study of external-memory BFS algorithms, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.601-610, January 22-26, 2006, Miami, Florida
	Jens Gustedt, Efficient sampling of random permutations, Journal of Discrete Algorithms, v.6 n.1, p.125-139, March, 2008
	Charalampos Konstantopoulos , Basilis Mamalis , Grammati Pantziou , Damianos Gavalas, Efficient parallel Text Retrieval techniques on Bulk Synchronous Parallel (BSP)/Coarse Grained Multicomputers (CGM), The Journal of Supercomputing, v.48 n.3, p.286-318, June 2009