{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:33:35Z","timestamp":1759638815653,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":60,"publisher":"ACM","license":[{"start":{"date-parts":[[2017,6,19]],"date-time":"2017-06-19T00:00:00Z","timestamp":1497830400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1617955,DGE-16-44869"],"award-info":[{"award-number":["CCF-1617955,DGE-16-44869"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006785","name":"Google","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006785","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2017,6,19]]},"DOI":"10.1145\/3055399.3055418","type":"proceedings-article","created":{"date-parts":[[2017,6,15]],"date-time":"2017-06-15T20:27:45Z","timestamp":1497558465000},"page":"902-913","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Approximate near neighbors for general symmetric norms"],"prefix":"10.1145","author":[{"given":"Alexandr","family":"Andoni","sequence":"first","affiliation":[{"name":"Columbia University, USA"}]},{"given":"Huy L.","family":"Nguyen","sequence":"additional","affiliation":[{"name":"Northeastern University, USA"}]},{"given":"Aleksandar","family":"Nikolov","sequence":"additional","affiliation":[{"name":"University of Toronto, Canada"}]},{"given":"Ilya","family":"Razenshteyn","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}]},{"given":"Erik","family":"Waingarten","sequence":"additional","affiliation":[{"name":"Columbia University, USA"}]}],"member":"320","published-online":{"date-parts":[[2017,6,19]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746595"},{"key":"e_1_3_2_2_2_1","unstructured":"Alexandr Andoni. 2009.  Alexandr Andoni. 2009."},{"volume-title":"Handbook of Big Data., Peter B\u00fchlmann, Petros Drineas, Michael Kane, and Mark J","author":"Andoni Alexandr","key":"e_1_3_2_2_4_1","unstructured":"Alexandr Andoni . 2016. High-Dimensional Computational Geometry . In Handbook of Big Data., Peter B\u00fchlmann, Petros Drineas, Michael Kane, and Mark J . van der Laan (Eds.). Chapman and Hall\/CRC , 105\u2013123. http:\/\/www.crcnetbase. com\/ Alexandr Andoni. 2016. High-Dimensional Computational Geometry. In Handbook of Big Data., Peter B\u00fchlmann, Petros Drineas, Michael Kane, and Mark J. van der Laan (Eds.). Chapman and Hall\/CRC, 105\u2013123. http:\/\/www.crcnetbase. com\/"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.89"},{"key":"e_1_3_2_2_6_1","unstructured":"Alexandr Andoni and Piotr Indyk. 2006.  Alexandr Andoni and Piotr Indyk. 2006."},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.49"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/1496770.1496864"},{"key":"e_1_3_2_2_9_1","unstructured":"Alexandr Andoni Piotr Indyk Huy L. Nguyen and Ilya Razenshteyn. 2014.  Alexandr Andoni Piotr Indyk Huy L. Nguyen and Ilya Razenshteyn. 2014."},{"volume-title":"Locality-Sensitive Hashing. In Proceedings of the 25th ACM-SIAM Symposium on Discrete Algorithms (SODA \u20192014)","author":"Beyond","key":"e_1_3_2_2_10_1","unstructured":"Beyond Locality-Sensitive Hashing. In Proceedings of the 25th ACM-SIAM Symposium on Discrete Algorithms (SODA \u20192014) . 1018\u20131028. Available as arXiv:1306.1547. Beyond Locality-Sensitive Hashing. In Proceedings of the 25th ACM-SIAM Symposium on Discrete Algorithms (SODA \u20192014). 1018\u20131028. Available as arXiv:1306.1547."},{"key":"e_1_3_2_2_11_1","unstructured":"Alexandr Andoni Robert Krauthgamer and Ilya Razenshteyn. 2015.  Alexandr Andoni Robert Krauthgamer and Ilya Razenshteyn. 2015."},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746552"},{"key":"e_1_3_2_2_13_1","unstructured":"Alexandr Andoni Thijs Laarhoven Ilya Razenshteyn and Erik Waingarten. 2017.  Alexandr Andoni Thijs Laarhoven Ilya Razenshteyn and Erik Waingarten. 2017."},{"volume-title":"Trade-offs for Approximate Near Neighbors. In Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms (SODA \u20192017)","author":"Time\u2013Space Optimal","key":"e_1_3_2_2_14_1","unstructured":"Optimal Hashing-based Time\u2013Space Trade-offs for Approximate Near Neighbors. In Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms (SODA \u20192017) . Available as arXiv:1608.03580. Optimal Hashing-based Time\u2013Space Trade-offs for Approximate Near Neighbors. In Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms (SODA \u20192017). Available as arXiv:1608.03580."},{"key":"e_1_3_2_2_15_1","unstructured":"Alexandr Andoni Huy L. Nguyen Aleksandar Nikolov Ilya Razenshteyn and Erik Waingarten. 2017.  Alexandr Andoni Huy L. Nguyen Aleksandar Nikolov Ilya Razenshteyn and Erik Waingarten. 2017."},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055418"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746553"},{"key":"e_1_3_2_2_18_1","volume-title":"Proceedings of Advances in Neural Information Processing Systems 25 (NIPS \u20192012)","author":"Argyriou Andreas","year":"2012","unstructured":"Andreas Argyriou , Rina Foygel , and Nathan Srebro . 2012 . Sparse Prediction with the k-Support Norm . In Proceedings of Advances in Neural Information Processing Systems 25 (NIPS \u20192012) . 944\u2013952. Andreas Argyriou, Rina Foygel, and Nathan Srebro. 2012. Sparse Prediction with the k-Support Norm. In Proceedings of Advances in Neural Information Processing Systems 25 (NIPS \u20192012). 944\u2013952."},{"key":"e_1_3_2_2_19_1","unstructured":"Keith Ball. 1997.  Keith Ball. 1997."},{"key":"e_1_3_2_2_20_1","unstructured":"An Elementary Introduction to Modern Convex Geometry. MSRI Publications Vol. 31. Cambridge University Press.  An Elementary Introduction to Modern Convex Geometry. MSRI Publications Vol. 31. Cambridge University Press."},{"key":"e_1_3_2_2_21_1","volume-title":"Approximate nearest neighbor search for","author":"Bartal Yair","year":"2015","unstructured":"Yair Bartal and Lee-Ad Gottlieb . 2015. Approximate nearest neighbor search for p -spaces ( 2 < p < \u221e) via embeddings. ( 2015 ). Available as arXiv:1512.01775. Yair Bartal and Lee-Ad Gottlieb. 2015. Approximate nearest neighbor search for p -spaces ( 2 < p < \u221e) via embeddings. (2015). Available as arXiv:1512.01775."},{"key":"e_1_3_2_2_22_1","unstructured":"Colin Bennett and Robert Sharpley. 1988.  Colin Bennett and Robert Sharpley. 1988."},{"volume-title":"Pure and Applied Mathematics","author":"Operators Interpolation","key":"e_1_3_2_2_23_1","unstructured":"Interpolation of Operators . Pure and Applied Mathematics , Vol. 129 . Academic Press . Interpolation of Operators. Pure and Applied Mathematics, Vol. 129. Academic Press."},{"key":"e_1_3_2_2_24_1","unstructured":"Alina Beygelzimer Sham Kakade and John Langford. 2006.  Alina Beygelzimer Sham Kakade and John Langford. 2006."},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1143844.1143857"},{"key":"e_1_3_2_2_26_1","volume-title":"Yang","author":"B\u0142asiok Jaros\u0142aw","year":"2015","unstructured":"Jaros\u0142aw B\u0142asiok , Vladimir Braverman , Stephen R. Chestnut , Robert Krauthgamer , and Lin F . Yang . 2015 . Streaming Symmetric Norms via Measure Concentration . (2015). Available as arXiv:1511.01111. Jaros\u0142aw B\u0142asiok, Vladimir Braverman, Stephen R. Chestnut, Robert Krauthgamer, and Lin F. Yang. 2015. Streaming Symmetric Norms via Measure Concentration. (2015). Available as arXiv:1511.01111."},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806729"},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009449"},{"key":"e_1_3_2_2_29_1","volume-title":"Woodruff","author":"Clarkson Kenneth L.","year":"2015","unstructured":"Kenneth L. Clarkson and David P . Woodruff . 2015 . Sketching for M-Estimators: A Unified Approach to Robust Regression. In Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms (SODA \u20192015). 921\u2013939. Kenneth L. Clarkson and David P. Woodruff. 2015. Sketching for M-Estimators: A Unified Approach to Robust Regression. In Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms (SODA \u20192015). 921\u2013939."},{"key":"e_1_3_2_2_30_1","unstructured":"S. J. Dilworth and S. J. Montgomery-Smith. 1993.  S. J. Dilworth and S. J. Montgomery-Smith. 1993."},{"key":"e_1_3_2_2_31_1","volume-title":"Annals of Probability 21, 4","author":"The","year":"1993","unstructured":"The distribution of vectorvalued Rademacher series. Annals of Probability 21, 4 ( 1993 ), 2046\u20132052. The distribution of vectorvalued Rademacher series. Annals of Probability 21, 4 (1993), 2046\u20132052."},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a014"},{"key":"e_1_3_2_2_33_1","unstructured":"Piotr Indyk. 2001.  Piotr Indyk. 2001."},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1781"},{"key":"e_1_3_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/513400.513414"},{"key":"e_1_3_2_2_36_1","volume-title":"Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA \u20192004)","author":"Indyk Piotr","year":"2004","unstructured":"Piotr Indyk . 2004 . Approximate Nearest Neighbor under edit distance via product metrics . In Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA \u20192004) . 646\u2013650. Piotr Indyk. 2004. Approximate Nearest Neighbor under edit distance via product metrics. In Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA \u20192004). 646\u2013650."},{"key":"e_1_3_2_2_37_1","unstructured":"Piotr Indyk and Rajeev Motwani. 1998.  Piotr Indyk and Rajeev Motwani. 1998."},{"key":"e_1_3_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276876"},{"key":"e_1_3_2_2_39_1","volume-title":"Studies and Essays Presented to R. Courant on his 60th Birthday","author":"John Fritz","year":"1948","unstructured":"Fritz John . 1948. Extremum problems with inequalities as subsidiary conditions . In Studies and Essays Presented to R. Courant on his 60th Birthday , January 8, 1948 . Fritz John. 1948. Extremum problems with inequalities as subsidiary conditions. In Studies and Essays Presented to R. Courant on his 60th Birthday, January 8, 1948."},{"key":"e_1_3_2_2_40_1","unstructured":"Interscience Publishers Inc. New York N. Y. 187\u2013204.  Interscience Publishers Inc. New York N. Y. 187\u2013204."},{"key":"e_1_3_2_2_41_1","unstructured":"Michael Kapralov and Rina Panigrahy. 2012.  Michael Kapralov and Rina Panigrahy. 2012."},{"key":"e_1_3_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_46"},{"key":"e_1_3_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510013"},{"key":"e_1_3_2_2_44_1","first-page":"209","article-title":"A Unified Framework for Linear Dimensionality Reduction in L1","volume":"70","author":"Krahmer Felix","year":"2016","unstructured":"Felix Krahmer and Rachel Ward . 2016 . A Unified Framework for Linear Dimensionality Reduction in L1 . RIM 70 , 1 (2016), 209 \u2013 231 . Felix Krahmer and Rachel Ward. 2016. A Unified Framework for Linear Dimensionality Reduction in L1. RIM 70, 1 (2016), 209\u2013231.","journal-title":"RIM"},{"key":"e_1_3_2_2_45_1","volume-title":"Lee","author":"Krauthgamer Robert","year":"2004","unstructured":"Robert Krauthgamer and James R . Lee . 2004 . Navigating nets: simple algorithms for proximity search. In Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA \u20192004). 798\u2013807. Robert Krauthgamer and James R. Lee. 2004. Navigating nets: simple algorithms for proximity search. In Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA \u20192004). 798\u2013807."},{"key":"e_1_3_2_2_46_1","unstructured":"Ilan Kremer Noam Nisan and Dana Ron. 1999.  Ilan Kremer Noam Nisan and Dana Ron. 1999."},{"key":"e_1_3_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/s000370050018"},{"key":"e_1_3_2_2_48_1","volume-title":"Arnold","author":"Marshall Albert W.","year":"2011","unstructured":"Albert W. Marshall , Ingram Olkin , and Barry C . Arnold . 2011 . Albert W. Marshall, Ingram Olkin, and Barry C. Arnold. 2011."},{"volume-title":"theory of majorization and its applications","author":"Inequalities","key":"e_1_3_2_2_49_1","unstructured":"Inequalities : theory of majorization and its applications . Academic press . Inequalities: theory of majorization and its applications. Academic press."},{"key":"e_1_3_2_2_50_1","unstructured":"Ji\u0159\u00ed Matou\u0161ek. 1996.  Ji\u0159\u00ed Matou\u0161ek. 1996."},{"key":"e_1_3_2_2_51_1","volume-title":"Israel Journal of Mathematics 93","author":"On","year":"1996","unstructured":"On the distortion required for embedding finite metric spaces into normed spaces. Israel Journal of Mathematics 93 ( 1996 ), 333\u2013344. On the distortion required for embedding finite metric spaces into normed spaces. Israel Journal of Mathematics 93 (1996), 333\u2013344."},{"key":"e_1_3_2_2_52_1","volume-title":"Proceedings of Advances in Neural Information Processing Systems 25 (NIPS \u20192014)","author":"McDonald Andrew M.","year":"2014","unstructured":"Andrew M. McDonald , Massimiliano Pontil , and Dimitris Stamos . 2014 . Spectral k-Support Norm Regularization . In Proceedings of Advances in Neural Information Processing Systems 25 (NIPS \u20192014) . 3644\u20133652. Andrew M. McDonald, Massimiliano Pontil, and Dimitris Stamos. 2014. Spectral k-Support Norm Regularization. In Proceedings of Advances in Neural Information Processing Systems 25 (NIPS \u20192014). 3644\u20133652."},{"key":"e_1_3_2_2_53_1","unstructured":"Assaf Naor. 2017.  Assaf Naor. 2017."},{"volume-title":"Proceedings of the 33rd International Symposium on Computational Geometry (SoCG \u20192017)","author":"A","key":"e_1_3_2_2_54_1","unstructured":"A spectral gap precludes low-dimensional embeddings . In Proceedings of the 33rd International Symposium on Computational Geometry (SoCG \u20192017) . A spectral gap precludes low-dimensional embeddings. In Proceedings of the 33rd International Symposium on Computational Geometry (SoCG \u20192017)."},{"key":"e_1_3_2_2_55_1","volume-title":"On approximate nearest neighbor search in p","author":"Naor Assaf","year":"2006","unstructured":"Assaf Naor and Yuval Rabani . 2006. On approximate nearest neighbor search in p , p > 2. ( 2006 ). Manuscript . Assaf Naor and Yuval Rabani. 2006. On approximate nearest neighbor search in p, p > 2. (2006). Manuscript."},{"key":"e_1_3_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1137\/05064206X"},{"key":"e_1_3_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.82"},{"key":"e_1_3_2_2_58_1","unstructured":"Jun Wang Wei Liu Sanjiv Kumar and Shih-Fu Chang. 2015. Learning to Hash for Indexing Big Data - A Survey. (2015). Available as arXiv:1509.05472.  Jun Wang Wei Liu Sanjiv Kumar and Shih-Fu Chang. 2015. Learning to Hash for Indexing Big Data - A Survey. (2015). Available as arXiv:1509.05472."},{"key":"e_1_3_2_2_59_1","volume-title":"Kingkuan Song, and Jianqiu Ji.","author":"Wang Jingdong","year":"2014","unstructured":"Jingdong Wang , Heng Tao Shen , Kingkuan Song, and Jianqiu Ji. 2014 . Hashing for Similarity Search: a Survey . (2014). Available as arXiv:1408.2927. Jingdong Wang, Heng Tao Shen, Kingkuan Song, and Jianqiu Ji. 2014. Hashing for Similarity Search: a Survey. (2014). Available as arXiv:1408.2927."},{"key":"e_1_3_2_2_60_1","unstructured":"Przemys\u0142aw Wojtaszczyk. 1991.  Przemys\u0142aw Wojtaszczyk. 1991."},{"key":"e_1_3_2_2_61_1","unstructured":"Banach Spaces for Analysts. Cambridge University Press.  Banach Spaces for Analysts. Cambridge University Press."}],"event":{"name":"STOC '17: Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Montreal Canada","acronym":"STOC '17"},"container-title":["Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3055399.3055418","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3055399.3055418","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3055399.3055418","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:23:27Z","timestamp":1750220607000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3055399.3055418"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,19]]},"references-count":60,"alternative-id":["10.1145\/3055399.3055418","10.1145\/3055399"],"URL":"https:\/\/doi.org\/10.1145\/3055399.3055418","relation":{},"subject":[],"published":{"date-parts":[[2017,6,19]]},"assertion":[{"value":"2017-06-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}