Real-valued embeddings and sketches for fast distance and similarity estimation
type: Item
instance of: scholarly article
title: Real-valued embeddings and sketches for fast distance and similarity estimation
zbMATH Open document ID: 1359.62261
author: Yong-Cai Geng
author: Sumit K. Garg
published in: Cybernetics and Systems Analysis
publication date: 2017-02-07T00:00:00Z
Mathematics Subject Classification ID: 62H30
Mathematics Subject Classification ID: 68T05
Mathematics Subject Classification ID: 68-02
zbMATH DE Number: 6681578
zbMATH Keywords: distance
zbMATH Keywords: similarity
zbMATH Keywords: embedding
zbMATH Keywords: sketch
zbMATH Keywords: dimensionality reduction
zbMATH Keywords: random projection
zbMATH Keywords: sampling
zbMATH Keywords: Johnson-Lindenstrauss lemma
zbMATH Keywords: kernel similarity
zbMATH Keywords: similarity search
describes a project that uses: FLANN
MaRDI profile type: Publication
full work available at URL: s10559-016-9899-x
OpenAlex ID: W2555370675
cites work: Binary vectors for fast distance and similarity estimation
cites work: Encyclopedia of Distances
cites work: Q4821338
cites work: Nearest-neighbor-preserving embeddings
cites work: Oblivious string embeddings and edit distance approximations
cites work: Synopses for massive data: samples, histograms, wavelets, sketches
cites work: Extensions of Lipschitz mappings into a Hilbert space
cites work: Q4542583
cites work: Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
cites work: On variants of the Johnson–Lindenstrauss lemma
cites work: Optimal Bounds for Johnson-Lindenstrauss Transforms and Streaming Problems with Subconstant Error
cites work: Almost Optimal Explicit Johnson-Lindenstrauss Families
cites work: The Johnson-Lindenstrauss lemma is optimal for linear dimensionality reduction
cites work: The sub-Gaussian norm of a binary random variable
cites work: Low distortion embeddings for edit distance
cites work: A simple proof of the restricted isometry property for random matrices
cites work: New constructions of RIP matrices with fast multiplication and fewer rows
cites work: New and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry Property
cites work: Fast and RIP-optimal transforms
cites work: The Restricted Isometry Property of Subsampled Fourier Matrices
cites work: Toward a unified theory of sparse dimensionality reduction in Euclidean space
cites work: Two observations regarding embedding subsets of Euclidean spaces in normed spaces
cites work: Isometric sketching of any set via the Restricted Isometry Property
cites work: Empirical processes and random projections
cites work: Explicit dimension reduction and its applications
cites work: Sparser Johnson-Lindenstrauss Transforms
cites work: Q4829005
cites work: Algorithmic derandomization via complexity theory
cites work: Vector data transformation using random binary matrices
cites work: Q4821981
cites work: An algorithmic theory of learning: Robust concepts and random projection
cites work: An information statistics approach to data stream and communication complexity
cites work: Dimensionality reductions in \(\ell_{2}\) that preserve volumes and distance to affine spaces
cites work: One-bit compressed sensing by linear programming
cites work: The Fast Johnson–Lindenstrauss Transform and Approximate Nearest Neighbors
cites work: Dimension reduction by random hyperplane tessellations
cites work: The Mailman algorithm: a note on matrix-vector multiplication
cites work: Randomized projective methods for the construction of binary sparse vector representations
cites work: Formation of similarity-reflecting binary vectors with random binary projections
cites work: Fast dimension reduction using Rademacher series on dual BCH codes
cites work: Dense fast random projections and Lean Walsh transforms
cites work: An Almost Optimal Unrestricted Fast Johnson-Lindenstrauss Transform
cites work: Restricted isometries for partial random circulant matrices
cites work: Johnson-Lindenstrauss lemma for circulant matrices**
cites work: A variant of the Johnson-Lindenstrauss lemma for circulant matrices
cites work: Suprema of chaos processes and the restricted isometry property
cites work: New bounds for circulant Johnson-Lindenstrauss embeddings
cites work: A unified framework for linear dimensionality reduction in L1
cites work: A sparse Johnson-Lindenstrauss transform
cites work: Sparsity lower bounds for dimensionality reducing maps
cites work: Embedding the diamond graph in \(L_p\) and dimension reduction in \(L_1\)
cites work: On the impossibility of dimension reduction in l 1
cites work: Metric structures in \(L_1\): dimension, snowflakes, and average distortion
cites work: Near Linear Lower Bound for Dimension Reduction in L1

Real-valued embeddings and sketches for fast distance and similarity estimation (cites work)
cites work: The dimension of almost spherical sections of convex bodies

