論文の概要: jXBW: Fast Substructure Search for Large-Scale JSONL Datasets with LLM Applications

• arxiv url: http://arxiv.org/abs/2508.12536v2
• Date: Thu, 18 Sep 2025 09:46:04 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-19 15:20:15.327478
• Title: jXBW: Fast Substructure Search for Large-Scale JSONL Datasets with LLM Applications
• Title（参考訳）: jXBW: LLMアプリケーションによる大規模JSONLデータセットの高速サブ構造探索
• Authors: Yasuo Tabei,
• Abstract要約: 主要な操作はサブストラクチャ検索であり、クエリパターンを含むすべてのオブジェクトを識別する。 既存の方法は非効率である: 木マッチング、簡潔な表現は空間を節約するが、探索を加速しない。 本稿では,XMLL 上の効率的な部分構造探索のための圧縮インデックス jXBW を提案する。
• 参考スコア（独自算出の注目度）: 0.033842793760651545
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: JSON Lines (JSONL) is widely used for managing large collections of semi-structured data, ranging from large language model (LLM) prompts to chemical compound records and geospatial datasets. A key operation is substructure search, which identifies all JSON objects containing a query pattern. This task underpins applications such as drug discovery (querying compounds for functional groups), prompt engineering (extracting prompts with schema fragments), and geospatial analytics (finding entities with nested attributes). However, existing methods are inefficient: traversal requires exhaustive tree matching, succinct JSON representations save space but do not accelerate search, and XML-based approaches incur conversion overhead and semantic mismatches. We present jXBW, a compressed index for efficient substructure search over JSONL. jXBW introduces three innovations: (i) a merged tree representation that consolidates repeated structures, (ii) a succinct tree index based on the eXtended Burrows--Wheeler Transform (XBW), and (iii) a three-phase algorithm for substructure search. These enable query-dependent complexity, where cost depends on query characteristics rather than dataset size, while retaining succinct space. This resolves a key bottleneck in retrieval-augmented generation (RAG) systems requiring structure-aware retrieval. Experiments on seven real datasets, including PubChem (1M compounds) and OSM geospatial data (6.6M objects), achieve up to 4,700$\times$ speedup over tree-based methods and over $6\times 10^6$ speedup relative to XML-based approaches. jXBW makes JSONL substructure search practical for the first time, opening opportunities for large-scale LLM-based analytics.
• Abstract（参考訳）: JSONL(JSON Lines)は、大規模言語モデル(LLM)プロンプトから化学複合記録や地理空間データセットまで、半構造化データの大規模なコレクション管理に広く使用されている。 重要な操作はサブストラクチャ検索であり、クエリパターンを含むすべてのJSONオブジェクトを識別する。 このタスクは、薬物発見(官能基をクエリする化合物)、プロンプトエンジニアリング(スキーマフラグメントでプロンプトを抽出する)、地理空間分析(ネスト属性を持つファイリングエンティティ)などの応用を支える。 しかし、既存のメソッドは非効率である: トラバーサルは網羅的なツリーマッチング、簡潔なJSON表現はスペースを節約するが検索を加速しない、XMLベースのアプローチは変換オーバーヘッドとセマンティックミスマッチを発生させる。 本稿では,JSONL 上の効率的な部分構造探索のための圧縮インデックス jXBW を提案する。 jXBWは3つのイノベーションを紹介します。 (i)繰り返し構造を集約する統合木表現 (ii)eXtended Burrowsに基づく簡潔な木指数-Wheeler Transform(XBW) 三) 部分構造探索のための三相アルゴリズム。 コストはデータセットのサイズよりもクエリ特性に依存するが、簡潔なスペースは保持する。 これにより、構造認識検索を必要とする検索拡張生成(RAG)システムにおいて、重要なボトルネックが解決される。 PubChem (1Mの化合物)やOSM地理空間データ (6.6Mのオブジェクト)を含む7つの実際のデータセットの実験では、ツリーベースのメソッドよりも最大4,700$\times$のスピードアップ、XMLベースのアプローチと比較して6.6$以上のスピードアップを実現している。 jXBWはJSONLサブストラクチャ検索を初めて実践し、大規模LLMベースの分析の機会を開く。

