On sorting strings in external memory (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On sorting strings in external memory (extended abstract)

Full text

Pdf (1.38 MB)

Source

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

El Paso, Texas, United States

Pages: 540 - 548

Year of Publication: 1997

ISBN:0-89791-888-6

Authors

Lars Arge	Department of Computer Science, Duke University, Durham, NC
Paolo Ferragina	Dipartimento di Informatica, Università di pisa, Pisa, Italy
Roberto Grossi	Dipartimento di Sistemi e Informatica, Università di Firenze, Firenze, Italy
Jeffrey Scott Vitter	Department of Computer Science, Duke University, Durham, NC

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

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

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/258533.258647 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	M. Adler, New coding techniques for improved bandwidth utilization, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.173, October 14-16, 1996
	2	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]
	3	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	4	Arne Andersson , Torben Hagerup , Stefan Nilsson , Rajeev Raman, Sorting in linear time?, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.427-436, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225173]
	5	A. Andersson and S. Nilsson. A new efficient radix sort. In Proc. IEEE Symp. on Foundations of Comp. Sci., pages 714- 721, 1994.
	6	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
	7	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
	8	L. Arge. Efficient External-Memory Data Structures and Applications. PhD thesis, University of Aarhus, February/August 1996.
	9	Lars Arge , Mikael Knudsen , Kirsten Larsen, A General Lower Bound on the I/O-Complexity of Comparison-based Algorithms, Proceedings of the Third Workshop on Algorithms and Data Structures, p.83-94, August 11-13, 1993
	10	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
	11	G. H. Gonnet , R. Baeza-Yates, Handbook of algorithms and data structures: in Pascal and C (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991
	12	R. Bayer and E. McCreight. Organization and maintenance of large ordered indexes. Acta Informatica, 1:173-189, 1972.
	13	Rudolf Bayer , Karl Unterauer, Prefix B-trees, ACM Transactions on Database Systems (TODS), v.2 n.1, p.11-26, March 1977 [doi>10.1145/320521.320530]
	14	Jon L. Bentley , Robert Sedgewick, Fast algorithms for sorting and searching strings, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.360-369, January 05-07, 1997, New Orleans, Louisiana, United States
	15	Peter M. Chen , Edward K. Lee , Garth A. Gibson , Randy H. Katz , David A. Patterson, RAID: high-performance, reliable secondary storage, ACM Computing Surveys (CSUR), v.26 n.2, p.145-185, June 1994 [doi>10.1145/176979.176981]
	16	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
	17	David R. Clark , J. Ian Munro, Efficient suffix trees on secondary storage, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.383-391, January 28-30, 1996, Atlanta, Georgia, United States
	18	Thomas H. Cormen , Leonard F. Wisniewski, Asymptotically Tight Bounds for Performing BMMC Permutations on Parallel Disk Systems, Dartmouth College, Hanover, NH, 1993
	19	Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979 [doi>10.1145/356770.356776]
	20	Paolo Ferragina , Roberto Grossi, A fully-dynamic data structure for external substring search, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.693-702, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225287]
	21	Paolo Ferragina , Roberto Grossi, A fully-dynamic data structure for external substring search, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.693-702, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225287]
	22	Paolo Ferragina , Roberto Grossi, Fast string searching in secondary storage: theoretical developments and experimental results, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.373-382, January 28-30, 1996, Atlanta, Georgia, United States
	23	Paolo Ferragina , Fabrizio Luccio, On the Parallel Dynamic Dictionary Matching Problem: New Results with Applications, Proceedings of the Fourth Annual European Symposium on Algorithms, p.261-275, September 25-27, 1996
	24	Edward A. Fox , Robert M. Akscyn , Richard K. Furuta , John J. Leggett, Digital libraries, Communications of the ACM, v.38 n.4, p.22-28, April 1995 [doi>10.1145/205323.205325]
	25	Michael L. Fredman , Dan E. Willard, Surpassing the information theoretic bound with fusion trees, Journal of Computer and System Sciences, v.47 n.3, p.424-436, Dec. 1993 [doi>10.1016/0022-0000(93)90040-4]
	26	Karen A. Frenkel, The human genome project and informatics, Communications of the ACM, v.34 n.11, p.40-51, Nov. 1991 [doi>10.1145/125490.125492]
	27	Garth A. Gibson , Jeffrey Scott Vitter , John Wilkes, Strategic directions in storage I/O issues in large-scale computing, ACM Computing Surveys (CSUR), v.28 n.4, p.779-793, Dec. 1996 [doi>10.1145/242223.242300]
	28	M. T Goodrich, J.-J. Tsay, D. E. Vengroff, and J. S. Vitter. External-memory computational geometry. In Proc. IEEE Symp. on Foundations of Comp. Sci., pages 714-723, 1993.
	29	Torben Hagerup, Optimal parallel string algorithms: sorting, merging and computing the minimum, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.382-391, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195202]
	30	Torben Hagerup , Ola Petersson, Merging and Sorting Strings in Parallel, Proceedings of the 17th International Symposium on Mathematical Foundations of Computer Science, p.298-306, August 24-28, 1992
	31	S. Huddleston and K. Mehlhom. A new data structure for representing sorted lists. Acta Informatica, 17:157-184, 1982.
	32	Joseph F. JáJá , Kwan Woo Ryu , Uzi Vishkin, Sorting strings and constructing digital search trees in parallel, Theoretical Computer Science, v.154 n.2, p.225-245, Feb. 5, 1996 [doi>10.1016/0304-3975(94)00263-0]
	33	Richard M. Karp , Raymond E. Miller , Arnold L. Rosenberg, Rapid identification of repeated patterns in strings, trees and arrays, Proceedings of the fourth annual ACM symposium on Theory of computing, p.125-136, May 01-03, 1972, Denver, Colorado, United States [doi>10.1145/800152.804905]
	34	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
	35	Udi Manber , Gene Myers, Suffix arrays: a new method for on-line string searches, SIAM Journal on Computing, v.22 n.5, p.935-948, Oct. 1993 [doi>10.1137/0222058]
	36	Edward M. McCreight, A Space-Economical Suffix Tree Construction Algorithm, Journal of the ACM (JACM), v.23 n.2, p.262-272, April 1976 [doi>10.1145/321941.321946]
	37	T. H. Merrett, Why sort-merge gives the best implementation of the natural join, ACM SIGMOD Record, v.13 n.2, p.39-51, January 1983 [doi>10.1145/984523.984526]
	38	Donald R. Morrison, PATRICIA—Practical Algorithm To Retrieve Information Coded in Alphanumeric, Journal of the ACM (JACM), v.15 n.4, p.514-534, Oct. 1968 [doi>10.1145/321479.321481]
	39	J. I. Munro and V. Raman. Sorting multisets and vectors inplace. In Proc. Workshop on Algorithms and Data Structures, LNCS 519, pages 473479, 1991.
	40	Mark H. Nodine , Jeffrey Scott Vitter, Deterministic distribution sort in shared and distributed memory multiprocessors, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.120-129, June 30-July 02, 1993, Velen, Germany [doi>10.1145/165231.165247]
	41	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]
	42	Yale N. Patt, The I/O subsystem/spl minus/a candidate for improvement, Computer, v.27 n.3, p.15-16, March 1994 [doi>10.1109/2.268880]
	43	Mikkel Thorup, Randomized sorting in O(n log log n) time and linear space using addition, shift, and bit-wise boolean operations, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.352-359, January 05-07, 1997, New Orleans, Louisiana, United States
	44	Erik D Vengroff , Scott J Vitter, I/O Efficient Scientific Computation Using TPIE, Duke University, Durham, NC, 1995
	45	D.E. Vengroff and J. S. Vitter. I/O-efficient computation: The TPIE approach. In Proceedings of the Go~_ddard Conference on Mass Storage Systems and Technologies, NASA Conference Publication 3340, 'Volume II, pages 553-570, College Park, MD, September 1996.
	46	J. S. Vitter and E. A. M. Shriven Algorithms for parallel memory, I: Two-level memories. Algorithmica, 12(2-3):110- 147, 1994.