Real-valued embeddings and sketches for fast distance and similarity estimation (cites work)
cites work: Embedding \(l_ p^ m\) into \(l_ 1^ n\)

Real-valued embeddings and sketches for fast distance and similarity estimation (cites work)
cites work: Sketching and Embedding are Equivalent for Norms

Real-valued embeddings and sketches for fast distance and similarity estimation (cites work)
cites work: Restricted Isometry Property for General p-Norms.

Real-valued embeddings and sketches for fast distance and similarity estimation (cites work)
cites work: Dimension Reduction Techniques for l_p (1<p<2), with Applications

Real-valued embeddings and sketches for fast distance and similarity estimation (cites work)
cites work: Stable distributions, pseudorandom generators, embeddings, and data stream computation

Real-valued embeddings and sketches for fast distance and similarity estimation (cites work)
cites work: Q3579462

Real-valued embeddings and sketches for fast distance and similarity estimation (cites work)
cites work: Priority sampling for estimation of arbitrary subset sums

Real-valued embeddings and sketches for fast distance and similarity estimation (cites work)
cites work: Bottom-k and priority sampling, set similarity and subset sums with minimal independence

Real-valued embeddings and sketches for fast distance and similarity estimation (cites work)
cites work: Similarity estimation techniques from rounding algorithms

Real-valued embeddings and sketches for fast distance and similarity estimation (cites work)
cites work: Estimation for monotone sampling

Real-valued embeddings and sketches for fast distance and similarity estimation (cites work)
cites work: The Dissimilarity Representation for Pattern Recognition

Real-valued embeddings and sketches for fast distance and similarity estimation (cites work)
cites work: Graph Embedding in Vector Spaces by Means of Prototype Selection

Real-valued embeddings and sketches for fast distance and similarity estimation (cites work)
cites work: Q5528329

Real-valued embeddings and sketches for fast distance and similarity estimation (cites work)
cites work: Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)

Real-valued embeddings and sketches for fast distance and similarity estimation (cites work)
cites work: Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions

Real-valued embeddings and sketches for fast distance and similarity estimation (cites work)
cites work: The string edit distance matching problem with moves

Real-valued embeddings and sketches for fast distance and similarity estimation (cites work)
cites work: Vector representations for efficient comparison and search for similar strings

Real-valued embeddings and sketches for fast distance and similarity estimation (cites work)
cites work: Approximating Edit Distance in Near-Linear Time

Real-valued embeddings and sketches for fast distance and similarity estimation (cites work)
cites work: Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity

Real-valued embeddings and sketches for fast distance and similarity estimation (cites work)
cites work: Improved lower bounds for embeddings into L1

Real-valued embeddings and sketches for fast distance and similarity estimation (cites work)
cites work: Homomorphic fingerprints under misalignments

Real-valued embeddings and sketches for fast distance and similarity estimation (cites work)
cites work: Graph kernels

Real-valued embeddings and sketches for fast distance and similarity estimation (cites work)
cites work: A Comparison of Explicit and Implicit Graph Embedding Methods for Pattern Recognition

Real-valued embeddings and sketches for fast distance and similarity estimation (cites work)
cites work: Q3188054

Real-valued embeddings and sketches for fast distance and similarity estimation (cites work)
cites work: Uniform Sampling for Matrix Approximation

Real-valued embeddings and sketches for fast distance and similarity estimation (cites work)
cites work: SPSD matrix approximation vis column selection: theories, algorithms, and extensions

Real-valued embeddings and sketches for fast distance and similarity estimation (cites work)
cites work: An Introduction to Matrix Concentration Inequalities

Real-valued embeddings and sketches for fast distance and similarity estimation (cites work)
cites work: Q4645667

Real-valued embeddings and sketches for fast distance and similarity estimation (cites work)
cites work: Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernels

Real-valued embeddings and sketches for fast distance and similarity estimation (cites work)
cites work: Sketching Information Divergences

Real-valued embeddings and sketches for fast distance and similarity estimation (cites work)
cites work: Similarity search. The metric space approach.

Real-valued embeddings and sketches for fast distance and similarity estimation (cites work)
cites work: Foundations of multidimensional and metric data structures.

Real-valued embeddings and sketches for fast distance and similarity estimation (cites work)
cites work: Linear dimensionality reduction: survey, insights, and generalizations

Real-valued embeddings and sketches for fast distance and similarity estimation (cites work)
cites work: Metric learning: a survey

Real-valued embeddings and sketches for fast distance and similarity estimation (cites work)
cites work: Learning a priori constrained weighted majority votes

Real-valued embeddings and sketches for fast distance and similarity estimation (DOI)
DOI: 10.1007/S10559-016-9899-X