論文の概要: PolyMinHash: Efficient Area-Based MinHashing of Polygons for Approximate Nearest Neighbor Search

• arxiv url: http://arxiv.org/abs/2511.16576v1
• Date: Thu, 20 Nov 2025 17:31:14 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-21 17:08:52.760874
• Title: PolyMinHash: Efficient Area-Based MinHashing of Polygons for Approximate Nearest Neighbor Search
• Title（参考訳）: PolyMinHash: 近接探索のための効率的なエリアベースポリゴンマイハッシング
• Authors: Alima Subedi, Sankalpa Pokharel, Satish Puri,
• Abstract要約: PolyMinHashは、MinHashを新しい2Dポリゴンハッシュ方式に適合させる、近似ポリゴン類似性探索システムである。 ミンハッシュは、サンプリングされた点がポリゴンの内部領域に着くのに必要な無作為にサンプリングされた点の数を数えることによって生成される。 我々のハッシュ機構は、ブルートフォースアルゴリズムにより処理される候補数と比較して、クエリ精算フェーズで処理される候補数を最大98%削減する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Similarity searches are a critical task in data mining. As data sets grow larger, exact nearest neighbor searches quickly become unfeasible, leading to the adoption of approximate nearest neighbor (ANN) searches. ANN has been studied for text data, images, and trajectories. However, there has been little effort to develop ANN systems for polygons in spatial database systems and geographic information systems. We present PolyMinHash, a system for approximate polygon similarity search that adapts MinHashing into a novel 2D polygon-hashing scheme to generate short, similarity-preserving signatures of input polygons. Minhash is generated by counting the number of randomly sampled points needed before the sampled point lands within the polygon's interior area, yielding hash values that preserve area-based Jaccard similarity. We present the tradeoff between search accuracy and runtime of our PolyMinHash system. Our hashing mechanism reduces the number of candidates to be processed in the query refinement phase by up to 98% compared to the number of candidates processed by the brute-force algorithm.
• Abstract（参考訳）: 類似性検索はデータマイニングにおいて重要な課題である。 データセットが大きくなるにつれて、最も近い隣人探索はすぐに実現不可能となり、近くの隣人探索(ANN)が採用される。 ANNはテキストデータ、画像、軌跡について研究されている。 しかし、空間データベースシステムや地理情報システムにおいて、ポリゴンのためのANNシステムを開発する努力はほとんど行われていない。 我々は、MinHashingを新しい2次元ポリゴンハッシュ方式に適応させ、入力ポリゴンの短い類似性保存シグネチャを生成する、近似ポリゴン類似性探索システムPolyMinHashを提案する。 ミンハッシュは、サンプリングされた点がポリゴンの内部領域に着地するために必要なランダムサンプリングされた点数を数え、領域ベースのジャカード類似性を保持するハッシュ値を生成することによって生成される。 検索精度とPolyMinHashシステムの実行時のトレードオフを示す。 我々のハッシュ機構は、ブルートフォースアルゴリズムにより処理される候補数と比較して、クエリ精算フェーズで処理される候補数を最大98%削減する。

関連論文リスト

• PECANN: Parallel Efficient Clustering with Graph-Based Approximate Nearest Neighbor Search [7.466687780705626]
  本稿では, 点集合の密度に基づくクラスタリングについて検討する。 密度ピークの異なる変種を単一のフレームワークPECANNに統合する。 PECANNを用いて5つのクラスタリングアルゴリズムを実装し,最大128万点,最大1024次元の合成および実世界のデータセットを双方向ハイパースレッディングを備えた30コアマシン上で評価する。
  論文  参考訳（メタデータ） (2023-12-06T22:43:50Z)
• Differentially Private One Permutation Hashing and Bin-wise Consistent Weighted Sampling [37.6593006747285]
  Minwise hashing (MinHash) は、大規模な検索および学習アプリケーションで広く使われている標準アルゴリズムである。 1つの置換ハッシュ(OPH)は、データベクトルを$K$ binに分割し、各bin内でハッシュ値を生成するMinHashの効率的な代替手段である。 我々は, DP-OPH-fix, DP-OPH-re, DP-OPH-randの3つの変種を用いたDP-OPHフレームワークを提案する。
  論文  参考訳（メタデータ） (2023-06-13T10:38:12Z)
