論文の概要: A Practical Index Structure Supporting Fr\'echet Proximity Queries Among Trajectories

• arxiv url: http://arxiv.org/abs/2005.13773v1
• Date: Thu, 28 May 2020 04:12:43 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-27 06:03:41.126851
• Title: A Practical Index Structure Supporting Fr\'echet Proximity Queries Among Trajectories
• Title（参考訳）: Fr'echet Proximity Queries をトラジェクトリ間で支援する実用的なインデックス構造
• Authors: Joachim Gudmundsson, Michael Horton, John Pfeifer, Martin P. Seybold
• Abstract要約: 我々は、計算コストの高いメトリクスの下で、レンジと近隣クエリに$k$のスケーラブルなアプローチを提案する。 計量指標のクラスタリングに基づいて,軌跡数に線形な木構造を求める。 本研究では,多種多様な合成および実世界のデータセットに関する広範な実験により,本手法の有効性と有効性について分析する。
• 参考スコア（独自算出の注目度）: 1.9335262420787858
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present a scalable approach for range and $k$ nearest neighbor queries under computationally expensive metrics, like the continuous Fr\'echet distance on trajectory data. Based on clustering for metric indexes, we obtain a dynamic tree structure whose size is linear in the number of trajectories, regardless of the trajectory's individual sizes or the spatial dimension, which allows one to exploit low `intrinsic dimensionality' of data sets for effective search space pruning. Since the distance computation is expensive, generic metric indexing methods are rendered impractical. We present strategies that (i) improve on known upper and lower bound computations, (ii) build cluster trees without any or very few distance calls, and (iii) search using bounds for metric pruning, interval orderings for reduction, and randomized pivoting for reporting the final results. We analyze the efficiency and effectiveness of our methods with extensive experiments on diverse synthetic and real-world data sets. The results show improvement over state-of-the-art methods for exact queries, and even further speed-ups are achieved for queries that may return approximate results. Surprisingly, the majority of exact nearest-neighbor queries on real data sets are answered without any distance computations.
• Abstract（参考訳）: トラジェクトリデータ上の連続的なFr'echet距離など,計算コストの高い測定値の下で,レンジと近接するクエリに対して,スケーラブルなアプローチを提案する。 計量指標のクラスタリングに基づいて, 軌道の個々の大きさや空間次元にかかわらず, 軌道数に線形な大きさの動的木構造を得る。 距離計算は高価であるため、一般的な計量インデックス化手法は実用的でない。 戦略を提示します (i)既知の上界と下界の計算を改善すること。 (ii)距離コールをほとんど必要とせずにクラスタツリーを構築し、 (3) 計量プルーニングのための境界を用いた探索, 縮小のための区間順序付け, 最終結果の報告のためのランダム化ピボット。 本手法の効率性と有効性について,多種多様な合成データと実世界のデータセットを用いた広範囲な実験を行った。 その結果、正確なクエリに対する最先端のメソッドよりも改善が見られ、近似結果を返すクエリではさらにスピードアップが達成される。 驚いたことに、実際のデータセットに最も近いクエリのほとんどは、距離計算なしで答えられる。

関連論文リスト

• Fast unsupervised ground metric learning with tree-Wasserstein distance [14.235762519615175]
  教師なしの地上距離学習アプローチが導入されました 木にサンプルや特徴を埋め込むことでWSV法を強化し,木-ワッサーシュタイン距離(TWD)を計算することを提案する。 我々は、このアルゴリズムが最もよく知られた方法よりも完全なWSVアプローチの近似に収束し、$mathcalO(n3)$複雑さを持つことを理論的かつ経験的に実証する。
  論文  参考訳（メタデータ） (2024-11-11T23:21:01Z)
• A Bi-metric Framework for Fast Similarity Search [23.254885582600775]
  近接するデータ構造を設計するための新しい「バイメトリック」フレームワークを提案する。 本フレームワークでは, 高精度で計算に費用がかかる基底トラストメトリックと, 安価だが精度の低いプロキシメトリックの2つの相似性関数を仮定する。 プロキシメトリックのみを使用して、両方のメトリクスに対して限られた数の呼び出ししか使用せず、データ構造を構築する方法を示す。
  論文  参考訳（メタデータ） (2024-06-05T03:17:48Z)
• Group Testing for Accurate and Efficient Range-Based Near Neighbor Search for Plagiarism Detection [2.3814052021083354]
  本研究は, 近接探索問題に対する適応型群検定フレームワークを提案する。 本研究では,データベース内の各項目を問合せ点の隣人あるいは非隣人として,余剰距離閾値に基づいて効率よくマークする。 本研究では,ソフトマックスに基づく特徴量を用いて,完全探索よりも10倍以上の高速化を実現し,精度を損なわないことを示す。
  論文  参考訳（メタデータ） (2023-11-05T06:12:03Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap は、ワーッサーシュタイン空間の低次元構造を明らかにするための計算可能なアルゴリズムである。 我々は,LOT Wassmapが正しい埋め込みを実現し,サンプルサイズの増加とともに品質が向上することを示す。 また、LOT Wassmapがペア距離計算に依存するアルゴリズムと比較して計算コストを大幅に削減することを示す。
  論文  参考訳（メタデータ） (2023-02-14T22:12:16Z)
• Shapley-NAS: Discovering Operation Contribution for Neural Architecture Search [96.20505710087392]
  ニューラルアーキテクチャ探索のための演算寄与度(Shapley-NAS)を評価するためのShapley値に基づく手法を提案する。 提案手法は,光探索コストに比例して最先端の手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-06-20T14:41:49Z)
• Efficient Wind Speed Nowcasting with GPU-Accelerated Nearest Neighbors Algorithm [0.0]
  本稿では, 簡易かつ効率的な高高度風速流路を提案する。 空域全体にわたって航空機が記録した大量のライブデータを効率的に処理する。 データセットの各ポイントごとにユニークなコンテキストを生成し、そこから外挿する。
  論文  参考訳（メタデータ） (2021-12-20T09:15:27Z)
• Estimating leverage scores via rank revealing methods and randomization [50.591267188664666]
  任意のランクの正方形密度あるいはスパース行列の統計レバレッジスコアを推定するアルゴリズムについて検討した。 提案手法は,高密度およびスパースなランダム化次元性還元変換の合成と階調明細化法を組み合わせることに基づく。
  論文  参考訳（メタデータ） (2021-05-23T19:21:55Z)
• Exact and Approximate Hierarchical Clustering Using A* [51.187990314731344]
  クラスタリングのA*探索に基づく新しいアプローチを紹介します。 A*と新しいエンフォレリスデータ構造を組み合わせることで、禁止的に大きな検索空間を克服します。 実験により,本手法は粒子物理利用事例や他のクラスタリングベンチマークにおいて,ベースラインよりもかなり高品質な結果が得られることを示した。
  論文  参考訳（メタデータ） (2021-04-14T18:15:27Z)
• 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)
• Stable and consistent density-based clustering via multiparameter persistence [77.34726150561087]
  トポロジカルデータ解析による次数-リップス構成について考察する。 我々は,入力データの摂動に対する安定性を,通信間距離を用いて解析する。 私たちはこれらのメソッドを、Persistableと呼ばれる密度ベースのクラスタリングのためのパイプラインに統合します。
  論文  参考訳（メタデータ） (2020-05-18T19:45:04Z)
• Scalable Distributed Approximation of Internal Measures for Clustering Evaluation [5.144809478361603]
  クラスタリング評価のための内部測度はシルエット係数であり、計算には2つの距離計算が必要である。 本稿では,任意の距離に基づいてクラスタリングの評価を行うための厳密な近似を計算した最初のスケーラブルアルゴリズムを提案する。 また,このアルゴリズムは凝集や分離などのクラスタリング品質の他の内部指標の厳密な近似に適応可能であることも証明した。
  論文  参考訳（メタデータ） (2020-03-03T10:28:14Z)

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

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