{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:47:00Z","timestamp":1750308420919,"version":"3.41.0"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T00:00:00Z","timestamp":1623801600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Science Foundation","award":["1845789"],"award-info":[{"award-number":["1845789"]}]},{"name":"Salt River Project Agricultural Improvement and Power District"},{"name":"OD-ARMY Training and Doctrine Command"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Spatial Algorithms Syst."],"published-print":{"date-parts":[[2021,9,30]]},"abstract":"<jats:p>\n            With the ubiquity of spatial data, vertexes or edges in graphs can possess spatial location attributes side by side with other non-spatial attributes. For instance, as of June 2018, the Wikidata knowledge graph contains 48,547,142 data items (i.e., vertexes) and\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            13% of them have spatial location attributes. The article proposes Riso-Tree, a generic efficient and scalable indexing framework for spatial entities in graph database management systems. Riso-Tree enables the fast execution of graph queries that involve different types of spatial predicates (GraSp queries). The proposed framework augments the classic R-Tree structure with pre-materialized sub-graph entries. The pruning power of R-Tree is enhanced with the sub-graph information. Riso-Tree partitions the graph into sub-graphs based on their connectivity to the spatial sub-regions. The proposed index allows for the fast execution of GraSp queries by efficiently pruning the traversed vertexes\/edges based upon the materialized sub-graph information. The experiments show that the proposed Riso-Tree achieves up to two orders of magnitude faster execution time than its counterparts when executing GraSp queries on real graphs (e.g., Wikidata). The strategy of limiting the size of each sub-graph entry (\n            <jats:italic>PN<\/jats:italic>\n            <jats:sub>\n              <jats:italic>max<\/jats:italic>\n            <\/jats:sub>\n            ) is proposed to reduce the storage overhead of Riso-Tree. The strategy can save up to around 70% storage without harming the query performance according to the experiments. Another strategy is proposed to ensure the performance of the index maintenance (Irrelevant Vertexes Skipping). The experiments show that the strategy can improve performance, especially for slow updates. It proves that Riso-Tree is useful for applications that need to support frequent updates.\n          <\/jats:p>","DOI":"10.1145\/3450945","type":"journal-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T14:54:13Z","timestamp":1623855253000},"page":"1-39","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Riso-Tree: An Efficient and Scalable Index for Spatial Entities in Graph Database Management Systems"],"prefix":"10.1145","volume":"7","author":[{"given":"Yuhan","family":"Sun","sequence":"first","affiliation":[{"name":"Arizona State University, United States, Tempe, AZ"}]},{"given":"Mohamed","family":"Sarwat","sequence":"additional","affiliation":[{"name":"Arizona State University, United States, Tempe, AZ"}]}],"member":"320","published-online":{"date-parts":[[2021,6,16]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.14778\/2536206.2536218"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1145\/3139958.3139980"},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_1","DOI":"10.1007\/BF00288683"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1145\/93605.98741"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.1145\/361002.361007"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.14778\/2732939.2732946"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.14778\/3231751.3231755"},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.1145\/356770.356776"},{"unstructured":"Oracle Corporation. 2019. Oracle Spatial and Graph. Retrieved from https:\/\/www.oracle.com\/database\/technologies\/spatialandgraph.html.  Oracle Corporation. 2019. Oracle Spatial and Graph. Retrieved from https:\/\/www.oracle.com\/database\/technologies\/spatialandgraph.html.","key":"e_1_2_1_9_1"},{"unstructured":"DataStax. 2019. Titan Distributed Graph Database. Retrieved from http:\/\/titan.thinkaurelius.com\/.  DataStax. 2019. Titan Distributed Graph Database. Retrieved from http:\/\/titan.thinkaurelius.com\/.","key":"e_1_2_1_10_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.1145\/1867699.1867707"},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.1145\/2187980.2188041"},{"unstructured":"Esri. 2019. ArcGIS Utility Network. Retrieved from https:\/\/www.esri.com\/en-us\/arcgis\/products\/arcgis-utility-network-management\/overview.  Esri. 2019. ArcGIS Utility Network. Retrieved from https:\/\/www.esri.com\/en-us\/arcgis\/products\/arcgis-utility-network-management\/overview.","key":"e_1_2_1_13_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.1145\/316194.316229"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.14778\/3055330.3055337"},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_1","DOI":"10.1109\/TKDE.2018.2845414"},{"doi-asserted-by":"publisher","key":"e_1_2_1_17_1","DOI":"10.1109\/ICDE.2008.4497474"},{"doi-asserted-by":"publisher","key":"e_1_2_1_18_1","DOI":"10.1007\/BF00288933"},{"doi-asserted-by":"publisher","key":"e_1_2_1_19_1","DOI":"10.1145\/3183713.3190657"},{"doi-asserted-by":"publisher","key":"e_1_2_1_20_1","DOI":"10.1145\/971697.602266"},{"volume-title":"Processing spatial-keyword (SK) queries in geographic information retrieval (GIR) systems","author":"Hariharan Ramaswamy","unstructured":"Ramaswamy Hariharan , Bijit Hore , Chen Li , and Sharad Mehrotra . 2007. Processing spatial-keyword (SK) queries in geographic information retrieval (GIR) systems . In SSDBM. IEEE Computer Society , 16. DOI:https:\/\/doi.org\/10.1109\/SSDBM.2007.22 Ramaswamy Hariharan, Bijit Hore, Chen Li, and Sharad Mehrotra. 2007. Processing spatial-keyword (SK) queries in geographic information retrieval (GIR) systems. In SSDBM. IEEE Computer Society, 16. DOI:https:\/\/doi.org\/10.1109\/SSDBM.2007.22","key":"e_1_2_1_21_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.5555\/645921.673135"},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_1","DOI":"10.1109\/TKDE.2010.149"},{"doi-asserted-by":"publisher","key":"e_1_2_1_24_1","DOI":"10.14778\/2732977.2733000"},{"doi-asserted-by":"publisher","key":"e_1_2_1_25_1","DOI":"10.5555\/647222.760124"},{"doi-asserted-by":"publisher","key":"e_1_2_1_26_1","DOI":"10.1145\/3187009.3177736"},{"unstructured":"Siqiang Luo Yifeng Luo Shuigeng Zhou Gao Cong and Jihong Guan. 2014. Distributed spatial keyword querying on road networks. In EDBT Sihem Amer-Yahia Vassilis Christophides Anastasios Kementsietsidis Minos N. Garofalakis Stratos Idreos and Vincent Leroy (Eds.). 235\u2013246. DOI:https:\/\/doi.org\/10.5441\/002\/edbt.2014.23  Siqiang Luo Yifeng Luo Shuigeng Zhou Gao Cong and Jihong Guan. 2014. Distributed spatial keyword querying on road networks. In EDBT Sihem Amer-Yahia Vassilis Christophides Anastasios Kementsietsidis Minos N. Garofalakis Stratos Idreos and Vincent Leroy (Eds.). 235\u2013246. DOI:https:\/\/doi.org\/10.5441\/002\/edbt.2014.23","key":"e_1_2_1_27_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_28_1","DOI":"10.1109\/TKDE.2014.2339838"},{"unstructured":"Inc. Neo4j. 2019. Neo4j Graph Database. Retrieved from https:\/\/neo4j.com\/.  Inc. Neo4j. 2019. Neo4j Graph Database. Retrieved from https:\/\/neo4j.com\/.","key":"e_1_2_1_29_1"},{"unstructured":"Inc. Neo4j. 2019. Neo4j Spatial Plugin. Retrieved from https:\/\/neo4j-contrib.github.io\/spatial\/.  Inc. Neo4j. 2019. Neo4j Spatial Plugin. Retrieved from https:\/\/neo4j-contrib.github.io\/spatial\/.","key":"e_1_2_1_30_1"},{"unstructured":"Inc. Neo4j. 2020. Neo4j Java API. Retrieved from https:\/\/neo4j.com\/developer\/java\/.  Inc. Neo4j. 2020. Neo4j Java API. Retrieved from https:\/\/neo4j.com\/developer\/java\/.","key":"e_1_2_1_31_1"},{"unstructured":"Open Geospatial Consortium (OGC). 2019. GeoSPARQL. Retrieved from http:\/\/www.opengeospatial.org\/standards\/geosparql.  Open Geospatial Consortium (OGC). 2019. GeoSPARQL. Retrieved from http:\/\/www.opengeospatial.org\/standards\/geosparql.","key":"e_1_2_1_32_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_33_1","DOI":"10.14778\/3021924.3021929"},{"doi-asserted-by":"publisher","key":"e_1_2_1_34_1","DOI":"10.5555\/377296"},{"doi-asserted-by":"publisher","key":"e_1_2_1_35_1","DOI":"10.1145\/2247596.2247617"},{"doi-asserted-by":"publisher","key":"e_1_2_1_36_1","DOI":"10.5555\/1076819"},{"key":"e_1_2_1_37_1","volume-title":"Mokbel","author":"Sarwat Mohamed","year":"2015","unstructured":"Mohamed Sarwat , Jie Bao , Chi-Yin Chow , Justin J. Levandoski , Amr Magdy , and Mohamed F . Mokbel . 2015 . Context awareness in mobile systems. In Data Management in Pervasive Systems . 257\u2013287. DOI:https:\/\/doi.org\/10.1007\/978-3-319-20062-0_13 Mohamed Sarwat, Jie Bao, Chi-Yin Chow, Justin J. Levandoski, Amr Magdy, and Mohamed F. Mokbel. 2015. Context awareness in mobile systems. In Data Management in Pervasive Systems. 257\u2013287. DOI:https:\/\/doi.org\/10.1007\/978-3-319-20062-0_13"},{"doi-asserted-by":"publisher","key":"e_1_2_1_38_1","DOI":"10.1109\/TKDE.2013.29"},{"doi-asserted-by":"crossref","unstructured":"Mohamed Sarwat and Yuhan Sun. 2017. Answering location-aware graph reachability queries on GeoSocial data. In ICDE. 207\u2013210. DOI:https:\/\/doi.org\/10.1109\/ICDE.2017.76  Mohamed Sarwat and Yuhan Sun. 2017. Answering location-aware graph reachability queries on GeoSocial data. In ICDE. 207\u2013210. DOI:https:\/\/doi.org\/10.1109\/ICDE.2017.76","key":"e_1_2_1_39_1","DOI":"10.1109\/ICDE.2017.76"},{"key":"e_1_2_1_40_1","volume-title":"Spatial Databases: A Tour","author":"Shekhar Shashi","year":"2003","unstructured":"Shashi Shekhar and Sanjay Chawla . 2003 . Spatial Databases: A Tour . Prentice Hall . Shashi Shekhar and Sanjay Chawla. 2003. Spatial Databases: A Tour. Prentice Hall."},{"doi-asserted-by":"publisher","key":"e_1_2_1_41_1","DOI":"10.1145\/2588555.2610497"},{"doi-asserted-by":"publisher","key":"e_1_2_1_42_1","DOI":"10.1016\/j.ins.2017.09.049"},{"doi-asserted-by":"publisher","key":"e_1_2_1_43_1","DOI":"10.1145\/2723372.2723732"},{"doi-asserted-by":"crossref","unstructured":"Yuhan Sun Nitin Pasumarthy and Mohamed Sarwat. 2017. On evaluating social proximity-aware spatial range queries. In MDM.  Yuhan Sun Nitin Pasumarthy and Mohamed Sarwat. 2017. On evaluating social proximity-aware spatial range queries. In MDM.","key":"e_1_2_1_44_1","DOI":"10.1109\/MDM.2017.20"},{"doi-asserted-by":"publisher","key":"e_1_2_1_45_1","DOI":"10.1007\/s10707-019-00361-2"},{"doi-asserted-by":"crossref","unstructured":"Yuhan Sun Jia Yu and Mohamed Sarwat. 2019. Demonstrating spindra: A geographic knowledge graph management system. In ICDE. 2044\u20132047. DOI:https:\/\/doi.org\/10.1109\/ICDE.2019.00235  Yuhan Sun Jia Yu and Mohamed Sarwat. 2019. Demonstrating spindra: A geographic knowledge graph management system. In ICDE. 2044\u20132047. DOI:https:\/\/doi.org\/10.1109\/ICDE.2019.00235","key":"e_1_2_1_46_1","DOI":"10.1109\/ICDE.2019.00235"},{"unstructured":"Andr\u00e9s Taylor. [n.d.]. Cypher Language. Retrieved from https:\/\/neo4j.com\/developer\/cypher-query-language\/.   Andr\u00e9s Taylor. [n.d.]. Cypher Language. Retrieved from https:\/\/neo4j.com\/developer\/cypher-query-language\/.","key":"e_1_2_1_47_1"},{"unstructured":"Apache TinkerPop. 2019. Gremlin. Retrieved from https:\/\/tinkerpop.apache.org\/gremlin.html.  Apache TinkerPop. 2019. Gremlin. Retrieved from https:\/\/tinkerpop.apache.org\/gremlin.html.","key":"e_1_2_1_48_1"},{"unstructured":"Apache TinkerPop. 2019. TinkerPop. Retrieved from https:\/\/tinkerpop.apache.org.  Apache TinkerPop. 2019. TinkerPop. Retrieved from https:\/\/tinkerpop.apache.org.","key":"e_1_2_1_49_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_50_1","DOI":"10.1145\/3297280.3299732"},{"doi-asserted-by":"publisher","key":"e_1_2_1_51_1","DOI":"10.1145\/2629489"},{"key":"e_1_2_1_52_1","volume-title":"Lecture Notes in Computer Science","volume":"10837","author":"Wang Junhu","year":"2018","unstructured":"Junhu Wang , Gao Cong , Jinjun Chen , and Jianzhong Qi ( Eds .). 2018 . In ADC . Lecture Notes in Computer Science , Vol. 10837 . Springer. DOI:https:\/\/doi.org\/10.1007\/978-3-319-9 2013-9 Junhu Wang, Gao Cong, Jinjun Chen, and Jianzhong Qi (Eds.). 2018. In ADC. Lecture Notes in Computer Science, Vol. 10837. Springer. DOI:https:\/\/doi.org\/10.1007\/978-3-319-92013-9"},{"key":"e_1_2_1_53_1","volume-title":"Muhammad Aamir Cheema, and Xiaoyang Wang","author":"Zhang Chengyuan","year":"2014","unstructured":"Chengyuan Zhang , Ying Zhang , Wenjie Zhang , Xuemin Lin , Muhammad Aamir Cheema, and Xiaoyang Wang . 2014 . Diversified spatial keyword search on road networks. In EDBT, Sihem Amer-Yahia, Vassilis Christophides, Anastasios Kementsietsidis, Minos N. Garofalakis, Stratos Idreos, and Vincent Leroy (Eds.). OpenProceedings .org, 367\u2013378. DOI:https:\/\/doi.org\/10.5441\/002\/edbt.2014.34 Chengyuan Zhang, Ying Zhang, Wenjie Zhang, Xuemin Lin, Muhammad Aamir Cheema, and Xiaoyang Wang. 2014. Diversified spatial keyword search on road networks. In EDBT, Sihem Amer-Yahia, Vassilis Christophides, Anastasios Kementsietsidis, Minos N. Garofalakis, Stratos Idreos, and Vincent Leroy (Eds.). OpenProceedings.org, 367\u2013378. DOI:https:\/\/doi.org\/10.5441\/002\/edbt.2014.34"},{"doi-asserted-by":"publisher","key":"e_1_2_1_54_1","DOI":"10.1145\/1099554.1099584"}],"container-title":["ACM Transactions on Spatial Algorithms and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3450945","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3450945","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:49:24Z","timestamp":1750268964000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3450945"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,16]]},"references-count":54,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,9,30]]}},"alternative-id":["10.1145\/3450945"],"URL":"https:\/\/doi.org\/10.1145\/3450945","relation":{},"ISSN":["2374-0353","2374-0361"],"issn-type":[{"type":"print","value":"2374-0353"},{"type":"electronic","value":"2374-0361"}],"subject":[],"published":{"date-parts":[[2021,6,16]]},"assertion":[{"value":"2020-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-06-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}