{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T18:00:18Z","timestamp":1743012018709,"version":"3.40.3"},"publisher-location":"Cham","reference-count":21,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319930398"},{"type":"electronic","value":"9783319930404"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-93040-4_13","type":"book-chapter","created":{"date-parts":[[2018,6,16]],"date-time":"2018-06-16T13:29:41Z","timestamp":1529155781000},"page":"151-163","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Efficient Approximate Algorithms for the Closest Pair Problem in High Dimensional Spaces"],"prefix":"10.1007","author":[{"given":"Xingyu","family":"Cai","sequence":"first","affiliation":[]},{"given":"Sanguthevar","family":"Rajasekaran","sequence":"additional","affiliation":[]},{"given":"Fan","family":"Zhang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,6,17]]},"reference":[{"key":"13_CR1","doi-asserted-by":"crossref","unstructured":"Bentley, J.L., Shamos, M.I.: Divide-and-conquer in multidimensional space. In: Proceedings of the Eighth Annual ACM Symposium on Theory of Computing, pp. 220\u2013230. ACM (1976)","DOI":"10.1145\/800113.803652"},{"issue":"1","key":"13_CR2","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/S0304-3975(96)00261-7","volume":"181","author":"S Chaudhuri","year":"1997","unstructured":"Chaudhuri, S., Dubhashi, D.: Probabilistic recurrence relations revisited. Theoret. Comput. Sci. 181(1), 45\u201356 (1997)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"13_CR3","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1145\/335191.335414","volume":"29","author":"Antonio Corral","year":"2000","unstructured":"Corral, A., Manolopoulos, Y., Theodoridis, Y., Vassilakopoulos, M.: Closest pair queries in spatial databases. In: ACM SIGMOD Record, vol. 29, pp. 189\u2013200. ACM (2000)","journal-title":"ACM SIGMOD Record"},{"issue":"1","key":"13_CR4","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1002\/rsa.10073","volume":"22","author":"S Dasgupta","year":"2003","unstructured":"Dasgupta, S., Gupta, A.: An elementary proof of a theorem of Johnson and Lindenstrauss. Random Struct. Algorithms 22(1), 60\u201365 (2003)","journal-title":"Random Struct. Algorithms"},{"key":"13_CR5","doi-asserted-by":"crossref","unstructured":"Datar, M., Immorlica, N., Indyk, P., Mirrokni, V.S.: Locality-sensitive hashing scheme based on p-stable distributions. In: Proceedings of the Twentieth Annual Symposium on Computational Geometry, pp. 253\u2013262. ACM (2004)","DOI":"10.1145\/997817.997857"},{"issue":"1","key":"13_CR6","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1006\/jagm.1997.0873","volume":"25","author":"M Dietzfelbinger","year":"1997","unstructured":"Dietzfelbinger, M., Hagerup, T., Katajainen, J., Penttonen, M.: A reliable randomized algorithm for the closest-pair problem. J. Algorithms 25(1), 19\u201351 (1997)","journal-title":"J. Algorithms"},{"key":"13_CR7","unstructured":"Rabin, M.: Probabilistic algorithms (1976)"},{"issue":"1","key":"13_CR8","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1016\/0020-0190(79)90085-1","volume":"8","author":"S Fortune","year":"1979","unstructured":"Fortune, S., Hopcroft, J.: A note on Rabin\u2019s nearest-neighbor algorithm. Inf. Process. Lett. 8(1), 20\u201323 (1979)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"13_CR9","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/s11390-006-0027-7","volume":"21","author":"Q Ge","year":"2006","unstructured":"Ge, Q., Wang, H.-T., Zhu, H.: An improved algorithm for finding the closest pair of points. J. Comput. Sci. Technol. 21(1), 27\u201331 (2006)","journal-title":"J. Comput. Sci. Technol."},{"key":"13_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"782","DOI":"10.1007\/978-3-540-27836-8_66","volume-title":"Automata, Languages and Programming","author":"P Indyk","year":"2004","unstructured":"Indyk, P., Lewenstein, M., Lipsky, O., Porat, E.: Closest pair problems in very high dimensions. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 782\u2013792. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-27836-8_66"},{"issue":"4","key":"13_CR11","doi-asserted-by":"publisher","first-page":"532","DOI":"10.1007\/s11390-007-9066-y","volume":"22","author":"M Jiang","year":"2007","unstructured":"Jiang, M., Gillespie, J.: Engineering the divide-and-conquer closest pair algorithm. J. Comput. Sci. Technol. 22(4), 532\u2013540 (2007)","journal-title":"J. Comput. Sci. Technol."},{"issue":"189\u2013206","key":"13_CR12","first-page":"1","volume":"26","author":"WB Johnson","year":"1984","unstructured":"Johnson, W.B., Lindenstrauss, J.: Extensions of Lipschitz mappings into a Hilbert space. Contemp. Math. 26(189\u2013206), 1 (1984)","journal-title":"Contemp. Math."},{"issue":"6","key":"13_CR13","doi-asserted-by":"publisher","first-page":"1136","DOI":"10.1145\/195613.195632","volume":"41","author":"RM Karp","year":"1994","unstructured":"Karp, R.M.: Probabilistic recurrence relations. J. ACM (JACM) 41(6), 1136\u20131150 (1994)","journal-title":"J. ACM (JACM)"},{"issue":"1","key":"13_CR14","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1006\/inco.1995.1049","volume":"118","author":"S Khuller","year":"1995","unstructured":"Khuller, S., Matias, Y.: A simple randomized Sieve algorithm for the closest-pair problem. Inf. Comput. 118(1), 34\u201337 (1995)","journal-title":"Inf. Comput."},{"key":"13_CR15","unstructured":"Lopez, M.A., Liao, S.: Finding k-closest-pairs efficiently for high dimensional data (2000)"},{"key":"13_CR16","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1137\/1.9781611972795.41","volume-title":"Proceedings of the 2009 SIAM International Conference on Data Mining","author":"Abdullah Mueen","year":"2009","unstructured":"Mueen, A., Keogh, E., Zhu, Q., Cash, S., Westover, B.: Exact discovery of time series motifs. In: Proceedings of the 2009 SIAM International Conference on Data Mining, pp. 473\u2013484. SIAM (2009)"},{"issue":"4","key":"13_CR17","doi-asserted-by":"publisher","first-page":"891","DOI":"10.1007\/s11390-012-1272-6","volume":"27","author":"JC Pereira","year":"2012","unstructured":"Pereira, J.C., Lobo, F.G.: An optimized divide-and-conquer algorithm for the closest-pair problem in the planar case. J. Comput. Sci. Technol. 27(4), 891\u2013896 (2012)","journal-title":"J. Comput. Sci. Technol."},{"key":"13_CR18","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry: An Introduction","author":"FP Preparata","year":"2012","unstructured":"Preparata, F.P., Shamos, M.: Computational Geometry: An Introduction. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-1-4612-1098-6"},{"key":"13_CR19","doi-asserted-by":"crossref","unstructured":"Shamos, M.I., Hoey, D.: Closest-point problems. In: 16th Annual Symposium on Foundations of Computer Science, pp. 151\u2013162. IEEE (1975)","DOI":"10.1109\/SFCS.1975.8"},{"issue":"3","key":"13_CR20","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1145\/1806907.1806912","volume":"35","author":"Y Tao","year":"2010","unstructured":"Tao, Y., Yi, K., Sheng, C., Kalnis, P.: Efficient and accurate nearest neighbor and closest pair search in high-dimensional space. ACM Trans. Database Syst. (TODS) 35(3), 20 (2010)","journal-title":"ACM Trans. Database Syst. (TODS)"},{"issue":"4","key":"13_CR21","doi-asserted-by":"publisher","first-page":"655","DOI":"10.1137\/0220041","volume":"20","author":"AC-C Yao","year":"1991","unstructured":"Yao, A.C.-C.: Lower bounds for algebraic computation trees of functions with finite domains. SIAM J. Comput. 20(4), 655\u2013668 (1991)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Advances in Knowledge Discovery and Data Mining"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-93040-4_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T10:54:10Z","timestamp":1710327250000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-93040-4_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319930398","9783319930404"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-93040-4_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"17 June 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"PAKDD","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Pacific-Asia Conference on Knowledge Discovery and Data Mining","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Melbourne, VIC","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Australia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3 June 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"6 June 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"pakdd2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/prada-research.net\/pakdd18\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}