{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,29]],"date-time":"2025-09-29T08:07:45Z","timestamp":1759133265994},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540100034"},{"type":"electronic","value":"9783540393467"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1980]]},"DOI":"10.1007\/3-540-10003-2_92","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T17:00:14Z","timestamp":1330189214000},"page":"470-482","source":"Crossref","is-referenced-by-count":12,"title":["A worst-case analysis of nearest neighbor searching by projection"],"prefix":"10.1007","author":[{"given":"Christos H.","family":"Papadimitriou","sequence":"first","affiliation":[]},{"given":"Jon Louis","family":"Bentley","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,24]]},"reference":[{"key":"39_CR1","volume-title":"Dynamic Programming","author":"R. Bellman","year":"1957","unstructured":"Bellman, R. [1957]. Dynamic Programming, Princeton University Press, Princeton, New Jersey."},{"key":"39_CR2","unstructured":"Bentley, J. L. [1976]. \"Divide and conquer algorithms for closest point problems in multidimensional space,\" unpublished Ph.D. Thesis, University of North Carolina, December 1976."},{"key":"39_CR3","unstructured":"Bentley, J.L. [1979]. \"Multidimensional divide-and-conquer,\" to appear in Communications of the ACM."},{"key":"39_CR4","unstructured":"Bentley, J. L., B. W. Weide, and A. C. Yao [1979]. \"Optimal expected-time algorithms for closest-point problems,\" Carnegie-Mellon University Computer Science Report CMU-CS-79-111."},{"key":"39_CR5","doi-asserted-by":"crossref","first-page":"1000","DOI":"10.1109\/T-C.1975.224110","volume":"10","author":"J. H. Friedman","year":"1975","unstructured":"Friedman, J. H., F. Baskett, and L. J. Shustek [1975]. \"An algorithm for finding nearest neighbors,\" IEEE Transactions on Computers C-24, 10, pp. 1000\u20131006, October 1975.","journal-title":"IEEE Transactions on Computers C-24"},{"key":"39_CR6","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1145\/355744.355745","volume":"3","author":"J. H. Friedman","year":"1977","unstructured":"Friedman, J. H., J. L. Bentley, and R. A. Finkel [1977]. \"An algorithm for finding best matches in logarithmic expected time,\" ACM Transactions on Mathematical Software 3, pp. 209\u2013226, September 1977.","journal-title":"ACM Transactions on Mathematical Software"},{"key":"39_CR7","volume-title":"The Art of Computer Programming, volume 3: Sorting and Searching","author":"D. E. Knuth","year":"1973","unstructured":"Knuth, D. E. [1973]. The Art of Computer Programming, volume 3: Sorting and Searching, Addison-Wesley, Reading, Massachusetts."},{"key":"39_CR8","first-page":"185","volume":"3","author":"R. C. T. T. Lee","year":"1976","unstructured":"Lee, R. C. T., Y. H. Chin, and S. C. Chang [1976]. \"Application of principal component analysis to multikey searching,\" IEEE Transactions on Software Engineering SE-2, 3, pp. 185\u2013193, September 1976.","journal-title":"IEEE Transactions on Software Engineering SE-2"},{"key":"39_CR9","doi-asserted-by":"crossref","unstructured":"Lipton, R. and R. E. Tarjan [1977]. \"Applications of a planar separator theorem,\" Eighteenth Symposium on the Foundations of Computer Science, pp. 162\u2013170, IEEE, October 1977.","DOI":"10.1109\/SFCS.1977.6"},{"key":"39_CR10","unstructured":"Papadimitriou, C. H. [1979]. \"Worst-case probabilistic analysis of a geometric location problem,\" submitted to Mathematics of Operations Research, November 1979."},{"key":"39_CR11","unstructured":"Shamos, M. I. [1978]. \"Computational geometry\", unpublished Ph.D. Thesis, Yale University, May 1978."},{"key":"39_CR12","unstructured":"Weide, B. W. [1978]. \"Statistical methods in algorithm design and analysis,\" Ph.D. Thesis, Carnegie-Mellon University, Carnegie-Mellon University Computer Science Report CMU-CS-78-142."},{"key":"39_CR13","unstructured":"Zolnowsky, J. E. [1978]. \"Topics in computational geometry,\" Ph.D. Thesis, Stanford University. Stanford Computer Science Department Report STAN-CS-78-659."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-10003-2_92.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T20:33:14Z","timestamp":1619555594000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-10003-2_92"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1980]]},"ISBN":["9783540100034","9783540393467"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/3-540-10003-2_92","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1980]]}}}