論文の概要: Exact Trajectory Similarity Search With N-tree: An Efficient Metric Index for kNN and Range Queries

• arxiv url: http://arxiv.org/abs/2408.07650v1
• Date: Wed, 14 Aug 2024 16:21:28 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-10 17:51:41.076339
• Title: Exact Trajectory Similarity Search With N-tree: An Efficient Metric Index for kNN and Range Queries
• Title（参考訳）: N-treeを用いた排他的類似性探索:kNNおよびレンジクエリのための効率的なメトリックインデックス
• Authors: Ralf Hartmut Güting, Suvam Kumar Das, Fabio Valdés, Suprio Ray,
• Abstract要約: 類似検索は、あるクエリオブジェクトに類似したオブジェクトのコレクションを見つける問題である。 軌道は、車両、動物、公共交通機関、または人体の一部といった移動体の運動を記録している。 本稿では,距離関数DistanceAvgを提案する。
• 参考スコア（独自算出の注目度）: 2.8059675184983424
• License:
• Abstract: Similarity search is the problem of finding in a collection of objects those that are similar to a given query object. It is a fundamental problem in modern applications and the objects considered may be as diverse as locations in space, text documents, images, twitter messages, or trajectories of moving objects. In this paper we are motivated by the latter application. Trajectories are recorded movements of mobile objects such as vehicles, animals, public transportation, or parts of the human body. We propose a novel distance function called DistanceAvg to capture the similarity of such movements. To be practical, it is necessary to provide indexing for this distance measure. Fortunately we do not need to start from scratch. A generic and unifying approach is metric space, which organizes the set of objects solely by a distance (similarity) function with certain natural properties. Our function DistanceAvg is a metric. Although metric indexes have been studied for decades and many such structures are available, they do not offer the best performance with trajectories. In this paper we propose a new design, which outperforms the best existing indexes for kNN queries and is equally good for range queries. It is especially suitable for expensive distance functions as they occur in trajectory similarity search. In many applications, kNN queries are more practical than range queries as it may be difficult to determine an appropriate search radius. Our index provides exact result sets for the given distance function.
• Abstract（参考訳）: 類似検索は、あるクエリオブジェクトに類似したオブジェクトのコレクションを見つける問題である。 現代のアプリケーションでは基本的な問題であり、考慮されているオブジェクトは、空間、テキスト文書、画像、twitterメッセージ、移動中のオブジェクトの軌跡の場所と同じくらい多様である可能性がある。 本稿では,後者の応用を動機とする。 軌道は、車両、動物、公共交通機関、または人体の一部といった移動体の運動を記録している。 本稿では,距離関数DistanceAvgを提案する。 現実には、この距離測定のための指標を提供する必要がある。 幸いなことに、ゼロから始める必要はありません。 一般的かつ統一的なアプローチは距離空間であり、ある性質を持つ距離(類似性)関数によってのみ対象の集合を整理する。 我々の関数 DistanceAvg はメトリックです。 計量指標は何十年も研究されてきたが、そのような構造の多くは利用できるが、軌道上での最高の性能は提供していない。 そこで本研究では,kNNクエリにおいて,既存の索引の最大性能を向上し,レンジクエリに等しく優れた新しい設計法を提案する。 軌道類似性探索において発生する高価な距離関数には特に適している。 多くのアプリケーションでは、適切な探索半径を決定するのが難しいため、kNNクエリはレンジクエリよりも実用的である。 我々の指数は与えられた距離関数に対して正確な結果セットを提供する。

関連論文リスト

• Vector search with small radiuses [10.880913075221361]
  本稿では,ベクトル検索結果に応じて難しい決定を下す必要がある場合に着目する。 本研究では,クエリー・ツー・ベクター距離に基づいて,範囲探索結果の値を厳密にモデル化できることを示す。 これにより、範囲探索の指標 RSM が得られ、これは原則的であり、エンドツーエンドの評価を行なわずに計算が容易である。
  論文  参考訳（メタデータ） (2024-03-16T00:34:25Z)
• Group Testing for Accurate and Efficient Range-Based Near Neighbor Search for Plagiarism Detection [2.3814052021083354]
  本研究は, 近接探索問題に対する適応型群検定フレームワークを提案する。 本研究では,データベース内の各項目を問合せ点の隣人あるいは非隣人として,余剰距離閾値に基づいて効率よくマークする。 本研究では,ソフトマックスに基づく特徴量を用いて,完全探索よりも10倍以上の高速化を実現し,精度を損なわないことを示す。
  論文  参考訳（メタデータ） (2023-11-05T06:12:03Z)
• Robust Multi-Object Tracking by Marginal Inference [92.48078680697311]
  ビデオにおける多目的追跡は、隣接するフレーム内のオブジェクト間の1対1の割り当てに関する根本的な問題を解決する必要がある。 本稿では,各オブジェクトの限界確率をリアルタイムに計算する効率的な手法を提案する。 MOT17とMOT20ベンチマークで競合する結果を得る。
  論文  参考訳（メタデータ） (2022-08-07T14:04:45Z)
• A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
  ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。 このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。 我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-03-28T21:34:16Z)
• Embracing Structure in Data for Billion-Scale Semantic Product Search [14.962039276966319]
  我々は、数十億の規模でダイアドニューラル埋め込みモデルを訓練し、展開するための原則的アプローチを提案する。 実世界のデータセットの自然な構造を活用することで、両方の課題に効率的に対処できることが示される。
  論文  参考訳（メタデータ） (2021-10-12T16:14:13Z)
• BR-NS: an Archive-less Approach to Novelty Search [70.13948372218849]
  行動認識に基づく新規性探索(BR-NS)という,新規性推定の代替手法について議論する。 BR-NSはアーカイブを必要とせず、行動空間で定義できるメトリクスを前提にせず、近隣の検索に依存しません。 我々は、その実現可能性とダイナミクス、および時間複雑性の観点からアーカイブベースのnsよりも潜在的に有利な点について洞察を得るために実験を行う。
  論文  参考訳（メタデータ） (2021-04-08T17:31:34Z)
• Neural Architecture Search From Fr\'echet Task Distance [50.9995960884133]
  与えられたベースラインタスクのセット内の対象タスクと各タスクの間の距離を、ターゲットタスクのニューラルネットワークアーキテクチャ検索スペースを減らすためにどのように使用できるかを示す。 タスク固有のアーキテクチャに対する検索空間の複雑さの低減は、このサイド情報を用いることなく完全な検索を行う代わりに、類似したタスクのために最適化されたアーキテクチャ上に構築することで達成される。
  論文  参考訳（メタデータ） (2021-03-23T20:43:31Z)
• Towards Improving the Consistency, Efficiency, and Flexibility of Differentiable Neural Architecture Search [84.4140192638394]
  最も微分可能なニューラルアーキテクチャ探索法は、探索用のスーパーネットを構築し、そのサブグラフとしてターゲットネットを導出する。 本稿では,エンジンセルとトランジットセルからなるEnTranNASを紹介する。 また,検索処理の高速化を図るため,メモリや計算コストの削減も図っている。
  論文  参考訳（メタデータ） (2021-01-27T12:16:47Z)
• 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)

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

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