論文の概要: GP-Tree: An in-memory spatial index combining adaptive grid cells with a prefix tree for efficient spatial querying

• arxiv url: http://arxiv.org/abs/2603.07517v1
• Date: Sun, 08 Mar 2026 07:59:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-10 15:13:14.707154
• Title: GP-Tree: An in-memory spatial index combining adaptive grid cells with a prefix tree for efficient spatial querying
• Title（参考訳）: GP-Tree:適応格子セルとプレフィックスツリーを組み合わせたメモリ内空間インデックスによる効率的な空間探索
• Authors: Xiangyang Yang, Xuefeng Guan, Lanxue Dang, Yi Xie, Qingyang Xu, Huayi Wu, Jiayao Wang,
• Abstract要約: GP-Treeは、空間オブジェクトの近似グリッドセルをプレフィックスツリー構造に整理する、きめ細かい空間インデックスである。 木伐採やノード最適化などの最適化手法を導入し,探索経路とメモリ消費を削減する。 実世界のデータセットの実験では、GP-Treeは従来の空間指標よりも大幅に優れていた。
• 参考スコア（独自算出の注目度）: 5.732286906919534
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Efficient spatial indexing is crucial for processing large-scale spatial data. Traditional spatial indexes, such as STR-Tree and Quad-Tree, organize spatial objects based on coarse approximations, such as their minimum bounding rectangles (MBRs). However, this coarse representation is inadequate for complex spatial objects (e.g., district boundaries and trajectories), limiting filtering accuracy and query performance of spatial indexes. To address these limitations, we propose GP-Tree, a fine-grained spatial index that organizes approximated grid cells of spatial objects into a prefix tree structure. GP-Tree enhances filtering ability by replacing coarse MBRs with fine-grained cell-based approximations of spatial objects. The prefix tree structure optimizes data organization and query efficiency by leveraging the shared prefixes in the hierarchical grid cell encodings between parent and child cells. Additionally, we introduce optimization strategies, including tree pruning and node optimization, to reduce search paths and memory consumption, further enhancing GP-Tree's performance. Finally, we implement a variety of spatial query operations on GP-Tree, including range queries, distance queries, and k-nearest neighbor queries. Extensive experiments on real-world datasets demonstrate that GP-Tree significantly outperforms traditional spatial indexes, achieving up to an order-of-magnitude improvement in query efficiency.
• Abstract（参考訳）: 大規模空間データの処理には,効率的な空間インデックス作成が不可欠である。 STR-Tree や Quad-Tree のような伝統的な空間指標は、その最小有界矩形(MBR)のような粗い近似に基づいて空間オブジェクトを整理する。 しかし、この粗い表現は複雑な空間オブジェクト(例えば、地区境界や軌道)には不十分であり、空間インデックスのフィルタリング精度とクエリ性能を制限している。 これらの制約に対処するために,空間オブジェクトの近似格子セルをプレフィックスツリー構造に整理した,きめ細かな空間指標GP-Treeを提案する。 GP-Treeは粗いMBRを空間オブジェクトの微細なセルベース近似に置き換えることでフィルタリング能力を向上させる。 プレフィックスツリー構造は、親と子間の階層的なグリッドセルエンコーディングにおける共有プレフィックスを活用することにより、データ構成とクエリ効率を最適化する。 さらに,木伐採やノード最適化などの最適化手法を導入し,探索経路とメモリ消費を削減し,GP-Treeの性能をさらに向上させる。 最後に,範囲クエリ,距離クエリ,k-nearest 近傍クエリなど,GP-Tree 上での様々な空間クエリ処理を実装した。 実世界のデータセットに対する大規模な実験により、GP-Treeは従来の空間指標を大幅に上回り、クエリ効率のオーダー・オブ・マグニチュードの改善を達成している。

関連論文リスト

• Divide-Then-Rule: A Cluster-Driven Hierarchical Interpolator for Attribute-Missing Graphs [51.13363550716544]
  ディープグラフクラスタリングは、不完全な属性を持つノードを異なるクラスタに分割することを目的とした教師なしのタスクである。 既存の属性欠落グラフの計算法は、ノード近傍で利用可能な情報の量が異なることを説明できないことが多い。 この問題に対処するために、DTRGC(Divide-Then-Rule Graph Completion)を提案する。
  論文  参考訳（メタデータ） (2025-07-12T03:33:19Z)
