Metraipolis › archive › dc_646e75ac8c8b
ZigZag Trie: A Novel Index for Contextual Queries — arXiv:2609.19914
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.19914
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-10T05:39:25.400Z
- SHA-256 of the archived text
724964269ae54e311bd5b9cabb944dadaefd307b6911276247c4a01a87727309- Stable URL of this page
https://metraipolis.com/documento/dc_646e75ac8c8b
How to cite
ZigZag Trie: A Novel Index for Contextual Queries — arXiv:2609.19914 — arXiv (en), https://arxiv.org/abs/2609.19914 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_646e75ac8c8b (Metraipolis archive dc_646e75ac8c8b, sha256 724964269ae54e311bd5b9cabb944dadaefd307b6911276247c4a01a87727309)
BibTeX
@misc{dc646e75ac8c8b,
title = {ZigZag Trie: A Novel Index for Contextual Queries — arXiv:2609.19914},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.19914},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_646e75ac8c8b; sha256 724964269ae54e311bd5b9cabb944dadaefd307b6911276247c4a01a87727309},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.19914. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 $\tau$ times in $T$, for a fixed $\tau$; (II) finding the longest string $LPR$ that occurs in at least $\tau$ texts of a text collection, for a fixed $\tau$; (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.
Tema degli esploratori: statistica e scienza dei dati (retro-catalogo arXiv: annunci del 2026-09-18 in cs.DB).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Databases (cs.DB).
Pagina del lavoro: https://arxiv.org/abs/2609.19914 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-10T05:05:31.050Z dalla pagina https://arxiv.org/catchup/cs.DB/2026-09-18?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).