Streaming Binary Sketching Based on Subspace Tracking and Diagonal Uniformization
Abstract
In this paper, we address the problem of learning compact similarity-preserving embeddings for massive high-dimensional streams of data in order to perform efficient similarity search. We present a new online method for computing binary compressed representations -sketches- of high-dimensional real feature vectors. Given an expected code length c and high-dimensional input data points, our algorithm provides a c-bits binary code for preserving the distance between the points from the original high-dimensional space. Our algorithm does not require neither the storage of the whole dataset nor a chunk, thus it is fully adaptable to the streaming setting. It also provides low time complexity and convergence guarantees. We demonstrate the quality of our binary sketches through experiments on real data for the nearest neighbors search task in the online setting.
Keywords
machine learning
signal processing
online learning
learning compact similarity-preserving embedding
big data
data stream
efficient similarity search
data mining
binary compressed representation
high-dimensional real feature vectors
high-dimensional input data points
high-dimensional space
adaptability
complexity
convergence guarantee
Sketching
streaming
subspace tracking
Given rotations
Time Complexity
Original Space
Binary Code
Nearest Neighbor Search
Low Time Complexity
Training Set
Symmetric Matrix
Projection Matrix
Hash Function
Orthogonal Matrix
Random Rotation
Locality Sensitive Hashing
Origin : Files produced by the author(s)