CITED BY 17

	H. V. Jagadish , Nick Koudas , Divesh Srivastava, On effective multi-dimensional indexing for strings, ACM SIGMOD Record, v.29 n.2, p.403-414, June 2000
	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
	Martin Farach-Colton , Paolo Ferragina , S. Muthukrishnan, On the sorting-complexity of suffix tree construction, Journal of the ACM (JACM), v.47 n.6, p.987-1011, Nov. 2000
	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
	Lars Arge, External memory data structures, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
	Jeffrey Scott Vitter, External memory algorithms, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
	Paolo Ferragina , Roberto Grossi, The string B-tree: a new data structure for string search in external memory and its applications, Journal of the ACM (JACM), v.46 n.2, p.236-280, March 1999
	Lars Arge , Octavian Procopiuc , Sridhar Ramaswamy , Torsten Suel , Jeffrey Scott Vitter, Theory and practice of I/O-efficient algorithms for multidimensional batched searching problems, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.685-694, January 25-27, 1998, San Francisco, California, 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
	Ranjan Sinha , Justin Zobel, Cache-conscious sorting of large sets of strings with dynamic tries, Journal of Experimental Algorithmics (JEA), v.9 n.es, 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
	Ranjan Sinha , Justin Zobel, Using random sampling to build approximate tries for efficient string sorting, Journal of Experimental Algorithmics (JEA), 10, 2005
	Milan Ružić, Making deterministic signatures quickly, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.900-909, January 07-09, 2007, New Orleans, Louisiana
	Jeffrey Scott Vitter, Algorithms and data structures for external memory, Foundations and Trends® in Theoretical Computer Science, v.2 n.4, p.305-474, January 2008
	Kangho Roh , Maxime Crochemore , Costas S. Iliopoulos , Kunsoo Park, External Memory Algorithms for String Problems, Fundamenta Informaticae, v.84 n.1, p.17-32, August 2008
	Roman Dementiev , Juha Kärkkäinen , Jens Mehnert , Peter Sanders, Better external memory suffix array construction, Journal of Experimental Algorithmics (JEA), 12, June 2008
	Milan Ružić, Making deterministic signatures quickly, ACM Transactions on Algorithms (TALG), v.5 n.3, p.1-26, July 2009