jXBW让百万级结构化JSON数据检索快到毫秒级，无需重复解析。
jXBW: A Compressed Index Enabling Structure-Aware JSONL Retrieval for Structured RAG
- 用合并树+压缩索引技术，减少冗余存储并加速查询
- 在最大数据集上比最强基线快2800倍，比Saxon快200万倍
- 适合处理化学、地理等百万级结构化数据的高效检索场景
为大语言模型提供结构化信息可提升多步推理与事实准确性。现有检索增强生成系统需在每次查询时从文本重建结构，而当数据本身已结构化（如JSONL格式）时，可直接进行结构化检索。核心操作是子结构搜索：在集合中找出包含给定查询模式的所有JSON对象。现有方法对每条文档独立建索引，导致索引空间和查询时间随数据量增长；基于XML的引擎存在转换开销和语义错配问题。本文提出jXBW，一种用于快速子结构搜索的压缩索引，融合三项创新：(i) 合并树表示，整合跨对象重复结构；(ii) 基于扩展Burrows-Wheeler变换（XBW）的紧凑树索引；(iii) 新设计的三阶段子结构搜索算法。三者结合实现查询相关复杂度：搜索不扫描全集且与候选结果数量敏感，在压缩空间内完成。在七个真实数据集上的实验表明，包括PubChem（10^6种化合物）和OpenStreetMap（6.6×10^6个对象），jXBW比最强的树基基线在最小数据集上快16倍，在最大数据集上快达2,800倍，且比XQuery引擎Saxon快2×10^6倍以上。jXBW将百万级JSONL结构化检索推入亚毫秒级别。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。