論文の概要: On Storage Neural Network Augmented Approximate Nearest Neighbor Search
- arxiv url: http://arxiv.org/abs/2501.16375v1
- Date: Thu, 23 Jan 2025 06:56:18 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-01-29 16:42:59.094371
- Title: On Storage Neural Network Augmented Approximate Nearest Neighbor Search
- Title(参考訳): 近似近似近傍探索を付加した記憶型ニューラルネットワークについて
- Authors: Taiga Ikeda, Daisuke Miyashita, Jun Deguchi,
- Abstract要約: メモリ上のデータではなく、ストレージデバイスに格納されているデータから、与えられたクエリベクターに最もよく似たベクターを検索する必要がある。
本稿では,ニューラルネットワークを用いて正しいクラスタを予測する手法を提案する。
K平均クラスタリングと線形サーチを併用した,最先端SPANNと網羅的手法と比較して, SIFT1Mでは, ストレージから取得したデータの80%と58%の削減で, 90%のリコールを実現している。
- 参考スコア(独自算出の注目度): 1.3654846342364308
- License:
- Abstract: Large-scale approximate nearest neighbor search (ANN) has been gaining attention along with the latest machine learning researches employing ANNs. If the data is too large to fit in memory, it is necessary to search for the most similar vectors to a given query vector from the data stored in storage devices, not from that in memory. The storage device such as NAND flash memory has larger capacity than the memory device such as DRAM, but they also have larger latency to read data. Therefore, ANN methods for storage require completely different approaches from conventional in-memory ANN methods. Since the approximation that the time required for search is determined only by the amount of data fetched from storage holds under reasonable assumptions, our goal is to minimize it while maximizing recall. For partitioning-based ANNs, vectors are partitioned into clusters in the index building phase. In the search phase, some of the clusters are chosen, the vectors in the chosen clusters are fetched from storage, and the nearest vector is retrieved from the fetched vectors. Thus, the key point is to accurately select the clusters containing the ground truth nearest neighbor vectors. We accomplish this by proposing a method to predict the correct clusters by means of a neural network that is gradually refined by alternating supervised learning and duplicated cluster assignment. Compared to state-of-the-art SPANN and an exhaustive method using k-means clustering and linear search, the proposed method achieves 90% recall on SIFT1M with 80% and 58% less data fetched from storage, respectively.
- Abstract(参考訳): 大規模ニアニアサーチ(ANN)は、ANNを用いた最新の機械学習研究とともに注目されている。
データがメモリに収まるには大きすぎる場合、メモリに格納されているデータから、与えられたクエリベクターに最もよく似たベクターを検索する必要がある。
NANDフラッシュメモリのようなストレージデバイスは、DRAMのようなメモリデバイスよりも容量が大きいが、データを読むのにも遅延が大きい。
したがって、ストレージのためのANNメソッドは、従来のインメモリANNメソッドとは全く異なるアプローチを必要とする。
ストレージから取得したデータ量によってのみ検索に要する時間が決定されるという近似は妥当な仮定で成り立つため,リコールを最大化しながら最小化することが目的である。
パーティショニングベースのANNでは、ベクトルはインデックス構築フェーズのクラスタに分割される。
検索フェーズでは、いくつかのクラスタが選択され、選択されたクラスタ内のベクターがストレージからフェッチされ、最も近いベクターがフェッチされたベクターから検索される。
したがって、鍵となる点は、接地真理近傍ベクトルを含むクラスタを正確に選択することである。
我々は、教師付き学習と重複クラスタ割り当ての交互化によって徐々に洗練されるニューラルネットワークを用いて、正しいクラスタを予測する方法を提案する。
k平均クラスタリングと線形サーチを併用した,最先端SPANNと網羅的手法と比較して, SIFT1Mでは, ストレージから取得したデータの80%と58%の削減で, 90%のリコールを実現している。
関連論文リスト
- On Simplifying Large-Scale Spatial Vectors: Fast, Memory-Efficient, and Cost-Predictable k-means [7.192072206801592]
k平均アルゴリズムは、高速な解析と学習をサポートするために、2Dジオロケーションや3Dポイントクラウドのような大規模な空間ベクトルを単純化することができる。
既存のk平均アルゴリズムは、メモリやCPU使用時間などの重要な計算資源で高い性能を達成する。
本稿では,Dsk-meansと呼ばれる高速で,メモリ効率が高く,コスト予測可能なk-meansを提案する。
論文 参考訳(メタデータ) (2024-12-03T08:16:59Z) - RetrievalAttention: Accelerating Long-Context LLM Inference via Vector Retrieval [24.472784635757016]
RetrievalAttentionは、注意計算を高速化し、GPUメモリ消費を減らすためのトレーニング不要のアプローチである。
RetrievalAttentionは1-3%のデータのみを必要としながら、ほぼ全注意精度を達成できることを示す。
論文 参考訳(メタデータ) (2024-09-16T17:59:52Z) - AiSAQ: All-in-Storage ANNS with Product Quantization for DRAM-free Information Retrieval [1.099532646524593]
DiskANNは、RAMとストレージの両方を使用して、大規模データセットのリコール速度バランスを良好に実現している。
製品量子化(PQ)による圧縮ベクターのロードによるメモリ使用量の削減を主張する一方で、そのメモリ使用量はデータセットの規模に比例して増加する。
本稿では、圧縮されたベクトルをストレージにオフロードするAiSAQ(All-in-Storage ANNS with Product Quantization)を提案する。
論文 参考訳(メタデータ) (2024-04-09T04:20:27Z) - Large-scale Fully-Unsupervised Re-Identification [78.47108158030213]
大規模未ラベルデータから学ぶための2つの戦略を提案する。
第1の戦略は、近傍関係に違反することなく、それぞれのデータセットサイズを減らすために、局所的な近傍サンプリングを行う。
第2の戦略は、低時間上限の複雑さを持ち、メモリの複雑さを O(n2) から O(kn) に k n で還元する新しい再帰的手法を利用する。
論文 参考訳(メタデータ) (2023-07-26T16:19:19Z) - Data Selection for Language Models via Importance Resampling [90.9263039747723]
我々は、望まれるターゲット分布に合わせるために、大規模な未ラベルデータセットのサブセットを選択するという問題を形式化する。
我々は、LMデータ選択のために低次元で使用される古典的な重要度再サンプリング手法を拡張した。
DSIRフレームワークをhash n-gram機能でインスタンス化し、4.5時間で1億のドキュメントを選択できる。
論文 参考訳(メタデータ) (2023-02-06T23:57:56Z) - Efficient Dataset Distillation Using Random Feature Approximation [109.07737733329019]
本稿では,ニューラルネットワークガウス過程(NNGP)カーネルのランダム特徴近似(RFA)を用いた新しいアルゴリズムを提案する。
我々のアルゴリズムは、KIP上で少なくとも100倍のスピードアップを提供し、1つのGPUで実行できる。
RFA蒸留 (RFAD) と呼ばれる本手法は, 大規模データセットの精度において, KIP や他のデータセット凝縮アルゴリズムと競合して動作する。
論文 参考訳(メタデータ) (2022-10-21T15:56:13Z) - SreaMRAK a Streaming Multi-Resolution Adaptive Kernel Algorithm [60.61943386819384]
既存のKRRの実装では、すべてのデータがメインメモリに格納される必要がある。
KRRのストリーミング版であるStreaMRAKを提案する。
本稿では,2つの合成問題と2重振り子の軌道予測について紹介する。
論文 参考訳(メタデータ) (2021-08-23T21:03:09Z) - IRLI: Iterative Re-partitioning for Learning to Index [104.72641345738425]
分散環境でのロードバランスとスケーラビリティを維持しながら、高い精度を得る方法とのトレードオフが必要だ。
クエリ項目関連データから直接バケットを学習することで、アイテムを反復的に分割するIRLIと呼ばれる新しいアプローチを提案する。
我々は,irliが極めて自然な仮定の下で高い確率で正しい項目を検索し,優れた負荷分散を実現することを数学的に示す。
論文 参考訳(メタデータ) (2021-03-17T23:13:25Z) - Coded Stochastic ADMM for Decentralized Consensus Optimization with Edge
Computing [113.52575069030192]
セキュリティ要件の高いアプリケーションを含むビッグデータは、モバイルデバイスやドローン、車両など、複数の異種デバイスに収集され、格納されることが多い。
通信コストとセキュリティ要件の制限のため、核融合センターにデータを集約するのではなく、分散的に情報を抽出することが最重要となる。
分散エッジノードを介してデータを局所的に処理するマルチエージェントシステムにおいて,モデルパラメータを学習する問題を考える。
分散学習モデルを開発するために,乗算器アルゴリズムの最小バッチ交互方向法(ADMM)のクラスについて検討した。
論文 参考訳(メタデータ) (2020-10-02T10:41:59Z) - SDCOR: Scalable Density-based Clustering for Local Outlier Detection in
Massive-Scale Datasets [0.0]
本稿では,大規模データセットにおける局所外乱検出のためのバッチワイド密度に基づくクラスタリング手法を提案する。
実生活および合成データセットの評価は,提案手法の線形時間複雑性が低いことを示す。
論文 参考訳(メタデータ) (2020-06-13T11:07:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。