Space-efficient indexes for forbidden extension queries

DOI10.1016/j.jda.2018.09.001zbMath1486.68051OpenAlexW2897174664MaRDI QIDQ1632508

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

Publication date: 14 December 2018

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

Full work available at URL: https://doi.org/10.1016/j.jda.2018.09.001

zbMATH Keywords

data structuresstring algorithmsdocument retrievalsuffix treestop-k

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Information storage and retrieval of data (68P20) Algorithms on strings (68W32)

Related Items

A framework for designing space-efficient dictionaries for parameterized and order-preserving matching

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fast set intersection and two-patterns matching
• String processing and information retrieval. 17th international symposium, SPIRE 2010, Los Cabos, Mexico, October 11--13, 2010. Proceedings
• Fractional cascading. I: A data structuring technique
• The complexity of selection and ranking in X+Y and matrices with sorted columns
• Trans-dichotomous algorithms for minimum spanning trees and shortest paths
• Forbidden Patterns
• Document Listing for Queries with Excluded Pattern
• Ranked Document Retrieval with Forbidden Pattern
• Top-$$k$$ Term-Proximity in Succinct Space
• Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays
• Space-Efficient Frameworks for Top- k String Retrieval
• Fast Algorithms for Finding Nearest Common Ancestors
• Rank/select operations on large alphabets
• Online Sorted Range Reporting
• Algorithms on Strings, Trees and Sequences
• On Hardness of Several String Indexing Problems
• Spaces, Trees, and Colors
• Forbidden Extension Queries