The DOI matches its Crossref record; 11 of the 11 references it cites were found in a registry or an index.
Database-friendly random projections
Abstract
A classic result of Johnson and Lindenstrauss asserts that any set of n points in d-dimensional Euclidean space can be embedded into k-dimensional Euclidean space where k is logarithmic in n and independent of d so that all pairwise distances are maintained within an arbitrarily small factor. All known constructions of such embeddings involve projecting the n points onto a random k-dimensional hyperplane. We give a novel construction of the embedding, suitable for database applications, which amounts to computing a simple aggregate over k random attribute partitions.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Approximate nearest neighbors: towards removing the curse of dimensionality
Indyk, P., & Motwani, R. (1998) · Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98 · doi:10.1145/276698.276876 · Cited by 4,188
Extensions of Lipschitz mappings into a Hilbert space
Johnson, W. B., & Lindenstrauss, J. (1984) · Contemporary Mathematics · doi:10.1090/conm/026/737400 · Cited by 2,523
The geometry of graphs and some of its algorithmic applications
Linial, N., London, E., & Rabinovich, Y. (1995) · Combinatorica · doi:10.1007/bf01200757 · Cited by 952
Latent semantic indexing: a probabilistic analysis
Papadimitriou, C. H., Tamaki, H., Raghavan, P., & Vempala, S. (1998) · Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems · doi:10.1145/275487.275505 · Cited by 863
Learning mixtures of Gaussians
Dasgupta, S. (2003) · 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039) · doi:10.1109/sffcs.1999.814639 · Cited by 588
Two algorithms for nearest-neighbor search in high dimensions
Kleinberg, J. M. (1997) · Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC '97 · doi:10.1145/258533.258653 · Cited by 348
An algorithmic theory of learning: Robust concepts and random projection
Arriaga, R. I., & Vempala, S. (2006) · Machine Learning · doi:10.1007/s10994-006-6265-7 · Cited by 316
The Johnson-Lindenstrauss lemma and the sphericity of some graphs
Frankl, P., & Maehara, H. (1988) · Journal of Combinatorial Theory, Series B · doi:10.1016/0095-8956(88)90043-3 · Cited by 299
Stable distributions, pseudorandom generators, embeddings and data stream computation
Indyk, P. (2002) · Proceedings 41st Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2000.892082 · Cited by 238
Learning mixtures of arbitrary gaussians
Sanjeev, A., & Kannan, R. (2001) · Proceedings of the thirty-third annual ACM symposium on Theory of computing · doi:10.1145/380752.380808 · Cited by 216
Cited by
Robust Face Recognition via Sparse Representation
Wright, J., Yang, A. Y., Ganesh, A., Sastry, S. S., & Ma, Y. (2009) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2008.79 · Cited by 9,388
A Simple Proof of the Restricted Isometry Property for Random Matrices
Baraniuk, R., Davenport, M., DeVore, R., & Wakin, M. (2008) · Constructive Approximation · doi:10.1007/s00365-007-9003-x · Cited by 2,372
Challenges of Big Data analysis
Fan, J., Han, F., & Liu, H. (2014) · National Science Review · doi:10.1093/nsr/nwt032 · Cited by 1,482
Database-friendly random projections: Johnson-Lindenstrauss with binary coins
Achlioptas, D. (2003) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(03)00025-4 · Cited by 1,392
Self-citationSubspace clustering for high dimensional data: a review
Parsons, L., Haque, E., & Liu, H. (2004) · ACM SIGKDD Explorations Newsletter · doi:10.1145/1007730.1007731 · Cited by 1,346
Finding frequent items in data streams
Charikar, M., Chen, K., & Farach-Colton, M. (2004) · Theoretical Computer Science · doi:10.1016/s0304-3975(03)00400-6 · Cited by 1,278
Random projection in dimensionality reduction: applications to image and text data
Bingham, E., & Mannila, H. (2001) · Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/502512.502546 · Cited by 1,274
Compressed sensing and best 𝑘-term approximation
Cohen, A., Dahmen, W., & DeVore, R. (2008) · Journal of the American Mathematical Society · doi:10.1090/s0894-0347-08-00610-3 · Cited by 1,002
An elementary proof of a theorem of Johnson and Lindenstrauss
Dasgupta, S., & Gupta, A. (2003) · Random Structures & Algorithms · doi:10.1002/rsa.10073 · Cited by 932
A survey on unsupervised outlier detection in high‐dimensional numerical data
Zimek, A., Schubert, E., & Kriegel, H. (2012) · Statistical Analysis and Data Mining The ASA Data Science Journal · doi:10.1002/sam.11161 · Cited by 864
Finding Frequent Items in Data Streams
Charikar, M., Chen, K., & Farach-Colton, M. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-45465-9_59 · Cited by 650
Signal Processing With Compressive Measurements
Davenport, M. A., Boufounos, P. T., Wakin, M. B., & Baraniuk, R. G. (2010) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2009.2039178 · Cited by 623
Compressed Sensing and Redundant Dictionaries
Rauhut, H., Schnass, K., & Vandergheynst, P. (2008) · IEEE Transactions on Information Theory · doi:10.1109/tit.2008.920190 · Cited by 541
Halder, R. K., Uddin, M. N., Uddin, M. A., Aryal, S., & Khraisat, A. (2024) · Journal of Big Data · doi:10.1186/s40537-024-00973-y · Cited by 520
Random Projections of Smooth Manifolds
Baraniuk, R. G., & Wakin, M. B. (2009) · Foundations of Computational Mathematics · doi:10.1007/s10208-007-9011-z · Cited by 404
Outlier Detection: Methods, Models, and Classification
Boukerche, A., Zheng, L., & Alfandi, O. (2021) · ACM Computing Surveys · doi:10.1145/3381028 · Cited by 334
Human Activity Recognition with Metric Learning
Tran, D., & Sorokin, A. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-88682-2_42 · Cited by 332
An algorithmic theory of learning: Robust concepts and random projection
Arriaga, R. I., & Vempala, S. (2006) · Machine Learning · doi:10.1007/s10994-006-6265-7 · Cited by 316
Geometric Approximation Algorithms
Har-Peled, S. (2011) · Mathematical Surveys and Monographs · doi:10.1090/surv/173 · Cited by 315
Texture Classification from Random Features
Liu, L., & Fieguth, P. (2012) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2011.145 · Cited by 289
Avron, H., & Toledo, S. (2011) · Journal of the ACM · doi:10.1145/1944345.1944349 · Cited by 284
Semantics-Aware Content-Based Recommender Systems
de Gemmis, M., Lops, P., Musto, C., Narducci, F., & Semeraro, G. (2015) · Recommender Systems Handbook · doi:10.1007/978-1-4899-7637-6_4 · Cited by 258
Simple and deterministic matrix sketching
Liberty, E. (2013) · Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/2487575.2487623 · Cited by 257
Algorithmic applications of low-distortion geometric embeddings
Indyk, P. (2001) · Proceedings 42nd IEEE Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2001.959878 · Cited by 253
Conwell, C., Prince, J. S., Kay, K. N., Alvarez, G. A., & Konkle, T. (2022) · doi:10.1101/2022.03.28.485868 · Cited by 160
Efficient Generation of Transcriptomic Profiles by Random Composite Measurements
Cleary, B., Cong, L., Cheung, A., Lander, E. S., & Regev, A. (2017) · Cell · doi:10.1016/j.cell.2017.10.023 · Cited by 114
Conwell, C., Prince, J. S., Kay, K. N., Alvarez, G. A., & Konkle, T. (2024) · Nature Communications · doi:10.1038/s41467-024-53147-y · Cited by 100
Exploring anomalous behaviour detection and classification for insider threat identification
Le, D. C., & Zincir‐Heywood, N. (2021) · International Journal of Network Management · doi:10.1002/nem.2109 · Cited by 56
Redundant Bit Vectors for Quickly Searching High-Dimensional Regions
Goldstein, J., Plat, J. C., & Burges, C. J. C. (2005) · Lecture Notes in Computer Science · doi:10.1007/11559887_9 · Cited by 22
“This pre-processing can be carried out by random projection [3][4], by principal components analysis, or by oriented principal components analysis [5].”
MethodSparsity-Aware Learning and Compressed Sensing: An Overview
Theodoridis, S., Kopsinis, Y., & Slavakis, K. (2014) · Academic Press Library in Signal Processing · doi:10.1016/b978-0-12-396502-8.00023-1 · Cited by 14
Metadata
- Authors
- Achlioptas, D.
- Venue
- Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems
- Publisher
- ACM
- Published
- 2001-05
- Pages
- 274-281
- OpenAlex
- W2053171205
- Cited by
- 699
- References
- 11
- FWCI
- 5.09
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.