{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,20]],"date-time":"2024-09-20T16:34:12Z","timestamp":1726850052145},"publisher-location":"Cham","reference-count":33,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030364113"},{"type":"electronic","value":"9783030364120"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","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":[[2019]]},"DOI":"10.1007\/978-3-030-36412-0_29","type":"book-chapter","created":{"date-parts":[[2019,12,6]],"date-time":"2019-12-06T00:04:15Z","timestamp":1575590655000},"page":"362-374","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A True $$O(n\\log {n})$$ Algorithm for the All-k-Nearest-Neighbors Problem"],"prefix":"10.1007","author":[{"given":"Hengzhao","family":"Ma","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jianzhong","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,11,23]]},"reference":[{"issue":"4","key":"29_CR1","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1145\/358841.358850","volume":"23","author":"JL Bentley","year":"1980","unstructured":"Bentley, J.L.: Multidimensional divide-and-conquer. Commun. ACM 23(4), 214\u2013229 (1980)","journal-title":"Commun. ACM"},{"unstructured":"Cai, Z., Miao, D., Li, Y.: Deletion propagation for multiple key preserving conjunctive queries: approximations and complexity. In: 35th IEEE International Conference on Data Engineering, ICDE 2019, Macao, China, 8\u201311 April 2019, pp. 506\u2013517. IEEE (2019). http:\/\/ieeexplore.ieee.org\/xpl\/mostRecentIssue.jsp?punumber=8725877","key":"29_CR2"},{"unstructured":"Callahan, P.B.: Optimal parallel all-nearest-neighbors using the well-separated pair decomposition. In: Proceedings of the 1993 IEEE 34th Annual Foundations of Computer Science, SFCS 1993, pp. 332\u2013340. IEEE Computer Society, Washington (1993)","key":"29_CR3"},{"doi-asserted-by":"crossref","unstructured":"Clarkson, K.L.: Fast algorithms for the all nearest neighbors problem. In: 24th Annual Symposium on Foundations of Computer Science (SFCS 1983), vol. 16, pp. 226\u2013232. IEEE, November 1983","key":"29_CR4","DOI":"10.1109\/SFCS.1983.16"},{"issue":"4","key":"29_CR5","doi-asserted-by":"publisher","first-page":"599","DOI":"10.1109\/TVCG.2010.9","volume":"16","author":"M Connor","year":"2010","unstructured":"Connor, M., Kumar, P.: Fast construction of k-nearest neighbor graphs for point clouds. IEEE Trans. Vis. Comput. Graph. 16(4), 599\u2013608 (2010)","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"doi-asserted-by":"crossref","unstructured":"Dong, W., Moses, C., Li, K.: Efficient k-nearest neighbor graph construction for generic similarity measures. In: Proceedings of the 20th international conference on World wide web - WWW 2011, p. 577. ACM Press, New York (2011)","key":"29_CR6","DOI":"10.1145\/1963405.1963487"},{"key":"29_CR7","volume-title":"Algorithms in Combinatorial Geometry","author":"H Edelsbrunner","year":"2012","unstructured":"Edelsbrunner, H.: Algorithms in Combinatorial Geometry, 1st edn. Springer, Heidelberg (2012)","edition":"1"},{"issue":"11","key":"29_CR8","doi-asserted-by":"publisher","first-page":"1875","DOI":"10.1109\/TPAMI.2006.227","volume":"28","author":"P Franti","year":"2006","unstructured":"Franti, P., Virmajoki, O., Hautamaki, V.: Fast agglomerative clustering using a k-nearest neighbor graph. IEEE Trans. Pattern Anal. Mach. Intell. 28(11), 1875\u20131881 (2006)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"doi-asserted-by":"crossref","unstructured":"Friedman, J.H.: An algorithm for finding best matches in logarithmic expected time. 3(3), 209\u2013226 (1977)","key":"29_CR9","DOI":"10.1145\/355744.355745"},{"key":"29_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-662-38452-7_1","volume-title":"Dritter Band: Analysis $$\\cdot $$ Grundlagen der Mathematik $$\\cdot $$ Physik Verschiedenes","author":"D Hilbert","year":"1935","unstructured":"Hilbert, D.: \u00dcber die stetige Abbildung einer Linie auf ein Fl\u00e4chenst\u00fcck. In: Hilbert, D. (ed.) Dritter Band: Analysis $$\\cdot $$ Grundlagen der Mathematik $$\\cdot $$ Physik Verschiedenes, pp. 1\u20132. Springer, Heidelberg (1935). https:\/\/doi.org\/10.1007\/978-3-662-38452-7_1"},{"doi-asserted-by":"crossref","unstructured":"Karypis, G.: Evaluation of item-based top- N recommendation algorithms. In: Proceedings of the Tenth International Conference on Information and Knowledge Management - CIKM 2001, p. 247. ACM Press, New York (2001)","key":"29_CR11","DOI":"10.1145\/502624.502627"},{"doi-asserted-by":"crossref","unstructured":"Komarov, I., Dashti, A., D\u2019Souza, R.: Fast \\$k\\$-NNG construction with GPU-based quick multi-select. 1\u201320 (2013)","key":"29_CR12","DOI":"10.1371\/journal.pone.0092409"},{"unstructured":"Ma, H., Li, J.: A true $$o(n \\log {n}) $$ algorithm for the all-k-nearest-neighbors problem (2019). https:\/\/arxiv.org\/abs\/1908.00159","key":"29_CR13"},{"issue":"1","key":"29_CR14","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1109\/TKDE.2017.2758361","volume":"30","author":"D Miao","year":"2018","unstructured":"Miao, D., Cai, Z., Li, J.: On the complexity of bounded view propagation for conjunctive queries. IEEE Trans. Knowl. Data Eng. 30(1), 115\u2013127 (2018)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"29_CR15","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/j.tcs.2017.07.033","volume":"749","author":"D Miao","year":"2018","unstructured":"Miao, D., Cai, Z., Li, Y.: SEF view deletion under bounded condition. Theor. Comput. Sci. 749, 17\u201325 (2018)","journal-title":"Theor. Comput. Sci."},{"key":"29_CR16","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.tcs.2018.10.034","volume":"788","author":"D Miao","year":"2019","unstructured":"Miao, D., Cai, Z., Yu, J., Li, Y.: Triangle edge deletion on planar glasses-free rgb-digraphs. Theor. Comput. Sci. 788, 2\u201311 (2019)","journal-title":"Theor. Comput. Sci."},{"key":"29_CR17","doi-asserted-by":"publisher","first-page":"594","DOI":"10.1016\/j.tcs.2015.02.010","volume":"609","author":"D Miao","year":"2016","unstructured":"Miao, D., Liu, X., Li, J.: On the complexity of sampling query feedback restricted database repair of functional dependency violations. Theor. Comput. Sci. 609, 594\u2013605 (2016)","journal-title":"Theor. Comput. Sci."},{"key":"29_CR18","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/j.tcs.2016.07.009","volume":"774","author":"D Miao","year":"2019","unstructured":"Miao, D., Liu, X., Li, Y., Li, J.: Vertex cover in conflict graphs. Theor. Comput. Sci. 774, 103\u2013112 (2019)","journal-title":"Theor. Comput. Sci."},{"unstructured":"Morton, G.M.: A computer oriented geodetic data base and a new technique in file sequencing. Technical report, IBM Ltd, Ottawa, Canada (1966)","key":"29_CR19"},{"issue":"2","key":"29_CR20","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1177\/0165551515594728","volume":"42","author":"Y Park","year":"2016","unstructured":"Park, Y., Lee, S.G.: A novel algorithm for scalable k-nearest neighbour graph construction. J. Inf. Sci. 42(2), 274\u2013288 (2016)","journal-title":"J. Inf. Sci."},{"unstructured":"Sieranoja, S.: High dimensional k NN-graph construction using space filling curves. Ph.D. thesis, University of Eastern Finland (2015)","key":"29_CR21"},{"unstructured":"Szummer, M., Jaakkola, T.: Partially labeled classification with markov random walks. In: Proceedings of the 14th International Conference on Neural Information Processing Systems: Natural and Synthetic, NIPS 2001, pp. 945\u2013952. MIT Press, Cambridge (2001)","key":"29_CR22"},{"doi-asserted-by":"crossref","unstructured":"Trad, M.R., Joly, A., Boujemaa, N.: Distributed KNN-graph approximation via hashing. In: Proceedings of the 2nd ACM International Conference on Multimedia Retrieval - ICMR 2012, p. 1. No. section 3. ACM Press, New York (2012)","key":"29_CR23","DOI":"10.1145\/2324796.2324847"},{"doi-asserted-by":"crossref","unstructured":"Vaidya, P.M.: An optimal algorithm for the all-nearest-neighbors problem. In: Intergovernmental Panel on Climate Change (ed.) 27th Annual Symposium on Foundations of Computer Science (SFCS 1986), pp. 117\u2013122. IEEE, Cambridge, October 1986","key":"29_CR24","DOI":"10.1109\/SFCS.1986.8"},{"issue":"2","key":"29_CR25","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/BF02187718","volume":"4","author":"PM Vaidya","year":"1989","unstructured":"Vaidya, P.M.: An O(n logn) algorithm for the all-nearest-neighbors problem. Discrete Comput. Geom. 4(2), 101\u2013115 (1989)","journal-title":"Discrete Comput. Geom."},{"unstructured":"Wang, J., Wang, J., Zeng, G., Tu, Z., Gan, R., Li, S.: Scalable k-NN graph construction for visual descriptors. In: 2012 IEEE Conference on Computer Vision and Pattern Recognition, pp. 1106\u20131113. IEEE (2012)","key":"29_CR26"},{"issue":"12","key":"29_CR27","doi-asserted-by":"publisher","first-page":"3142","DOI":"10.1587\/transinf.2014EDP7108","volume":"97\u2013D","author":"T Warashina","year":"2014","unstructured":"Warashina, T., Aoyama, K., Sawada, H., Hattori, T.: Efficient K-nearest neighbor graph construction using MapReduce for large-scale data sets. IEICE Trans. Inform. Syst. 97\u2013D(12), 3142\u20133154 (2014)","journal-title":"IEICE Trans. Inform. Syst."},{"doi-asserted-by":"crossref","unstructured":"Yang, X., Latecki, L.J.: Affinity learning on a tensor product graph with applications to shape and image retrieval. In: Proceedings of the 2011 IEEE Conference on Computer Vision and Pattern Recognition, pp. 2369\u20132376. CVPR 2011. IEEE Computer Society, Washington (2011)","key":"29_CR28","DOI":"10.1109\/CVPR.2011.5995325"},{"doi-asserted-by":"crossref","unstructured":"Yao, B., Li, F., Kumar, P.: K nearest neighbor queries and kNN-Joins in large relational databases (almost) for free. In: 2010 IEEE 26th International Conference on Data Engineering (ICDE 2010), pp. 4\u201315. IEEE (2010)","key":"29_CR29","DOI":"10.1109\/ICDE.2010.5447837"},{"issue":"3","key":"29_CR30","doi-asserted-by":"publisher","first-page":"1368","DOI":"10.1137\/070690419","volume":"19","author":"EA Yildirim","year":"2008","unstructured":"Yildirim, E.A.: Two algorithms for the minimum enclosing ball problem. SIAM J. Optim. 19(3), 1368\u20131391 (2008)","journal-title":"SIAM J. Optim."},{"unstructured":"Zarrabi-Zadeh, H., Chan, T.: A simple streaming algorithm for minimum enclosing balls. In: Proceedings of 18th Annual Canadian Conference Computing, pp. 14\u201317 (2006)","key":"29_CR31"},{"key":"29_CR32","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"660","DOI":"10.1007\/978-3-642-40991-2_42","volume-title":"Machine Learning and Knowledge Discovery in Databases","author":"Y-M Zhang","year":"2013","unstructured":"Zhang, Y.-M., Huang, K., Geng, G., Liu, C.-L.: Fast kNN Graph Construction with Locality Sensitive Hashing. In: Blockeel, H., Kersting, K., Nijssen, S., \u017delezn\u00fd, F. (eds.) ECML PKDD 2013. LNCS (LNAI), vol. 8189, pp. 660\u2013674. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-40991-2_42"},{"issue":"4","key":"29_CR33","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1109\/TCBB.2008.99","volume":"7","author":"J Zhou","year":"2010","unstructured":"Zhou, J., Sander, J., Cai, Z., Wang, L., Lin, G.: Finding the nearest neighbors in biological databases using less distance computations. IEEE\/ACM Trans. Comput. Biol. Bioinform. 7(4), 669\u2013680 (2010)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-36412-0_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,7]],"date-time":"2022-10-07T20:39:51Z","timestamp":1665175191000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-36412-0_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030364113","9783030364120"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-36412-0_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"23 November 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Combinatorial Optimization and Applications","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Xiamen","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 December 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 December 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoa2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/cocoaconference.org\/index.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"easychair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"108","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"49","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"45% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.2","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"10","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"No","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}