{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T08:28:23Z","timestamp":1774945703175,"version":"3.50.1"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2010,2,1]],"date-time":"2010-02-01T00:00:00Z","timestamp":1264982400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Commun. ACM"],"published-print":{"date-parts":[[2010,2]]},"abstract":"<jats:p>Data represented geometrically in high-dimensional vector spaces can be found in many applications. Images and videos, are often represented by assigning a dimension for every pixel (and time). Text documents may be represented in a vector space where each word in the dictionary incurs a dimension. The need to manipulate such data in huge corpora such as the web and to support various query types gives rise to the question of how to represent the data in a lower-dimensional space to allow more space and time efficient computation. Linear mappings are an attractive approach to this problem because the mapped input can be readily fed into popular algorithms that operate on linear spaces (such as principal-component analysis, PCA) while avoiding the curse of dimensionality.<\/jats:p>\n          <jats:p>The fact that such mappings even exist became known in computer science following seminal work by Johnson and Lindenstrauss in the early 1980s. The underlying technique is often called \"random projection.\" The complexity of the mapping itself, essentially the product of a vector with a dense matrix, did not attract much attention until recently. In 2006, we discovered a way to \"sparsify\" the matrix via a computational version of Heisenberg's Uncertainty Principle. This led to a significant speedup, which also retained the practical simplicity of the standard Johnson-Lindenstrauss projection. We describe the improvement in this article, together with some of its applications.<\/jats:p>","DOI":"10.1145\/1646353.1646379","type":"journal-article","created":{"date-parts":[[2010,1,26]],"date-time":"2010-01-26T14:01:38Z","timestamp":1264514498000},"page":"97-104","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":49,"title":["Faster dimension reduction"],"prefix":"10.1145","volume":"53","author":[{"given":"Nir","family":"Ailon","sequence":"first","affiliation":[{"name":"Google Research"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bernard","family":"Chazelle","sequence":"additional","affiliation":[{"name":"Princeton University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00025-4"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/060673096"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-008-9110-x"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85363-3_40"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(03)00227-9"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","DOI":"10.1002\/0471722154","volume-title":"The Probabilistic Method","author":"Alon N.","year":"2000","unstructured":"Alon , N. , Spencer , J. The Probabilistic Method . John Wiley , 2 nd edition, 2000 . Alon, N., Spencer, J. The Probabilistic Method. John Wiley, 2nd edition, 2000.","edition":"2"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/290179.290180"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Arya S.","year":"1993","unstructured":"Arya , S. , Mount , D.M. Approximate nearest neighbor queries in fixed dimensions . In Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) ( Austin, TX, United States , 1993 ), 271--280. Arya, S., Mount, D.M. Approximate nearest neighbor queries in fixed dimensions. In Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (Austin, TX, United States, 1993), 271--280."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/293347.293348"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90222-U"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/502512.502546"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301330"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009390"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/177424.177609"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009449"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109682"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/795665.796531"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/48184.48193"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/795664.796429"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Indyk P.","year":"2000","unstructured":"Indyk , P. Dimensionality reduction techniques for proximity problems . In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) ( 2000 ), 371--378. Indyk, P. Dimensionality reduction techniques for proximity problems. In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2000), 371--378."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1201\/9781420035315.ch39"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276876"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/026\/737400"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258653"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798347177"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0709640104"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200757"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796309764"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/321752.321761"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/321879.321881"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/647821.736373"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/275487.275505"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.21236\/ADA489855"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.37"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335373"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2007.12.002"},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Yianilos P.N.","year":"1993","unstructured":"Yianilos , P.N. Data structures and algorithms for nearest neighbor search in general metric spaces . In Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) ( 1993 ), 311--321. Yianilos, P.N. Data structures and algorithms for nearest neighbor search in general metric spaces. In Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (1993), 311--321."},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Yianilos P.N.","year":"2000","unstructured":"Yianilos , P.N. Locally lifting the curse of dimensionality for nearest neighbor search (extended abstract) . In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) ( 2000 ), 361--370. Yianilos, P.N. Locally lifting the curse of dimensionality for nearest neighbor search (extended abstract). In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2000), 361--370."}],"container-title":["Communications of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1646353.1646379","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1646353.1646379","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:40:56Z","timestamp":1750250456000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1646353.1646379"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,2]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,2]]}},"alternative-id":["10.1145\/1646353.1646379"],"URL":"https:\/\/doi.org\/10.1145\/1646353.1646379","relation":{},"ISSN":["0001-0782","1557-7317"],"issn-type":[{"value":"0001-0782","type":"print"},{"value":"1557-7317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,2]]},"assertion":[{"value":"2010-02-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}