Complete inverted files for efficient text retrieval and analysis

DOI10.1145/28869.28873zbMath1433.68118OpenAlexW2030839740WikidataQ90311855 ScholiaQ90311855MaRDI QIDQ5222002

Anselm Blumer, Janet A. Blumer, David Haussler, Andrzej Ehrenfeucht, Ross M. McConnell

Publication date: 5 April 2020

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/28869.28873

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Data structures (68P05) Information storage and retrieval of data (68P20)

Related Items

Novel results on the number of runs of the Burrows-Wheeler-transform ⋮ General suffix automaton construction algorithm and space bounds ⋮ GLOUDS: representing tree-like graphs ⋮ La reconnaissance des facteurs d'un langage fini dans un texte en temps linéaire. (Recognition of the factors of a finite language in a text in linear time) ⋮ Compact directed acyclic word graphs for a sliding window ⋮ On Sturmian graphs ⋮ Composite Repetition-Aware Data Structures ⋮ Matching a set of strings with variable length don't cares ⋮ A general framework for enumerating equivalence classes of solutions ⋮ The palindromization map ⋮ Fast detection of specific fragments against a set of sequences ⋮ Inferring strings from position heaps in linear time ⋮ Linear-time computation of DAWGs, symmetric indexing structures, and MAWs for integer alphabets ⋮ On the bit-parallel simulation of the nondeterministic Aho-Corasick and suffix automata for a set of patterns ⋮ On Sensitivity of Compact Directed Acyclic Word Graphs ⋮ Sensitivity of string compressors and repetitiveness measures ⋮ The parameterized suffix tray ⋮ Unnamed Item ⋮ Parallel construction of minimal suffix and factor automata ⋮ Succinct data structures for flexible text retrieval systems ⋮ Block trees ⋮ Universal compressed text indexing ⋮ Algorithms for Indexing Highly Similar DNA Sequences ⋮ Position heaps: a simple and dynamic text indexing data structure ⋮ On-line construction of compact directed acyclic word graphs ⋮ Forty Years of Text Indexing ⋮ Ternary directed acyclic word graphs ⋮ On suffix extensions in suffix trees ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A faster algorithm for matching a set of patterns with variable length don't cares ⋮ The subsequence composition of a string ⋮ Online algorithms for constructing linear-size suffix trie ⋮ Optimal rank and select queries on dictionary-compressed text ⋮ Fully-online suffix tree and directed acyclic word graph construction for multiple texts ⋮ Efficient dynamic dictionary matching with DAWGs and AC-automata ⋮ Approximate string matching using factor automata ⋮ A speed-up for the commute between subword trees and DAWGs. ⋮ On maximal repeats in strings