Real-valued embeddings and sketches for fast distance and similarity estimation

DOI10.1007/S10559-016-9899-XzbMATH Open1359.62261OpenAlexW2555370675MaRDI QIDQ508585FDOQ508585

Authors: Yong-Cai Geng, Sumit K. Garg 

Publication date: 7 February 2017

Published in: Cybernetics and Systems Analysis (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10559-016-9899-x

Recommendations

• Binary vectors for fast distance and similarity estimation
• Estimation of vectors similarity by their randomized binary projections
• Index structures for fast similarity search for real-valued vectors. I
• Selecting Sketches for Similarity Search
• Index structures for fast similarity search for real vectors. II

zbMATH Keywords

samplingdimensionality reductiondistancesketchembeddingsimilarityrandom projectionsimilarity searchJohnson-Lindenstrauss lemmakernel similarity

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Learning and adaptive systems in artificial intelligence (68T05) Research exposition (monographs, survey articles) pertaining to computer science (68-02)

Cites Work

• Extensions of Lipschitz mappings into a Hilbert space
• Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
• A simple proof of the restricted isometry property for random matrices
• Fast dimension reduction using Rademacher series on dual BCH codes
• Graph kernels
• Sparsity lower bounds for dimensionality reducing maps
• An introduction to matrix concentration inequalities
• Linear dimensionality reduction: survey, insights, and generalizations
• The Dissimilarity Representation for Pattern Recognition
• Similarity estimation techniques from rounding algorithms
• Title not available (Why is that?)
• The dimension of almost spherical sections of convex bodies
• Embedding the diamond graph in \(L_p\) and dimension reduction in \(L_1\)
• Foundations of multidimensional and metric data structures.
• Metric structures in \(L_1\): dimension, snowflakes, and average distortion
• On the impossibility of dimension reduction in l ₁
• Priority sampling for estimation of arbitrary subset sums
• Title not available (Why is that?)
• Title not available (Why is that?)
• Bottom-k and priority sampling, set similarity and subset sums with minimal independence
• Title not available (Why is that?)
• One-bit compressed sensing by linear programming
• Title not available (Why is that?)
• Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
• Suprema of chaos processes and the restricted isometry property
• An Almost Optimal Unrestricted Fast Johnson-Lindenstrauss Transform
• New and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry Property
• On variants of the Johnson–Lindenstrauss lemma
• New constructions of RIP matrices with fast multiplication and fewer rows
• An information statistics approach to data stream and communication complexity
• The string edit distance matching problem with moves
• A unified framework for linear dimensionality reduction in L1
• Stable distributions, pseudorandom generators, embeddings, and data stream computation
• Title not available (Why is that?)
• Restricted isometries for partial random circulant matrices
• Randomized projective methods for the construction of binary sparse vector representations
• Vector data transformation using random binary matrices
• Embedding \(l_ p^ m\) into \(l_ 1^ n\)
• Near Linear Lower Bound for Dimension Reduction in L1
• The fast Johnson-Lindenstrauss transform and approximate nearest neighbors
• The Restricted Isometry Property of Subsampled Fourier Matrices
• A variant of the Johnson-Lindenstrauss lemma for circulant matrices
• Improved lower bounds for embeddings into L₁
• The Mailman algorithm: a note on matrix-vector multiplication
• Nearest-neighbor-preserving embeddings
• Empirical processes and random projections
• Similarity search. The metric space approach.
• Two observations regarding embedding subsets of Euclidean spaces in normed spaces
• New bounds for circulant Johnson-Lindenstrauss embeddings
• Johnson-Lindenstrauss lemma for circulant matrices
• A sparse Johnson-Lindenstrauss transform
• Sparser Johnson-Lindenstrauss transforms
• The Johnson-Lindenstrauss lemma is optimal for linear dimensionality reduction
• Toward a unified theory of sparse dimensionality reduction in Euclidean space
• Homomorphic fingerprints under misalignments
• Dimension reduction by random hyperplane tessellations
• Binary vectors for fast distance and similarity estimation
• Dimensionality reductions in \(\ell_{2}\) that preserve volumes and distance to affine spaces
• Vector representations for efficient comparison and search for similar strings
• An algorithmic theory of learning: Robust concepts and random projection
• Learning a priori constrained weighted majority votes
• Fast and RIP-optimal transforms
• Formation of similarity-reflecting binary vectors with random binary projections
• SPSD matrix approximation vis column selection: theories, algorithms, and extensions
• Metric learning: a survey
• Explicit dimension reduction and its applications
• Synopses for massive data: samples, histograms, wavelets, sketches
• The sub-Gaussian norm of a binary random variable
• Optimal bounds for Johnson-Lindenstrauss transforms and streaming problems with subconstant error
• Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
• Sketching and embedding are equivalent for norms
• Estimation for monotone sampling
• Uniform Sampling for Matrix Approximation
• Almost Optimal Explicit Johnson-Lindenstrauss Families
• Dimension Reduction Techniques for l_p (1<p<2), with Applications
• Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernels
• Algorithmic derandomization via complexity theory
• Oblivious string embeddings and edit distance approximations
• Title not available (Why is that?)
• Title not available (Why is that?)
• Approximating edit distance in near-linear time
• A comparison of explicit and implicit graph embedding methods for pattern recognition
• Polylogarithmic approximation for edit distance and the asymmetric query complexity
• Isometric sketching of any set via the Restricted Isometry Property
• Graph Embedding in Vector Spaces by Means of Prototype Selection
• Restricted Isometry Property for General p-Norms.
• Sketching Information Divergences
• Encyclopedia of Distances
• Low distortion embeddings for edit distance
• Dense fast random projections and Lean Walsh transforms

Cited In (12)

• A linear system output transformation for sparse approximation
• Distance-based index structures for fast similarity search
• Index structures for fast similarity search for real vectors. II
• Binary vectors for fast distance and similarity estimation
• Index structures for fast similarity search for real-valued vectors. I
• Index structures for fast similarity search for binary vectors
• Index structures for fast similarity search for symbol strings
• Fast similarity search for graphs by edit distance
• Rademacher-Sketch: A Dimensionality-Reducing Embedding for Sum-Product Norms, with an Application to Earth-Mover Distance
• Title not available (Why is that?)
• Technology of autonomous take-off and landing for the modern flight and navigation complex of an unmanned aerial vehicle
• Selecting Sketches for Similarity Search

Uses Software

• FLANN

This page was built for publication: Real-valued embeddings and sketches for fast distance and similarity estimation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q508585)