Inverted-File k-Means Clustering: Performance Analysis

• URL: http://arxiv.org/abs/2002.09094v1
• Date: Fri, 21 Feb 2020 02:20:33 GMT
• Title: Inverted-File k-Means Clustering: Performance Analysis
• Authors: Kazuo Aoyama, Kazumi Saito, and Tetsuo Ikeda
• Abstract summary: inverted-file k-means clustering algorithm (IVF) suitable for a large-scale sparse data set with potentially numerous classes. We experimentally demonstrate that IVF achieves better performance than the designed algorithms.
• Score: 1.3955252961896318
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper presents an inverted-file k-means clustering algorithm (IVF) suitable for a large-scale sparse data set with potentially numerous classes. Given such a data set, IVF efficiently works at high-speed and with low memory consumption, which keeps the same solution as a standard Lloyd's algorithm. The high performance arises from two distinct data representations. One is a sparse expression for both the object and mean feature vectors. The other is an inverted-file data structure for a set of the mean feature vectors. To confirm the effect of these representations, we design three algorithms using distinct data structures and expressions for comparison. We experimentally demonstrate that IVF achieves better performance than the designed algorithms when they are applied to large-scale real document data sets in a modern computer system equipped with superscalar out-of-order processors and a deep hierarchical memory system. We also introduce a simple yet practical clock-cycle per instruction (CPI) model for speed-performance analysis. Analytical results reveal that IVF suppresses three performance degradation factors: the numbers of cache misses, branch mispredictions, and the completed instructions.

Related papers

• Accelerating spherical K-means clustering for large-scale sparse document data [0.7366405857677226]
  This paper presents an accelerated spherical K-means clustering algorithm for large-scale and high-dimensional sparse document data sets. We experimentally demonstrate that our algorithm efficiently achieves superior speed performance in large-scale documents compared with algorithms using the state-of-the-art techniques.
  arXiv  Detail & Related papers  (2024-11-18T05:50:58Z)
• Compact Neural Graphics Primitives with Learned Hash Probing [100.07267906666293]
  We show that a hash table with learned probes has neither disadvantage, resulting in a favorable combination of size and speed. Inference is faster than unprobed hash tables at equal quality while training is only 1.2-2.6x slower.
  arXiv  Detail & Related papers  (2023-12-28T18:58:45Z)
• Efficient Match Pair Retrieval for Large-scale UAV Images via Graph Indexed Global Descriptor [9.402103660431791]
  This paper proposes an efficient match pair retrieval method and implements an integrated workflow for parallel SfM reconstruction. The proposed solution has been verified using three large-scale datasets.
  arXiv  Detail & Related papers  (2023-07-10T12:41:55Z)
• Performance Embeddings: A Similarity-based Approach to Automatic Performance Optimization [71.69092462147292]
  Performance embeddings enable knowledge transfer of performance tuning between applications. We demonstrate this transfer tuning approach on case studies in deep neural networks, dense and sparse linear algebra compositions, and numerical weather prediction stencils.
  arXiv  Detail & Related papers  (2023-03-14T15:51:35Z)
• UNETR++: Delving into Efficient and Accurate 3D Medical Image Segmentation [93.88170217725805]
  We propose a 3D medical image segmentation approach, named UNETR++, that offers both high-quality segmentation masks as well as efficiency in terms of parameters, compute cost, and inference speed. The core of our design is the introduction of a novel efficient paired attention (EPA) block that efficiently learns spatial and channel-wise discriminative features. Our evaluations on five benchmarks, Synapse, BTCV, ACDC, BRaTs, and Decathlon-Lung, reveal the effectiveness of our contributions in terms of both efficiency and accuracy.
  arXiv  Detail & Related papers  (2022-12-08T18:59:57Z)
• Rethinking Space-Time Networks with Improved Memory Coverage for Efficient Video Object Segmentation [68.45737688496654]
  We establish correspondences directly between frames without re-encoding the mask features for every object. With the correspondences, every node in the current query frame is inferred by aggregating features from the past in an associative fashion. We validated that every memory node now has a chance to contribute, and experimentally showed that such diversified voting is beneficial to both memory efficiency and inference accuracy.
  arXiv  Detail & Related papers  (2021-06-09T16:50:57Z)
• Structured Inverted-File k-Means Clustering for High-Dimensional Sparse Data [2.487445341407889]
  This paper presents an architecture-friendly k-means clustering algorithm called SIVF for a large-scale and high-dimensional sparse data set. Our performance analysis reveals that SIVF achieves the higher speed by suppressing performance degradation factors of the number of cache misses and branch mispredictions.
  arXiv  Detail & Related papers  (2021-03-30T07:54:02Z)
• Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature Selection [138.97647716793333]
  We propose a simple and efficient unsupervised feature selection method, by combining reconstruction error with $l_2,p$-norm regularization. We present an efficient optimization algorithm to solve the proposed unsupervised model, and analyse the convergence and computational complexity of the algorithm theoretically.
  arXiv  Detail & Related papers  (2020-12-29T04:08:38Z)
• DHOG: Deep Hierarchical Object Grouping [0.0]
  We show that greedy or local methods of maximising mutual information (such as gradient optimisation) discover local optima of the mutual information criterion. We introduce deep hierarchical object grouping (DHOG) that computes a number distinct discrete representations of images in a hierarchical order. We find that these representations align better with the downstream task of grouping into underlying object classes.
  arXiv  Detail & Related papers  (2020-03-13T14:11:48Z)
• New advances in enumerative biclustering algorithms with online partitioning [80.22629846165306]
  This paper further extends RIn-Close_CVC, a biclustering algorithm capable of performing an efficient, complete, correct and non-redundant enumeration of maximal biclusters with constant values on columns in numerical datasets. The improved algorithm is called RIn-Close_CVC3, keeps those attractive properties of RIn-Close_CVC, and is characterized by: a drastic reduction in memory usage; a consistent gain in runtime.
  arXiv  Detail & Related papers  (2020-03-07T14:54:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.