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.

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keymorvan2017streaming

Related papers

• Sub-linear Memory Sketches For Near Neighbor Search On Streaming Data (2019)0.00
• Nearest Neighbor Search With Compact Codes: A Decoder Perspective (2021)3.58
• Simisketch: Efficiently Estimating Similarity Of Streaming Multisets (2024)0.00
• A Memory-efficient Sketch Method For Estimating High Similarities In Streaming Sets (2019)12.02
• Online Hashing With Efficient Updating Of Binary Codes (2019)8.09
• Polysemous Codes (2016)11.49
• Clustering The Sketch: A Novel Approach To Embedding Table Compression (2022)0.00
• Fast Similarity Sketching (2017)9.41