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
samplingdimensionality reductiondistancesketchembeddingsimilarityrandom projectionsimilarity searchJohnson-Lindenstrauss lemmakernel similarity
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 1
- 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 L1
- 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
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)