論文の概要: ProHD: Projection-Based Hausdorff Distance Approximation

• arxiv url: http://arxiv.org/abs/2511.18207v1
• Date: Sat, 22 Nov 2025 22:44:46 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-25 18:34:24.692158
• Title: ProHD: Projection-Based Hausdorff Distance Approximation
• Title（参考訳）: ProHD: プロジェクションに基づくハウスドルフ距離近似
• Authors: Jiuzhou Fu, Luanzheng Guo, Nathan R. Tallent, Dongfang Zhao,
• Abstract要約: ハウスドルフ距離は集合の相似性の頑健な測度である。 ProHDはプロジェクション誘導近似アルゴリズムであり、HD計算を劇的に高速化する。 提案手法は,大規模ベクトルデータベースやストリーミングデータなどのシナリオにおいて,実用的なHD計算を可能にする。
• 参考スコア（独自算出の注目度）: 1.412864345734062
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Hausdorff distance (HD) is a robust measure of set dissimilarity, but computing it exactly on large, high-dimensional datasets is prohibitively expensive. We propose \textbf{ProHD}, a projection-guided approximation algorithm that dramatically accelerates HD computation while maintaining high accuracy. ProHD identifies a small subset of candidate "extreme" points by projecting the data onto a few informative directions (such as the centroid axis and top principal components) and computing the HD on this subset. This approach guarantees an underestimate of the true HD with a bounded additive error and typically achieves results within a few percent of the exact value. In extensive experiments on image, physics, and synthetic datasets (up to two million points in $D=256$), ProHD runs 10--100$\times$ faster than exact algorithms while attaining 5--20$\times$ lower error than random sampling-based approximations. Our method enables practical HD calculations in scenarios like large vector databases and streaming data, where quick and reliable set distance estimation is needed.
• Abstract（参考訳）: ハウスドルフ距離(Hausdorff distance、HD)は集合の相似性の頑健な測度であるが、大規模で高次元のデータセット上で正確に計算することは違法に高価である。 本稿では,高い精度を維持しながらHD計算を劇的に高速化するプロジェクション誘導近似アルゴリズムである‘textbf{ProHD} を提案する。 ProHDは、データをいくつかの情報的方向(セントロイド軸やトップ主成分など)に投影し、この部分集合上でHDを計算することで、候補の「極端」点の小さな部分集合を識別する。 このアプローチは、有界加法誤差を持つ真のHDの過小評価を保証し、通常は正確な値の数パーセントで結果を得る。 画像、物理、合成データセット(最大200万ポイントの$D=256$)に関する広範な実験において、ProHDは10-100$\times$を正確なアルゴリズムより高速に実行し、ランダムサンプリングベースの近似よりも5-20$\times$低いエラーを達成する。 提案手法は,高速かつ信頼性の高い設定距離推定を必要とする大規模ベクトルデータベースやストリーミングデータなどのシナリオにおいて,実用的なHD計算を可能にする。

関連論文リスト

• Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search [14.77572360618428]
  高次元近似$K$近接探索(AKNN)は情報検索を含む様々なアプリケーションの基本課題である。 AKNNの既存のアルゴリズムのほとんどは、候補生成と距離比較演算(DCO)という2つの主要コンポーネントに分解することができる。 低次元空間における正確な距離を近似するDADEと呼ばれるデータ認識距離推定手法を提案する。
  論文  参考訳（メタデータ） (2024-11-26T08:51:46Z)
• Hyperdimensional Representation Learning for Node Classification and Link Prediction [0.0]
  本稿では,グラフのノード分類とリンク予測のための新しい手法であるHyperdimensional Graph Learner (HDGL)を紹介する。 グラフニューラルネットワーク(GNN)系におけるノード表現の傾き特性を用いた高次元空間へのノード特徴のマッピング 本稿では,ノード分類タスクにおいて,最新のGNN手法と競合する精度を,計算コストを大幅に削減することを示すために,広く使用されているベンチマークデータセットを用いた実験結果について報告する。
  論文  参考訳（メタデータ） (2024-02-26T23:15:01Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap は、ワーッサーシュタイン空間の低次元構造を明らかにするための計算可能なアルゴリズムである。 我々は,LOT Wassmapが正しい埋め込みを実現し,サンプルサイズの増加とともに品質が向上することを示す。 また、LOT Wassmapがペア距離計算に依存するアルゴリズムと比較して計算コストを大幅に削減することを示す。
  論文  参考訳（メタデータ） (2023-02-14T22:12:16Z)
• Efficient Hyperdimensional Computing [4.8915861089531205]
  我々は,2次元超ベクトルを用いたHDCモデルを,最先端HDCモデルよりも桁違いに低次元で開発する。 例えば、MNISTデータセットでは、次元が64の画像分類において91.12%のHDC精度を達成する。
  論文  参考訳（メタデータ） (2023-01-26T02:22:46Z)
• Fully Sparse 3D Object Detection [57.05834683261658]
  長距離LiDARオブジェクト検出のためのフルスパース3Dオブジェクト検出器(FSD)を構築した。 FSDは一般的なスパース・ボクセル・エンコーダと新しいスパース・インスタンス認識(SIR)モジュール上に構築されている。 SIRは、ポイントをインスタンスにグループ化することで、以前のポイントベースのメソッドでの待ち行列クエリを避ける。
  論文  参考訳（メタデータ） (2022-07-20T17:01:33Z)
• Torchhd: An Open Source Python Library to Support Research on Hyperdimensional Computing and Vector Symbolic Architectures [99.70485761868193]
  我々はHD/VSA用の高性能オープンソースPythonライブラリであるTorchhdを紹介する。 Torchhdは、HD/VSAをよりアクセスしやすくし、さらなる研究とアプリケーション開発のための効率的な基盤となることを目指している。
  論文  参考訳（メタデータ） (2022-05-18T20:34:25Z)
• List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
  高次元におけるリストデコタブル平均推定の基本的な課題について検討する。 我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。 我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
  論文  参考訳（メタデータ） (2020-11-19T17:21:37Z)
• List-Decodable Mean Estimation via Iterative Multi-Filtering [44.805549762166926]
  未知の$alpha$-fraction of points in $T$は未知の平均と有界な共分散分布$D$から引き出される。 仮説ベクトルの小さなリストを出力し、その中の少なくとも一方が$D$に近いようにする。 より詳しくは、本アルゴリズムはサンプリングと計算効率が良く、情報理論上の準最適誤差を実現する。
  論文  参考訳（メタデータ） (2020-06-18T17:47:37Z)
• Augmented Sliced Wasserstein Distances [55.028065567756066]
  拡張スライスされたワッサーシュタイン距離(ASWD)と呼ばれる新しい距離測定法を提案する。 ASWDは、ニューラルネットワークによってパラメータ化された高次元超曲面への最初のマッピングサンプルによって構成される。 数値的な結果から、ASWDは、合成問題と実世界の問題の両方において、他のワッサーシュタイン変種を著しく上回っていることが示されている。
  論文  参考訳（メタデータ） (2020-06-15T23:00:08Z)
• Maximizing Determinants under Matroid Constraints [69.25768526213689]
  我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。 この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
  論文  参考訳（メタデータ） (2020-04-16T19:16:38Z)

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

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