論文の概要: Efficient Sketching and Nearest Neighbor Search Algorithms for Sparse Vector Sets

• arxiv url: http://arxiv.org/abs/2509.24815v1
• Date: Mon, 29 Sep 2025 14:02:45 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-30 22:32:20.033792
• Title: Efficient Sketching and Nearest Neighbor Search Algorithms for Sparse Vector Sets
• Title（参考訳）: スパースベクトル集合に対する効率的なスケッチと近傍探索アルゴリズム
• Authors: Sebastian Bruch, Franco Maria Nardini, Cosimo Rulli, Rossano Venturini,
• Abstract要約: スパースANNSのための新しいデータ構造とアルゴリズム手法を提案する。 我々の貢献は、スパースベクトルに対する理論的に基底化されたスケッチアルゴリズムから、それらの有効次元を減少させるものまで様々である。 我々の最終アルゴリズムは耐震性と呼ばれ、大規模ベンチマークデータセット上で高精度でミリ秒以下のレイテンシに達する。
• 参考スコア（独自算出の注目度）: 16.768212375976546
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Sparse embeddings of data form an attractive class due to their inherent interpretability: Every dimension is tied to a term in some vocabulary, making it easy to visually decipher the latent space. Sparsity, however, poses unique challenges for Approximate Nearest Neighbor Search (ANNS) which finds, from a collection of vectors, the k vectors closest to a query. To encourage research on this underexplored topic, sparse ANNS featured prominently in a BigANN Challenge at NeurIPS 2023, where approximate algorithms were evaluated on large benchmark datasets by throughput and accuracy. In this work, we introduce a set of novel data structures and algorithmic methods, a combination of which leads to an elegant, effective, and highly efficient solution to sparse ANNS. Our contributions range from a theoretically-grounded sketching algorithm for sparse vectors to reduce their effective dimensionality while preserving inner product-induced ranks; a geometric organization of the inverted index; and the blending of local and global information to improve the efficiency and efficacy of ANNS. Empirically, our final algorithm, dubbed Seismic, reaches sub-millisecond per-query latency with high accuracy on a large-scale benchmark dataset using a single CPU.
• Abstract（参考訳）: データの疎埋め込みは、その固有の解釈可能性のために魅力的なクラスを形成する: すべての次元は、ある語彙の項に結びついているので、潜伏空間を視覚的に容易に解読できる。 しかし、スパシティは、クエリに最も近いkベクトルの集合であるベクトルの集合から、近似近傍探索(ANNS)に固有の課題を生じさせる。 この未調査トピックの研究を促進するため、NeurIPS 2023で行なわれたBigANN Challengeでは、スループットと精度によって、大規模なベンチマークデータセットで近似アルゴリズムが評価された。 本研究では,新しいデータ構造とアルゴリズム手法のセットを導入し,その組み合わせにより,ANNSをスパースするエレガントで効率的かつ高効率な解が得られることを示す。 我々の貢献は、内部積によるランクを維持しながら有効次元を減少させるためのスパースベクトルの理論的に基底化されたスケッチアルゴリズム、逆インデックスの幾何学的構成、ANNSの効率と有効性を改善するための局所的および大域的情報のブレンディングなど多岐にわたる。 経験的に、我々の最終アルゴリズムは耐震性と呼ばれ、単一のCPUを用いて大規模なベンチマークデータセット上で高い精度で、クエリ毎のミリ秒未満のレイテンシに達する。

関連論文リスト

• Infinity Search: Approximate Vector Search with Projections on q-Metric Spaces [94.12116458306916]
  我々は、$q$の測度空間において、計量木は三角形の不等式のより強いバージョンを活用でき、正確な探索の比較を減らすことができることを示した。 任意の異方性測度を持つデータセットを$q$-metric空間に埋め込む新しい射影法を提案する。
  論文  参考訳（メタデータ） (2025-06-06T22:09:44Z)
• PECANN: Parallel Efficient Clustering with Graph-Based Approximate Nearest Neighbor Search [7.466687780705626]
  本稿では, 点集合の密度に基づくクラスタリングについて検討する。 密度ピークの異なる変種を単一のフレームワークPECANNに統合する。 PECANNを用いて5つのクラスタリングアルゴリズムを実装し,最大128万点,最大1024次元の合成および実世界のデータセットを双方向ハイパースレッディングを備えた30コアマシン上で評価する。
  論文  参考訳（メタデータ） (2023-12-06T22:43:50Z)
• ParlayANN: Scalable and Deterministic Parallel Graph-Based Approximate Nearest Neighbor Search Algorithms [5.478671305092084]
  本稿では,ParlayANNについて紹介する。ParlayANNは決定論的および並列グラフに基づく近接探索アルゴリズムのライブラリである。 我々は、数十億のデータセットにスケールする4つの最先端グラフベースのANNSアルゴリズムに対して、新しい並列実装を開発する。
  論文  参考訳（メタデータ） (2023-05-07T19:28:23Z)
• Efficient Convex Algorithms for Universal Kernel Learning [46.573275307034336]
  カーネルの理想的な集合: 線形パラメータ化(トラクタビリティ)を認める; すべてのカーネルの集合に密着する(正確性)。 従来のカーネル最適化アルゴリズムは分類に限られており、計算に複雑なセミデフィニティプログラミング(SDP)アルゴリズムに依存していた。 本稿では,従来のSDP手法と比較して計算量を大幅に削減するSVD-QCQPQPアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-04-15T04:57:37Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap は、ワーッサーシュタイン空間の低次元構造を明らかにするための計算可能なアルゴリズムである。 我々は,LOT Wassmapが正しい埋め込みを実現し,サンプルサイズの増加とともに品質が向上することを示す。 また、LOT Wassmapがペア距離計算に依存するアルゴリズムと比較して計算コストを大幅に削減することを示す。
  論文  参考訳（メタデータ） (2023-02-14T22:12:16Z)
• A density peaks clustering algorithm with sparse search and K-d tree [16.141611031128427]
  この問題を解決するために,スパース探索とK-d木を用いた密度ピーククラスタリングアルゴリズムを開発した。 分散特性が異なるデータセット上で、他の5つの典型的なクラスタリングアルゴリズムと比較して実験を行う。
  論文  参考訳（メタデータ） (2022-03-02T09:29:40Z)
• Estimating leverage scores via rank revealing methods and randomization [50.591267188664666]
  任意のランクの正方形密度あるいはスパース行列の統計レバレッジスコアを推定するアルゴリズムについて検討した。 提案手法は,高密度およびスパースなランダム化次元性還元変換の合成と階調明細化法を組み合わせることに基づく。
  論文  参考訳（メタデータ） (2021-05-23T19:21:55Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)

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

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