{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T22:37:06Z","timestamp":1740177426995,"version":"3.37.3"},"reference-count":73,"publisher":"Association for Computing Machinery (ACM)","issue":"2","funder":[{"name":"National Science Foundation","award":["ACI 1443054 and IIS 1350885"]},{"name":"National Institute of Health","award":["K25CA181503 and U01CA242936"]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Spatial Algorithms Syst."],"published-print":{"date-parts":[[2022,6,30]]},"abstract":"\n 3D spatial data has been generated at an extreme scale from many emerging applications, such as high definition maps for autonomous driving and 3D Human BioMolecular Atlas. In particular, 3D digital pathology provides a revolutionary approach to map human tissues in 3D, which is highly promising for advancing computer-aided diagnosis and understanding diseases through spatial queries and analysis. However, the exponential increase of data at 3D leads to significant I\/O, communication, and computational challenges for 3D spatial queries. The complex structures of 3D objects such as bifurcated vessels make it difficult to effectively support 3D spatial queries with traditional methods. In this article, we present our work on building an efficient and scalable spatial query system,\n iSPEED,<\/jats:italic>\n for large-scale 3D data with complex structures. iSPEED adopts effective progressive compression for each 3D object with successive levels of detail. Further, iSPEED exploits structural indexing for complex structured objects in distance-based queries. By querying with data represented in successive levels of details and structural indexes, iSPEED provides an option for users to balance between query efficiency and query accuracy. iSPEED builds in-memory indexes and decompresses data on-demand, which has a minimal memory footprint. iSPEED provides a 3D spatial query engine that can be invoked on-demand to run many instances in parallel implemented with, but not limited to, MapReduce. We evaluate iSPEED with three representative queries: 3D spatial joins, 3D nearest neighbor query, and 3D spatial proximity estimation. The extensive experiments demonstrate that iSPEED significantly improves the performance of existing spatial query systems.\n <\/jats:p>","DOI":"10.1145\/3502221","type":"journal-article","created":{"date-parts":[[2022,2,12]],"date-time":"2022-02-12T12:31:55Z","timestamp":1644669115000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Efficient 3D Spatial Queries for Complex Objects"],"prefix":"10.1145","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0103-8348","authenticated-orcid":false,"given":"Dejun","family":"Teng","sequence":"first","affiliation":[{"name":"Stony Brook University, Stony Brook, NY, USA"}]},{"given":"Yanhui","family":"Liang","sequence":"additional","affiliation":[{"name":"Waymo LLC, Mountain View, CA, USA"}]},{"given":"Hoang","family":"Vo","sequence":"additional","affiliation":[{"name":"Stony Brook University, Stony Brook, NY, USA"}]},{"given":"Jun","family":"Kong","sequence":"additional","affiliation":[{"name":"Georgia State University, Atlanta, GA, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9369-9361","authenticated-orcid":false,"given":"Fusheng","family":"Wang","sequence":"additional","affiliation":[{"name":"Stony Brook University, Stony Brook, NY, USA"}]}],"member":"320","published-online":{"date-parts":[[2022,2,12]]},"reference":[{"key":"e_1_3_1_2_2","unstructured":"Retrieved from https:\/\/en.wikipedia.org\/wiki\/3D_modeling 3D Modelling"},{"key":"e_1_3_1_3_2","unstructured":"Retrieved from https:\/\/www.carmera.com\/ CARMERA"},{"key":"e_1_3_1_4_2","unstructured":"Retrieved from https:\/\/civilmaps.com\/ Civil Maps"},{"key":"e_1_3_1_5_2","unstructured":"Retrieved from http:\/\/www.cgal.org\/ The Computational Geometry Algorithms Library (CGAL)"},{"key":"e_1_3_1_6_2","unstructured":"Retrieved from https:\/\/www.deepmap.ai\/ Deepmap"},{"key":"e_1_3_1_7_2","unstructured":"Retrieved from http:\/\/www.esri.com\/products\/arcgis-capabilities\/3d-gis ESRI 3D GIS"},{"key":"e_1_3_1_8_2","unstructured":"Retrieved from https:\/\/www.fda.gov\/newsevents\/newsroom\/ucm552742.htm FDAWSI"},{"key":"e_1_3_1_9_2","unstructured":"Retrieved from https:\/\/www.nanalyze.com\/2018\/11\/hd-mapping-autonomous-vehicles HD Map"},{"key":"e_1_3_1_10_2","unstructured":"Retrieved from https:\/\/www.mapbox.com\/ Mapbox.ai"},{"key":"e_1_3_1_11_2","unstructured":"Retrieved from https:\/\/mapper.ai\/ Mapper"},{"key":"e_1_3_1_12_2","unstructured":"Retrieved from https:\/\/en.wikipedia.org\/wiki\/OFF_(file_format) OFF Format"},{"key":"e_1_3_1_13_2","unstructured":"Retrieved from http:\/\/www.opentopography.org\/ OpenTopography"},{"key":"e_1_3_1_14_2","unstructured":"Retrieved from http:\/\/www.pitneybowes.com\/pbencom\/homepage.html pbEncom"},{"key":"e_1_3_1_15_2","unstructured":"Retrieved from https:\/\/www.proteinatlas.org\/ Proteinatlas"},{"key":"e_1_3_1_16_2","unstructured":"Retrieved from https:\/\/www.ncbi.nlm.nih.gov\/pubmed\/31127980 Spatial Epigenome"},{"key":"e_1_3_1_17_2","unstructured":"Retrieved from http:\/\/libspatialindex.github.com Spatial Index Library"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.14778\/2536222.2536227"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-010-0182-x"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497493"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.5555\/645339.650131"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.5555\/2563475"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/3139958.3140019"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/93605.98741"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.5555\/645927.672197"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.5555\/645503.656271"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.5555\/645481.655583"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1002\/glia.21264"},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.5555\/868963"},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41586-019-1629-x"},{"key":"e_1_3_1_31_2","volume-title":"Optimizing Shuffle Performance in Spark","author":"Davidson A.","year":"2013","unstructured":"A. Davidson and A. Or. 2013. Optimizing Shuffle Performance in Spark. Technique Report. UC Berkeley."},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113382"},{"key":"e_1_3_1_33_2","doi-asserted-by":"publisher","DOI":"10.5555\/3001460.3001507"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.7848\/ksgpc.2013.31.1.41"},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/237170.237216"},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/1206049.1206056"},{"key":"e_1_3_1_37_2","volume-title":"Hilbert R-tree: An Improved R-tree Using Fractals","author":"Kamel Ibrahim","year":"1993","unstructured":"Ibrahim Kamel and Christos Faloutsos. 1993. Hilbert R-tree: An Improved R-tree Using Fractals. Technical Report."},{"key":"e_1_3_1_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/344779.344922"},{"key":"e_1_3_1_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/2996913.2996925"},{"key":"e_1_3_1_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/3139958.3139961"},{"key":"e_1_3_1_41_2","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1007\/978-3-319-24574-4_30","volume-title":"Medical Image Computing and Computer-assisted Intervention\u2013MICCAI 2015","author":"Liang Yanhui","year":"2015","unstructured":"Yanhui Liang, Fusheng Wang, Darren Treanor, Derek Magee, George Teodoro, Yangyang Zhu, and Jun Kong. 2015. A 3D primary vessel reconstruction framework with serial microscopy images. In Medical Image Computing and Computer-assisted Intervention\u2013MICCAI 2015. Springer, 251\u2013259."},{"key":"e_1_3_1_42_2","first-page":"182","volume-title":"IEEE 12th International Symposium on Biomedical Imaging (ISBI)","author":"Liang Yanhui","year":"2015","unstructured":"Yanhui Liang, Fusheng Wang, Darren Treanor, Derek Magee, George Teodoro, Yangyang Zhu, and Jun Kong. 2015. Liver whole slide image analysis for 3D vessel reconstruction. In IEEE 12th International Symposium on Biomedical Imaging (ISBI). IEEE, 182\u2013185."},{"key":"e_1_3_1_43_2","first-page":"75","article-title":"Development of a framework for large-scale three-dimensional pathology and biomarker imaging and spatial analytics","volume":"2017","author":"Liang Yanhui","year":"2017","unstructured":"Yanhui Liang, Fusheng Wang, Pengyue Zhang, Joel H. Saltz, Daniel J. Brat, and Jun Kong. 2017. Development of a framework for large-scale three-dimensional pathology and biomarker imaging and spatial analytics. AMIA Summ. Translat. Sci. Proc. 2017 (2017), 75.","journal-title":"AMIA Summ. Translat. Sci. Proc."},{"key":"e_1_3_1_44_2","unstructured":"Harvey Lodish Arnold Berk S. Lawrence Zipursky Paul Matsudaira David Baltimore and James Darnell. 2000. Viruses: structure function and uses. In Molecular Cell Biology . 4th edition. WH Freeman."},{"key":"e_1_3_1_45_2","doi-asserted-by":"publisher","DOI":"10.5555\/2821571"},{"key":"e_1_3_1_46_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cag.2012.03.023"},{"key":"e_1_3_1_47_2","article-title":"An Overview of 3D Data Content, File Formats and Viewers","author":"McHenry Kenton","year":"2008","unstructured":"Kenton McHenry and Peter Bajcsy. 2008. An Overview of 3D Data Content, File Formats and Viewers. Retrieved from https:\/\/isda.ncsa.illinois.edu\/drupal\/sites\/default\/files\/NCSA-ISDA-2008-002.pdf.","journal-title":"Retrieved from https:\/\/isda.ncsa.illinois.edu\/drupal\/sites\/default\/files\/NCSA-ISDA-2008-002.pdf"},{"volume-title":"Oracle 3D","key":"e_1_3_1_48_2","unstructured":"Oracle. Oracle 3D. Retrieved from https:\/\/docs.oracle.com\/database\/121\/SPATL\/three-dimensional-spatial-objects.htm#SPATL468."},{"key":"e_1_3_1_49_2","doi-asserted-by":"publisher","DOI":"10.5555\/1972515"},{"key":"e_1_3_1_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/253262.253342"},{"key":"e_1_3_1_51_2","first-page":"2029","volume-title":"Computer Graphics Forum","author":"Peng Jingliang","year":"2010","unstructured":"Jingliang Peng, Yan Huang, C.-C. Jay Kuo, Ilya Eckstein, and M. Gopi. 2010. Feature oriented progressive lossless mesh coding. In Computer Graphics Forum, Vol. 29. Wiley Online Library, 2029\u20132038."},{"key":"e_1_3_1_52_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jvcir.2005.03.001"},{"key":"e_1_3_1_53_2","doi-asserted-by":"publisher","DOI":"10.1145\/1186822.1073237"},{"key":"e_1_3_1_54_2","doi-asserted-by":"publisher","DOI":"10.1145\/3347146.3359351"},{"key":"e_1_3_1_55_2","doi-asserted-by":"publisher","DOI":"10.1145\/568271.223794"},{"key":"e_1_3_1_56_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cell.2020.03.053"},{"key":"e_1_3_1_57_2","doi-asserted-by":"publisher","DOI":"10.5555\/286071"},{"key":"e_1_3_1_58_2","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2012.03178.x"},{"key":"e_1_3_1_59_2","volume-title":"Pathology of Organ Structure by Analysis and Interpretation of Images (2nd ed.)","author":"Takahashi Tohru","year":"2011","unstructured":"Tohru Takahashi. 2011. Pathology of Organ Structure by Analysis and Interpretation of Images (2nd ed.). SciPress, Tokyo."},{"key":"e_1_3_1_60_2","doi-asserted-by":"publisher","DOI":"10.14778\/3007263.3007310"},{"key":"e_1_3_1_61_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2013.01.017"},{"key":"e_1_3_1_62_2","unstructured":"Pierre Terdiman. [n.d.]. OPCODE 3D Collision Detection Library 2005. http:\/\/www.codercorner.com\/Opcode.htm."},{"key":"e_1_3_1_63_2","doi-asserted-by":"publisher","DOI":"10.5555\/1735603.1735610"},{"key":"e_1_3_1_64_2","doi-asserted-by":"publisher","DOI":"10.1145\/2666310.2666365"},{"key":"e_1_3_1_65_2","doi-asserted-by":"publisher","DOI":"10.14778\/3229863.3236264"},{"key":"e_1_3_1_66_2","doi-asserted-by":"publisher","DOI":"10.4103\/2153-3539.108543"},{"key":"e_1_3_1_67_2","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350268"},{"key":"e_1_3_1_68_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.datak.2016.02.003"},{"key":"e_1_3_1_69_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ymeth.2009.09.006"},{"key":"e_1_3_1_70_2","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915237"},{"key":"e_1_3_1_71_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDEW.2015.7129541"},{"key":"e_1_3_1_72_2","doi-asserted-by":"publisher","DOI":"10.1145\/2820783.2820860"},{"key":"e_1_3_1_73_2","doi-asserted-by":"publisher","DOI":"10.1145\/3347146.3359353"},{"key":"e_1_3_1_74_2","doi-asserted-by":"publisher","DOI":"10.1109\/CLUSTR.2009.5289178"}],"container-title":["ACM Transactions on Spatial Algorithms and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3502221","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T21:06:53Z","timestamp":1672607213000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3502221"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,12]]},"references-count":73,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,6,30]]}},"alternative-id":["10.1145\/3502221"],"URL":"https:\/\/doi.org\/10.1145\/3502221","relation":{},"ISSN":["2374-0353","2374-0361"],"issn-type":[{"type":"print","value":"2374-0353"},{"type":"electronic","value":"2374-0361"}],"subject":[],"published":{"date-parts":[[2022,2,12]]},"assertion":[{"value":"2021-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-02-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}