Forty years of text indexing

Alberto Apostolico, Maxime Crochemore, Martin Farach-Colton, Zvi Galil, S. Muthukrishnan

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    This paper reviews the first 40 years in the life of textual inverted indexes, their many incarnations, and their applications. The paper is non-technical and assumes some familiarity with the structures and constructions discussed. It is not meant to be exhaustive. It is meant to be a tribute to a ubiquitous tool of string matching - the suffix tree and its variants - and one of the most persistent subjects of study in the theory of algorithms.

    Original languageEnglish (US)
    Title of host publicationCombinatorial Pattern Matching - 24th Annual Symposium, CPM 2013, Proceedings
    Pages1-10
    Number of pages10
    DOIs
    StatePublished - 2013
    Event24th Annual Symposium on Combinatorial Pattern Matching, CPM 2013 - Bad Herrenalb, Germany
    Duration: Jun 17 2013Jun 19 2013

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume7922 LNCS
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Conference

    Conference24th Annual Symposium on Combinatorial Pattern Matching, CPM 2013
    CountryGermany
    CityBad Herrenalb
    Period6/17/136/19/13

    Keywords

    • FM-index
    • bi-tree
    • dawg
    • factor automaton
    • pattern matching
    • string searching
    • suffix array
    • suffix automaton
    • suffix tree
    • wavelet tree

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Computer Science(all)

    Fingerprint Dive into the research topics of 'Forty years of text indexing'. Together they form a unique fingerprint.

  • Cite this

    Apostolico, A., Crochemore, M., Farach-Colton, M., Galil, Z., & Muthukrishnan, S. (2013). Forty years of text indexing. In Combinatorial Pattern Matching - 24th Annual Symposium, CPM 2013, Proceedings (pp. 1-10). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7922 LNCS). https://doi.org/10.1007/978-3-642-38905-4_1