Thumbnail
Access Restriction
Subscribed

Author Hon, Wing-Kai ♦ Shah, Rahul ♦ Thankachan, Sharma V ♦ Vitter, Jeffrey Scott
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2014
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword String matching ♦ Document retrieval ♦ Top-k queries
Abstract The inverted index is the backbone of modern web search engines. For each word in a collection of web documents, the index records the list of documents where this word occurs. Given a set of query words, the job of a search engine is to output a ranked list of the most relevant documents containing the query. However, if the query consists of an arbitrary string—which can be a partial word, multiword phrase, or more generally any sequence of characters—then word boundaries are no longer relevant and we need a different approach. In string retrieval settings, we are given a set $D={d_{1},$ $d_{2},d_{3},$ …, $d_{D}}$ of $\textit{D}$ strings with $\textit{n}$ characters in total taken from an alphabet set Σ = [σ], and the task of the search engine, for a given query pattern $\textit{P}$ of length $\textit{p},$ is to report the “most relevant” strings in $\textit{D}$ containing $\textit{P}.$ The query may also consist of two or more patterns. The notion of relevance can be captured by a function $score(P,d_{r}),$ which indicates how relevant document $d_{r}$ is to the pattern $\textit{P}.$ Some example score functions are the $\textit{frequency}$ of pattern occurrences, $\textit{proximity}$ between pattern occurrences, or pattern-independent $\textit{PageRank}$ of the document. The first formal framework to study such kinds of retrieval problems was given by Muthukrishnan [SODA 2002]. He considered two metrics for relevance: frequency and proximity. He took a threshold-based approach on these metrics and gave data structures that use $\textit{O}(\textit{n}$ log $\textit{n})$ words of space. We study this problem in a somewhat more natural $top-\textit{k}$ framework. Here, $\textit{k}$ is a part of the query, and the top $\textit{k}$ most relevant (highest-scoring) documents are to be reported in sorted order of score. We present the first linear-space framework (i.e., using $\textit{O}(\textit{n})$ words of space) that is capable of handling arbitrary score functions with near-optimal $\textit{O}(\textit{p}$ + $\textit{k}log$ $\textit{k})$ query time. The query time can be made optimal $\textit{O}(\textit{p}+\textit{k})$ if sorted order is not necessary. Further, we derive compact space and succinct space indexes (for some specific score functions). This space compression comes at the cost of higher query time. At last, we extend our framework to handle the case of multiple patterns. Apart from providing a robust framework, our results also improve many earlier results in index space or query time or both.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2014-04-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 61
Issue Number 2
Page Count 36
Starting Page 1
Ending Page 36


Open content in new tab

   Open content in new tab
Source: ACM Digital Library