{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,21]],"date-time":"2026-02-21T08:18:51Z","timestamp":1771661931279,"version":"3.50.1"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2015,12,11]],"date-time":"2015-12-11T00:00:00Z","timestamp":1449792000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"Spanish Ministry of Economy and Competitiveness (MINECO) and European Union (FEDER funds)","award":["TIN2013-46181-C2-1-R"],"award-info":[{"award-number":["TIN2013-46181-C2-1-R"]}]},{"name":"Catalan Agency for the Management of University and Research Grants (AGAUR)","award":["SGR 2014:1034 (ALBCOM)"],"award-info":[{"award-number":["SGR 2014:1034 (ALBCOM)"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2016,8]]},"DOI":"10.1007\/s00453-015-0097-4","type":"journal-article","created":{"date-parts":[[2015,12,11]],"date-time":"2015-12-11T10:58:20Z","timestamp":1449831500000},"page":"684-723","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["On the Cost of Fixed Partial Match Queries in K-d Trees"],"prefix":"10.1007","volume":"75","author":[{"given":"Amalia","family":"Duch","sequence":"first","affiliation":[]},{"given":"Gustavo","family":"Lau","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1302-9067","authenticated-orcid":false,"given":"Conrado","family":"Mart\u00ednez","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,12,11]]},"reference":[{"issue":"9","key":"97_CR1","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1145\/361002.361007","volume":"18","author":"JL Bentley","year":"1975","unstructured":"Bentley, J.L.: Multidimensional binary search trees used for associative retrieval. Commun. ACM 18(9), 509\u2013517 (1975)","journal-title":"Commun. ACM"},{"issue":"1","key":"97_CR2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF00288933","volume":"4","author":"JL Bentley","year":"1974","unstructured":"Bentley, J.L., Finkel, R.A.: Quad trees: a data structure for retrieval on composite keys. Acta Inform. 4(1), 1\u20139 (1974)","journal-title":"Acta Inform."},{"issue":"6","key":"97_CR3","doi-asserted-by":"crossref","first-page":"2560","DOI":"10.1214\/12-AAP912","volume":"23","author":"N Broutin","year":"2013","unstructured":"Broutin, N., Neininger, R., Sulzbach, H.: A limit process for partial match queries in random quadtrees and 2-d trees. Ann. Appl. Probab. 23(6), 2560\u20132603 (2013)","journal-title":"Ann. Appl. Probab."},{"issue":"4\u20135","key":"97_CR4","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1007\/s002360000044","volume":"37","author":"P Chanzy","year":"2001","unstructured":"Chanzy, P., Devroye, L., Zamora-Cura, C.: Analysis of range search for random $$k$$ k -d trees. Acta Inform. 37(4\u20135), 355\u2013383 (2001)","journal-title":"Acta Inform."},{"issue":"6","key":"97_CR5","doi-asserted-by":"crossref","first-page":"1440","DOI":"10.1137\/S0097539703437491","volume":"35","author":"H-H Chern","year":"2006","unstructured":"Chern, H.-H., Hwang, H.-K.: Partial match queries in random $$k$$ k -d trees. SIAM J. Comput. 35(6), 1440\u20131466 (2006)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"97_CR6","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1239\/aap\/1300198518","volume":"43","author":"N Curien","year":"2011","unstructured":"Curien, N., Joseph, A.: Partial match queries in two-dimensional quadtrees: a probabilistic approach. Adv. Appl. Probab. 43(1), 178\u2013194 (2011)","journal-title":"Adv. Appl. Probab."},{"key":"97_CR7","doi-asserted-by":"crossref","unstructured":"Cunto, W., Lau, G., Flajolet, Ph.: Analysis of $$k$$ k d-trees improved by local reorganisations. In: Dehne, F., Sack, J.-R., Santoro, N. (eds.), Workshop on Algorithms and Data Structures (WADS\u201989), Volume 382 of Lecture Notes in Computer Science, pp. 24\u201338. Springer (1989)","DOI":"10.1007\/3-540-51542-9_4"},{"key":"97_CR8","unstructured":"Duch A., Estivill-Castro, V., Mart\u00ednez, C.: Randomized $$k$$ k International Symposium on Algorithms and Computation (ISAAC), Volume 1533 of Lecture Notes in Computer Science, pp. 199\u2013208. Springer (1998)"},{"issue":"1","key":"97_CR9","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1002\/rsa.20476","volume":"45","author":"A Duch","year":"2014","unstructured":"Duch, A., Jim\u00e9nez, R.M., Mart\u00ednez, C.: Selection by rank in $$k$$ k -dimensional binary search trees. Random Struct. Algorithms 45(1), 14\u201337 (2014)","journal-title":"Random Struct. Algorithms"},{"issue":"5","key":"97_CR10","doi-asserted-by":"crossref","first-page":"1678","DOI":"10.1137\/S0097539799358926","volume":"30","author":"L Devroye","year":"2000","unstructured":"Devroye, L., Jabbour, J., Zamora-Cura, C.: Squarish $$k$$ k -d trees. SIAM J. Comput. 30(5), 1678\u20131700 (2000)","journal-title":"SIAM J. Comput."},{"key":"97_CR11","unstructured":"Duch, A., Lau, G., Mart\u00ednez, C.: On the average performance of fixed partial match queries in random relaxed $$k$$ k International Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA). Discrete Mathematics & Theoretical Computer Science (Proceedings), pp. 103\u2013114 (2014)"},{"issue":"1","key":"97_CR12","doi-asserted-by":"crossref","first-page":"226","DOI":"10.1016\/S0196-6774(02)00213-4","volume":"44","author":"A Duch","year":"2002","unstructured":"Duch, A., Mart\u00ednez, C.: On the average performance of orthogonal range search in multidimensional data structures. J. Algorithms 44(1), 226\u2013245 (2002)","journal-title":"J. Algorithms"},{"key":"97_CR13","volume-title":"An Introduction to Probability Theory and Its Applications","author":"W Feller","year":"1971","unstructured":"Feller, W.: An Introduction to Probability Theory and Its Applications. Wiley, New York (1971)"},{"issue":"1","key":"97_CR14","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1137\/0403019","volume":"3","author":"Ph Flajolet","year":"1990","unstructured":"Flajolet, Ph, Odlyzko, A.: Singularity analysis of generating functions. SIAM J. Discrete Math. 3(1), 216\u2013240 (1990)","journal-title":"SIAM J. Discrete Math."},{"issue":"2","key":"97_CR15","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1145\/5383.5453","volume":"33","author":"Ph Flajolet","year":"1986","unstructured":"Flajolet, Ph, Puech, C.: Partial match retrieval of multidimensional data. J. ACM 33(2), 371\u2013407 (1986)","journal-title":"J. ACM"},{"key":"97_CR16","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511801655","volume-title":"Analytic Combinatorics","author":"Ph Flajolet","year":"2009","unstructured":"Flajolet, Ph, Sedgewick, R.: Analytic Combinatorics. Cambridge University Press, Cambridge (2009)"},{"key":"97_CR17","volume-title":"Univariate Discrete Distributions","author":"NL Johnson","year":"1992","unstructured":"Johnson, N.L., Kotz, S., Kemp, A.W.: Univariate Discrete Distributions, 2nd edn. Wiley, New York (1992)","edition":"2"},{"issue":"1\u20132","key":"97_CR18","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/BF02679618","volume":"29","author":"C Mart\u00ednez","year":"2001","unstructured":"Mart\u00ednez, C., Panholzer, A., Prodinger, H.: Partial match queries in relaxed multidimensional search trees. Algorithmica 29(1\u20132), 181\u2013204 (2001)","journal-title":"Algorithmica"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0097-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-015-0097-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0097-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T19:47:22Z","timestamp":1559072842000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-015-0097-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,12,11]]},"references-count":18,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,8]]}},"alternative-id":["97"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-0097-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,12,11]]}}}