論文の概要: COL-Trees: Efficient Hierarchical Object Search in Road Networks

• arxiv url: http://arxiv.org/abs/2601.22183v1
• Date: Wed, 28 Jan 2026 10:43:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-02 18:28:14.979414
• Title: COL-Trees: Efficient Hierarchical Object Search in Road Networks
• Title（参考訳）: COL-Trees: 道路網における効率的な階層的物体探索
• Authors: Tenindra Abeywickrama, Muhammad Aamir Cheema, Sabine Storandt,
• Abstract要約: 位置情報ベースのサービスは、特定の場所の近くで関連する関心ポイント(POI)を探索する効率的な方法に大きく依存している。 既存のほとんどの手法は、近くのPOIを1つのエージェントで検索することに焦点を当てているが、これらの検索は他の多くのアプリケーションに変換されない。 我々は,COL-Treesを用いてAkNN,kFN,その他のクエリに効率的に応答するクエリアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 7.363671754306327
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Location-based services rely heavily on efficient methods that search for relevant points-of-interest (POIs) near a given location. A k Nearest Neighbor (kNN) query is one such example that finds the k closest POIs from an agent's location. While most existing techniques focus on retrieving nearby POIs for a single agent, these search heuristics do not translate to many other applications. For example, Aggregate k Nearest Neighbor (AkNN) queries require POIs that are close to multiple agents. k Farthest Neighbor (kFN) queries require POIs that are the antithesis of nearest. Such problems naturally benefit from a hierarchical approach, but existing methods rely on Euclidean-based heuristics, which have diminished effectiveness in graphs such as road networks. We propose a novel data structure, COL-Tree (Compacted Object-Landmark Tree), to address this gap by enabling efficient hierarchical graph traversal using a more accurate landmark-based heuristic. We then present query algorithms that utilize COL-Trees to efficiently answer AkNN, kFN, and other queries. In our experiments on real-world and synthetic datasets, we demonstrate that our techniques significantly outperform existing approaches, achieving up to 4 orders of magnitude improvement. Moreover, this comes at a small pre-processing overhead in both theory and practice.
• Abstract（参考訳）: 位置情報ベースのサービスは、特定の場所の近くで関連する関心ポイント(POI)を探索する効率的な方法に大きく依存している。 k Nearest Neighbor (kNN) クエリは、エージェントの場所から k に近い POI を見つけるような例である。 既存のほとんどの手法は、近くのPOIを1つのエージェントで検索することに焦点を当てているが、これらの探索ヒューリスティックスは、他の多くのアプリケーションに翻訳しない。 例えば、Aggregate k Nearest Neighbor (AkNN)クエリは、複数のエージェントに近いPOIを必要とする。 k Farthest Neighbor (kFN) クエリは、最寄りのアンチテーゼである POI を必要とする。 このような問題は自然に階層的なアプローチの恩恵を受けるが、既存の手法はユークリッドに基づくヒューリスティックに依存しており、道路網のようなグラフの有効性は低下している。 我々は,より正確なランドマークベースのヒューリスティックを用いて,効率的な階層グラフトラバースを実現することにより,このギャップに対処する新しいデータ構造であるCOL-Tree(Compacted Object-Landmark Tree)を提案する。 次に、COL-Treesを用いてAkNN、kFN、その他のクエリに効率よく答えるクエリアルゴリズムを提案する。 実世界のデータセットと合成データセットに関する実験では、我々の技術が既存のアプローチを大幅に上回っており、最大4桁の改善が達成されていることを実証した。 さらに、これは理論と実践の両方において、小さな事前処理のオーバーヘッドが伴います。

関連論文リスト

• Early Exit Strategies for Approximate k-NN Search in Dense Retrieval [10.48678957367324]
  アーリーエグジットのための最先端のA-kNNを構築し,忍耐の概念に基づく教師なし手法を提案する。 我々は,A-kNNの効率を最大5倍の高速化で向上すると同時に,無視可能な効率損失を達成できることを示す。
  論文  参考訳（メタデータ） (2024-08-09T10:17:07Z)
