Database-friendly random projections: Johnson-Lindenstrauss with binary coins

2003/06/01 by Dimitris Achlioptas · 1,427 citations
Computer Science · Mathematics · #Advanced Image and Video Retrieval Techniques #Aggregate (composite) #Algorithm #Arithmetic #Artificial intelligence #Binary number #Block (permutation group theory) #Combinatorics #Computational Geometry and Mesh Generation #Computer science #Data Management and Algorithms #Discrete mathematics #Embedding #Euclidean geometry #Euclidean space #Geometry #Hyperplane #Mathematics #Pairwise comparison #Projection (relational algebra) #Set (abstract data type) #Space (punctuation)

paper · pdf · doi:10.1016/s0022-0000(03)00025-4

published in Journal of Computer and System Sciences 66(4), 671-687 (Elsevier BV)

openalex publication_date 2003/06/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/02

Cited by

• Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• The Fast Johnson–Lindenstrauss Transform and Approximate Nearest Neighbors
• OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings
• Sparse, Dense, and Attentional Representations for Text Retrieval
• Efficient Planning under Partial Observability with Unnormalized Q Functions and Spectral Learning
• A Survey on Hyperdimensional Computing aka Vector Symbolic Architectures, Part I: Models and Data Transformations
• Efficient Second Order Online Learning by Sketching
• Deep Fried Convnets
• Statistical optimality conditions for compressive ensembles
• Tensor Random Projection for Low Memory Dimension Reduction
• Analysis of SparseHash: an efficient embedding of set-similarity via sparse projections
• Compressive Sensing with Redundant Dictionaries and Structured\n Measurements
• Effective and Sparse Count-Sketch via k-means clustering
• Role Similarity Metric Based on Spanning Rooted Forest
• Johnson-Lindenstrauss lemma for circulant matrices
• Binarized Johnson-Lindenstrauss embeddings
• Random projections for linear programming
• Fast approximation of matrix coherence and statistical leverage
• Chernoff-Hoeffding Inequality and Applications
• Beyond Attributes: Adversarial Erasing Embedding Network for Zero-shot Learning
• Algorithms and Hardness for Linear Algebra on Geometric Graphs
• Near-Optimal Compression for the Planar Graph Metric
• Blazed oblique plane microscopy reveals scale-invariant inference of brain-wide population activity
• A Sparse Johnson--Lindenstrauss Transform
• Randomized algorithms for matrices and data
• Acceleration of Randomized Kaczmarz Method via the Johnson-Lindenstrauss\n Lemma
• Neural Random Projections for Language Modelling
• The GaussianSketch for Almost Relative Error Kernel Distance
• Scalable Initialization Methods for Large-Scale Clustering
• Feature Hashing for Large Scale Multitask Learning
• Semi-supervised Embedding Learning for High-dimensional Bayesian Optimization
• Predicting Training Time Without Training
• Application of Compressive Sensing Techniques in Distributed Sensor Networks: A Survey
• Winner-Take-All Computation in Spiking Neural Networks
• Notes on Randomized Algorithms
• Very Sparse Stable Random Projections, Estimators and Tail Bounds for Stable Random Projections
• Scaling Up Collaborative Filtering Data Sets through Randomized Fractal Expansions
• Structure-aware error bounds for linear classification with the zero-one loss
• Sparsity Lower Bounds for Dimensionality Reducing Maps
• Quantization Algorithms for Random Fourier Features
• Random Sampling for Distributed Coded Matrix Multiplication
• Hashing Algorithms for Large-Scale Learning
• Similarity preserving compressions of high dimensional sparse data
• Improved Practical Matrix Sketching with Guarantees
• Learning Latent Factors from Diversified Projections and its Applications to Over-Estimated and Weak Factors
• Sub-linear Memory Sketches for Near Neighbor Search on Streaming Data
• Row Sampling for Matrix Algorithms via a Non-Commutative Bernstein Bound
• Recipes for stable linear embeddings from Hilbert spaces to R^m
• On Learning from Ghost Imaging without Imaging
• Training Logistic Regression and SVM on 200GB Data Using b-Bit Minwise Hashing and Comparisons with Vowpal Wabbit (VW)
• Improving Similarity Search with High-dimensional Locality-sensitive Hashing
• Exploring Embedding Methods in Binary Hyperdimensional Computing: A Case Study for Motor-Imagery based Brain-Computer Interfaces
• An Analysis of Random Projections in Cancelable Biometrics
• Near neighbor preserving dimension reduction for doubling subsets of ℓ₁
• Stable Takens' Embeddings for Linear Dynamical Systems
• Optimized Kernel-based Projection Space of Riemannian Manifolds
• Sketching Datasets for Large-Scale Learning (long version)
• Random Projections for Linear Support Vector Machines
• Euclidean distortion and the Sparsest Cut
• ADAGIO: Fast Data-aware Near-Isometric Linear Embeddings
• Almost Optimal Explicit Johnson-Lindenstrauss Transformations
• Mixed Compressed Sensing Based on Random Graphs
• (2+ε)-ANN for time series under the Fréchet distance
• Particle systems and kinetic equations modeling interacting agents in high dimension
• Greedy type algorithms for RIP matrices. A study of two selection rules
• Incomplete Pivoted QR-based Dimensionality Reduction
• List-Decodable Mean Estimation in Nearly-PCA Time
• An Improved Frequent Directions Algorithm for Low-Rank Approximation via Block Krylov Iteration
• Randomized Gram-Schmidt process with application to GMRES
• Efficient Gaussian Process Regression for Large Data Sets
• Recovering the Optimal Solution by Dual Random Projection
• Randomness Efficient Fast-Johnson-Lindenstrauss Transform with Applications in Differential Privacy and Compressed Sensing
• Accumulation of Sub-Sampling Matrices with Applications to Statistical Computation
• Robust Regression Revisited: Acceleration and Improved Estimation Rates
• Failing Loudly: An Empirical Study of Methods for Detecting Dataset Shift
• Asymptotically exact streaming algorithms
• Robustness Properties of Dimensionality Reduction with Gaussian Random Matrices
• The Rare Eclipse Problem on Tiles: Quantised Embeddings of Disjoint Convex Sets
• Breaking the Multicommodity Flow Barrier for sqrt(log(n))-Approximations to Sparsest Cut
• Nonuniform Sparse Recovery with Subgaussian Matrices
• Contextual Bandits with Random Projection
• Lower Memory Oblivious (Tensor) Subspace Embeddings with Fewer Random Bits: Modewise Methods for Least Squares
• Greedy Column Subset Selection for Large-scale Data Sets
• Numerical Solution of Stiff ODEs with Physics-Informed RPNNs
• Random Projections for k-means Clustering
• Randomized Interpolative Decomposition of Separated Representations
• Optimal Bounds for Johnson-Lindenstrauss Transformations
• Gradient tree boosting with random output projections for multi-label classification and multi-output regression
• A Derandomized Sparse Johnson-Lindenstrauss Transform
• Finding the Mode of a Kernel Density Estimate
• Guided projections for analysing the structure of high-dimensional data
• Binary embeddings with structured hashed projections
• Faster Least Squares Optimization
• Tensorized Random Projections
• Precise expressions for random projections: Low-rank approximation and randomized Newton
• Rademacher Chaos, Random Eulerian Graphs and The Sparse Johnson-Lindenstrauss Transform
• High-dimensional clustering via Random Projections
• Estimating informativeness of samples with Smooth Unique Information
• Fast and RIP-optimal transforms
• Sparse Matrix-based Random Projection for Classification
• Scalable Realistic Recommendation Datasets through Fractal Expansions
• Dynamic Streaming Spectral Sparsification in Nearly Linear Time and Space
• Fast and Accurate Network Embeddings via Very Sparse Random Projection
• Compressed dynamic mode decomposition for background modeling
• A survey on unsupervised outlier detection in high‐dimensional numerical data
• Compressive Spectral Clustering
• Dimensionality Reduction for k-means Clustering
• Efficient Inference via Universal LSH Kernel
• Stochastic Newton and Quasi-Newton Methods for Large Linear\n Least-squares Problems
• Model-based clustering in very high dimensions via adaptive projections
• Principal Component Analysis and Higher Correlations for Distributed\n Data
• Dimensionality Reduction for Categorical Data
• Tight oracle bounds for low-rank matrix recovery from a minimal number of random measurements
• Compressive matched-field processing
• The Effectiveness of Johnson-Lindenstrauss Transform for High Dimensional Optimization With Adversarial Outliers, and the Recovery
• Continual Learning in Practice
• Rademacher Random Projections with Tensor Networks
• Clustering articles based on semantic similarity
• Computationally Efficient Estimators for Dimension Reductions Using Stable Random Projections
• Johnson–Lindenstrauss lemma [wikipedia]
• Efficient techniques for genotype-phenotype correlational analysis. [europepmc]
• Machine learning methods in the computational biology of cancer. [europepmc]
• Scale adaptive compressive tracking. [europepmc]
• A theorem proving approach for automatically synthesizing visualizations of flow cytometry data. [europepmc]
• Iterative Schemes to Solve Low-Dimensional Calibration Equations in Parallel MR Image Reconstruction with GRAPPA. [europepmc]
• Fast Constrained Spectral Clustering and Cluster Ensemble with Random Projection. [europepmc]
• An evaluation of multi-probe locality sensitive hashing for computing similarities over web-scale query logs. [europepmc]
• Random selection of factors preserves the correlation structure in a linear factor model to a high degree. [europepmc]
• A Method of Constructing Measurement Matrix for Compressed Sensing by Chebyshev Chaotic Sequence. [europepmc]
• Symbolic, Distributed, and Distributional Representations for Natural Language Processing in the Era of Deep Learning: A Survey. [europepmc]
• Stochastic quasi-gradient methods: variance reduction via Jacobian sketching. [europepmc]
• Design and Application of Deep Hash Embedding Algorithm with Fusion Entity Attribute Information. [europepmc]
• Blazed oblique plane microscopy reveals scale-invariant inference of brain-wide population activity. [europepmc]
• Utilizing Low-Dimensional Molecular Embeddings for Rapid Chemical Similarity Search. [europepmc]
• Anchor objects drive realism while diagnostic objects drive categorization in GAN generated scenes. [europepmc]
• Principled neuromorphic reservoir computing. [europepmc]
• Prediction of drug target interaction based on under sampling strategy and random forest algorithm. [europepmc]
• Recent Advances in Text-to-Pattern Distance Algorithms [europepmc]
• Almost Universally Optimal Distributed Laplacian Solvers via Low-Congestion Shortcuts [europepmc]