2021/12/01 by Debajyoti Bera, Rameshwar Pratap, Bhisham Dev Verma
Computer Science · Mathematics · #Advanced Clustering Algorithms Research #Algorithm #Artificial intelligence #Categorical variable #Cluster analysis #Computer science #Curse of dimensionality #Data Stream Mining Techniques #Data mining #Decoding methods #Dimension (graph theory) #Dimensionality reduction #Face and Expression Recognition #Hamming code #Hamming distance #Hamming space #Hash function #Machine learning #Mathematics #Pattern recognition (psychology) #cs.LG
paper · pdf · doi:10.1109/tkde.2021.3132373
Accepted in IEEE Transactions on Knowledge and Data Engineering. Copyright IEEE, 1969
arxiv created 2021/12/01 · openalex publication_date 2021/12/03 · arxiv updated 2021/12/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
Categorical attributes are those that can take a discrete set of values, e.g., colours. This work is about compressing vectors over categorical attributes to low-dimension discrete vectors. The current hash-based methods compressing vectors over categorical attributes to low-dimension discrete vectors do not provide any guarantee on the Hamming distances between the compressed representations. Here we presentFSketchto create sketches for a sparse categorical data and an estimator to estimate the pairwise Hamming distances among the uncompressed data only from their sketches. We claim that these sketches can be used in the usual data mining tasks in place of the original data without compromising the quality of the task. For that we ensure that the sketches also are categorical, sparse, and the Hamming distance estimates are reasonably precise. Both the sketch construction and the Hamming distance estimation algorithms require just a single-pass; furthermore, changes to a data point can be incorporated into its sketch in an efficient manner. The compressibility depends upon how sparse the data is and is independent of the original dimension – making our algorithm attractive for many real-life scenarios. Our claims are backed by rigorous theoretical analysis of the properties ofFSketchand supplemented by extensive comparative evaluations with related algorithms on some real-world datasets. We show thatFSketchis significantly faster, and the accuracy obtained by using its sketches are among the top for the standard unsupervised tasks ofRMSE, clustering and similarity search.