{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T07:14:07Z","timestamp":1780384447074,"version":"3.54.1"},"reference-count":16,"publisher":"Elsevier BV","issue":"4","license":[{"start":{"date-parts":[[2003,6,1]],"date-time":"2003-06-01T00:00:00Z","timestamp":1054425600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,8,22]],"date-time":"2013-08-22T00:00:00Z","timestamp":1377129600000},"content-version":"vor","delay-in-days":3735,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Computer and System Sciences"],"published-print":{"date-parts":[[2003,6]]},"DOI":"10.1016\/s0022-0000(03)00025-4","type":"journal-article","created":{"date-parts":[[2003,6,21]],"date-time":"2003-06-21T00:11:16Z","timestamp":1056154276000},"page":"671-687","source":"Crossref","is-referenced-by-count":871,"title":["Database-friendly random projections: Johnson-Lindenstrauss with binary coins"],"prefix":"10.1016","volume":"66","author":[{"given":"Dimitris","family":"Achlioptas","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"78","reference":[{"key":"10.1016\/S0022-0000(03)00025-4_BIB1","doi-asserted-by":"crossref","unstructured":"D. Achlioptas, Database-friendly random projections, 20th Annual Symposium on Principles of Database Systems, Santa Barbara, CA, 2001, pp. 274\u2013281.","DOI":"10.1145\/375551.375608"},{"key":"10.1016\/S0022-0000(03)00025-4_BIB2","doi-asserted-by":"crossref","unstructured":"R.I. Arriaga, S. Vempala, An algorithmic theory of learning: robust concepts and random projection, 40th Annual Symposium on Foundations of Computer Science, New York, NY, 1999, IEEE Computer Society Press, Los Alamitos, CA, 1999, pp. 616\u2013623.","DOI":"10.1109\/SFFCS.1999.814637"},{"key":"10.1016\/S0022-0000(03)00025-4_BIB3","doi-asserted-by":"crossref","unstructured":"S. Arora, R. Kannan, Learning mixtures of arbitrary Gaussians, 33rd Annual ACM Symposium on Theory of Computing, Creete, Greece, ACM, New York, 2001, pp. 247\u2013257.","DOI":"10.1145\/380752.380808"},{"key":"10.1016\/S0022-0000(03)00025-4_BIB4","doi-asserted-by":"crossref","unstructured":"S. Dasgupta, Learning mixtures of Gaussians, 40th Annual Symposium on Foundations of Computer Science, New York, NY, 1999, IEEE Computer Society Press, Los Alamitos, CA, 1999, pp. 634\u2013644.","DOI":"10.1109\/SFFCS.1999.814639"},{"key":"10.1016\/S0022-0000(03)00025-4_BIB5","unstructured":"S. Dasgupta, A. Gupta, An elementary proof of the Johnson\u2013Lindenstrauss lemma. Technical Report 99-006, UC Berkeley, March 1999."},{"issue":"3","key":"10.1016\/S0022-0000(03)00025-4_BIB6","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1016\/0095-8956(88)90043-3","article-title":"The Johnson-Lindenstrauss lemma and the sphericity of some graphs","volume":"44","author":"Frankl","year":"1988","journal-title":"J. Combin. Theory Ser. B"},{"key":"10.1016\/S0022-0000(03)00025-4_BIB7","doi-asserted-by":"crossref","unstructured":"P. Indyk, Stable distributions, pseudorandom generators, embeddings and data stream computation, 41st Annual Symposium on Foundations of Computer Science, Redondo Beach, CA, 2000, IEEE Computer Society Press, Los Alamitos, CA, 2000, pp. 189\u2013197.","DOI":"10.1109\/SFCS.2000.892082"},{"key":"10.1016\/S0022-0000(03)00025-4_BIB8","doi-asserted-by":"crossref","unstructured":"P. Indyk, R. Motwani, Approximate nearest neighbors: towards removing the curse of dimensionality, 30th Annual ACM Symposium on Theory of Computing, Dallas, TX, ACM, New York, 1998, pp. 604\u2013613.","DOI":"10.1145\/276698.276876"},{"key":"10.1016\/S0022-0000(03)00025-4_BIB9","doi-asserted-by":"crossref","unstructured":"W.B. Johnson, J. Lindenstrauss, Extensions of Lipschitz mappings into a Hilbert space, Conference in modern analysis and probability, New Haven, CI, 1982, Amer. Math. Soc., Providence, RI, 1984, pp. 189\u2013206.","DOI":"10.1090\/conm\/026\/737400"},{"key":"10.1016\/S0022-0000(03)00025-4_BIB10","doi-asserted-by":"crossref","unstructured":"J. Kleinberg, Two algorithms for nearest-neighbor search in high dimensions, 29th Annual ACM Symposium on Theory of Computing, El Paso, TX, 1997, ACM, New York, 1997, pp. 599\u2013608.","DOI":"10.1145\/258533.258653"},{"issue":"2","key":"10.1016\/S0022-0000(03)00025-4_BIB11","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1137\/S0097539798347177","article-title":"Efficient search for approximate nearest neighbor in high dimensional spaces","volume":"30","author":"Kushilevitz","year":"2000","journal-title":"SIAM J. Comput."},{"issue":"2","key":"10.1016\/S0022-0000(03)00025-4_BIB12","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/BF01200757","article-title":"The geometry of graphs and some of its algorithmic applications","volume":"15","author":"Linial","year":"1995","journal-title":"Combinatorica"},{"key":"10.1016\/S0022-0000(03)00025-4_BIB13","doi-asserted-by":"crossref","unstructured":"C.H. Papadimitriou, P. Raghavan, H. Tamaki, S. Vempala, Latent semantic indexing: a probabilistic analysis, 17th Annual Symposium on Principles of Database Systems, Seattle, WA, 1998, pp. 159\u2013168.","DOI":"10.1145\/275487.275505"},{"key":"10.1016\/S0022-0000(03)00025-4_BIB14","doi-asserted-by":"crossref","unstructured":"L.J. Schulman, Clustering for edge-cost minimization, 32nd Annual ACM Symposium on Theory of Computing, Portland, OR, 2000, ACM, New York, 2000, pp. 547\u2013555.","DOI":"10.1145\/335305.335373"},{"key":"10.1016\/S0022-0000(03)00025-4_BIB15","doi-asserted-by":"crossref","unstructured":"D. Sivakumar, Algorithmic derandomization via complexity theory, 34th Annual ACM Symposium on Theory of Computing, Montreal, QC, 2002, ACM, New York, 2002, pp. 619\u2013626.","DOI":"10.1145\/509907.509996"},{"key":"10.1016\/S0022-0000(03)00025-4_BIB16","doi-asserted-by":"crossref","unstructured":"S. Vempala, A random sampling based algorithm for learning the intersection of half-spaces, 38th Annual Symposium on Foundations of Computer Science, Miami, FL, 1997, IEEE Computer Society Press, Los Alamitos, CA, 1997, pp. 508\u2013513.","DOI":"10.1109\/SFCS.1997.646139"}],"container-title":["Journal of Computer and System Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000003000254?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000003000254?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,12,12]],"date-time":"2024-12-12T23:23:37Z","timestamp":1734045817000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0022000003000254"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,6]]},"references-count":16,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2003,6]]}},"alternative-id":["S0022000003000254"],"URL":"https:\/\/doi.org\/10.1016\/s0022-0000(03)00025-4","relation":{},"ISSN":["0022-0000"],"issn-type":[{"value":"0022-0000","type":"print"}],"subject":[],"published":{"date-parts":[[2003,6]]}}}