{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:05:47Z","timestamp":1750694747352,"version":"3.37.3"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2019,3,5]],"date-time":"2019-03-05T00:00:00Z","timestamp":1551744000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,3,5]],"date-time":"2019-03-05T00:00:00Z","timestamp":1551744000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1814026"],"award-info":[{"award-number":["CCF-1814026"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2019,6]]},"DOI":"10.1007\/s00454-019-00062-5","type":"journal-article","created":{"date-parts":[[2019,3,5]],"date-time":"2019-03-05T23:31:54Z","timestamp":1551828714000},"page":"899-922","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Orthogonal Range Searching in Moderate Dimensions: k-d Trees and Range Trees Strike Back"],"prefix":"10.1007","volume":"61","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8093-0675","authenticated-orcid":false,"given":"Timothy M.","family":"Chan","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,3,5]]},"reference":[{"key":"62_CR1","doi-asserted-by":"crossref","unstructured":"Abboud, A., Williams, R., Yu, H.: More applications of the polynomial method to algorithm design. In: Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201915), pp. 218\u2013230. SIAM, Philadelphia (2015)","DOI":"10.1137\/1.9781611973730.17"},{"key":"62_CR2","doi-asserted-by":"crossref","unstructured":"Afshani, P., Chan, T.M., Tsakalidis, K.: Deterministic rectangle enclosure and offline dominance reporting on the RAM. In: Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP\u201914), Part I. Lecture Notes in Computer Science, vol. 8572, pp. 77\u201388. Springer, Heidelberg (2014)","DOI":"10.1007\/978-3-662-43948-7_7"},{"issue":"1","key":"62_CR3","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1006\/inco.1997.2632","volume":"136","author":"S Albers","year":"1997","unstructured":"Albers, S., Hagerup, T.: Improved parallel integer sorting without concurrent writing. Inf. Comput. 136(1), 25\u201351 (1997)","journal-title":"Inf. Comput."},{"key":"62_CR4","doi-asserted-by":"crossref","unstructured":"Alman, J., Chan, T.M., Williams, R.: Polynomial representations of threshold functions and algorithmic applications. In: Proceedings of the 57th IEEE Symposium on Foundations of Computer Science (FOCS\u201916), pp. 467\u2013476 (2016)","DOI":"10.1109\/FOCS.2016.57"},{"key":"62_CR5","doi-asserted-by":"crossref","unstructured":"Alman, J., Williams, R.: Probabilistic polynomials and Hamming nearest neighbors. In: Proceedings of the 56th IEEE Symposium on Foundations of Computer Science (FOCS\u201915), pp. 136\u2013150 (2015)","DOI":"10.1109\/FOCS.2015.18"},{"key":"62_CR6","doi-asserted-by":"crossref","unstructured":"Andoni, A., Croitoru, D., P\u0103tra\u015fcu, M.M.: Hardness of nearest neighbor under $$L_\\infty $$. In: Proceedings of the 49th IEEE Symposium on Foundations of Computer Science (FOCS\u201908), pp. 424\u2013433 (2008)","DOI":"10.1109\/FOCS.2008.89"},{"key":"62_CR7","first-page":"1209","volume":"11","author":"VL Arlazarov","year":"1970","unstructured":"Arlazarov, V.L., Dinic, E.A., Kronrod, M.A., Faradzhev, I.A.: On economical construction of the transitive closure of a directed graph. Sov. Math. Dokl. 11, 1209\u20131210 (1970)","journal-title":"Sov. Math. Dokl."},{"issue":"4","key":"62_CR8","doi-asserted-by":"publisher","first-page":"547","DOI":"10.1007\/PL00009478","volume":"22","author":"TM Chan","year":"1999","unstructured":"Chan, T.M.: Geometric applications of a randomized optimization technique. Discret. Comput. Geom. 22(4), 547\u2013567 (1999)","journal-title":"Discret. Comput. Geom."},{"issue":"2","key":"62_CR9","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1007\/s00453-007-9062-1","volume":"50","author":"TM Chan","year":"2008","unstructured":"Chan, T.M.: All-pairs shortest paths with real weights in $$O(n^3\/\\log n)$$ time. Algorithmica 50(2), 236\u2013243 (2008)","journal-title":"Algorithmica"},{"issue":"5","key":"62_CR10","doi-asserted-by":"publisher","first-page":"2075","DOI":"10.1137\/08071990X","volume":"39","author":"TM Chan","year":"2010","unstructured":"Chan, T.M.: More algorithms for all-pairs shortest paths in weighted graphs. SIAM J. Comput. 39(5), 2075\u20132089 (2010)","journal-title":"SIAM J. Comput."},{"key":"62_CR11","doi-asserted-by":"crossref","unstructured":"Chan, T.M.: Speeding up the Four Russians algorithm by about one more logarithmic factor. In: Proceedings of the 26th ACM\u2013SIAM Symposium on Discrete Algorithms (SODA\u201915), pp. 212\u2013217. SIAM, Philadelphia (2015)","DOI":"10.1137\/1.9781611973730.16"},{"key":"62_CR12","doi-asserted-by":"crossref","unstructured":"Chan, T.M., Larsen, K.G., P\u0103tra\u015fcu, M.: Orthogonal range searching on the RAM, revisited. In: Proceedings of the 27th ACM Symposium on Computational Geometry (SoCG\u201911), pp. 1\u201310. ACM, New York (2011)","DOI":"10.1145\/1998196.1998198"},{"key":"62_CR13","doi-asserted-by":"crossref","unstructured":"Chan, T.M., P\u0103tra\u015fcu, M.: Counting inversions, offline orthogonal range counting, and related problems. In: Proceedings of the 21st ACM\u2013SIAM Symposium on Discrete Algorithms (SODA\u201910), pp. 161\u2013173. SIAM, Philadelphia (2010)","DOI":"10.1137\/1.9781611973075.15"},{"key":"62_CR14","doi-asserted-by":"crossref","unstructured":"Chan, T.M., Williams, R.: Deterministic APSP, orthogonal vectors, and more: Quickly derandomizing Razborov\u2013Smolensky. In: Proceedings of the 27th ACM\u2013SIAM Symposium on Discrete Algorithms (SODA\u201916), pp. 1246\u20131255. ACM, New York (2016)","DOI":"10.1137\/1.9781611974331.ch87"},{"issue":"2","key":"62_CR15","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1006\/jcta.1996.0077","volume":"75","author":"DM Gordon","year":"1996","unstructured":"Gordon, D.M., Patashnik, O., Kuperberg, G., Spencer, J.H.: Asymptotically optimal covering designs. J. Comb. Theory Ser. A 75(2), 270\u2013280 (1996)","journal-title":"J. Comb. Theory Ser. A"},{"key":"62_CR16","doi-asserted-by":"crossref","unstructured":"Han, Y., Takaoka, T.: An $$O(n^3\\log \\log n\/\\log ^2n)$$ time algorithm for all pairs shortest paths. In: Proceedings of the 13th Scandinavian Workshop on Algorithm Theory (SWAT\u201912). Lecture Notes in Computer Science, vol. 7357, pp. 131\u2013141. Springer, Heidelberg (2012)","DOI":"10.1007\/978-3-642-31155-0_12"},{"issue":"1","key":"62_CR17","doi-asserted-by":"publisher","first-page":"321","DOI":"10.4086\/toc.2012.v008a014","volume":"8","author":"S Har-Peled","year":"2012","unstructured":"Har-Peled, S., Indyk, P., Motwani, R.: Approximate nearest neighbor: towards removing the curse of dimensionality. Theory Comput. 8(1), 321\u2013350 (2012)","journal-title":"Theory Comput."},{"key":"62_CR18","unstructured":"Impagliazzo, R., Lovett, S., Paturi, R., Schneider, S.: 0-1 integer linear programming with a linear number of constraints (2014). \n                    arXiv:1401.5512"},{"issue":"4","key":"62_CR19","doi-asserted-by":"publisher","first-page":"627","DOI":"10.1006\/jcss.2001.1781","volume":"63","author":"P Indyk","year":"2001","unstructured":"Indyk, P.: On approximate nearest neighbors under $$l_\\infty $$ norm. J. Comput. Syst. Sci. 63(4), 627\u2013638 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"62_CR20","doi-asserted-by":"crossref","unstructured":"Larsen, K.G., Williams, R.: Faster online matrix-vector multiplication. In: Proceedings of the 28th ACM\u2013SIAM Symposium on Discrete Algorithms (SODA\u201917), pp. 2182\u20132189. SIAM, Philadelphia (2017)","DOI":"10.1137\/1.9781611974782.142"},{"key":"62_CR21","doi-asserted-by":"crossref","unstructured":"Le Gall, F.: Powers of tensors and fast matrix multiplication. In: Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation (ISSAC\u201914), pp. 296\u2013303. ACM, New York (2014)","DOI":"10.1145\/2608628.2608664"},{"key":"62_CR22","doi-asserted-by":"crossref","unstructured":"Le Gall, F., Urrutia, F.: Improved rectangular matrix multiplication using powers of the Coppersmith\u2013Winograd tensor. In: Proceedings of the 29th ACM\u2013SIAM Symposium on Discrete Algorithms (SODA\u201918), pp. 1029\u20131046. SIAM, Philadelphia (2018)","DOI":"10.1137\/1.9781611975031.67"},{"issue":"5","key":"62_CR23","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/0020-0190(91)90071-O","volume":"38","author":"J Matou\u0161ek","year":"1991","unstructured":"Matou\u0161ek, J.: Computing dominances in $$E^n$$. Inf. Process. Lett. 38(5), 277\u2013278 (1991)","journal-title":"Inf. Process. Lett."},{"key":"62_CR24","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry: An Introduction. Texts and Monographs in Computer Science","author":"FP Preparata","year":"1985","unstructured":"Preparata, F.P., Shamos, M.I.: Computational Geometry: An Introduction. Texts and Monographs in Computer Science. Springer, New York (1985)"},{"issue":"2","key":"62_CR25","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1006\/jagm.2002.1211","volume":"42","author":"M Thorup","year":"2002","unstructured":"Thorup, M.: Randomized sorting in $$O(n\\log \\log n)$$ time and linear space using addition, shift, and bit-wise Boolean operations. J. Algorithms 42(2), 205\u2013230 (2002)","journal-title":"J. Algorithms"},{"issue":"2\u20133","key":"62_CR26","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1016\/j.tcs.2005.09.023","volume":"348","author":"R Williams","year":"2005","unstructured":"Williams, R.: A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci. 348(2\u20133), 357\u2013365 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"62_CR27","unstructured":"Williams, R.: Matrix-vector multiplication in sub-quadratic time (some preprocessing required). In: Proceedings of the 18th ACM\u2013SIAM Symposium on Discrete Algorithms (SODA\u201907), pp. 995\u20131001. ACM, New York (2007)"},{"key":"62_CR28","doi-asserted-by":"crossref","unstructured":"Williams, R.: Multiplying matrices faster than Coppersmith\u2013Winograd. In: Proceedings of the 44th Symposium on Theory of Computing (STOC\u201912), pp. 887\u2013898. ACM, New York (2012)","DOI":"10.1145\/2213977.2214056"},{"key":"62_CR29","doi-asserted-by":"crossref","unstructured":"Williams, R.: Faster all-pairs shortest paths via circuit complexity. In: Proceedings of the 46th ACM Symposium on Theory of Computing (STOC\u201914), pp. 664\u2013673. ACM, New York (2014)","DOI":"10.1145\/2591796.2591811"},{"key":"62_CR30","doi-asserted-by":"crossref","unstructured":"Yu, H.: An improved combinatorial algorithm for Boolean matrix multiplication. In: Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP\u201915), Part I. Lecture Notes in Computer Science, vol. 9134, pp. 1094\u20131105. Springer, Heidelberg (2015)","DOI":"10.1007\/978-3-662-47672-7_89"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-019-00062-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-019-00062-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-019-00062-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,17]],"date-time":"2020-05-17T06:39:39Z","timestamp":1589697579000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-019-00062-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,3,5]]},"references-count":30,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,6]]}},"alternative-id":["62"],"URL":"https:\/\/doi.org\/10.1007\/s00454-019-00062-5","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2019,3,5]]},"assertion":[{"value":"2 October 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 December 2018","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 January 2019","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 March 2019","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}