• Group Testing for Accurate and Efficient Range-Based Near Neighbor Search for Plagiarism Detection [2.3814052021083354]
  本研究は, 近接探索問題に対する適応型群検定フレームワークを提案する。 本研究では,データベース内の各項目を問合せ点の隣人あるいは非隣人として,余剰距離閾値に基づいて効率よくマークする。 本研究では,ソフトマックスに基づく特徴量を用いて,完全探索よりも10倍以上の高速化を実現し,精度を損なわないことを示す。
  論文  参考訳（メタデータ） (2023-11-05T06:12:03Z)
• Efficient k-NN Search with Cross-Encoders using Adaptive Multi-Round CUR Decomposition [77.4863142882136]
  クロスエンコーダモデルは、直接k-nearest neighbor(k-NN)サーチには不当に高価である。 本稿では,現実的に重要なトップk近傍の近似誤差を適応的に,反復的に,効率的に最小化するADACURを提案する。
  論文  参考訳（メタデータ） (2023-05-04T17:01:17Z)
• A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graph [51.880164098926166]
  グラフベースのアルゴリズムは、近隣探索(NN-Search)問題において最先端の性能を示す。 グラフベースのNN-Searchアルゴリズムには実践と理論のギャップがある。 低次元および高密度ベクトルに対する ANN-Graph 上の欲求探索による NN-Search の解法を理論的に保証する。
  論文  参考訳（メタデータ） (2023-03-10T21:18:34Z)
• FINGER: Fast Inference for Graph-based Approximate Nearest Neighbor Search [20.928821121591493]
  効率的なグラフ探索を実現するための高速推論手法であるFINGERを提案する。 FINGERは、近傍の残差ベクトルと低ランク基底と分布マッチングとの角度を推定することで距離関数を近似する。 実証的に、FINGERによるHNSWと呼ばれるグラフベースの手法の高速化は、異なるベンチマークデータセット間で既存のグラフベースの手法を20%から60%上回っている。
  論文  参考訳（メタデータ） (2022-06-22T22:30:46Z)
• Learning Query Expansion over the Nearest Neighbor Graph [94.80212602202518]
  グラフクエリ拡張(GQE)が提示され、教師付き方法で学習され、クエリの拡張近傍で集約を実行する。 この技術は既知のベンチマークよりも最先端の結果が得られる。
  論文  参考訳（メタデータ） (2021-12-05T19:48:42Z)
• Exact and Approximate Hierarchical Clustering Using A* [51.187990314731344]
  クラスタリングのA*探索に基づく新しいアプローチを紹介します。 A*と新しいエンフォレリスデータ構造を組み合わせることで、禁止的に大きな検索空間を克服します。 実験により,本手法は粒子物理利用事例や他のクラスタリングベンチマークにおいて,ベースラインよりもかなり高品質な結果が得られることを示した。
  論文  参考訳（メタデータ） (2021-04-14T18:15:27Z)
• BR-NS: an Archive-less Approach to Novelty Search [70.13948372218849]
  行動認識に基づく新規性探索(BR-NS)という,新規性推定の代替手法について議論する。 BR-NSはアーカイブを必要とせず、行動空間で定義できるメトリクスを前提にせず、近隣の検索に依存しません。 我々は、その実現可能性とダイナミクス、および時間複雑性の観点からアーカイブベースのnsよりも潜在的に有利な点について洞察を得るために実験を行う。
  論文  参考訳（メタデータ） (2021-04-08T17:31:34Z)
• A Note on Graph-Based Nearest Neighbor Search [4.38837720322254]
  高いクラスタリング係数は、グラフの最大強連結成分 (scc) に、q の k に近い近傍の大半を配置することを示している。 グラフに基づく探索アルゴリズムは,任意の地点を訪れると最大 SCC を横切ることが保証されている。
  論文  参考訳（メタデータ） (2020-12-21T02:18:05Z)
• Cross-Domain Generalization Through Memorization: A Study of Nearest Neighbors in Neural Duplicate Question Detection [72.01292864036087]
  重複質問検出(DQD)は,コミュニティの効率向上と自動質問応答システムの実現に重要である。 我々は、DQDのクロスドメイン一般化のために、ニューラル表現を活用し、近接する隣人を研究する。 StackExchange、Spring、Quoraの各データセットの異なるクロスドメインシナリオにおいて、このメソッドの堅牢なパフォーマンスを観察します。
  論文  参考訳（メタデータ） (2020-11-22T19:19:33Z)

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

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