• Unified Functional Hashing in Automatic Machine Learning [58.77232199682271]
  高速に統一された関数型ハッシュを用いることで,大きな効率向上が得られることを示す。 私たちのハッシュは"機能的"であり、表現やコードが異なる場合でも同等の候補を識別します。 ニューラルアーキテクチャ検索やアルゴリズム発見など、複数のAutoMLドメインで劇的な改善がなされている。
  論文  参考訳（メタデータ） (2023-02-10T18:50:37Z)
• A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
  ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。 このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。 我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-03-28T21:34:16Z)
• SLOSH: Set LOcality Sensitive Hashing via Sliced-Wasserstein Embeddings [18.916058638077274]
  本稿では,ANN (Non-parametric and data-independent learning from set-structured data using almost near neighbor (ANN) solutions。 Sliced-Wasserstein set embedding as a computerly efficient "set-2-vector" mechanism that possible downstream ANN。 本稿では,SLOSH (Set-LOcality Sensitive Hashing) と呼ばれるアルゴリズムの有効性を,様々なデータセットで示す。
  論文  参考訳（メタデータ） (2021-12-11T00:10:05Z)
• Graph Sampling Based Deep Metric Learning for Generalizable Person Re-Identification [114.56752624945142]
  我々は、最も一般的なランダムサンプリング手法である有名なpkサンプリングは、深層メトリック学習にとって有益で効率的ではないと主張する。 大規模計量学習のためのグラフサンプリング(GS)と呼ばれる効率的なミニバッチサンプリング手法を提案する。
  論文  参考訳（メタデータ） (2021-04-04T06:44:15Z)
• Unsupervised Multi-Index Semantic Hashing [23.169142004594434]
  マルチインデックスハッシュに最適化することで,効率的かつ高効率なハッシュコードを学習する教師なしハッシュモデルを提案する。 文書類似度検索のタスクにおいて、MISHと最先端のセマンティックハッシュベースラインを実験的に比較する。 マルチインデックスハッシュは、線形スキャンと比較してベースラインの効率も向上しますが、MISHよりも33%遅くなっています。
  論文  参考訳（メタデータ） (2021-03-26T13:33:48Z)
• Distributed Tera-Scale Similarity Search with MPI: Provably Efficient Similarity Search over billions without a Single Distance Computation [40.75034970144169]
  SLASHはテラバイト規模のデータセットの類似性を近似的に検索する分散システムである。 SLASHはこの2.3テラバイトのデータを1時間以内に20ノードにインデックスし、クエリ時間をミリ秒単位で表示する。
  論文  参考訳（メタデータ） (2020-08-05T18:15:36Z)
• Reinforcing Short-Length Hashing [61.75883795807109]
  既存の手法は、非常に短いハッシュコードを用いた検索性能が劣っている。 本研究では, 短寿命ハッシュ(RSLH)を改良する新しい手法を提案する。 本稿では,ハッシュ表現とセマンティックラベルの相互再構成を行い,セマンティック情報を保存する。 3つの大規模画像ベンチマークの実験は、様々な短いハッシュシナリオ下でのRSLHの優れた性能を示す。
  論文  参考訳（メタデータ） (2020-04-24T02:23:52Z)
• LSF-Join: Locality Sensitive Filtering for Distributed All-Pairs Set Similarity Under Skew [58.21885402826496]
  全ペアセットの類似性は、大規模で高次元のデータセットであっても広く使われているデータマイニングタスクである。 我々は,全対集合の類似性を近似するために,新しい分散アルゴリズム LSF-Join を提案する。 LSF-Joinは、小さな類似度閾値やスキュー入力セットであっても、最も近いペアを効率的に見つける。
  論文  参考訳（メタデータ） (2020-03-06T00:06:20Z)
• A Survey on Deep Hashing Methods [52.326472103233854]
  最寄りの検索は、データベースからクエリまでの距離が最小のサンプルを取得することを目的としている。 ディープラーニングの発展により、ディープハッシュ法は従来の方法よりも多くの利点を示す。 深い教師付きハッシュは、ペアワイズ法、ランキングベースの方法、ポイントワイズ法、量子化に分類される。 深い教師なしハッシュは、類似性再構築に基づく方法、擬似ラベルに基づく方法、予測自由な自己教師あり学習に基づく方法に分類される。
  論文  参考訳（メタデータ） (2020-03-04T08:25:15Z)

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

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