mlsanityData to 14 Oct 2026

OPORP: One Permutation + One Random Projection

arXiv 2302.03505 ↗First posted 7 Feb 2023stat.ML cs.LGcited by 12

Not on the map. Why?

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.

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

29 of 87 references.

References · 29

  1. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,399
  2. 2020Language Models are Few-Shot Learnerscited by 32,419
  3. 2016Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphscited by 861
  4. 2017Reading Wikipedia to Answer Open-Domain Questionscited by 777
  5. 2022Text and Code Embeddings by Contrastive Pre-Trainingcited by 361
  6. 2020DeCLUTR: Deep Contrastive Learning for Unsupervised Textual Representationscited by 251
  7. 2018Failing Loudly: An Empirical Study of Methods for Detecting Dataset Shiftcited by 243
  8. 2018Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoisingcited by 218
  9. 2020FetchSGD: Communication-Efficient Federated Learning with Sketchingcited by 179
  10. 2020Pre-training Tasks for Embedding-based Large-scale Retrievalcited by 153
  11. 2015Compressing Neural Networks with the Hashing Trickcited by 150
  12. 2020General Multi-label Image Classification with Transformerscited by 127
17 more
  1. 2014Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS)cited by 109
  2. 2014Deep Fragment Embeddings for Bidirectional Image Sentence Mappingcited by 99
  3. 2021Federated Reconstruction: Partially Local Federated Learningcited by 79
  4. 2019DEMO-Net: Degree-specific Graph Neural Networks for Node and Graph Classificationcited by 59
  5. 2018Hierarchical Bilinear Pooling for Fine-Grained Visual Recognitioncited by 47
  6. 2013Experiments with Random Projectioncited by 27
  7. 2019Dynamic Malware Analysis with Feature Engineering and Feature Learningcited by 23
  8. 2020FedSKETCH: Communication-Efficient and Private Federated Learning via Sketchingcited by 20
  9. 2015Sparse Projection Oblique Randomer Forestscited by 15
  10. 2014One-bit compressive sensing with norm estimationcited by 12
  11. 2016Individual Differential Privacy: A Utility-Preserving Formulation of Differential Privacy Guaranteescited by 10
  12. 2013Coding for Random Projectionscited by 8
  13. 2018Sign-Full Random Projectionscited by 7
  14. 2022GCWSNet: Generalized Consistent Weighted Sampling for Scalable and Accurate Training of Neural Networkscited by 6
  15. 2019A Memory-Efficient Sketch Method for Estimating High Similarities in Streaming Setscited by 5
  16. 2022Boost CTR Prediction for New Advertisements via Modeling Visual Contentcited by 5
  17. 2022Finding the Needle in a Haystack: On the Automatic Identification of Accessibility User Reviewscited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 2; 2024: 4; 2025: 2; 2026: 4.

12 papers.

  1. 2024Token-wise Influential Training Data Retrieval for Large Language Modelscited by 20
  2. 2025Understanding Impact of Human Feedback via Influence Functionscited by 11
  3. 2025GraSS: Scalable Data Attribution with Gradient Sparsification and Sparse Projectioncited by 8
  4. 2023Differential Privacy with Random Projections and Sign Random Projectionscited by 5
  5. 2026Scout Before You Attend: Sketch-and-Walk Sparse Attention for Efficient LLM Inferencecited by 4
  6. 2023Differentially Private One Permutation Hashing and Bin-wise Consistent Weighted Samplingcited by 3
  7. 2024DMin: Scalable Training Data Influence Estimation for Diffusion Modelscited by 3
  8. 2024LiNR: Model Based Neural Retrieval on GPUs at LinkedIncited by 2
  9. 2024Learning to Retrieve for Job Matchingcited by 1
  10. 2026Quality over Quantity: Demonstration Curation via Influence Functions for Data-Centric Robot Learningcited by 1
  11. 2026Sketching the Readout of Large Language Models for Scalable Data Attribution and Valuationcited by 1
  12. 2026HIVE: Hidden-Evidence Verification for Hallucination Detection in Diffusion Large Language Modelscited by 1