Ranked document retrieval for multiple patterns
type: Item
instance of: scholarly article
title: Ranked document retrieval for multiple patterns
zbMATH Open document ID: 1408.68052
author: Sudip Biswas
author: Arnab Ganguly
author: Rahul Shah
author: Sharma V. Thankachan
published in: Theoretical Computer Science
publication date: 2018-09-27T00:00:00Z
review text: Index data structures for full-text search are very important in information retrieval with applications ranging from web search to various bioinformatics settings. One of the most important questions is to find the most relevant documents based on multiple patterns. The state-of-the-art practical techniques (e.g., inverted indices) do not give good performance guarantees in the worst case. This paper represents a step in closing this gap between theory and practice by giving improved time/space bounds for this problem. The techniques build heavily on known advanced data structures in stringology, in particular suffix trees and least-common-ancestor data structures.
reviewed by: Peter Sanders
Mathematics Subject Classification ID: 68P20
Mathematics Subject Classification ID: 68P05
zbMATH DE Number: 6944703
zbMATH Keywords: suffix tree
zbMATH Keywords: suffix array
zbMATH Keywords: weighted ancestor query
zbMATH Keywords: compressed suffix array
zbMATH Keywords: succinct encoding
MaRDI profile type: Publication
full work available at URL: j.tcs.2018.06.029
OpenAlex ID: W2809416223
cites work: Q4598234
cites work: Optimal static range reporting in one dimension
cites work: Alphabet-Independent Compressed Text Indexing
cites work: Forbidden Extension Queries
cites work: Ranked Document Retrieval with Forbidden Pattern
cites work: Succinct Indexes for Reporting Discriminating and Generic Words
cites work: Fast set intersection and two-patterns matching
cites work: Introduction to algorithms
cites work: Linear-Space Data Structures for Range Frequency Queries on Arrays and Trees
cites work: Efficient Storage and Retrieval by Content and Address of Static Files
cites work: Indexing compressed text
cites work: Forbidden Patterns
cites work: Weighted Ancestors in Suffix Trees
cites work: Rank/select operations on large alphabets
cites work: Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract)
cites work: Algorithms on Strings, Trees and Sequences
cites work: Document Listing for Queries with Excluded Pattern
cites work: Space-Efficient Frameworks for Top- k String Retrieval
cites work: Space-Efficient Framework for Top-k String Retrieval Problems
cites work: Higher Lower Bounds from the 3SUM Conjecture
cites work: On Hardness of Several String Indexing Problems
cites work: Top-$$k$$ Term-Proximity in Succinct Space
cites work: Q4828998
cites work: Spaces, Trees, and Colors
cites work: Compressed representations of sequences and full-text indexes
cites work: Q5743458
cites work: New space/time tradeoffs for top-\(k\) document retrieval on sequences
cites work: Bottom-\(k\) document retrieval
cites work: Q5417613
cites work: Top-k Document Retrieval in External Memory
Wikidata QID: Q129650522
DOI: 10.1016/J.TCS.2018.06.029
description: scientific article; zbMATH DE number 6944703