{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,8]],"date-time":"2026-02-08T05:21:40Z","timestamp":1770528100054,"version":"3.49.0"},"reference-count":66,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2021,6,2]],"date-time":"2021-06-02T00:00:00Z","timestamp":1622592000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGOPS Oper. Syst. Rev."],"published-print":{"date-parts":[[2021,6,2]]},"abstract":"<jats:p>In many applications of graph processing, the input data is often generated from an underlying geometric point data set. However, existing high-performance graph processing frameworks assume that the input data is given as a graph. Therefore, to use these frameworks, the user must write or use external programs based on computational geometry algorithms to convert their point data set to a graph, which requires more programming effort and can also lead to performance degradation.<\/jats:p>\n          <jats:p>In this paper, we present our ongoing work on the Geo- Graph framework for shared-memory multicore machines, which seamlessly supports routines for parallel geometric graph construction and parallel graph processing within the same environment. GeoGraph supports graph construction based on k-nearest neighbors, Delaunay triangulation, and b-skeleton graphs. It can then pass these generated graphs to over 25 graph algorithms. GeoGraph contains highperformance parallel primitives and algorithms implemented in C++, and includes a Python interface. We present four examples of using GeoGraph, and some experimental results showing good parallel speedups and improvements over the Higra library. We conclude with a vision of future directions for research in bridging graph and geometric data processing.<\/jats:p>","DOI":"10.1145\/3469379.3469384","type":"journal-article","created":{"date-parts":[[2021,6,6]],"date-time":"2021-06-06T12:43:56Z","timestamp":1622983436000},"page":"38-46","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["GeoGraph"],"prefix":"10.1145","volume":"55","author":[{"given":"Yiqiu","family":"Wang","sequence":"first","affiliation":[{"name":"MIT CSAIL"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shangdi","family":"Yu","sequence":"additional","affiliation":[{"name":"MIT CSAIL"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Laxman","family":"Dhulipala","sequence":"additional","affiliation":[{"name":"MIT CSAIL"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yan","family":"Gu","sequence":"additional","affiliation":[{"name":"UC Riverside"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Julian","family":"Shun","sequence":"additional","affiliation":[{"name":"MIT CSAIL"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,6,6]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"an open source library for parallel algorithms in computational geometry. https:\/\/github.com\/ wangyiqiu\/pargeo","author":"Pargeo","year":"2021"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1214\/10-STS335"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2019.02.006"},{"key":"e_1_2_1_4_1","volume-title":"Feb","author":"Barthelemy Marc","year":"2011"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-20565-6"},{"key":"e_1_2_1_6_1","volume-title":"Tal Ben-Nun, and Torsten Hoefler. Graph processing on FPGAs: Taxonomy, survey, challenges. CoRR, abs\/1903.06697","author":"Besta Maciej","year":"2019"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDMW.2018.00144"},{"key":"e_1_2_1_8_1","first-page":"507","volume-title":"ACM Symposium on Parallelism in Algorithms and Architectures","author":"Blelloch Guy E.","year":"2020"},{"key":"e_1_2_1_9_1","first-page":"163","volume-title":"A Survey of Benchmarks for Graph- Processing Systems","author":"Bonifati Angela","year":"2018"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2016.7498244"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-7152(96)00213-1"},{"key":"e_1_2_1_12_1","first-page":"1","volume-title":"Hierarchical density estimates for data clustering, visualization, and outlier detection. ACM Transactions on Knowledge Discovery from Data","author":"Campello Ricardo","year":"2015"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15992-3_29"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2012.11.005"},{"issue":"9","key":"e_1_2_1_15_1","article-title":"Fast approximate kNN graph construction for high dimensional data via recursive Lanczos bisection","volume":"10","author":"Chen Jie","year":"2009","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_2_1_16_1","volume-title":"An analysis of the graph processing landscape. 44 Journal of Big Data, 8(1):55","author":"Coimbra Miguel E.","year":"2021"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.21105\/joss.00726"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3210377.3210414"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314598"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3398682.3399168"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963487"},{"key":"e_1_2_1_23_1","first-page":"226","volume-title":"ACM SIGKDD Conference on Knowledge Discovery and Data Mining","author":"Ester Martin","year":"1996"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2768577.2768579"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2006.227"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/355744.355745"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/3303753.3303754"},{"key":"e_1_2_1_28_1","volume-title":"Minimum spanning trees and single linkage cluster analysis. Journal of the Royal Statistical Society: Series C (Applied Statistics), 18(1):54--64","author":"Gower John C.","year":"1969"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11390-019-1914-z"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41586-020-2649-2"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPR.2004.1334558"},{"key":"e_1_2_1_32_1","volume-title":"June","author":"Heidari Safiollah","year":"2018"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/5.163414"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/2.781637"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-444-87806-9.50013-X"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1631\/FITEE.1900127"},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1007\/978-3-642-33260-9_22","volume-title":"Computer Information Systems and Industrial Management","author":"Wierzcho\u00b4n Luci\u00b4nska","year":"2012"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.01.009"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2018.2889473"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/1394399"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2818185"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00076-2"},{"key":"e_1_2_1_43_1","volume-title":"Scalable 45 bottom-up hierarchical clustering. arXiv preprint arXiv:2010.11821","author":"Monath Nicholas","year":"2020"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/11575832_14"},{"key":"e_1_2_1_45_1","first-page":"2825","article-title":"Scikit-learn: Machine learning","volume":"12","author":"Fabian Pedregosa","year":"2011","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.softx.2019.100335"},{"key":"e_1_2_1_47_1","volume-title":"Computational Geometry","author":"Preparata Franco P.","year":"1990"},{"issue":"1","key":"e_1_2_1_48_1","first-page":"15","article-title":"The use of spatial decompositions for constructing street centerlines","volume":"5","author":"Radke John","year":"1999","journal-title":"Geographic Information Sciences"},{"key":"e_1_2_1_49_1","volume-title":"Proceedings of the International Conference on Pattern Recognition (ICPR)","author":"Thomas","year":"2002"},{"key":"e_1_2_1_50_1","volume-title":"Parallel clique counting and peeling algorithms. arXiv preprint arXiv:2002.10047","author":"Shi Jessica","year":"2020"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3128571"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2312005.2312018"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/DCC.2015.8"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.5555\/2765801"},{"key":"e_1_2_1_55_1","first-page":"13748","volume-title":"Conference on Neural Information Processing Systems","author":"Subramanya Suhas Jayaram","year":"2019"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.290.5500.2319"},{"key":"e_1_2_1_57_1","first-page":"222","volume-title":"Machine Learning and Data Mining in Pattern Recognition","author":"Godfried","year":"2012"},{"key":"e_1_2_1_58_1","volume-title":"ACM SIGMOD International Conference on Management of Data","author":"Tseng Tom","year":"2021"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.5555\/1965254"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(92)90003-B"},{"key":"e_1_2_1_61_1","volume-title":"SciPy 1.0: fundamental algorithms for scientific computing in Python. Nature Methods, 17(3):261--272","author":"Pauli Virtanen","year":"2020"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1020381720601"},{"key":"e_1_2_1_63_1","first-page":"2555","volume-title":"ACM SIGMOD International Conference on Management of Data","author":"Wang Yiqiu","year":"2020"},{"key":"e_1_2_1_64_1","volume-title":"ACM SIGMOD International Conference on Management of Data","author":"Yu Shangdi","year":"2021"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1016\/0306-4573(88)90027-1"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1561\/9781680832433"}],"container-title":["ACM SIGOPS Operating Systems Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3469379.3469384","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3469379.3469384","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:28:23Z","timestamp":1750195703000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3469379.3469384"}},"subtitle":["A Framework for Graph Processing on Geometric Data"],"short-title":[],"issued":{"date-parts":[[2021,6,2]]},"references-count":66,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,6,2]]}},"alternative-id":["10.1145\/3469379.3469384"],"URL":"https:\/\/doi.org\/10.1145\/3469379.3469384","relation":{},"ISSN":["0163-5980"],"issn-type":[{"value":"0163-5980","type":"print"}],"subject":[],"published":{"date-parts":[[2021,6,2]]},"assertion":[{"value":"2021-06-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}