2015/07/21 by Roger Donaldson, Donaldson, Roger, Arijit Gupta +5
Computer Science · #Advanced Image and Video Retrieval Techniques #Data Management and Algorithms #FOS: Computer and information sciences #Image Retrieval and Classification Techniques #Information Retrieval (cs.IR) #Information Theory (cs.IT)
paper · pdf · doi:10.48550/arxiv.1507.05929
openalex publication_date 2015/07/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We give a practical random mapping that takes any set of documents represented as vectors in Euclidean space and then maps them to a sparse subset of the Hamming cube while retaining ordering of inter-vector inner products. Once represented in the sparse space, it is natural to index documents using commercial text-based search engines which are specialized to take advantage of this sparse and discrete structure for large-scale document retrieval. We give a theoretical analysis of the mapping scheme, characterizing exact asymptotic behavior and also giving non-asymptotic bounds which we verify through numerical simulations. We balance the theoretical treatment with several practical considerations; these allow substantial speed up of the method. We further illustrate the use of this method on search over two real data sets: a corpus of images represented by their color histograms, and a corpus of daily stock market index values.