2014/05/22 by Michail Vlachos, Vlachos, Michail, Nikolaos M. Freris +3
Computer Science · Engineering · #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Information Theory (cs.IT) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Medical Image Segmentation Techniques #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.1405.5873
openalex publication_date 2014/05/22 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28
Real-world data typically contain repeated and periodic patterns. This\nsuggests that they can be effectively represented and compressed using only a\nfew coefficients of an appropriate basis (e.g., Fourier, Wavelets, etc.).\nHowever, distance estimation when the data are represented using different sets\nof coefficients is still a largely unexplored area. This work studies the\noptimization problems related to obtaining the \tightest lower/upper\nbound on Euclidean distances when each data object is potentially compressed\nusing a different set of orthonormal coefficients. Our technique leads to\ntighter distance estimates, which translates into more accurate search,\nlearning and mining operations \directly in the compressed domain.\n We formulate the problem of estimating lower/upper distance bounds as an\noptimization problem. We establish the properties of optimal solutions, and\nleverage the theoretical analysis to develop a fast algorithm to obtain an\n\exact solution to the problem. The suggested solution provides the\ntightest estimation of the L2-norm or the correlation. We show that typical\ndata-analysis operations, such as k-NN search or k-Means clustering, can\noperate more accurately using the proposed compression and distance\nreconstruction technique. We compare it with many other prevalent compression\nand reconstruction techniques, including random projections and PCA-based\ntechniques. We highlight a surprising result, namely that when the data are\nhighly sparse in some basis, our technique may even outperform PCA-based\ncompression.\n The contributions of this work are generic as our methodology is applicable\nto any sequential or high-dimensional data as well as to any orthogonal data\ntransformation used for the underlying data compression scheme.\n