• Hierarchical Quantized Diffusion Based Tree Generation Method for Hierarchical Representation and Lineage Analysis [49.00783841494125]
  HDTreeは階層的潜在空間内の木関係を、統一的な階層的コードブックと量子化拡散プロセスを用いてキャプチャする。 HDTreeの有効性は、汎用データセットと単一セルデータセットの比較によって示される。 これらの貢献は階層的な系統解析のための新しいツールを提供し、より正確で効率的な細胞分化経路のモデリングを可能にする。
  論文  参考訳（メタデータ） (2025-06-29T15:19:13Z)
• A Query-Driven Approach to Space-Efficient Range Searching [12.760453906939446]
  クエリのほぼ直線的なサンプルは、クエリ中に訪れたノード数がほぼ最適であるパーティションツリーを構築することができることを示す。 我々は、ノード処理を分類問題として扱い、浅いニューラルネットワークのような高速な分類器を活用して、実験的に効率的なクエリ時間を得ることにより、このアプローチを強化する。 我々のアルゴリズムは,クエリのサンプルに基づいて,セパレータに関連付けられたノードを持つバランスのとれたツリーを構築し,クエリの待ち行列を最小化する。
  論文  参考訳（メタデータ） (2025-02-19T12:01:00Z)
• ReTreever: Tree-based Coarse-to-Fine Representations for Retrieval [64.44265315244579]
  そこで本研究では,様々なレベルで参照文書を整理し,表現するためのツリーベース手法を提案する。 我々の手法はReTreeverと呼ばれ、クエリと参照ドキュメントが同様のツリーブランチに割り当てられるように、バイナリツリーの内部ノード毎のルーティング関数を共同で学習する。 我々の評価では、ReTreeverは一般的に完全な表現精度を保っている。
  論文  参考訳（メタデータ） (2025-02-11T21:35:13Z)
• The "AI+R"-tree: An Instance-optimized R-tree [8.645596995409647]
  本稿では,空間指標の性能向上に機械学習技術を活用することを提案する。 本稿では,Rツリーの探索操作を多ラベル分類タスクに変換するAIツリーを提案する。 実際のデータセットの実験では、"AI+R"ツリーが従来のRツリーのクエリ性能を最大500%向上できることが示されている。
  論文  参考訳（メタデータ） (2022-07-01T17:08:17Z)
• Exact and Approximate Hierarchical Clustering Using A* [51.187990314731344]
  クラスタリングのA*探索に基づく新しいアプローチを紹介します。 A*と新しいエンフォレリスデータ構造を組み合わせることで、禁止的に大きな検索空間を克服します。 実験により,本手法は粒子物理利用事例や他のクラスタリングベンチマークにおいて,ベースラインよりもかなり高品質な結果が得られることを示した。
  論文  参考訳（メタデータ） (2021-04-14T18:15:27Z)
• The RLR-Tree: A Reinforcement Learning Based R-Tree for Spatial Data [33.26284196513858]
  B-Treeのような古典的なインデックス構造を機械学習(ML)モデルに置き換えるための学習インデックスが提案されている。 構造やクエリ処理アルゴリズムを変更することなく、従来のR-Treeのクエリ性能を向上させるために、ML技術を使用する根本的に異なる方法を提案します。
  論文  参考訳（メタデータ） (2021-03-08T04:29:58Z)
• The Case for Learned Spatial Indexes [62.88514422115702]
  我々は、空間範囲の問合せに答えるために、最先端の学習した多次元インデックス構造(すなわちFlood)から提案した手法を用いる。 i) パーティション内の機械学習検索は、1次元でフィルタリングを使用する場合の2進探索よりも11.79%速く、39.51%高速であることを示す。 また、2次元でフィルタする最も近い競合相手の1.23倍から1.83倍の速さで機械学習インデックスを精査する。
  論文  参考訳（メタデータ） (2020-08-24T12:09:55Z)
• A Practical Index Structure Supporting Fr\'echet Proximity Queries Among Trajectories [1.9335262420787858]
  我々は、計算コストの高いメトリクスの下で、レンジと近隣クエリに$k$のスケーラブルなアプローチを提案する。 計量指標のクラスタリングに基づいて,軌跡数に線形な木構造を求める。 本研究では,多種多様な合成および実世界のデータセットに関する広範な実験により,本手法の有効性と有効性について分析する。
  論文  参考訳（メタデータ） (2020-05-28T04:12:43Z)

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

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