{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:20:50Z","timestamp":1759638050596,"version":"3.41.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2018,4,16]],"date-time":"2018-04-16T00:00:00Z","timestamp":1523836800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Unions Horizon 2020 research and innovation programme","award":["734242 (Project LAMBDA)"],"award-info":[{"award-number":["734242 (Project LAMBDA)"]}]},{"name":"\u201cHuman Resources Development, Education and Lifelong Learning\u201d"},{"name":"European Social Fund and the Greek Government"},{"name":"State Scholarships Foundation of Greece, financed by action \u201cSupporting human resources in research through the implementation of doctoral research\u201d"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2018,4,30]]},"abstract":"<jats:p>\n            Approximate nearest neighbor search (\u03f5-ANN) in high dimensions has been mainly addressed by Locality Sensitive Hashing (LSH), which has complexity with polynomial dependence in dimension, sublinear query time, but subquadratic space requirement. We introduce a new \u201clow-quality\u201d embedding for metric spaces requiring that, for some query, there exists an approximate nearest neighbor among the pre-images of its\n            <jats:italic>k<\/jats:italic>\n            &gt; 1 approximate nearest neighbors in the target space. In Euclidean spaces, we employ random projections to a dimension inversely proportional to\n            <jats:italic>k<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>\n            Our approach extends to the decision problem with witness of checking whether there exists an approximate\n            <jats:italic>near<\/jats:italic>\n            neighbor; this also implies a solution for \u03f5-ANN. After dimension reduction, we store points in a uniform grid of side length \u03f5 \/\u221a\n            <jats:italic>d<\/jats:italic>\n            <jats:sup>\u2032<\/jats:sup>\n            , where\n            <jats:italic>d<\/jats:italic>\n            <jats:sup>\u2032<\/jats:sup>\n            is the reduced dimension. Given a query, we explore cells intersecting the unit ball around the query. This data structure requires linear space and query time in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>d<\/jats:italic>\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\u03c1<\/jats:sup>\n            ), \u03c1 \u2248 1-\u03f5\n            <jats:sup>2<\/jats:sup>\n            i&gt;\/log(1\u03f5), where\n            <jats:italic>n<\/jats:italic>\n            denotes input cardinality and\n            <jats:italic>d<\/jats:italic>\n            space dimension. Bounds are improved for doubling subsets via\n            <jats:italic>r<\/jats:italic>\n            -nets.\n          <\/jats:p>\n          <jats:p>\n            We present our implementation for \u03f5-ANN in C++ and experiments for\n            <jats:italic>d<\/jats:italic>\n            \u2264 960,\n            <jats:italic>n<\/jats:italic>\n            \u2264 10\n            <jats:sup>6<\/jats:sup>\n            , using synthetic and real datasets, which confirm the theoretical analysis and, typically, yield better practical performance. We compare to FALCONN, the state-of-the-art implementation of multi-probe LSH: our prototype software is essentially comparable in terms of preprocessing, query time, and storage usage.\n          <\/jats:p>","DOI":"10.1145\/3178540","type":"journal-article","created":{"date-parts":[[2018,4,18]],"date-time":"2018-04-18T17:21:50Z","timestamp":1524072110000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Randomized Embeddings with Slack and High-Dimensional Approximate Nearest Neighbor"],"prefix":"10.1145","volume":"14","author":[{"given":"Evangelos","family":"Anagnostopoulos","sequence":"first","affiliation":[{"name":"National 8 Kapodistrian University of Athens, Greece"}]},{"given":"Ioannis Z.","family":"Emiris","sequence":"additional","affiliation":[{"name":"National 8 Kapodistrian University of Athens, and ATHENA Research Center, Greece"}]},{"given":"Ioannis","family":"Psarros","sequence":"additional","affiliation":[{"name":"National 8 Kapodistrian University of Athens, Greece"}]}],"member":"320","published-online":{"date-parts":[[2018,4,16]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.51"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00025-4"},{"volume-title":"Proc. 31st International Symp. on Computational Geometry (SoCG). 436--450","author":"Anagnostopoulos E.","key":"e_1_2_1_3_1","unstructured":"E. Anagnostopoulos , I. Z. Emiris , and I. Psarros . 2015. Low-quality dimension reduction and high-dimensional approximate nearest neighbor . In Proc. 31st International Symp. on Computational Geometry (SoCG). 436--450 . E. Anagnostopoulos, I. Z. Emiris, and I. Psarros. 2015. Low-quality dimension reduction and high-dimensional approximate nearest neighbor. In Proc. 31st International Symp. on Computational Geometry (SoCG). 436--450."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327494"},{"volume-title":"Advances Neural Information Proc. Systems 28: Annual Conf. Neural Information Processing Systems. 1225--1233","author":"Andoni A.","key":"e_1_2_1_5_1","unstructured":"A. Andoni , P. Indyk , T. Laarhoven , I. P. Razenshteyn , and L. Schmidt . 2015. Practical and optimal LSH for angular distance . In Advances Neural Information Proc. Systems 28: Annual Conf. Neural Information Processing Systems. 1225--1233 . A. Andoni, P. Indyk, T. Laarhoven, I. P. Razenshteyn, and L. Schmidt. 2015. Practical and optimal LSH for angular distance. In Advances Neural Information Proc. Systems 28: Annual Conf. Neural Information Processing Systems. 1225--1233."},{"volume-title":"Proc. of the 28th Annual ACM-SIAM Symp. on Discrete Algorithms, SODA 2017. 47--66","author":"Andoni A.","key":"e_1_2_1_6_1","unstructured":"A. Andoni , T. Laarhoven , I. P. Razenshteyn , and E. Waingarten . 2017. Optimal hashing-based time-space trade-offs for approximate near neighbors . In Proc. of the 28th Annual ACM-SIAM Symp. on Discrete Algorithms, SODA 2017. 47--66 . A. Andoni, T. Laarhoven, I. P. Razenshteyn, and E. Waingarten. 2017. Optimal hashing-based time-space trade-offs for approximate near neighbors. In Proc. of the 28th Annual ACM-SIAM Symp. on Discrete Algorithms, SODA 2017. 47--66."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746553"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993713"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1613676.1613677"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/293347.293348"},{"volume-title":"Proc. 28th Annual ACM-SIAM Symp. on Discrete Algorithms, SODA. 16--30","author":"Avarikioti G.","key":"e_1_2_1_11_1","unstructured":"G. Avarikioti , I. Z. Emiris , L. Kavouras , and I. Psarros . 2017. High-dimensional approximate r-nets . In Proc. 28th Annual ACM-SIAM Symp. on Discrete Algorithms, SODA. 16--30 . G. Avarikioti, I. Z. Emiris, L. Kavouras, and I. Psarros. 2017. High-dimensional approximate r-nets. In Proc. 28th Annual ACM-SIAM Symp. on Discrete Algorithms, SODA. 16--30."},{"key":"e_1_2_1_12_1","unstructured":"Y. Bartal and L. Gottlieb. 2015. Approximate nearest neighbor search for &ell;<sub>p<\/sub>-spaces (2 &lt; p &gt; \u221e) via embeddings. CoRR abs\/1512.01775 (2015). http:\/\/arxiv.org\/abs\/1512.01775  Y. Bartal and L. Gottlieb. 2015. Approximate nearest neighbor search for &ell;<sub> p <\/sub>-spaces (2 &lt; p &gt; \u221e) via embeddings. CoRR abs\/1512.01775 (2015). http:\/\/arxiv.org\/abs\/1512.01775"},{"volume-title":"Proc. 22nd Annual ACM-SIAM Symp. on Discrete Algorithms. SIAM, 868--887","author":"Bartal Y.","key":"e_1_2_1_13_1","unstructured":"Y. Bartal , B. Recht , and L. J. Schulman . 2011. Dimensionality reduction: Beyond the Johnson-Lindenstrauss bound . In Proc. 22nd Annual ACM-SIAM Symp. on Discrete Algorithms. SIAM, 868--887 . http:\/\/dl.acm.org\/citation.cfm?id&equals;2133036.2133104 Y. Bartal, B. Recht, and L. J. Schulman. 2011. Dimensionality reduction: Beyond the Johnson-Lindenstrauss bound. In Proc. 22nd Annual ACM-SIAM Symp. on Discrete Algorithms. SIAM, 868--887. http:\/\/dl.acm.org\/citation.cfm?id&equals;2133036.2133104"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1143844.1143857"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374452"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10073"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9885-5"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/997817.997857"},{"key":"e_1_2_1_19_1","unstructured":"D. Eppstein S. Har-Peled and A. Sidiropoulos. 2015. Approximate greedy clustering and distance selection for graph metrics. CoRR abs\/1507.01555 (2015). http:\/\/arxiv.org\/abs\/1507.01555  D. Eppstein S. Har-Peled and A. Sidiropoulos. 2015. Approximate greedy clustering and distance selection for graph metrics. CoRR abs\/1507.01555 (2015). http:\/\/arxiv.org\/abs\/1507.01555"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-015-9707-9"},{"volume-title":"Proc. 44th Annual IEEE Symp. Foundations of Computer Science (FOCS\u201903)","author":"Gupta A.","key":"e_1_2_1_21_1","unstructured":"A. Gupta , R. Krauthgamer , and J. R. Lee . 2003. Bounded geometries, fractals, and low-distortion embeddings . In Proc. 44th Annual IEEE Symp. Foundations of Computer Science (FOCS\u201903) . 534--541. A. Gupta, R. Krauthgamer, and J. R. Lee. 2003. Bounded geometries, fractals, and low-distortion embeddings. In Proc. 44th Annual IEEE Symp. Foundations of Computer Science (FOCS\u201903). 534--541."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/3116656.3116964"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a014"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1064092.1064117"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276876"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1273340.1273347"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2010.57"},{"key":"e_1_2_1_28_1","volume-title":"Proc. Conf. in Modern Analysis and Probability","author":"Johnson W.","year":"1982","unstructured":"W. Johnson and J. Lindenstrauss . 1984. Extensions of Lipschitz mappings into a Hilbert space . In Proc. Conf. in Modern Analysis and Probability ( New Haven, Conn. , 1982 ) (Contemporary Mathematics), Vol. 26. American Mathematical Society, 189--206. W. Johnson and J. Lindenstrauss. 1984. Extensions of Lipschitz mappings into a Hilbert space. In Proc. Conf. in Modern Analysis and Probability (New Haven, Conn., 1982) (Contemporary Mathematics), Vol. 26. American Mathematical Society, 189--206."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2745754.2745761"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510013"},{"volume-title":"Proc. 15th Annual ACM-SIAM Symp. Discrete Algorithms (SODA\u201904)","author":"Krauthgamer R.","key":"e_1_2_1_31_1","unstructured":"R. Krauthgamer and J. R. Lee . 2004. Navigating nets: Simple algorithms for proximity search . In Proc. 15th Annual ACM-SIAM Symp. Discrete Algorithms (SODA\u201904) . 798--807. R. Krauthgamer and J. R. Lee. 2004. Navigating nets: Simple algorithms for proximity search. In Proc. 15th Annual ACM-SIAM Symp. Discrete Algorithms (SODA\u201904). 798--807."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1993.1057"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2578221"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109688"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735461.2735462"},{"key":"e_1_2_1_36_1","volume-title":"Proc. Foundations of Software Technology 8 Theor. Computer Science. 48--57","author":"Vempala S.","year":"2012","unstructured":"S. Vempala . 2012 . Randomly-oriented k-d trees adapt to intrinsic dimension . In Proc. Foundations of Software Technology 8 Theor. Computer Science. 48--57 . S. Vempala. 2012. Randomly-oriented k-d trees adapt to intrinsic dimension. In Proc. Foundations of Software Technology 8 Theor. Computer Science. 48--57."},{"volume-title":"Proc. IEEE 86","author":"Bengio Y.","key":"e_1_2_1_37_1","unstructured":"Y. Bengio , Y. LeCun , L. Bottou , and P. Haffner . Gradient-based learning applied to document recognition . Proc. IEEE 86 , 11, 2278--2324. Y. Bengio, Y. LeCun, L. Bottou, and P. Haffner. Gradient-based learning applied to document recognition. Proc. IEEE 86, 11, 2278--2324."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3178540","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3178540","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:26:59Z","timestamp":1750213619000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3178540"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,4,16]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,4,30]]}},"alternative-id":["10.1145\/3178540"],"URL":"https:\/\/doi.org\/10.1145\/3178540","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2018,4,16]]},"assertion":[{"value":"2016-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-04-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}