Article

Free access

Fast string searching in secondary storage: theoretical developments and experimental results

Authors:

Paolo Ferragina,

Roberto GrossiAuthors Info & Claims

SODA '96: Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms

Pages 373 - 382

Published: 28 January 1996 Publication History

PDF eReader

References

[1]

BAYER, R., AND MCCREIGHT, C. Organization and maintenance of large ordered indexes. Acta Informatica i (1972), pp. 173-189.

Google Scholar

[2]

BAYER, R., AND UNTERAURER, K. Prefix B-trees. A CM Trans. Database Syst. 2 (1977), pp. 11-26.

Digital Library

Google Scholar

[3]

BLUMER, A., BLUMER, J., HAUSSLER, D., Mc- CONNEL, R., AND EFIRENFEUCHT, A. Complete inverted files for efficient text retrieval and analysis. Journal of the A CM 3~ (1987), pp. 578-595.

Digital Library

Google Scholar

[4]

CHURCH, K. W. Personal communication.

Google Scholar

[5]

CLARK, D. R., AND MUNRO, J. I. Efficient suffix trees on secondary stor~tge. In ACM-SIAM Symposium on Discrete Algorithms (1996), this volume.

Digital Library

Google Scholar

[6]

COMER, D. The ubiquitous B-Tree. Computing Surveys 11 (1979), pp. 121-137.

Digital Library

Google Scholar

[7]

DAaaAGH, J. Z., CLEARY, J. G., AND WITTEN, I. H. Bonsai: A compact representation of trees. Software- Practice and Experience ~3 (1993), pp. 277-291.

Digital Library

Google Scholar

[8]

FERRAGINA, P., AND GROSSI, R. A fully-dynamic data structure for external substring search. In ACM STOC (1995), pp. 693-702.

Digital Library

Google Scholar

[9]

FERRAGINA, P., LuccIo, F., AND PAGLI, L. Maintaining B-trees in a two level PRAM. Franco Angeli Ed., vol. 1418.3 (1995), pp. 104-113.

Google Scholar

[10]

FRENKBL, K. A. The human genome project and informatics. Comm. ACM 3~ (1991), pp. 41-51.

Digital Library

Google Scholar

[11]

GONNET, G. It., BAEZA-YATES, R. A., AND SNIDER, T. New indices for text: PAT trees and PAT arrays. In In}ormation Retrieval: Data Structures and Algorithms, Frakes and Baeza-Yates Eds., Prentice-Ha!l, 1992, pp. 66-82.

Digital Library

Google Scholar

[12]

JACOBSON, G. Succinct static data structures. Tech. Rep. CMU-CS-89-112, Carnegie Mellon Univ., 1989.

Google Scholar

[13]

KNUTH, D. E. The Art of Computer Programming. Addison-Wesley, 1973, vol. 3: Sorting and Searching.

Digital Library

Google Scholar

[14]

MANBER, U., AND MYEas, G. Suffix arrays: a new method for on-line string searches. SIAM Journal on Computing 22 (1993), pp. 935-948.

Digital Library

Google Scholar

[15]

MCCREIGHT, E. M. A space-economical suffix tree construction algorithm. J. ACM 23 (1976), pp.262-272.

Digital Library

Google Scholar

[16]

MERRET, T. H., AND SHANG, H. Trie methods for representing the text. Manuscript (1995).

Google Scholar

[17]

MEwEs, H. W., AND HEtnWANN, K. Genome analysis: Pattern search in biological macromolecules. In CPM (1995), LNCS 937, pp. 261-285.

Google Scholar

[18]

MORRmON, D. R. PATRICIA: Practical algorithm to retrieve information coded in alphanumeric. J. A CM 15 (1968), pp. 514-534.

Digital Library

Google Scholar

[19]

PaYWES, N. S., AND GRAY, H. J. The organization of a Multilist-type associative memory. IEEE Trans. on Comm. and Electronics 68 (1963), pp. 488-492.

Google Scholar

[20]

SHANG, H. Trie methods for text and spatial data structures on secondary storage. PhD thesis, McGill University, 1995.

Digital Library

Google Scholar

[21]

SoaKn~, G. B. Personal communication.

Google Scholar

[22]

VENGROFF, D. E. A transparent parallel I/O environment. In DAGS Syrup. on Parallel Comp. (1994).

Google Scholar

[23]

WEn~BERGER, P. J. UNIX B-trees. Personal communication.

Google Scholar

Cited By

View all

