{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,6]],"date-time":"2026-08-06T02:53:29Z","timestamp":1785984809936,"version":"3.56.0"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100004284","name":"Xerox","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100004284","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100007277","name":"Center for Massive Data Algorithmics","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100007277","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001732","name":"Danish National Research Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001732","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2014,1]]},"abstract":"<jats:p>\n            We give two different and simple constructions for dimensionality reduction in\n            <jats:italic>\u2113<\/jats:italic>\n            <jats:sub>2<\/jats:sub>\n            via linear mappings that are sparse: only an\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>\u03b5<\/jats:italic>\n            )-fraction of entries in each column of our embedding matrices are non-zero to achieve distortion 1 +\n            <jats:italic>\u03b5<\/jats:italic>\n            with high probability, while still achieving the asymptotically optimal number of rows. These are the first constructions to provide subconstant sparsity for all values of parameters, improving upon previous works of Achlioptas [2003] and Dasgupta et al. [2010]. Such distributions can be used to speed up applications where\n            <jats:italic>\u2113<\/jats:italic>\n            <jats:sub>2<\/jats:sub>\n            dimensionality reduction is used.\n          <\/jats:p>","DOI":"10.1145\/2559902","type":"journal-article","created":{"date-parts":[[2014,2,4]],"date-time":"2014-02-04T14:16:21Z","timestamp":1391523381000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":127,"title":["Sparser Johnson-Lindenstrauss Transforms"],"prefix":"10.1145","volume":"61","author":[{"given":"Daniel M.","family":"Kane","sequence":"first","affiliation":[{"name":"Harvard University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jelani","family":"Nelson","sequence":"additional","affiliation":[{"name":"MIT"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2014,1]]},"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.1145\/2483699.2483701"},{"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":"publisher","DOI":"10.1007\/s10994-006-6265-7"},{"key":"e_1_2_1_7_1","unstructured":"Vladimir Braverman Rafail Ostrovsky and Yuval Rabani. 2010. Rademacher chaos Random Eulerian graphs and the sparse Johnson-Lindenstrauss transform. CoRR abs\/1011.2590."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(79)90044-8"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00400-6"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536445"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488620"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806737"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10073"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/48184.48193"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579329"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177693335"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a014"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20360"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875596"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2483699.2483706"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/026\/737400"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/2033252.2033307"},{"key":"e_1_2_1_23_1","volume-title":"Kane and Jelani Nelson","author":"Daniel","year":"2010","unstructured":"Daniel M. Kane and Jelani Nelson. 2010. A derandomized sparse Johnson-Lindenstrauss transform. CoRR abs\/1006.3585."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095210"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993735"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-008-9267-y"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/100810447"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.v33:2"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488621"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/211390"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.21"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488622"},{"key":"e_1_2_1_33_1","volume-title":"Introduction to Data Mining","author":"Pang-Ning Tan Vipin Kumar","unstructured":"Vipin Kumar Pang-Ning Tan and Michael Steinbach. 2005. Introduction to Data Mining. Addison-Wesley."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.37"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/100800774"},{"key":"e_1_2_1_36_1","volume-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science","volume":"65","author":"Vempala Santosh","year":"2004","unstructured":"Santosh Vempala. 2004. The Random Projection Method. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 65, American Mathematical Society."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/304952"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jfa.2010.11.014"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1553374.1553516"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.2307\/1970079"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2559902","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2559902","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:10:25Z","timestamp":1750234225000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2559902"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1]]},"references-count":40,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["10.1145\/2559902"],"URL":"https:\/\/doi.org\/10.1145\/2559902","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,1]]},"assertion":[{"value":"2012-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-08-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-01-01","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}