Cluster-aware compression with provable k-means preservation

Nikolaos M. Freris, Michail Vlachos, Deepak S. Turaga

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

This work rigorously explores the design of clusterpreserving compression schemes for high-dimensional data. We focus on the K-means algorithm and identify conditions under which running the algorithm on the compressed data yields the same clustering outcome as on the original. The compression is performed using single and multi-bit minimum mean square error quantization schemes as well as a given clustering assignment of the original data. We provide theoretical guarantees on post-quantization cluster preservation under certain conditions on the cluster structure, and propose an additional data transformation that can ensure cluster preservation unconditionally; this transformation is invertible and thus induces virtually no distortion on the compressed data. In addition, we provide an efficient scheme for multi-bit allocation, per cluster and data dimension, which enables a trade-off between high compression efficiency and low data distortion. Our experimental studies highlight that the suggested scheme accurately preserved the clusters formed in all cases, while incurring minimal distortion on the data shapes. Our results can find many applications, e.g., in a) clustering, analysis and distribution of massive datasets, where the proposed data compression can boost performance while providing provable guarantees on the clustering result, as well as, in b) cloud computing services, as the optional transformation provides a data-hiding functionality in addition to preserving the K-means clustering outcome.

Original languageEnglish (US)
Title of host publicationProceedings of the 12th SIAM International Conference on Data Mining, SDM 2012
PublisherSociety for Industrial and Applied Mathematics Publications
Pages82-93
Number of pages12
ISBN (Print)9781611972320
DOIs
StatePublished - 2012
Event12th SIAM International Conference on Data Mining, SDM 2012 - Anaheim, CA, United States
Duration: Apr 26 2012Apr 28 2012

Publication series

NameProceedings of the 12th SIAM International Conference on Data Mining, SDM 2012

Other

Other12th SIAM International Conference on Data Mining, SDM 2012
Country/TerritoryUnited States
CityAnaheim, CA
Period4/26/124/28/12

Keywords

  • Cluster preservation
  • Clustering
  • Compression
  • K-means
  • Mmse quantization

ASJC Scopus subject areas

  • Computer Science Applications

Fingerprint

Dive into the research topics of 'Cluster-aware compression with provable k-means preservation'. Together they form a unique fingerprint.

Cite this