{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,11]],"date-time":"2025-12-11T07:08:36Z","timestamp":1765436916251,"version":"build-2065373602"},"reference-count":42,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2021,12,1]],"date-time":"2021-12-01T00:00:00Z","timestamp":1638316800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"the Key Fund of the National Natural Science  Foundation of China","award":["41631175"],"award-info":[{"award-number":["41631175"]}]},{"name":"The National Key Research and Development Program of China","award":["2017YFB0503500"],"award-info":[{"award-number":["2017YFB0503500"]}]},{"name":"the National Science Foundation Grant","award":["1637541"],"award-info":[{"award-number":["1637541"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IJGI"],"abstract":"<jats:p>The range query is one of the most important query types in spatial data processing. Geographic information systems use it to find spatial objects within a user-specified range, and it supports data mining tasks, such as density-based clustering. In many applications, ranges are not computed in unrestricted Euclidean space, but on a network. While the majority of access methods cannot trivially be extended to network space, existing network index structures partition the network space without considering the data distribution. This potentially results in inefficiency due to a very skewed node distribution. To improve range query processing on networks, this paper proposes a balanced Hierarchical Network index (HN-tree) to query spatial objects on networks. The main idea is to recursively partition the data on the network such that each partition has a similar number of spatial objects. Leveraging the HN-tree, we present an efficient range query algorithm, which is empirically evaluated using three different road networks and several baselines and state-of-the-art network indices. The experimental evaluation shows that the HN-tree substantially outperforms existing methods.<\/jats:p>","DOI":"10.3390\/ijgi10120814","type":"journal-article","created":{"date-parts":[[2021,12,2]],"date-time":"2021-12-02T02:40:02Z","timestamp":1638412802000},"page":"814","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["A Hierarchical Spatial Network Index for Arbitrarily Distributed Spatial Objects"],"prefix":"10.3390","volume":"10","author":[{"given":"Xiangqiang","family":"Min","sequence":"first","affiliation":[{"name":"Key Laboratory of the Virtual Geographic Environment, Ministry of Education of PRC, Nanjing Normal University, Nanjing 210023, China"},{"name":"Department of Geography and Geoinformation Science, George Mason University, Fairfax, VA 22030, USA"},{"name":"Jiangsu Center for Collaborative Innovation in Geographical Information Resource Development and Application, Nanjing Normal University, Nanjing 210023, China"}]},{"given":"Dieter","family":"Pfoser","sequence":"additional","affiliation":[{"name":"Department of Geography and Geoinformation Science, George Mason University, Fairfax, VA 22030, USA"}]},{"given":"Andreas","family":"Z\u00fcfle","sequence":"additional","affiliation":[{"name":"Department of Geography and Geoinformation Science, George Mason University, Fairfax, VA 22030, USA"}]},{"given":"Yehua","family":"Sheng","sequence":"additional","affiliation":[{"name":"Key Laboratory of the Virtual Geographic Environment, Ministry of Education of PRC, Nanjing Normal University, Nanjing 210023, China"},{"name":"Jiangsu Center for Collaborative Innovation in Geographical Information Resource Development and Application, Nanjing Normal University, Nanjing 210023, China"}]}],"member":"1968","published-online":{"date-parts":[[2021,12,1]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/j.isprsjprs.2015.10.012","article-title":"Geospatial big data handling theory and methods: A review and research challenges","volume":"115","author":"Li","year":"2016","journal-title":"ISPRS J. Photogramm. Remote Sens."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1109\/69.755614","article-title":"Spatial databases-accomplishments and research needs","volume":"11","author":"Shekhar","year":"1999","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1007\/s00778-019-00568-7","article-title":"Spatial crowdsourcing: A survey","volume":"29","author":"Tong","year":"2020","journal-title":"VLDB J."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"1765","DOI":"10.1080\/13658816.2020.1730848","article-title":"Volunteered geographic information research in the first decade: A narrative review of selected journal articles in GIScience","volume":"34","author":"Yan","year":"2020","journal-title":"Int. J. Geogr. Inf. Sci."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"1062","DOI":"10.1080\/13658816.2018.1563302","article-title":"Measuring inter-city connectivity in an urban agglomeration based on multi-source data","volume":"33","author":"Lin","year":"2019","journal-title":"Int. J. Geogr. Inf. Sci."},{"key":"ref_6","first-page":"226","article-title":"A density-based algorithm for discovering clusters in large spatial databases with noise","volume":"96","author":"Ester","year":"1996","journal-title":"KDD-96 Proc."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Guttman, A. (1984, January 18\u201321). R-trees: A dynamic index structure for spatial searching. Proceedings of the 1984 ACM SIGMOD International Conference on Management of Data, Boston, MA, USA.","DOI":"10.1145\/602264.602266"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"382","DOI":"10.1109\/TKDE.2014.2330836","article-title":"An air index for spatial query processing in road networks","volume":"27","author":"Sun","year":"2014","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1038\/486033a","article-title":"Q&A: The data visualizer","volume":"486","author":"Hoffman","year":"2012","journal-title":"Nature"},{"key":"ref_10","unstructured":"Pfoser, D., Jensen, C.S., and Theodoridis, Y. (2000, January 10\u201314). Novel approaches to the indexing of moving object trajectories. Proceedings of the 26th VLDB Conference, Cairo, Egypt."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Cudre-Mauroux, P., Wu, E., and Madden, S. (2010, January 1\u20136). Trajstore: An adaptive storage system for very large trajectory data sets. Proceedings of the 2010 IEEE 26th International Conference on Data Engineering (ICDE 2010), Long Beach, CA, USA.","DOI":"10.1109\/ICDE.2010.5447829"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s10844-011-0180-5","article-title":"cTraj: Efficient indexing and searching of sequences containing multiple moving objects","volume":"39","year":"2012","journal-title":"J. Intell. Inf. Syst."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.ins.2012.03.001","article-title":"Spatial indexing for massively update intensive applications","volume":"203","author":"Song","year":"2012","journal-title":"Inf. Sci."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1007\/s10115-015-0830-y","article-title":"A survey on indexing techniques for big data: Taxonomy and performance evaluation","volume":"46","author":"Gani","year":"2016","journal-title":"Knowl. Inf. Syst."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1007\/s10707-005-6429-9","article-title":"Trajectory indexing using movement constraints","volume":"9","author":"Pfoser","year":"2005","journal-title":"GeoInformatica"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"643","DOI":"10.1007\/s00778-011-0236-8","article-title":"Indexing in-network trajectory flows","volume":"20","author":"Popa","year":"2011","journal-title":"VLDB J."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"637","DOI":"10.1016\/j.jcss.2010.02.005","article-title":"Voronoi-based range and continuous range query processing in mobile databases","volume":"77","author":"Xuan","year":"2011","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Papadias, D., Zhang, J., Mamoulis, N., and Tao, Y. (2003). Query processing in spatial network databases. Proceedings 2003 VLDB Conference, Elsevier.","DOI":"10.1016\/B978-012722442-8\/50076-8"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"2175","DOI":"10.1109\/TKDE.2015.2399306","article-title":"G-tree: An efficient and scalable index for spatial search on road networks","volume":"27","author":"Zhong","year":"2015","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"547","DOI":"10.1109\/TKDE.2010.243","article-title":"ROAD: A new spatial object search framework for road networks","volume":"24","author":"Lee","year":"2010","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1007\/s10707-014-0206-6","article-title":"Partition-based range query for uncertain trajectories in road networks","volume":"19","author":"Chen","year":"2015","journal-title":"GeoInformatica"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Teng, X., Yang, J., Kim, J.S., Trajcevski, G., Z\u00fcfle, A., and Nascimento, M.A. (2019, January 19\u201321). Fine-grained diversification of proximity constrained queries on road networks. Proceedings of the 16th International Symposium on Spatial and Temporal Databases, Vienna, Austria.","DOI":"10.1145\/3340964.3340970"},{"key":"ref_23","first-page":"3","article-title":"Indexing the trajectories of moving objects","volume":"25","author":"Pfoser","year":"2002","journal-title":"IEEE Data Eng. Bull."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1109\/TSE.1979.234200","article-title":"Multidimensional binary search trees in database applications","volume":"4","author":"Bentley","year":"1979","journal-title":"IEEE Trans. Softw. Eng."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Beckmann, N., Kriegel, H.P., Schneider, R., and Seeger, B. (1990, January 23\u201325). The R*-tree: An efficient and robust access method for points and rectangles. Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, Atlantic City, NJ, USA.","DOI":"10.1145\/93597.98741"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"\u0160um\u00e1k, M., and Gursk\u1ef3, P. (2014). R++-tree: An efficient spatial access method for highly redundant point data. New Trends in Databases and Information Systems, Springer.","DOI":"10.1007\/978-3-319-01863-8_4"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"487","DOI":"10.1007\/s10707-014-0218-2","article-title":"The TM-RTree: An index on generic moving objects for range queries","volume":"19","author":"Xu","year":"2015","journal-title":"GeoInformatica"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Li, Z., Chen, L., and Wang, Y. (2019, January 8\u201311). G*-Tree: An Efficient Spatial Index on Road Networks. Proceedings of the 2019 IEEE 35th International Conference on Data Engineering (ICDE), Macao, China.","DOI":"10.1109\/ICDE.2019.00032"},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Zhang, H., Lu, F., and Chen, J. (2016). A line graph-based continuous range query method for moving objects in networks. ISPRS Int. J. Geo-Inf., 5.","DOI":"10.3390\/ijgi5120246"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Yin, X., Ding, Z., and Li, J. (April, January 31). Moving continuous k nearest neighbor queries in spatial network databases. Proceedings of the 2009 WRI World Congress on Computer Science and Information Engineering, Washington, DC, USA.","DOI":"10.1109\/CSIE.2009.626"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"763","DOI":"10.1007\/s10707-017-0306-1","article-title":"Knowledge extraction from crowdsourced data for the enrichment of road networks","volume":"21","author":"Schmid","year":"2017","journal-title":"Geoinformatica"},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Skoumas, G., Schmid, K.A., Joss\u00e9, G., Schubert, M., Nascimento, M.A., Z\u00fcfle, A., Renz, M., and Pfoser, D. (2015). Knowledge-enriched route computation. International Symposium on Spatial and Temporal Databases, Springer.","DOI":"10.1007\/978-3-319-22363-6_9"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"1065","DOI":"10.1109\/TKDE.2010.171","article-title":"Processing of continuous location-based range queries on moving objects in road networks","volume":"23","author":"Wang","year":"2010","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Lee, K.C., Lee, W.C., and Zheng, B. (2009, January 24\u201326). Fast object search on road networks. Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, Saint Petersburg, Russia.","DOI":"10.1145\/1516360.1516476"},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Frentzos, E. (2003). Indexing objects moving on fixed networks. International Symposium on Spatial and Temporal Databases, Springer.","DOI":"10.1007\/978-3-540-45072-6_17"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","article-title":"A note on two problems in connexion with graphs","volume":"1","author":"Dijkstra","year":"1959","journal-title":"Numer. Math."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1137\/S1064827595287997","article-title":"A fast and high quality multilevel scheme for partitioning irregular graphs","volume":"20","author":"Karypis","year":"1998","journal-title":"SIAM J. Sci. Comput."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1016\/j.is.2016.09.006","article-title":"Partitioning road networks using density peak graphs: Efficiency vs. accuracy","volume":"64","author":"Anwar","year":"2017","journal-title":"Inf. Syst."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"1136","DOI":"10.1007\/s10618-020-00688-7","article-title":"TEAGS: Time-aware text embedding approach to generate subgraphs","volume":"34","author":"Hosseini","year":"2020","journal-title":"Data Min. Knowl. Discov."},{"key":"ref_40","unstructured":"Najafipour, S., Hosseini, S., Hua, W., Kangavari, M.R., and Zhou, X. (2020). SoulMate: Short-text author linking through Multi-aspect temporal-textual embedding. IEEE Trans. Knowl. Data Eng."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"2713","DOI":"10.1007\/s11227-020-03290-2","article-title":"GS4: Graph stream summarization based on both the structure and semantics","volume":"77","author":"Kangavari","year":"2021","journal-title":"J. Supercomput."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1023\/A:1015231126594","article-title":"A Framework for Generating Network-Based Moving Objects","volume":"6","author":"Brinkhoff","year":"2002","journal-title":"Geoinformatica"}],"container-title":["ISPRS International Journal of Geo-Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2220-9964\/10\/12\/814\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T07:38:30Z","timestamp":1760168310000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2220-9964\/10\/12\/814"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,1]]},"references-count":42,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2021,12]]}},"alternative-id":["ijgi10120814"],"URL":"https:\/\/doi.org\/10.3390\/ijgi10120814","relation":{},"ISSN":["2220-9964"],"issn-type":[{"type":"electronic","value":"2220-9964"}],"subject":[],"published":{"date-parts":[[2021,12,1]]}}}