{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:49:21Z","timestamp":1773481761773,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":69,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,7,11]],"date-time":"2022-07-11T00:00:00Z","timestamp":1657497600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Science Foundation","award":["CCF-2103483"],"award-info":[{"award-number":["CCF-2103483"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,7,11]]},"DOI":"10.1145\/3490148.3538581","type":"proceedings-article","created":{"date-parts":[[2022,7,10]],"date-time":"2022-07-10T22:10:15Z","timestamp":1657491015000},"page":"259-272","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Parallel Cover Trees and their Applications"],"prefix":"10.1145","author":[{"given":"Yan","family":"Gu","sequence":"first","affiliation":[{"name":"UC Riverside, Riverside, CA, USA"}]},{"given":"Zachary","family":"Napier","sequence":"additional","affiliation":[{"name":"UC Riverside, Riverside, CA, USA"}]},{"given":"Yihan","family":"Sun","sequence":"additional","affiliation":[{"name":"UC Riverside, Riverside, CA, USA"}]},{"given":"Letong","family":"Wang","sequence":"additional","affiliation":[{"name":"UC Riverside, Riverside, CA, USA"}]}],"member":"320","published-online":{"date-parts":[[2022,7,11]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1201\/b17320"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2612669.2612688"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2016.2524018"},{"key":"e_1_3_2_1_4_1","volume-title":"Many sequential iterative algorithms can be parallel and (almost) work-efficient. (unpublished work, submitted to SPAA","author":"Authors A.","year":"2022","unstructured":"A. Authors . Many sequential iterative algorithms can be parallel and (almost) work-efficient. (unpublished work, submitted to SPAA 2022 ), 2022. A. Authors. Many sequential iterative algorithms can be parallel and (almost) work-efficient. (unpublished work, submitted to SPAA 2022), 2022."},{"key":"e_1_3_2_1_5_1","volume-title":"The uniform metric on product spaces. Lecture Notes","author":"Bell J.","unstructured":"J. Bell . The uniform metric on product spaces. Lecture Notes , University of Toronto . J. Bell. The uniform metric on product spaces. Lecture Notes, University of Toronto."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2018.00081"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1978.1675043"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1143844.1143857"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1093\/mnras\/282.4.1461"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2935764.2935768"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3350755.3400227"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2312005.2312058"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1810479.1810519"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3210377.3210380"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3402819"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3350755.3400255"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/324133.324234"},{"issue":"3","key":"e_1_3_2_1_18_1","first-page":"37","article-title":"Ojist\u00e9m probl\u00e9mu minim\u00e1ln'im. Pr\u00e1ce Mor. Prirodved. Spol. Brne(Acta Societ","volume":"3","author":"Boruvka O.","year":"1926","unstructured":"O. Boruvka . Ojist\u00e9m probl\u00e9mu minim\u00e1ln'im. Pr\u00e1ce Mor. Prirodved. Spol. Brne(Acta Societ . Scienc. Natur. Moravicae) , 3 ( 3 ): 37 -- 58 , 1926 . O. Boruvka. Ojist\u00e9m probl\u00e9mu minim\u00e1ln'im. Pr\u00e1ce Mor. Prirodved. Spol. Brne(Acta Societ. Scienc. Natur. Moravicae), 3(3):37--58, 1926.","journal-title":"Scienc. Natur. Moravicae)"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13193-6_41"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15992-3_29"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087556.3087586"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2013.04.008"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"crossref","first-page":"15","DOI":"10.7551\/mitpress\/4908.003.0005","volume-title":"Nearest-neighbor searching and metric space dimensions. Nearest-neighbor methods for learning and vision: theory and practice","author":"Clarkson K. L.","year":"2006","unstructured":"K. L. Clarkson Nearest-neighbor searching and metric space dimensions. Nearest-neighbor methods for learning and vision: theory and practice , pages 15 -- 59 , 2006 . K. L. Clarkson et al. Nearest-neighbor searching and metric space dimensions. Nearest-neighbor methods for learning and vision: theory and practice, pages 15--59, 2006."},{"key":"e_1_3_2_1_24_1","volume-title":"Resource oblivious sorting on multicores. ACM Transactions on Parallel Computing (TOPC), 3(4)","author":"Cole R.","year":"2017","unstructured":"R. Cole and V. Ramachandran . Resource oblivious sorting on multicores. ACM Transactions on Parallel Computing (TOPC), 3(4) , 2017 . R. Cole and V. Ramachandran. Resource oblivious sorting on multicores. ACM Transactions on Parallel Computing (TOPC), 3(4), 2017."},{"key":"e_1_3_2_1_25_1","volume-title":"Introduction to Algorithms","author":"Cormen T. H.","year":"2009","unstructured":"T. H. Cormen , C. E. Leiserson , R. L. Rivest , and C. Stein . Introduction to Algorithms ( 3 rd edition). MIT Press , 2009 . T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms (3rd edition). MIT Press, 2009.","edition":"3"},{"key":"e_1_3_2_1_26_1","volume-title":"Georgia Institute of Technology","author":"Curtin R. R.","year":"2015","unstructured":"R. R. Curtin . Improving dual-tree algorithms. PhD thesis , Georgia Institute of Technology , 2015 . R. R. Curtin. Improving dual-tree algorithms. PhD thesis, Georgia Institute of Technology, 2015."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519939.3523733"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314598"},{"key":"e_1_3_2_1_29_1","volume-title":"Proceedings of the VLDB Endowment (PVLDB), 13(9)","author":"Dhulipala L.","year":"2020","unstructured":"L. Dhulipala , C. McGuffey , H. Kang , Y. Gu , G. E. Blelloch , P. B. Gibbons , and J. Shun . Semi-asymmetric parallel graph algorithms for nvrams . Proceedings of the VLDB Endowment (PVLDB), 13(9) , 2020 . L. Dhulipala, C. McGuffey, H. Kang, Y. Gu, G. E. Blelloch, P. B. Gibbons, and J. Shun. Semi-asymmetric parallel graph algorithms for nvrams. Proceedings of the VLDB Endowment (PVLDB), 13(9), 2020."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.95.25.14863"},{"key":"e_1_3_2_1_31_1","volume-title":"A new compressed cover tree guarantees a near linear parameterized complexity for all k-nearest neighbors search in metric spaces. arXiv preprint:2111.15478","author":"Elkin Y.","year":"2021","unstructured":"Y. Elkin and V. Kurlin . A new compressed cover tree guarantees a near linear parameterized complexity for all k-nearest neighbors search in metric spaces. arXiv preprint:2111.15478 , 2021 . Y. Elkin and V. Kurlin. A new compressed cover tree guarantees a near linear parameterized complexity for all k-nearest neighbors search in metric spaces. arXiv preprint:2111.15478, 2021."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3139958.3140015"},{"key":"e_1_3_2_1_33_1","volume-title":"KDD","author":"Ester M.","year":"1996","unstructured":"M. Ester , H.-P. Kriegel , J. Sander , and X. Xu . A density-based algorithm for discovering clusters a density-based algorithm for discovering clusters in large spatial databases with noise . In KDD , 1996 . M. Ester, H.-P. Kriegel, J. Sander, and X. Xu. A density-based algorithm for discovering clusters a density-based algorithm for discovering clusters in large spatial databases with noise. In KDD, 1996."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2006.227"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2492045.2492054"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2755573.2755597"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPR.2004.1334558"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.18.6.1138"},{"key":"e_1_3_2_1_39_1","first-page":"1162","volume-title":"International Conference on Machine Learning (ICML)","author":"Izbicki M.","year":"2015","unstructured":"M. Izbicki and C. Shelton . Faster cover trees . In International Conference on Machine Learning (ICML) , pages 1162 -- 1170 . PMLR, 2015 . M. Izbicki and C. Shelton. Faster cover trees. In International Conference on Machine Learning (ICML), pages 1162--1170. PMLR, 2015."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/133889"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510013"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/2.781637"},{"key":"e_1_3_2_1_43_1","volume-title":"Fast nearest neighbors","author":"Kollar T.","year":"2006","unstructured":"T. Kollar . Fast nearest neighbors , 2006 . T. Kollar. Fast nearest neighbors, 2006."},{"key":"e_1_3_2_1_44_1","first-page":"798","volume-title":"Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms","author":"Krauthgamer R.","year":"2004","unstructured":"R. Krauthgamer and J. R. Lee . Navigating nets: simple algorithms for proximity search . In Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms , pages 798 -- 807 . Citeseer , 2004 . R. Krauthgamer and J. R. Lee. Navigating nets: simple algorithms for proximity search. In Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, pages 798--807. Citeseer, 2004."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/TMC.2004.10"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/070698257"},{"key":"e_1_3_2_1_47_1","first-page":"254","volume-title":"Computer Information Systems and Industrial Management","author":"Wierzchon M. Luci'n","year":"2012","unstructured":"M. Luci'n ska and S. T. Wierzchon . Spectral clustering based on k-nearest neighbor graph . In Computer Information Systems and Industrial Management , pages 254 -- 265 , 2012 . M. Luci'n ska and S. T. Wierzchon. Spectral clustering based on k-nearest neighbor graph. In Computer Information Systems and Industrial Management, pages 254--265, 2012."},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.01.009"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835882"},{"key":"e_1_3_2_1_50_1","volume-title":"Mrsrf: an efficient mapreduce algorithm for analyzing large collections of evolutionary trees. BMC bioinformatics, 11(S1):S15","author":"Matthews S. J.","year":"2010","unstructured":"S. J. Matthews and T. L. Williams . Mrsrf: an efficient mapreduce algorithm for analyzing large collections of evolutionary trees. BMC bioinformatics, 11(S1):S15 , 2010 . S. J. Matthews and T. L. Williams. Mrsrf: an efficient mapreduce algorithm for analyzing large collections of evolutionary trees. BMC bioinformatics, 11(S1):S15, 2010."},{"key":"e_1_3_2_1_51_1","first-page":"2440","volume-title":"International Conference on Artificial Intelligence and Statistics","author":"Moseley B.","year":"2021","unstructured":"B. Moseley , S. Vassilvtiskii , and Y. Wang . Hierarchical clustering in general metric spaces using approximate nearest neighbors . In International Conference on Artificial Intelligence and Statistics , pages 2440 -- 2448 . PMLR, 2021 . B. Moseley, S. Vassilvtiskii, and Y. Wang. Hierarchical clustering in general metric spaces using approximate nearest neighbors. In International Conference on Artificial Intelligence and Statistics, pages 2440--2448. PMLR, 2021."},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/945394.945400"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/11575832_14"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.buildenv.2019.106330"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPR.2002.1047852"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1975.8"},{"key":"e_1_3_2_1_57_1","first-page":"8887","article-title":"Design and implementation of cover tree algorithm on cuda-compatible gpu","volume":"975","author":"Sharma M.","year":"2010","unstructured":"M. Sharma and R. Joshi . Design and implementation of cover tree algorithm on cuda-compatible gpu . International Journal of Computer Applications , 975 : 8887 , 2010 . M. Sharma and R. Joshi. Design and implementation of cover tree algorithm on cuda-compatible gpu. International Journal of Computer Applications, 975:8887, 2010.","journal-title":"International Journal of Computer Applications"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3490148.3538574"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.5555\/2722129.2722159"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0010-2180(98)00023-6"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975499.13"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178487.3178509"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.290.5500.2319"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1109\/RT.2008.4634626"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380582"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457296"},{"key":"e_1_3_2_1_67_1","volume-title":"a critical review. Information processing & management, 24(5):577--597","author":"Willett P.","year":"1988","unstructured":"P. Willett . Recent trends in hierarchic document clustering : a critical review. Information processing & management, 24(5):577--597 , 1988 . P. Willett. Recent trends in hierarchic document clustering: a critical review. Information processing & management, 24(5):577--597, 1988."},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1137\/0211059"},{"key":"e_1_3_2_1_69_1","volume-title":"A practical scalable shared-memory parallel algorithm for computing minimum spanning trees. Master's thesis","author":"Zhou W.","year":"2017","unstructured":"W. Zhou . A practical scalable shared-memory parallel algorithm for computing minimum spanning trees. Master's thesis , Karlsruhe Institute of Technology , 2017 . W. Zhou. A practical scalable shared-memory parallel algorithm for computing minimum spanning trees. Master's thesis, Karlsruhe Institute of Technology, 2017."}],"event":{"name":"SPAA '22: 34th ACM Symposium on Parallelism in Algorithms and Architectures","location":"Philadelphia PA USA","acronym":"SPAA '22","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory","SIGARCH ACM Special Interest Group on Computer Architecture","EATCS European Association for Theoretical Computer Science"]},"container-title":["Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3490148.3538581","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3490148.3538581","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:02:10Z","timestamp":1750186930000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3490148.3538581"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,11]]},"references-count":69,"alternative-id":["10.1145\/3490148.3538581","10.1145\/3490148"],"URL":"https:\/\/doi.org\/10.1145\/3490148.3538581","relation":{},"subject":[],"published":{"date-parts":[[2022,7,11]]},"assertion":[{"value":"2022-07-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}