A fully-dynamic data structure for external substring search

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A fully-dynamic data structure for external substring search

Full text

Pdf (1.20 MB)

Source

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

Las Vegas, Nevada, United States

Pages: 693 - 702

Year of Publication: 1995

ISBN:0-89791-718-9

Authors

Paolo Ferragina	Dipartimento di Informatica, Università di Pisa, Italy
Roberto Grossi	Dipartimento di Sistemi e Informatica, Università di Firenze, Italy

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 43, Citation Count: 15

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/225058.225287 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	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	Amihood Amir , Martin Farach , Zvi Galil , Raffaele Giancarlo , Kunsoo Park, Dynamic dictionary matching, Journal of Computer and System Sciences, v.49 n.2, p.208-222, Oct. 1994 [doi>10.1016/S0022-0000(05)80047-9]
	3	Amihood Amir , Martin Farach , S. Muthukrishnan, Alphabet dependence in parameterized matching, Information Processing Letters, v.49 n.3, p.111-115, Feb. 11, 1994 [doi>10.1016/0020-0190(94)90086-8]
	4	APOSTOLIC, A. The myriad virtues of subword trees. In Combinator~al Algorithms on Words (1985), A. Apostolic and Z. Galil, Eds., NATO ASI F: Computer and System Sciences, Springer-Verlag, pp. 85-96.
	5	Brenda S. Baker, A theory of parameterized pattern matching: algorithms and applications, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.71-80, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167115]
	6	BAYER, R., AND MCCREIGHT, C. Organization maintenance of large ordered indexes. Act a Injormatica 1, 3 (1972), pp. 173-189.
	7	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]
	8	A. Blumer , J. Blumer , D. Haussler , R. McConnell , A. Ehrenfeucht, Complete inverted files for efficient text retrieval and analysis, Journal of the ACM (JACM), v.34 n.3, p.578-595, July 1987 [doi>10.1145/28869.28873]
	9	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
	10	Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979 [doi>10.1145/356770.356776]
	11	Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
	12	Paolo Ferragina , Roberto Grossi, Fast incremental text editing, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.531-540, January 22-24, 1995, San Francisco, California, United States
	13	Philippe Flajolet , Robert Sedgewick, Digital search trees revisited, SIAM Journal on Computing, v.15 n.3, p.748-767, August 1986 [doi>10.1137/0215054]
	14	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]
	15	GALIL, Z. Open problems in stringology. In Combina-torial Algorithms on Words (1985), A. Apostolic and Z. Galil, Eds., NATO ASI Series F: Computer and Sys-tem Sciences, Springer-Verlag, pp. 1-8.
	16	Gaston H. Gonnet , Ricardo A. Baeza-Yates , Tim Snider, New indices for text: PAT Trees and PAT arrays, Information retrieval: data structures and algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
	17	GOODRICH, M. T., TSAY, J.-J., VENGROFF, D. E., AND VITTER, J. S. External-memory computational geometry. In IEEE Foundations of Comp. Sci. (1993), pp. 714-723.
	18	Dan Gusfield , Gad M. Landau , Baruch Schieber, An efficient algorithm for the All Pairs Suffix-Prefix Problem, Information Processing Letters, v.41 n.4, p.181-185, March 18, 1992 [doi>10.1016/0020-0190(92)90176-V]
	19	Ramana M. Idury , Alejandro A. Schäffer, Multiple Matching of Parameterized Patterns, Proceedings of the 5th Annual Symposium on Combinatorial Pattern Matching, p.226-239, June 05-08, 1994
	20	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
	21	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]
	22	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]
	23	Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
	24	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
	25	WEINER, P. Linear pattern matching algorithm. In Proc. IEEE SWAT (now, FOCS) (1973), pp. 1-11.

CITED BY 15

	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
	Lars Arge , Paolo Ferragina , Roberto Grossi , Jeffrey Scott Vitter, On sorting strings in external memory (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.540-548, May 04-06, 1997, El Paso, Texas, United States
	Lars Arge , Paolo Ferragina , Roberto Grossi , Jeffrey Scott Vitter, On sorting strings in external memory (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.540-548, May 04-06, 1997, El Paso, Texas, United States
	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
	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
	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
	Maxime Crochemore, Reducing space for index implementation, Theoretical Computer Science, v.292 n.1, p.185-197, January 2003
	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
	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
	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
	Adam L. Buchsbaum , Glenn S. Fowler , Balachannder Kirishnamurthy , Kiem-Phong Vo , Jia Wang, Fast prefix matching of bounded strings, Journal of Experimental Algorithmics (JEA), 8, 2003
	Bijit Hore , Hakan Hacigumus , Bala Iyer , Sharad Mehrotra, Indexing text data under space constraints, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA
	Paolo Ferragina , Nick Koudas , Divesh Srivastava , S. Muthukrishnan, Two-dimensional substring indexing, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.282-288, May 2001, Santa Barbara, California, United States
	Radim Bača , Michal Krátký , Václav Snášel, On the efficient search of an XML twig query in large DataGuide trees, Proceedings of the 2008 international symposium on Database engineering & applications, September 10-12, 2008, Coimbra, Portugal