Ranked document retrieval for multiple patterns

DOI10.1016/J.TCS.2018.06.029MaRDI QIDQ1784746zbMATH OpenOpenAlexWikidataFDO

Authors Sudip Biswas, Arnab Ganguly, Rahul Shah, Sharma V. Thankachan

Publication date 27 September 2018

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2018.06.029

zbMATH Keywords

suffix treesuffix arraysuccinct encodingcompressed suffix arrayweighted ancestor query

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Data structures (68P05)

Recommendations

• Ranked document retrieval with forbidden pattern
• Forbidden Extension Queries
• Forbidden patterns
• Top-\(k\) document retrieval in optimal time and linear space
• Top-\(k\) document retrieval in compact space and near-optimal time

Cites work

• scientific article; zbMATH DE number 2119724 (Why is no real title available?)
• Algorithms on Strings, Trees and Sequences
• Alphabet-independent compressed text indexing
• Bottom-\(k\) document retrieval
• Compressed representations of sequences and full-text indexes
• Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract)
• Data structure lower bounds for document indexing problems
• Document listing for queries with excluded pattern
• Efficient Storage and Retrieval by Content and Address of Static Files
• Fast set intersection and two-patterns matching
• Forbidden Extension Queries
• Forbidden patterns
• Fully-functional succinct trees
• Higher lower bounds from the 3SUM conjecture
• Indexing compressed text
• Introduction to algorithms
• Linear-space data structures for range frequency queries on arrays and trees
• New space/time tradeoffs for top-\(k\) document retrieval on sequences
• On Hardness of Several String Indexing Problems
• Optimal static range reporting in one dimension
• Rank/select operations on large alphabets
• Ranked document retrieval with forbidden pattern
• Space-Efficient Framework for Top-k String Retrieval Problems
• Space-efficient frameworks for top-\(k\) string retrieval
• Spaces, trees, and colors: the algorithmic landscape of document retrieval on sequences
• Succinct indexes for reporting discriminating and generic words
• Top-\(k\) document retrieval in external memory
• Top-\(k\) document retrieval in optimal time and linear space
• Top-\(k\) term-proximity in succinct space
• Weighted ancestors in suffix trees

Cited in

(13)

• A framework for designing space-efficient dictionaries for parameterized and order-preserving matching
• On hardness of several string indexing problems
• Top-\(k\) ranked document search in general text databases
• Cross-document pattern matching
• Ranked Document Retrieval in External Memory
• Ranked document retrieval with forbidden pattern
• String indexing for top-\(k\) close consecutive occurrences
• Ranked document selection
• Forbidden patterns
• Document listing for queries with excluded pattern
• Indexes for document retrieval with relevance
• Spaces, trees, and colors: the algorithmic landscape of document retrieval on sequences
• Gapped indexing for consecutive occurrences

This page was built for publication: Ranked document retrieval for multiple patterns

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