Askitis NZobel J(2009)B-tries for disk-based string managementThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-008-0094-118:1(157-179)Online publication date: 1-Jan-2009
https://dl.acm.org/doi/10.1007/s00778-008-0094-1
Vitter J(2008)Algorithms and data structures for external memoryFoundations and Trends® in Theoretical Computer Science10.1561/04000000142:4(305-474)Online publication date: 1-Jan-2008
https://dl.acm.org/doi/10.1561/0400000014
Arroyuelo DNavarro G(2007)A Lempel-Ziv text index on secondary storageProceedings of the 18th annual conference on Combinatorial Pattern Matching10.5555/2394373.2394388(83-94)Online publication date: 9-Jul-2007
https://dl.acm.org/doi/10.5555/2394373.2394388
Show More Cited By

Index Terms

Fast string searching in secondary storage: theoretical developments and experimental results

Recommendations

Dynamic string searching
SODA '01: Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms

Optimal bounds are presented for dynamic string searching. If the longest common prefix between a query key x and a currently stored string y is ℓ words, then finding the stored string lexicographically nearest to x takes optimal Θ(√log n/log log n + ℓ) ...
Fast k-Nearest Neighbor Searching in Static Objects

The k-nearest neighbor searching is a classical problem that has been seriously studied, due to its many important applications. The paper proposes an efficient algorithm to search the k-nearest neighbors for static objects. Since locations of static ...
Analysis of Secondary Storage Fragmentation

Fragmentation of storage is a common phenomenon in both main storage and secondary storage. Fragmentation in secondary storage not only jeopardizes the allocation of space but also, since secondary storage access time-unlike that in main storage-is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SODA '96: Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms

January 1996

586 pages

ISBN:0898713668

Chairman:
Éva Tardos

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 28 January 1996

Check for updates

Qualifiers

Article

Conference

SODA96

Sponsor:

SIGACT
SIAM

SODA96: Conference on Discrete Algorithms

January 28 - 30, 1996

Georgia, Atlanta, USA

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
661
Total Downloads

Downloads (Last 12 months)33
Downloads (Last 6 weeks)10

Reflects downloads up to 03 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Askitis NZobel J(2009)B-tries for disk-based string managementThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-008-0094-118:1(157-179)Online publication date: 1-Jan-2009
https://dl.acm.org/doi/10.1007/s00778-008-0094-1
Vitter J(2008)Algorithms and data structures for external memoryFoundations and Trends® in Theoretical Computer Science10.1561/04000000142:4(305-474)Online publication date: 1-Jan-2008
https://dl.acm.org/doi/10.1561/0400000014
Arroyuelo DNavarro G(2007)A Lempel-Ziv text index on secondary storageProceedings of the 18th annual conference on Combinatorial Pattern Matching10.5555/2394373.2394388(83-94)Online publication date: 9-Jul-2007
https://dl.acm.org/doi/10.5555/2394373.2394388
Ko PAluru S(2006)Obtaining provably good performance from suffix trees in secondary storageProceedings of the 17th Annual conference on Combinatorial Pattern Matching10.1007/11780441_8(72-83)Online publication date: 5-Jul-2006
https://dl.acm.org/doi/10.1007/11780441_8
Clifford RSergot M(2003)Distributed and paged suffix trees for large genetic databasesProceedings of the 14th annual conference on Combinatorial pattern matching10.5555/1756553.1756559(70-82)Online publication date: 25-Jun-2003
https://dl.acm.org/doi/10.5555/1756553.1756559
Wang HPerng CFan WYu P(2002)An Index Structure for Pattern Similarity Searching in DNA Microarray DataProceedings of the IEEE Computer Society Conference on Bioinformatics10.5555/792771.793847Online publication date: 14-Aug-2002
https://dl.acm.org/doi/10.5555/792771.793847
Arge L(2002)External memory data structuresHandbook of massive data sets10.5555/779232.779242(313-357)Online publication date: 1-Jan-2002
https://dl.acm.org/doi/10.5555/779232.779242
Bumbulis PBowman IMoon BDeWitt DFranklin M(2002)A compact B-treeProceedings of the 2002 ACM SIGMOD international conference on Management of data10.1145/564691.564753(533-541)Online publication date: 3-Jun-2002
https://dl.acm.org/doi/10.1145/564691.564753
Vitter J(2001)External memory algorithms and data structuresACM Computing Surveys10.1145/384192.38419333:2(209-271)Online publication date: 1-Jun-2001
https://dl.acm.org/doi/10.1145/384192.384193
Ferragina PKoudas NSrivastava DMuthukrishnan SBuneman P(2001)Two-dimensional substring indexingProceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems10.1145/375551.375610(282-288)Online publication date: 1-May-2001
https://dl.acm.org/doi/10.1145/375551.375610
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Dynamic string searching

Fast k-Nearest Neighbor Searching in Static Objects

Analysis of Secondary Storage Fragmentation