Ranked document retrieval for multiple patterns (Q1784746)

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.