{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:43:43Z","timestamp":1725489823677},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540739487"},{"type":"electronic","value":"9783540739517"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-73951-7_11","type":"book-chapter","created":{"date-parts":[[2007,8,20]],"date-time":"2007-08-20T10:18:03Z","timestamp":1187605083000},"page":"114-126","source":"Crossref","is-referenced-by-count":0,"title":["Discrepancy-Sensitive Dynamic Fractional Cascading, Dominated Maxima Searching, and 2-d Nearest Neighbors in Any Minkowski Metric"],"prefix":"10.1007","author":[{"given":"Mikhail J.","family":"Atallah","sequence":"first","affiliation":[]},{"given":"Marina","family":"Blanton","sequence":"additional","affiliation":[]},{"given":"Michael T.","family":"Goodrich","sequence":"additional","affiliation":[]},{"given":"Stanislas","family":"Polu","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"11_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/3-540-45506-X_2","volume-title":"Computational Discrete Mathematics: Advanced Lectures","author":"H. Alt","year":"2001","unstructured":"Alt, H.: The nearest neighbor. In: Computational Discrete Mathematics. LNCS, vol.\u00a02122, pp. 13\u201324. Springer, Heidelberg (2001)"},{"key":"11_CR2","volume-title":"A First Course in Order Statitics","author":"B.C. Arnold","year":"1992","unstructured":"Arnold, B.C., Balakrishnan, N., Nagaraja, H.N.: A First Course in Order Statitics. Wiley-Interscience, Chichester (1992)"},{"key":"11_CR3","doi-asserted-by":"publisher","first-page":"891","DOI":"10.1145\/293347.293348","volume":"45","author":"S. Arya","year":"1998","unstructured":"Arya, S., Mount, D.M., Netanyahu, N.S., Silverman, R., Wu, A.: An optimal algorithm for approximate nearest neighbor searching in fixed dimensions. J. ACM\u00a045, 891\u2013923 (1998)","journal-title":"J. ACM"},{"key":"11_CR4","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1145\/98524.98564","volume-title":"SCG 1990","author":"J.L. Bentley","year":"1990","unstructured":"Bentley, J.L.: K-d trees for semidynamic point sets. In: SCG 1990. Proceedings of the sixth annual symposium on Computational geometry, pp. 187\u2013197. ACM Press, New York (1990)"},{"issue":"4","key":"11_CR5","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1145\/355921.355927","volume":"6","author":"J.L. Bentley","year":"1980","unstructured":"Bentley, J.L., Weide, B.W., Yao, A.C.: Optimal expected-time algorithms for closest point problems. ACM Trans. Math. Softw.\u00a06(4), 563\u2013580 (1980)","journal-title":"ACM Trans. Math. Softw."},{"key":"11_CR6","doi-asserted-by":"crossref","unstructured":"Beygelzimer, A., Kakade, S., Langford, J.: Cover trees for nearest neighbor. In: ICML 2006. Proceedings of the 23rd international conference on Machine learning, pp. 97\u2013104 (2006)","DOI":"10.1145\/1143844.1143857"},{"key":"11_CR7","doi-asserted-by":"publisher","first-page":"1196","DOI":"10.1145\/1109557.1109689","volume-title":"Proceedings of the seventeenth ACM-SIAM symposium on Discrete algorithm","author":"T.M. Chan","year":"2006","unstructured":"Chan, T.M.: A dynamic data structure for 3-d convex hull and 2-d nearest neighbor queries. In: Proceedings of the seventeenth ACM-SIAM symposium on Discrete algorithm, pp. 1196\u20131202. ACM Press, New York (2006)"},{"key":"11_CR8","unstructured":"Chazelle, B.: Geometric complexity and the discrepancy method. In: Abstracts 15th European Workshop Comput. Geom., pp. 21\u201323. INRIA Sophia-Antipolis (1999)"},{"key":"11_CR9","volume-title":"The Discrepancy Method","author":"B. Chazelle","year":"2002","unstructured":"Chazelle, B.: The Discrepancy Method. Cambridge Univ. Press, Cambridge (2002)"},{"issue":"3","key":"11_CR10","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/BF01840440","volume":"1","author":"B. Chazelle","year":"1986","unstructured":"Chazelle, B., Guibas, L.J.: Fractional cascading: I. A data structuring technique. Algorithmica\u00a01(3), 133\u2013162 (1986)","journal-title":"Algorithmica"},{"key":"11_CR11","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/BF01840441","volume":"1","author":"B. Chazelle","year":"1986","unstructured":"Chazelle, B., Guibas, L.J.: Fractional cascading: II. Applications. Algorithmica\u00a01, 163\u2013191 (1986)","journal-title":"Algorithmica"},{"key":"11_CR12","doi-asserted-by":"crossref","first-page":"15","DOI":"10.7551\/mitpress\/4908.003.0005","volume-title":"Nearest-Neighbor Methods for Learning and Vision: Theory and Practice","author":"K.L. Clarkson","year":"2006","unstructured":"Clarkson, K.L.: Nearest-neighbor searching and metric space dimensions. In: Shakhnarovich, G., Darrell, T., Indyk, P. (eds.) Nearest-Neighbor Methods for Learning and Vision: Theory and Practice, pp. 15\u201359. MIT Press, Cambridge (2006)"},{"key":"11_CR13","doi-asserted-by":"crossref","DOI":"10.1002\/0471722162","volume-title":"Order Statitics","author":"H.A. David","year":"2003","unstructured":"David, H.A., Nagaraja, H.N.: Order Statitics, 3rd edn. Wiley-Interscience, Chichester (2003)","edition":"3"},{"key":"11_CR14","first-page":"296","volume-title":"SCG","author":"D. Eppstein","year":"2005","unstructured":"Eppstein, D., Goodrich, M.T., Sun, J.Z.: The skip quadtree: A simple dynamic data structure for multidimensional data. In: SCG. 21st ACM Symp. on Computational Geometry, pp. 296\u2013305. ACM Press, New York (2005)"},{"key":"11_CR15","doi-asserted-by":"publisher","first-page":"741","DOI":"10.1145\/509907.510013","volume-title":"STOC 2002","author":"D.R. Karger","year":"2002","unstructured":"Karger, D.R., Ruhl, M.: Finding nearest neighbors in growth-restricted metrics. In: STOC 2002. Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pp. 741\u2013750. ACM Press, New York (2002)"},{"key":"11_CR16","first-page":"798","volume-title":"SODA","author":"R. Krauthgamer","year":"2004","unstructured":"Krauthgamer, R., Lee, J.R.: Navigating nets: simple algorithms for proximity search. In: SODA. Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms, pp. 798\u2013807. ACM Press, New York (2004)"},{"key":"11_CR17","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/BF01840386","volume":"5","author":"K. Mehlhorn","year":"1990","unstructured":"Mehlhorn, K., N\u00e4her, S.: Dynamic fractional cascading. Algorithmica\u00a05, 215\u2013241 (1990)","journal-title":"Algorithmica"},{"key":"11_CR18","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R. Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, New York (1995)"},{"key":"11_CR19","unstructured":"Munro, J.I., Papadakis, T., Sedgewick, R.: Deterministic skip lists. In: SODA. Proc. Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 367\u2013375 (1992)"},{"key":"11_CR20","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry: An Introduction","author":"F.P. Preparata","year":"1985","unstructured":"Preparata, F.P., Shamos, M.I.: Computational Geometry: An Introduction. Springer, New York (1985)"},{"issue":"2","key":"11_CR21","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1006\/jagm.1995.1032","volume":"19","author":"S. Sen","year":"1995","unstructured":"Sen, S.: Fractional cascading revisited. J. Algorithms\u00a019(2), 161\u2013172 (1995)","journal-title":"J. Algorithms"},{"key":"11_CR22","doi-asserted-by":"crossref","unstructured":"Weisstein, E.W.: Beta binomial distribution. In: MathWorld\u2014A Wolfram Web Resource. Wolfram (2007), http:\/\/mathworld.wolfram.com\/BetaBinomialDistribution.html","DOI":"10.3888\/tmj.10.3-3"},{"key":"11_CR23","doi-asserted-by":"crossref","unstructured":"Weisstein, E.W.: Local discrepancy. In: MathWorld\u2014A Wolfram Web Resource. Wolfram (2007), http:\/\/mathworld.wolfram.com\/LocalDiscrepancy.html","DOI":"10.3888\/tmj.10.3-3"},{"key":"11_CR24","unstructured":"Yap, C., Zhu, Y.: Yet another look at fractional cascading: B-graphs with application to point location. In: CCCG 2001. Proceedings of the 13th Canadian Conference on Computational Geometry, pp. 173\u2013176 (2001)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-73951-7_11.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,17]],"date-time":"2024-02-17T13:31:01Z","timestamp":1708176661000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-73951-7_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540739487","9783540739517"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-73951-7_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}