View PDF HTML (experimental)

Abstract:Providing \textit{structured} information to large language models (LLMs) improves multi-step reasoning and factual grounding, and recent retrieval-augmented generation (RAG) systems therefore reconstruct structure from retrieved text on every query. When the corpus is \emph{already} structured --- as in JSON Lines (JSONL), a popular format for LLM prompts, chemical compounds, and geospatial records --- this per-query rebuilding can be replaced by direct \emph{structural retrieval}. The core primitive is \textit{substructure search}: finding all JSON objects in a collection that contain a given query pattern. Existing approaches index each document separately, so both index space and query time grow with the total collection size; XML-based engines add conversion overhead and semantic mismatches. We propose \textbf{jXBW}, a compressed index for fast substructure search over JSONL, combining three innovations: (i) a merged tree representation that consolidates repeated structures across objects, (ii) a succinct tree index based on the eXtended Burrows--Wheeler Transform (XBW), and (iii) a newly developed three-phase substructure search algorithm that runs on this index. Together they achieve \textbf{query-dependent complexity}: \chgb{the search avoids a full scan of the collection and is candidate- and output-sensitive}, in compressed space. Experiments on seven real-world datasets, including PubChem ($10^6$ compounds) and OpenStreetMap ($6.6 \times 10^6$ objects), show that jXBW outperforms the strongest tree-based baseline by $\mathbf{16\times}$ on the smallest dataset and by up to $\mathbf{2{,}800\times}$ on the largest, and is more than $\mathbf{2 \times 10^6\times}$ faster than the XQuery engine Saxon. jXBW thus brings structural retrieval over million-record JSONL collections into the sub-millisecond range.

Submission history

From: Yasuo Tabei [view email]
[v1] Mon, 18 Aug 2025 00:14:24 UTC (321 KB)
[v2] Thu, 18 Sep 2025 09:46:04 UTC (324 KB)
[v3] Sun, 7 Jun 2026 16:31:47 UTC (1,291 KB)
[v4] Fri, 21 Aug 2026 09:18:38 UTC (1,294 KB)