Zigzag trie indexes string contexts for faster text queries
ZigZag Trie: A Novel Index for Contextual Queries
Data Structures and AlgorithmsDatabases
Summary
Searching for all the ways a word or phrase appears with specific surroundings in a huge text is very slow with current tools. The authors created a new structure called the ZigZag Trie that groups these surroundings efficiently so we can find them much faster. They built special indexes on top of this structure to answer different types of context-based questions quickly and using reasonable computing resources. Tests on enormous text datasets show their approach is much faster than previous methods while staying compact.
What this means in practice
- •For text database engineers: Speed up queries that require retrieving phrases with specific contexts in large text collections using compact and fast indexes based on the ZigZag Trie.
- •For search engine developers: Improve search features that need to find patterns together with their surrounding words efficiently in massive text datasets.
Authors
Ling Li, Daniel Gibney, Sharma V. Thankachan, Rahul Shah, Grigorios Loukides, Solon P. Pissis
Abstract
There is increasing interest in queries about the context of a string $P$ in a longer text $T$, i.e., the set of all string pairs $(L,R)$, with $|L|=|R|=q$, for a given $q$, such that the string $LPR$ occurs in $T$. Such contextual queries are important in several domains but are challenging to answer efficiently. This is because the length of $T$ in applications is massive and existing indexes do not directly encode the context of a given $P$, which is key for answering retrieval queries efficiently. Our work introduces the ZigZag Trie (ZZT), a new full-text index to specifically address these challenges. This index reorganizes the text so that, for any $P$, all possible strings $L$ and $R$ growing symmetrically around $P$ are grouped into a common subtree of the index, allowing their efficient retrieval. We show how to construct the ZZT of $T$, which has size $\mathcal{O}(n)$ where $n=|T|$, in $\mathcal{O}(n\log n)$ time and $\mathcal{O}(n)$ space. On top of ZZT, we design specialized indexes that, for a query pattern $P$, answer four new types of contextual queries: (I) finding the longest string $LPR$ that occurs at least $τ$ times in $T$, for a fixed $τ$; (II) finding the longest string $LPR$ that occurs in at least $τ$ texts of a text collection, for a fixed $τ$; (III) reporting the total number of distinct contexts of $P$ in $T$; and (IV) retrieving, for a given $q$, the $k$ pairs $(L,R)$ of $P$ with the highest scores according to a given scoring function. Our indexes answer queries of type I, II, and III in optimal time, and of type IV in near-optimal time. Moreover, their size, construction space, and construction time are linear or near-linear in $n$, given ZZT. Using real billion-letter datasets, we show that our indexes answer queries orders of magnitude faster than baselines and perform similarly or better in index size and construction space and time.