A linear lower bound on index size for text retrieval

DOI10.1016/S0196-6774(03)00043-9MaRDI QIDQ4458870zbMATH OpenOpenAlexFDO

Authors Erik D. Demaine, Alejandro Lopez-Ortiz

Publication date 14 March 2004

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0196-6774(03)00043-9

zbMATH Keywords

information-retrieval systems

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20)

Recommendations

• A linear lower bound on index size for text retrieval
• Improved Dynamic Text Indexing
• Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
• Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract)
• Indexing compressed text

Cited in

(14)

• Succinct indices for path minimum, with applications
• Complete inverted files for efficient text retrieval and analysis
• A Survey of Data Structures in the Bitprobe Model
• A linear lower bound on index size for text retrieval
• Counting suffix arrays and strings
• Towards efficient positional inverted index
• Data structure lower bounds for document indexing problems
• Fast string dictionary lookup with one error
• Random access to high-order entropy compressed text
• Orthogonal range searching for text indexing
• On a model of indexability and its bounds for range queries
• scientific article; zbMATH DE number 6850405 (Why is no real title available?)
• The function-inversion problem: barriers and opportunities
• The cell probe complexity of succinct data structures

This page was built for publication: A linear lower bound on index size for text retrieval

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4458870)