{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,9]],"date-time":"2026-07-09T06:03:06Z","timestamp":1783576986268,"version":"3.55.0"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540684046","type":"print"},{"value":"9783540684053","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-68405-3_1","type":"book-chapter","created":{"date-parts":[[2008,8,26]],"date-time":"2008-08-26T08:22:42Z","timestamp":1219738962000},"page":"3-18","source":"Crossref","is-referenced-by-count":15,"title":["Quantitative Analysis of Nearest-Neighbors Search in High-Dimensional Sampling-Based Motion Planning"],"prefix":"10.1007","author":[{"given":"Erion","family":"Plaku","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lydia E.","family":"Kavraki","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"1_CR1","unstructured":"Amato, N.M., Bayazit, B., Dale, L., Jones, C., Vallejo, D.: OBPRM: An obstacle-based PRM for 3d workspaces. In: Agarwal, P., Kavraki, L.E., Mason, M. (eds.) Robotics: The Algorithmic Perspective, pp. 156\u2013168. AK Peters (1998)"},{"issue":"6","key":"1_CR2","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., Nathan, S.: An optimal algorithm for approximate nearest neighbor searching in fixed dimensions. Journal of the ACM\u00a045(6), 891\u2013923 (1998)","journal-title":"Journal of the ACM"},{"key":"1_CR3","doi-asserted-by":"crossref","unstructured":"Atramentov, A., LaValle, S.M.: Efficient nearest neighbor searching for motion planning. In: IEEE International Conference on Robotics and Automation, Washington, DC, pp. 632\u2013637 (2002)","DOI":"10.1109\/ROBOT.2002.1013429"},{"key":"1_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/3-540-49257-7_15","volume-title":"Database Theory - ICDT\u201999","author":"K. Beyer","year":"1998","unstructured":"Beyer, K., Goldstein, J., Ramakrishnan, R., Shaft, U.: When is \u201cnearest neighbor\u201d meaningful? In: Beeri, C., Bruneman, P. (eds.) ICDT 1999. LNCS, vol.\u00a01540, pp. 217\u2013235. Springer, Heidelberg (1998)"},{"key":"1_CR5","doi-asserted-by":"crossref","unstructured":"Boor, V., Overmars, M.H., van der Stappen, A.F.: The gaussian sampling strategy for probabilistic roadmap planners. In: IEEE International Conference on Robotics and Automation, Detroit, MI, pp. 1018\u20131023 (1999)","DOI":"10.1109\/ROBOT.1999.772447"},{"key":"1_CR6","doi-asserted-by":"crossref","unstructured":"Borodin, A., Ostrovsky, R., Rabani, Y.: Lower bounds for high dimensional nearest neighbor search and related problems. In: ACM Symposium on Theory of Computing, Atlanta, GA, pp. 312\u2013321 (1999)","DOI":"10.1145\/301250.301330"},{"key":"1_CR7","unstructured":"Brin, S.: Near neighbor search in large metric spaces. In: International Conference on Very Large Data Bases, San Francisco, California, pp. 574\u2013584 (1995)"},{"key":"1_CR8","unstructured":"Bullo, F., Murray, R.M.: Proportional derivative (PD) control on the Euclidean group. In: European Control Conference, Rome, Italy, pp. 1091\u20131097 (1995)"},{"key":"1_CR9","volume-title":"Principles of Robot Motion: Theory, Algorithms, and Implementations","author":"H. Choset","year":"2005","unstructured":"Choset, H., Lynch, K.M., Hutchinson, S., Kantor, G., Burgard, W., Kavraki, L.E., Thrun, S.: Principles of Robot Motion: Theory, Algorithms, and Implementations. MIT Press, Cambridge (2005)"},{"key":"1_CR10","unstructured":"Cui, B., Shen, H.T., Shen, J., Tan, K.-L.: Exploring bit-difference for approximate knn search in high-dimensional databases. In: Australasian Database Conference, Newcastle, Australia, pp. 165\u2013174 (2005)"},{"issue":"2","key":"1_CR11","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1145\/280277.280279","volume":"30","author":"V. Gaede","year":"1998","unstructured":"Gaede, V., G\u00fcnther, O.: Multidimensional access methods. ACM Computing Surveys\u00a030(2), 170\u2013231 (1998)","journal-title":"ACM Computing Surveys"},{"key":"1_CR12","unstructured":"Hinneburg, A., Aggarwal, C.C., Keim, D.A.: What is the nearest neighbor in high dimensional spaces? In: International Conference on Very Large Data Bases, Cairo, Egypt, pp. 506\u2013515 (2000)"},{"key":"1_CR13","doi-asserted-by":"crossref","unstructured":"Hsu, D., Jiang, T., Reif, J., Sun, Z.: The bridge test for sampling narrow passages with probabilistic roadmap planners. In: IEEE International Conference on Robotics and Automation, Taipei, Taiwan, pp. 4420\u20134442 (2003)","DOI":"10.1109\/ROBOT.2003.1242285"},{"issue":"3","key":"1_CR14","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1177\/027836402320556421","volume":"21","author":"D. Hsu","year":"2002","unstructured":"Hsu, D., Kindel, R., Latombe, J.-C., Rock, S.: Randomized kinodynamic motion planning with moving obstacles. International Journal of Robotics Research\u00a021(3), 233\u2013255 (2002)","journal-title":"International Journal of Robotics Research"},{"key":"1_CR15","first-page":"877","volume-title":"Handbook of Discrete and Computational Geometry","author":"P. Indyk","year":"2004","unstructured":"Indyk, P.: Nearest neighbors in high-dimensional spaces. In: Goodman, J.E., O\u2019Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, pp. 877\u2013892. CRC Press, Boca Raton (2004)"},{"key":"1_CR16","first-page":"177","volume-title":"Handbook of Discrete and Computational Geometry","author":"P. Indyk","year":"2004","unstructured":"Indyk, P., Matou\u0161ek, J.: Low-distortion embeddings of finite metric spaces. In: Goodman, J.E., O\u2019Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, pp. 177\u2013196. CRC Press, Boca Raton (2004)"},{"issue":"4","key":"1_CR17","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1109\/70.508439","volume":"12","author":"L.E. Kavraki","year":"1996","unstructured":"Kavraki, L.E., \u0160vestka, P., Latombe, J.-C., Overmars, M.H.: Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Transactions on Robotics and Automation\u00a012(4), 566\u2013580 (1996)","journal-title":"IEEE Transactions on Robotics and Automation"},{"issue":"1","key":"1_CR18","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1109\/69.908983","volume":"13","author":"F. Korn","year":"2001","unstructured":"Korn, F., Pagel, B.-U., Faloutsos, C.: On the \u2018dimensionality curse\u2019 and the \u2018self-similarity blessing\u2019. IEEE Transactions on Knowledge and Data Engineering\u00a013(1), 96\u2013111 (2001)","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"issue":"2","key":"1_CR19","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1137\/S0097539798347177","volume":"30","author":"E. Kushilevitz","year":"2000","unstructured":"Kushilevitz, E., Ostrovsky, R., Rabani, Y.: Efficient search for approximate nearest neighbor in high dimensional spaces. SIAM Journal of Computing\u00a030(2), 457\u2013474 (2000)","journal-title":"SIAM Journal of Computing"},{"issue":"5","key":"1_CR20","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1177\/02783640122067453","volume":"20","author":"S.M. LaValle","year":"2001","unstructured":"LaValle, S.M., Kuffner, J.J.: Randomized kinodynamic planning. International Journal of Robotics Research\u00a020(5), 378\u2013400 (2001)","journal-title":"International Journal of Robotics Research"},{"key":"1_CR21","first-page":"825","volume-title":"Advances in Neural Information Processing Systems","author":"T. Liu","year":"2005","unstructured":"Liu, T., Moore, A.W., Gray, A., Yang, K.: An investigation of practical approximate nearest neighbor algorithms. In: Saul, L.K., Weiss, Y., Bottou, L. (eds.) Advances in Neural Information Processing Systems, pp. 825\u2013832. MIT Press, Cambridge (2005)"},{"issue":"4","key":"1_CR22","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1109\/TRO.2005.847599","volume":"21","author":"E. Plaku","year":"2005","unstructured":"Plaku, E., Bekris, K.E., Chen, B.Y., Ladd, A.M., Kavraki, L.E.: Sampling-based roadmap of trees for parallel motion planning. IEEE Transactions on Robotics\u00a021(4), 597\u2013608 (2005)","journal-title":"IEEE Transactions on Robotics"},{"key":"1_CR23","unstructured":"Weber, R., Schek, H.-J., Blott, S.: A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces. In: International Conference on Very Large Data Bases, pp. 194\u2013205. New York (1998)"}],"container-title":["Springer Tracts in Advanced Robotics","Algorithmic Foundation of Robotics VII"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-68405-3_1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,3]],"date-time":"2021-05-03T00:50:50Z","timestamp":1620003050000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-68405-3_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540684046","9783540684053"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-68405-3_1","relation":{},"ISSN":["1610-7438","1610-742X"],"issn-type":[{"value":"1610-7438","type":"print"},{"value":"1610-742X","type":"electronic"}],"subject":[]}}