# OPORP: One Permutation + One Random Projection

arXiv: https://arxiv.org/abs/2302.03505 · HTML: https://mlsanity.com/paper/2302.03505/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 87 references that are in the map.
- First posted on arXiv 7 Feb 2023.

## Builds on (most cited first, 29 of 29)

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [Reading Wikipedia to Answer Open-Domain Questions](https://mlsanity.com/paper/1704.00051/) (2017)
- [Text and Code Embeddings by Contrastive Pre-Training](https://mlsanity.com/paper/2201.10005/) (2022)
- [DeCLUTR: Deep Contrastive Learning for Unsupervised Textual Representations](https://mlsanity.com/paper/2006.03659/) (2020)
- [Failing Loudly: An Empirical Study of Methods for Detecting Dataset Shift](https://mlsanity.com/paper/1810.11953/) (2018)
- [Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoising](https://mlsanity.com/paper/1805.06530/) (2018)
- [FetchSGD: Communication-Efficient Federated Learning with Sketching](https://mlsanity.com/paper/2007.07682/) (2020)
- [Pre-training Tasks for Embedding-based Large-scale Retrieval](https://mlsanity.com/paper/2002.03932/) (2020)
- [Compressing Neural Networks with the Hashing Trick](https://mlsanity.com/paper/1504.04788/) (2015)
- [General Multi-label Image Classification with Transformers](https://mlsanity.com/paper/2011.14027/) (2020)
- [Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS)](https://mlsanity.com/paper/1405.5869/) (2014)
- [Deep Fragment Embeddings for Bidirectional Image Sentence Mapping](https://mlsanity.com/paper/1406.5679/) (2014)
- [Federated Reconstruction: Partially Local Federated Learning](https://mlsanity.com/paper/2102.03448/) (2021)
- [DEMO-Net: Degree-specific Graph Neural Networks for Node and Graph Classification](https://mlsanity.com/paper/1906.02319/) (2019)
- [Hierarchical Bilinear Pooling for Fine-Grained Visual Recognition](https://mlsanity.com/paper/1807.09915/) (2018)
- [Experiments with Random Projection](https://mlsanity.com/paper/1301.3849/) (2013)
- [Dynamic Malware Analysis with Feature Engineering and Feature Learning](https://mlsanity.com/paper/1907.07352/) (2019)
- [FedSKETCH: Communication-Efficient and Private Federated Learning via Sketching](https://mlsanity.com/paper/2008.04975/) (2020)
- [Sparse Projection Oblique Randomer Forests](https://mlsanity.com/paper/1506.03410/) (2015)
- [One-bit compressive sensing with norm estimation](https://mlsanity.com/paper/1404.6853/) (2014)
- [Individual Differential Privacy: A Utility-Preserving Formulation of Differential Privacy Guarantees](https://mlsanity.com/paper/1612.02298/) (2016)
- [Coding for Random Projections](https://mlsanity.com/paper/1308.2218/) (2013)
- [Sign-Full Random Projections](https://mlsanity.com/paper/1805.00533/) (2018)
- [GCWSNet: Generalized Consistent Weighted Sampling for Scalable and Accurate Training of Neural Networks](https://mlsanity.com/paper/2201.02283/) (2022)
- [A Memory-Efficient Sketch Method for Estimating High Similarities in Streaming Sets](https://mlsanity.com/paper/1905.08977/) (2019)
- [Boost CTR Prediction for New Advertisements via Modeling Visual Content](https://mlsanity.com/paper/2209.11727/) (2022)
- [Finding the Needle in a Haystack: On the Automatic Identification of Accessibility User Reviews](https://mlsanity.com/paper/2210.09947/) (2022)

## Built on by (most cited first, 12 of 12)

- [Token-wise Influential Training Data Retrieval for Large Language Models](https://mlsanity.com/paper/2405.11724/) (2024)
- [Understanding Impact of Human Feedback via Influence Functions](https://mlsanity.com/paper/2501.05790/) (2025)
- [GraSS: Scalable Data Attribution with Gradient Sparsification and Sparse Projection](https://mlsanity.com/paper/2505.18976/) (2025)
- [Differential Privacy with Random Projections and Sign Random Projections](https://mlsanity.com/paper/2306.01751/) (2023)
- [Scout Before You Attend: Sketch-and-Walk Sparse Attention for Efficient LLM Inference](https://mlsanity.com/paper/2602.07397/) (2026)
- [Differentially Private One Permutation Hashing and Bin-wise Consistent Weighted Sampling](https://mlsanity.com/paper/2306.07674/) (2023)
- [DMin: Scalable Training Data Influence Estimation for Diffusion Models](https://mlsanity.com/paper/2412.08637/) (2024)
- [LiNR: Model Based Neural Retrieval on GPUs at LinkedIn](https://mlsanity.com/paper/2407.13218/) (2024)
- [Learning to Retrieve for Job Matching](https://mlsanity.com/paper/2402.13435/) (2024)
- [Quality over Quantity: Demonstration Curation via Influence Functions for Data-Centric Robot Learning](https://mlsanity.com/paper/2603.09056/) (2026)
- [Sketching the Readout of Large Language Models for Scalable Data Attribution and Valuation](https://mlsanity.com/paper/2604.16197/) (2026)
- [HIVE: Hidden-Evidence Verification for Hallucination Detection in Diffusion Large Language Models](https://mlsanity.com/paper/2604.26139/) (2026)

## Abstract (arXiv)

Consider two D-dimensional data vectors (e.g., embeddings): u, v. In many embedding-based retrieval (EBR) applications where the vectors are generated from trained models, D=256~ 1024 are common. In this paper, OPORP (one permutation + one random projection) uses a variant of the ``count-sketch'' type of data structures for achieving data reduction/compression. With OPORP, we first apply a permutation on the data vectors. A random vector r is generated i.i.d. with moments: E(ri) = 0, E(ri2)=1, E(ri3) =0, E(ri4)=s. We multiply (as dot product) r with all permuted data vectors. Then we break the D columns into k equal-length bins and aggregate (i.e., sum) the values in each bin to obtain k samples from each data vector. One crucial step is to normalize the k samples to the unit l2 norm. We show that the estimation variance is essentially: (s-1)A + fracD-kD-1frac1kleft[ (1-ρ2)2 -2Aright], where A≥ 0 is a function of the data (u,v). This formula reveals several key properties: (1) We need s=1. (2) The factor fracD-kD-1 can be highly beneficial in reducing variances. (3) The term frac1k(1-ρ2)2 is a substantial improvement compared with frac1k(1+ρ2), which corresponds to the un-normalized estimator. We illustrate that by letting the k in OPORP to be k=1 and repeat the procedure m times, we exactly recover the work of ``very spars random projections'' (VSRP). This immediately leads to a normalized estimator for VSRP which substantially improves the original estimator of VSRP. In summary, with OPORP, the two key steps: (i) the normalization and (ii) the fixed-length binning scheme, have considerably improved the accuracy in estimating the cosine similarity, which is a routine (and crucial) task in modern embedding-based retrieval (EBR) applications.