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

DOI10.1007/s10559-016-9899-xzbMath1359.62261OpenAlexW2555370675MaRDI QIDQ508585

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

zbMATH Keywords

samplingsketchembeddingdistancesimilaritydimensionality reductionrandom 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)

Related Items

Binary vectors for fast distance and similarity estimation, Fast similarity search for graphs by edit distance, Technology of autonomous take-off and landing for the modern flight and navigation complex of an unmanned aerial vehicle, Distance-based index structures for fast similarity search, 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 real vectors. II, Index structures for fast similarity search for symbol strings, A linear system output transformation for sparse approximation

Uses Software

• FLANN

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions
• A unified framework for linear dimensionality reduction in L1
• Randomized projective methods for the construction of binary sparse vector representations
• Restricted isometries for partial random circulant matrices
• New bounds for circulant Johnson-Lindenstrauss embeddings
• Toward a unified theory of sparse dimensionality reduction in Euclidean space
• An information statistics approach to data stream and communication complexity
• A variant of the Johnson-Lindenstrauss lemma for circulant matrices
• Dense fast random projections and Lean Walsh transforms
• Two observations regarding embedding subsets of Euclidean spaces in normed spaces
• Vector data transformation using random binary matrices
• The Mailman algorithm: a note on matrix-vector multiplication
• A simple proof of the restricted isometry property for random matrices
• Fast dimension reduction using Rademacher series on dual BCH codes
• Embedding \(l_ p^ m\) into \(l_ 1^ n\)
• The dimension of almost spherical sections of convex bodies
• Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
• Embedding the diamond graph in \(L_p\) and dimension reduction in \(L_1\)
• 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
• Foundations of multidimensional and metric data structures.
• 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
• Empirical processes and random projections
• Metric structures in \(L_1\): dimension, snowflakes, and average distortion
• Similarity search. The metric space approach.
• One-Bit Compressed Sensing by Linear Programming
• Metric Learning: A Survey
• A sparse Johnson
• Explicit Dimension Reduction and Its Applications
• Synopses for Massive Data: Samples, Histograms, Wavelets, Sketches
• The sub-Gaussian norm of a binary random variable
• Suprema of Chaos Processes and the Restricted Isometry Property
• An Almost Optimal Unrestricted Fast Johnson-Lindenstrauss Transform
• 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
• The string edit distance matching problem with moves
• Uniform Sampling for Matrix Approximation
• Almost Optimal Explicit Johnson-Lindenstrauss Families
• Johnson-Lindenstrauss lemma for circulant matrices**
• New and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry Property
• Dimension Reduction Techniques for l_p (1<p<2), with Applications
• Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernels
• Sparser Johnson-Lindenstrauss Transforms
• Extensions of Lipschitz mappings into a Hilbert space
• The Dissimilarity Representation for Pattern Recognition
• Stable distributions, pseudorandom generators, embeddings, and data stream computation
• On variants of the Johnson–Lindenstrauss lemma
• On the impossibility of dimension reduction in l ₁
• Priority sampling for estimation of arbitrary subset sums
• Algorithmic derandomization via complexity theory
• Similarity estimation techniques from rounding algorithms
• Nearest-neighbor-preserving embeddings
• Oblivious string embeddings and edit distance approximations
• Improved lower bounds for embeddings into L₁
• The Johnson-Lindenstrauss lemma is optimal for linear dimensionality reduction
• 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
• The Fast Johnson–Lindenstrauss Transform and Approximate Nearest Neighbors
• Isometric sketching of any set via the Restricted Isometry Property
• The Restricted Isometry Property of Subsampled Fourier Matrices
• Graph Embedding in Vector Spaces by Means of Prototype Selection
• Restricted Isometry Property for General p-Norms.
• New constructions of RIP matrices with fast multiplication and fewer rows
• Sketching Information Divergences
• Near Linear Lower Bound for Dimension Reduction in L1
• Sparsity lower bounds for dimensionality reducing maps
• Bottom-k and priority sampling, set similarity and subset sums with minimal independence
• Homomorphic fingerprints under misalignments
• An Introduction to Matrix Concentration Inequalities
• Encyclopedia of Distances
• Low distortion embeddings for edit distance