関連論文リスト

• ReTreever: Tree-based Coarse-to-Fine Representations for Retrieval [64.44265315244579]
  そこで本研究では,様々なレベルで参照文書を整理し,表現するためのツリーベース手法を提案する。 我々の手法はReTreeverと呼ばれ、クエリと参照ドキュメントが同様のツリーブランチに割り当てられるように、バイナリツリーの内部ノード毎のルーティング関数を共同で学習する。 我々の評価では、ReTreeverは一般的に完全な表現精度を保っている。
  論文  参考訳（メタデータ） (2025-02-11T21:35:13Z)
• Learning Tree-Structured Composition of Data Augmentation [16.435641358351976]
  そこで本研究では,$k$変換の2進木構造合成を探索するアルゴリズムを提案する。 我々のアルゴリズムはランタイムの複雑さを$O(2d k)$で達成し、$O(kd)$よりもはるかに高速である。
  論文  参考訳（メタデータ） (2024-08-26T16:04:13Z)
• LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
  本研究では,動的ノード選択とノードレベルの探索予算を備えた新しいガイド付き木探索アルゴリズムを提案する。 GSM8KおよびTabMWPデータセットを用いて行った実験により,本手法はベースライン法に比べて計算コストが大幅に低いことを示した。
  論文  参考訳（メタデータ） (2024-06-29T05:14:04Z)
• scTree: Discovering Cellular Hierarchies in the Presence of Batch Effects in scRNA-seq Data [12.01555110624794]
  scTreeは、ツリー構造データ表現を同時に学習しながら、バッチ効果を補正する。 scTreeがデータの基礎となるクラスタを発見できる7つのデータセットを実証的に示す。
  論文  参考訳（メタデータ） (2024-06-27T16:16:55Z)
• Hierarchical clustering with dot products recovers hidden tree structure [53.68551192799585]
  本稿では,階層構造の回復に着目した凝集クラスタリングアルゴリズムの新しい視点を提案する。 クラスタを最大平均点積でマージし、例えば最小距離やクラスタ内分散でマージしないような、標準的なアルゴリズムの単純な変種を推奨する。 このアルゴリズムにより得られた木は、汎用確率的グラフィカルモデルの下で、データ中の生成的階層構造をボナフェイド推定することを示した。
  論文  参考訳（メタデータ） (2023-05-24T11:05:12Z)
• Tree Learning: Optimal Algorithms and Sample Complexity [10.638365461509]
  任意の分布から抽出したラベル付きサンプルから,データの階層木表現を学習する問題について検討する。 本稿では,この問題に対する最適なサンプル境界を,学習やオンライン学習など,いくつかの学習環境において提示する。
  論文  参考訳（メタデータ） (2023-02-09T08:35:17Z)
• On the Power of Learning-Augmented Search Trees [7.325724756104182]
  本稿では,Treapsを用いた学習強化二分探索木(BST)について,慎重に設計した優先順位で検討する。 その結果、各項目の深さが予測重量$w_x$によって決定される単純な探索木となる。
  論文  参考訳（メタデータ） (2022-11-16T22:50:40Z)
• Exact and Approximate Hierarchical Clustering Using A* [51.187990314731344]
  クラスタリングのA*探索に基づく新しいアプローチを紹介します。 A*と新しいエンフォレリスデータ構造を組み合わせることで、禁止的に大きな検索空間を克服します。 実験により,本手法は粒子物理利用事例や他のクラスタリングベンチマークにおいて,ベースラインよりもかなり高品質な結果が得られることを示した。
  論文  参考訳（メタデータ） (2021-04-14T18:15:27Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。