論文の概要: On Simplifying Large-Scale Spatial Vectors: Fast, Memory-Efficient, and Cost-Predictable k-means
- arxiv url: http://arxiv.org/abs/2412.02244v1
- Date: Tue, 03 Dec 2024 08:16:59 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-04 15:43:20.091104
- Title: On Simplifying Large-Scale Spatial Vectors: Fast, Memory-Efficient, and Cost-Predictable k-means
- Title（参考訳）: 大規模空間ベクトルの簡易化:高速, メモリ効率, コスト予測可能なk平均
- Authors: Yushuai Ji, Zepeng Liu, Sheng Wang, Yuan Sun, Zhiyong Peng,
- Abstract要約: k平均アルゴリズムは、高速な解析と学習をサポートするために、2Dジオロケーションや3Dポイントクラウドのような大規模な空間ベクトルを単純化することができる。
既存のk平均アルゴリズムは、メモリやCPU使用時間などの重要な計算資源で高い性能を達成する。
本稿では,Dsk-meansと呼ばれる高速で,メモリ効率が高く,コスト予測可能なk-meansを提案する。
- 参考スコア（独自算出の注目度）: 7.192072206801592
- License:
- Abstract: The k-means algorithm can simplify large-scale spatial vectors, such as 2D geo-locations and 3D point clouds, to support fast analytics and learning. However, when processing large-scale datasets, existing k-means algorithms have been developed to achieve high performance with significant computational resources, such as memory and CPU usage time. These algorithms, though effective, are not well-suited for resource-constrained devices. In this paper, we propose a fast, memory-efficient, and cost-predictable k-means called Dask-means. We first accelerate k-means by designing a memory-efficient accelerator, which utilizes an optimized nearest neighbor search over a memory-tunable index to assign spatial vectors to clusters in batches. We then design a lightweight cost estimator to predict the memory cost and runtime of the k-means task, allowing it to request appropriate memory from devices or adjust the accelerator's required space to meet memory constraints, and ensure sufficient CPU time for running k-means. Experiments show that when simplifying datasets with scale such as $10^6$, Dask-means uses less than $30$MB of memory, achieves over $168$ times speedup compared to the widely-used Lloyd's algorithm. We also validate Dask-means on mobile devices, where it demonstrates significant speedup and low memory cost compared to other state-of-the-art (SOTA) k-means algorithms. Our cost estimator estimates the memory cost with a difference of less than $3\%$ from the actual ones and predicts runtime with an MSE up to $33.3\%$ lower than SOTA methods.
- Abstract（参考訳）: k平均アルゴリズムは、高速な解析と学習をサポートするために、2Dジオロケーションや3Dポイントクラウドのような大規模な空間ベクトルを単純化することができる。
しかし、大規模なデータセットを処理する際には、メモリやCPU使用時間などの計算資源で高い性能を達成するために、既存のk平均アルゴリズムが開発されている。
これらのアルゴリズムは、有効ではあるが、リソース制約のあるデバイスには適していない。
本稿では,Dask-meansと呼ばれる高速で,メモリ効率が高く,コスト予測可能なk-meansを提案する。
我々はまず、メモリ効率のアクセラレータを設計してk平均を加速する。これは、メモリチューニング可能なインデックス上で最適化された近接探索を用いて、バッチ内のクラスタに空間ベクトルを割り当てる。
次に、k-meansタスクのメモリコストと実行時間を予測する軽量なコスト推定器を設計し、デバイスから適切なメモリを要求したり、メモリ制約を満たすためにアクセラレータに必要なスペースを調整したり、k-meansの実行に必要なCPU時間を確保する。
10^6$のようなスケールでデータセットを単純化する場合、Dask-meansは30$MB未満のメモリを使用する。
また,モバイル端末上でのDask-meansの有効性を検証し,従来のSOTA(State-of-the-art)k-meansアルゴリズムと比較して,大幅な高速化とメモリコストの低下を示す。
我々のコスト推定器は、メモリコストを実際のコストと$3\%未満の差で推定し、実行時を最大で$33.3\%のSOTAメソッドより低く予測する。
関連論文リスト
- On Storage Neural Network Augmented Approximate Nearest Neighbor Search [1.3654846342364308]
メモリ上のデータではなく、ストレージデバイスに格納されているデータから、与えられたクエリベクターに最もよく似たベクターを検索する必要がある。
本稿では,ニューラルネットワークを用いて正しいクラスタを予測する手法を提案する。
K平均クラスタリングと線形サーチを併用した,最先端SPANNと網羅的手法と比較して, SIFT1Mでは, ストレージから取得したデータの80%と58%の削減で, 90%のリコールを実現している。
論文 参考訳（メタデータ） (2025-01-23T06:56:18Z) - RetrievalAttention: Accelerating Long-Context LLM Inference via Vector Retrieval [24.472784635757016]
RetrievalAttentionは、注意計算を高速化し、GPUメモリ消費を減らすためのトレーニング不要のアプローチである。
RetrievalAttentionは1-3%のデータのみを必要としながら、ほぼ全注意精度を達成できることを示す。
論文 参考訳（メタデータ） (2024-09-16T17:59:52Z) - Loki: Low-rank Keys for Efficient Sparse Attention [44.74682508879725]
大規模言語モデル(LLM)の推論は、計算コストとメモリコストの面で高価である。
本研究では,注目ブロックで計算された鍵ベクトルの次元性に着目し,自己注意を近似する手法を提案する。
低次元空間で計算されたアテンションスコアに基づいてKVキャッシュ内のトークンをランク付けし、選択する新しいスパースアテンション手法であるLokiを提案する。
論文 参考訳（メタデータ） (2024-06-04T17:58:03Z) - A Specialized Semismooth Newton Method for Kernel-Based Optimal
Transport [92.96250725599958]
カーネルベース最適輸送(OT)推定器は、サンプルからOT問題に対処するための代替的機能的推定手順を提供する。
SSN法は, 標準正規性条件下でのグローバル収束率$O (1/sqrtk)$, 局所二次収束率を達成できることを示す。
論文 参考訳（メタデータ） (2023-10-21T18:48:45Z) - AdaLomo: Low-memory Optimization with Adaptive Learning Rate [59.64965955386855]
大規模言語モデルに対する適応学習率(AdaLomo)を用いた低メモリ最適化を提案する。
AdaLomoはAdamWと同等の結果を得ると同時に、メモリ要件を大幅に削減し、大きな言語モデルをトレーニングするためのハードウェア障壁を低くする。
論文 参考訳（メタデータ） (2023-10-16T09:04:28Z) - Efficient Dataset Distillation Using Random Feature Approximation [109.07737733329019]
本稿では,ニューラルネットワークガウス過程(NNGP)カーネルのランダム特徴近似(RFA)を用いた新しいアルゴリズムを提案する。
我々のアルゴリズムは、KIP上で少なくとも100倍のスピードアップを提供し、1つのGPUで実行できる。
RFA蒸留 (RFAD) と呼ばれる本手法は, 大規模データセットの精度において, KIP や他のデータセット凝縮アルゴリズムと競合して動作する。
論文 参考訳（メタデータ） (2022-10-21T15:56:13Z) - Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。
我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
論文 参考訳（メタデータ） (2022-10-14T01:42:05Z) - Asymmetric Scalable Cross-modal Hashing [51.309905690367835]
クロスモーダルハッシュは、大規模なマルチメディア検索問題を解決する方法として成功している。
これらの問題に対処する新しい非対称スケーラブルクロスモーダルハッシュ(ASCMH)を提案する。
我々のASCMHは、最先端のクロスモーダルハッシュ法よりも精度と効率の点で優れています。
論文 参考訳（メタデータ） (2022-07-26T04:38:47Z) - SreaMRAK a Streaming Multi-Resolution Adaptive Kernel Algorithm [60.61943386819384]
既存のKRRの実装では、すべてのデータがメインメモリに格納される必要がある。
KRRのストリーミング版であるStreaMRAKを提案する。
本稿では,2つの合成問題と2重振り子の軌道予測について紹介する。
論文 参考訳（メタデータ） (2021-08-23T21:03:09Z) - Exact Acceleration of K-Means++ and K-Means$\|$ [22.66983713481359]
K-Means++とK-Means$|$はK-meansの初期種を選択するデファクトツールとなっている。
我々は、K-Means++とK-Means$|$の最初のアクセラレーションを示すために、特殊三角不等式プルーニング戦略と動的優先度待ち行列を開発する。
論文 参考訳（メタデータ） (2021-05-06T20:22:55Z) - An Efficient $k$-modes Algorithm for Clustering Categorical Datasets [8.528384027684194]
我々は, OTQT と呼ばれる$k$-modes の斬新で効率的な実装を提供する。
OTQTは既存の$k$-modesアルゴリズムでは検出不可能な目的関数を改善するために更新されていることを証明している。
OTQTはイテレーション毎に常に正確で、最終最適化までほぼ常に高速である(一部のデータセットではわずかに遅い)。
論文 参考訳（メタデータ） (2020-06-06T18:41:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。