{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:28Z","timestamp":1740109288980,"version":"3.37.3"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2020,1,7]],"date-time":"2020-01-07T00:00:00Z","timestamp":1578355200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,1,7]],"date-time":"2020-01-07T00:00:00Z","timestamp":1578355200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100010665","name":"H2020 Marie Sklodowska-Curie Actions","doi-asserted-by":"publisher","award":["734242"],"award-info":[{"award-number":["734242"]}],"id":[{"id":"10.13039\/100010665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,6]]},"DOI":"10.1007\/s00453-019-00664-8","type":"journal-article","created":{"date-parts":[[2020,2,3]],"date-time":"2020-02-03T14:24:35Z","timestamp":1580739875000},"page":"1675-1702","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["High-Dimensional Approximate r-Nets"],"prefix":"10.1007","volume":"82","author":[{"given":"Z.","family":"Avarikioti","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2339-5303","authenticated-orcid":false,"given":"I. Z.","family":"Emiris","sequence":"additional","affiliation":[]},{"given":"L.","family":"Kavouras","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5079-5003","authenticated-orcid":false,"given":"I.","family":"Psarros","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,1,7]]},"reference":[{"key":"664_CR1","unstructured":"Agarwal, P.K., Har-Peled, S., Varadarajan, K.R.: Geometric approximation via coresets. In: Goodman, J.E., Pach, J., Welzl, E. (eds.) Combinatorial and Computational Geometry, MSRI, pp. 1\u201330. University Press (2005)"},{"key":"664_CR2","doi-asserted-by":"crossref","unstructured":"Alman, J., Chan, T.M., Williams, R.: Polynomial representations of threshold functions and algorithmic application. In: Proceedings 57th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 467\u2013476 (2016)","DOI":"10.1109\/FOCS.2016.57"},{"key":"664_CR3","unstructured":"Anagnostopoulos, E., Emiris, I.Z., Psarros, I.: Low-quality dimension reduction and high-dimensional approximate nearest neighbor. CoRR arxiv: abs\/1412.1683 (2014)"},{"issue":"1","key":"664_CR4","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1145\/1327452.1327494","volume":"51","author":"A Andoni","year":"2008","unstructured":"Andoni, A., Indyk, P.: Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. Commun. ACM 51(1), 117\u2013122 (2008). https:\/\/doi.org\/10.1145\/1327452.1327494","journal-title":"Commun. ACM"},{"key":"664_CR5","doi-asserted-by":"publisher","unstructured":"Avarikioti, G., Emiris, I.Z., Kavouras, L., Psarros, I.: High-dimensional approximate r-nets. In: Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 16\u201330 (2017). https:\/\/doi.org\/10.1137\/1.9781611974782.2","DOI":"10.1137\/1.9781611974782.2"},{"key":"664_CR6","doi-asserted-by":"crossref","unstructured":"Avarikioti, G., Ryser, A., Wang, Y., Wattenhofer, R.: High dimensional clustering with r-nets. In: The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-First Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, pp. 3207\u20133214 (2019)","DOI":"10.1609\/aaai.v33i01.33013207"},{"key":"664_CR7","doi-asserted-by":"crossref","unstructured":"Charikar, M.: Similarity estimation techniques from rounding algorithms. In: Proceedings 34th Annual ACM Symposium on Theory of Computing, 2002, Montr\u00e9al, Canada, pp. 380\u2013388 (2002)","DOI":"10.1145\/509907.509965"},{"issue":"1","key":"664_CR8","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1006\/jcom.1997.0438","volume":"13","author":"D Coppersmith","year":"1997","unstructured":"Coppersmith, D.: Rectangular matrix multiplication revisited. J. Complex. 13(1), 42\u201349 (1997). https:\/\/doi.org\/10.1006\/jcom.1997.0438","journal-title":"J. Complex."},{"issue":"1","key":"664_CR9","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1002\/rsa.10073","volume":"22","author":"S Dasgupta","year":"2003","unstructured":"Dasgupta, S., Gupta, A.: An elementary proof of a theorem of Johnson and Lindenstrauss. Random Struct. Algorithms 22(1), 60\u201365 (2003). https:\/\/doi.org\/10.1002\/rsa.10073","journal-title":"Random Struct. Algorithms"},{"key":"664_CR10","unstructured":"Eppstein, D., Har-Peled, S., Sidiropoulos, A.: Approximate greedy clustering and distance selection for graph metrics. CoRR arxiv: abs\/1507.01555 (2015)"},{"key":"664_CR11","unstructured":"Goel, A., Indyk, P., Varadarajan, K.: Reductions among high dimensional proximity problems. In: Proceedings 12th Symposium on Discrete Algorithms (SODA), pp. 769\u2013778 (2001). http:\/\/dl.acm.org\/citation.cfm?id=365411.365776. Accessed June 2016"},{"issue":"4","key":"664_CR12","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1007\/s00454-004-2822-7","volume":"31","author":"S Har-Peled","year":"2004","unstructured":"Har-Peled, S.: Clustering motion. Discret. Comput. Geom. 31(4), 545\u2013565 (2004). https:\/\/doi.org\/10.1007\/s00454-004-2822-7","journal-title":"Discret. Comput. Geom."},{"key":"664_CR13","doi-asserted-by":"publisher","unstructured":"Har-Peled, S., Mendel, M.: Fast construction of nets in low dimensional metrics, and their applications. In: Proceedings 21st Annual Symposium Computational Geometry, pp. 150\u2013158 (2005). https:\/\/doi.org\/10.1145\/1064092.1064117","DOI":"10.1145\/1064092.1064117"},{"issue":"6","key":"664_CR14","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1145\/2831230","volume":"62","author":"S Har-Peled","year":"2015","unstructured":"Har-Peled, S., Raichel, B.: Net and prune: a linear time algorithm for euclidean distance problems. J. ACM 62(6), 44 (2015). https:\/\/doi.org\/10.1145\/2831230","journal-title":"J. ACM"},{"key":"664_CR15","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511813603","volume-title":"Probability and Computing: Randomized Algorithms and Probabilistic Analysis","author":"M Mitzenmacher","year":"2005","unstructured":"Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, Cambridge (2005). https:\/\/doi.org\/10.1017\/CBO9780511813603"},{"key":"664_CR16","doi-asserted-by":"publisher","unstructured":"Valiant, G.: Finding correlations in subquadratic time, with applications to learning parities and juntas. In: 53rd Annual IEEE Symposium Foundations of Computer Science (FOCS), pp. 11\u201320 (2012). https:\/\/doi.org\/10.1109\/FOCS.2012.27","DOI":"10.1109\/FOCS.2012.27"},{"issue":"2","key":"664_CR17","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1145\/2728167","volume":"62","author":"G Valiant","year":"2015","unstructured":"Valiant, G.: Finding correlations in subquadratic time, with applications to learning parities and the closest pair problem. J. ACM 62(2), 13 (2015). https:\/\/doi.org\/10.1145\/2728167","journal-title":"J. ACM"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00664-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00664-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00664-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,1,6]],"date-time":"2021-01-06T00:40:44Z","timestamp":1609893644000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00664-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,7]]},"references-count":17,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2020,6]]}},"alternative-id":["664"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00664-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2020,1,7]]},"assertion":[{"value":"1 May 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 December 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 January 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}