Lempel-Ziv compressed structures for document retrieval

DOI10.1016/J.IC.2019.01.006MaRDI QIDQ2272976zbMATH OpenOpenAlexWikidataFDO

Authors Héctor Ferrada, Gonzalo Navarro

Publication date 17 September 2019

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2019.01.006

zbMATH Keywords

compressed data structuresdocument retrievaltop-\(k\) queriesstring databasesdocument listing

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Data structures (68P05) Database theory (68P15) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Recommendations

• General document retrieval in compact space
• Improved compressed indexes for full-text document retrieval
• Space-Efficient Algorithms for Document Retrieval
• Stronger Lempel-Ziv based compressed text indexing
• Time-space trade-offs for Lempel-Ziv compressed indexing

Cites work

• scientific article; zbMATH DE number 3887059 (Why is no real title available?)
• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• scientific article; zbMATH DE number 2079421 (Why is no real title available?)
• scientific article; zbMATH DE number 2119724 (Why is no real title available?)
• An analysis of the Burrows-Wheeler transform
• Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
• Compressed representations of sequences and full-text indexes
• Compression of Low Entropy Strings with Lempel--Ziv Algorithms
• Compression of individual sequences via variable-rate coding
• Fully functional static and dynamic succinct trees
• General document retrieval in compact space
• Implementing the LZ-index, theory versus practice
• Improved compressed indexes for full-text document retrieval
• Improved range minimum queries
• Improved single-term top-\(k\) document retrieval
• Indexing compressed text
• Indexing text using the Ziv--Lempel trie
• Information retrieval. Implementing and evaluating search engines.
• New algorithms on wavelet trees and applications to information retrieval
• New text indexing functionalities of the compressed suffix arrays
• On compressing and indexing repetitive sequences
• On the height of digital trees and related problems
• Representing trees of higher degree
• Space-Efficient Algorithms for Document Retrieval
• Space-Efficient Framework for Top-k String Retrieval Problems
• Space-efficient data-analysis queries on grids
• Space-efficient frameworks for top-\(k\) string retrieval
• Space-efficient preprocessing schemes for range minimum queries on static arrays
• Spaces, trees, and colors: the algorithmic landscape of document retrieval on sequences
• Stronger Lempel-Ziv based compressed text indexing
• Succinct Trees in Practice
• Succinct data structures for flexible text retrieval systems
• Succinct indexable dictionaries with applications to encoding \(k\)-ary trees, prefix sums and multisets
• Succinct representation of balanced parentheses and static trees
• Suffix Arrays: A New Method for On-Line String Searches
• Top-\(k\) document retrieval in optimal time and linear space
• Top-\(k\) ranked document search in general text databases

Cited in

(7)

• Unique-order interpolative coding for fast querying and space-efficient indexing in information retrieval systems
• Space-Efficient Algorithms for Document Retrieval
• Inverted file compression through document identifier reassignment.
• A linear lower bound on index size for text retrieval
• FLPI: an optimal algorithm for document indexing based on LPI
• Improved compressed indexes for full-text document retrieval
• Sensitivity of string compressors and repetitiveness measures

Describes a project that uses

Uses Software

• Wumpus

This page was built for publication: Lempel-Ziv compressed structures for document retrieval

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