Ordered Pattern Matching: Towards Full-Text Retrieval
Wing-Kai Hon, Rahul Shah, Jeffrey Scott Vitter · Purdue e-Pubs (Purdue University System) · 2006
A typical query in Information Retrieval consists of multiple keywords, and the target is to retrieve matching documents. Various selection heuristics and ranking criteria are based on the proximity of keywords. For this purpose, it helps if the positions of the keywords in the document are listed in sorted order. For traditional documents consisting of lists of words, existing data structures like inverted indexes serve this purpose well. In this paper, we extend the study to full-text searching where each document is a single string of characters; this problem is well motivated in biological sequence mining. A key building block for such a functionality is a set of queries which can perform pattern matching with constraints on text positions. Let T[O..n 11 be the text. We preprocess this text and build a data structure to answer the following queries efficiently: (1) Given a pattern P , a position p and a rank k, output the position of the kth (in text order) occurrence of P in Tlp..n 11, and (2) Given a pattern P, and positions i and j , report (or count) all occurrences of P in T[i.. j]. Then, we show how to use these queries to solve various problems including document retrieval, proximity searching and aligned pattern matching. One point to notice is that: Each of the above queries can also be considered as a two-dimensional range query, and there are existing geometric data structures with good query performance. Nevertheless, the design of our data structure follows an alternative approach, which is based on augmenting a binary search tree with bit dictionaries.