{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:21:06Z","timestamp":1760242866727,"version":"build-2065373602"},"reference-count":33,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2016,9,23]],"date-time":"2016-09-23T00:00:00Z","timestamp":1474588800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IJGI"],"abstract":"<jats:p>Top-k spatial preference queries rank objects based on the score of feature objects in their spatial neighborhood. Top-k preference queries are crucial for a wide range of location based services such as hotel browsing and apartment searching. In recent years, a lot of research has been conducted on processing of top-k spatial preference queries in Euclidean space. While few algorithms study top-k preference queries in road networks, they all focus on undirected road networks. In this paper, we investigate the problem of processing the top-k spatial preference queries in directed road networks where each road segment has a particular orientation. Computation of data object scores requires examining the scores of each feature object in its spatial neighborhood. This may cause the computational delay, thus resulting in a high query processing time. In this paper, we address this problem by proposing a pruning and grouping of feature objects to reduce the number of feature objects. Furthermore, we present an efficient algorithm called TOPS that can process top-k spatial preference queries in directed road networks. Experimental results indicate that our algorithm significantly reduces the query processing time compared to period solution for a wide range of problem settings.<\/jats:p>","DOI":"10.3390\/ijgi5100170","type":"journal-article","created":{"date-parts":[[2016,9,23]],"date-time":"2016-09-23T10:06:39Z","timestamp":1474625199000},"page":"170","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Top-k Spatial Preference Queries in Directed Road Networks"],"prefix":"10.3390","volume":"5","author":[{"given":"Muhammad","family":"Attique","sequence":"first","affiliation":[{"name":"Department of Software, Ajou University, Worldcup-ro 206, Yeongtong-gu, Suwon 16499, Korea"}]},{"given":"Hyung-Ju","family":"Cho","sequence":"additional","affiliation":[{"name":"Department of Software, Kyungpook National University, Gyeongsang-daero 2559, Sangju-si 37224, Korea"}]},{"given":"Rize","family":"Jin","sequence":"additional","affiliation":[{"name":"Department of Software, Ajou University, Worldcup-ro 206, Yeongtong-gu, Suwon 16499, Korea"}]},{"given":"Tae-Sun","family":"Chung","sequence":"additional","affiliation":[{"name":"Department of Software, Ajou University, Worldcup-ro 206, Yeongtong-gu, Suwon 16499, Korea"}]}],"member":"1968","published-online":{"date-parts":[[2016,9,23]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Bao, J., Chow, C., Mokbel, M., and Ku, W. (2010, January 23\u201326). Efficient evaluation of k-range nearest neighbor queries in road networks. Proceedings of the Eleventh International Conference on Mobile Data Management (MDM), Kansas City, MO, USA.","DOI":"10.1109\/MDM.2010.40"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.is.2013.10.008","article-title":"An efficient algorithm for computing safe exit points of moving range queries in directed road networks","volume":"41","author":"Cho","year":"2014","journal-title":"Inf. Syst."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1007\/s00778-011-0235-9","article-title":"Continuous reverse k nearest neighbors queries in Euclidean space and in spatial networks","volume":"21","author":"Cheema","year":"2012","journal-title":"VLDB J."},{"key":"ref_4","first-page":"540","article-title":"A safe exit approach for continuous monitoring of reverse k-nearest neighbors in road networks","volume":"12","author":"Attique","year":"2015","journal-title":"Int. Arab J. Inf. Technol."},{"key":"ref_5","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":"2011","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Ilyas, I., Beskales, G., and Soliman, M. (2008). A survey of Top-k query processing techniques in relational database systems. ACM Comput. Surv., 40.","DOI":"10.1145\/1391729.1391730"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Mamoulis, N., Yiu, M., Cheng, K., and Cheung, D. (2007). Efficient Top-k aggregation of ranked inputs. ACM Trans. Database Syst., 32.","DOI":"10.1145\/1272743.1272749"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1109\/TKDE.2010.119","article-title":"Ranking spatial data by quality preferences","volume":"23","author":"Yiu","year":"2011","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Yiu, M., Dai, X., Mamoulis, N., and Vaitis, M. (2007, January 15\u201320). Top-k spatial preference queries. Proceedings of the IEEE 23rd International Conference on Data Engineering (ICDE 2007), Istanbul, Turkey.","DOI":"10.1109\/ICDE.2007.368966"},{"key":"ref_10","first-page":"93","article-title":"Efficient processing of top-k spatial preference queries","volume":"4","author":"Vlachou","year":"2010","journal-title":"PVLDB"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"599","DOI":"10.1007\/s10115-013-0696-9","article-title":"ALPS: An efficient algorithm for top-k spatial preference search in road networks","volume":"42","author":"Cho","year":"2015","journal-title":"Knowl. Inf. Syst."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Attique, M., Qamar, R., Cho, H.-J., and Chung, T.-S. (2014, January 4\u20137). A new approach to process top-k spatial preference queries in a directed road network. Proceedings of the Third ACM SIGSPATIAL International Workshop on Mobile Geographic Information Systems, Dallas, TX, USA.","DOI":"10.1145\/2675316.2675320"},{"key":"ref_13","unstructured":"Kolahdouzan, M., and Shahabi, C. (September, January 31). Voronoi-based k nearest neighbor search for spatial network databases. Proceedings of the Thirtieth International Conference on Very Large Data Bases, Toronto, ON, Canada."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Song, Z., and Roussopoulos, N. (2001, January 12\u201315). k-Nearest neighbor search for moving query point. Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, Redondo Beach, CA, USA.","DOI":"10.1007\/3-540-47724-1_5"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Sun, Y., Yu, X., Bie, R., and Song, H. (2016). Discovering time-dependent shortest path on traffic graph for drivers towards green driving. J. Netw. Comput. Appl., in press.","DOI":"10.1016\/j.jnca.2015.10.018"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1007\/s11280-012-0185-1","article-title":"Efficient general spatial skyline computation","volume":"16","author":"Lin","year":"2013","journal-title":"World Wide Web"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"2507","DOI":"10.1109\/TKDE.2012.216","article-title":"Efficient Index-based approaches for skyline queries in location-based applications","volume":"25","author":"Lee","year":"2013","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_18","unstructured":"Liu, W., Jing, Y., Chen, K., and Sun, W. (2012). Web-Age Information Management, Springer."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Deng, K., Zhou, X., and Shen, H. (2007, January 15\u201320). Multi-source skyline query processing in road networks. Proceedings of the IEEE 23rd International Conference on Data Engineering, Istanbul, Turkey.","DOI":"10.1109\/ICDE.2007.367925"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1007\/s10115-012-0489-6","article-title":"Recommendations for two-way selections using skyline view queries","volume":"34","author":"Chen","year":"2013","journal-title":"Knowl. Inf. Syst."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Wang, Y., Wei, W., Deng, Q., Liu, W., and Song, H. (2016). An energy-efficient skyline query for massively multidimensional sensing data. Sensors, 16.","DOI":"10.3390\/s16010083"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Cheema, M., Lin, X., Zhang, W., and Zhang, Y. (2013, January 18\u201322). A safe zone based approach for monitoring moving skyline queries. Proceedings of the 16th International Conference on Extending Database Technology, Genoa, Italy.","DOI":"10.1145\/2452376.2452409"},{"key":"ref_23","unstructured":"Xia, T., Zhang, D., Kanoulas, E., and Du, Y. (September, January 30). On computing top-t most influential spatial sites. Proceedings of the 31st International Conference on Very Large Data Bases, Trondheim, Norway."},{"key":"ref_24","unstructured":"Du, Y., Zhang, D., and Xia, T. (2005). Advances in Spatial and Temporal Databases, Springer."},{"key":"ref_25","unstructured":"Zhang, D., Du, Y., Xia, T., and Tao, Y. (2006, January 12\u201315). Progessive computation of the min-dist optimal-location query. Proceedings of the 32nd International Conference on Very Large Data Bases, Seoul, Korea."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Mouratidis, K., Lin, Y., and Yiu, M. (2010, January 1\u20136). Preference queries in large multi-cost transportation networks. Proceedings of the 2010 IEEE 26th International Conference on Data Engineering (ICDE 2010), Long Beach, CA, USA.","DOI":"10.1109\/ICDE.2010.5447851"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1007\/s00779-016-0913-0","article-title":"K-multi-preference query over road networks","volume":"20","author":"Lin","year":"2016","journal-title":"Pers. Ubiquitous Comput."},{"key":"ref_28","unstructured":"Hartmann, A. (2012). Phase Transitions and Clustering Properties of Optimization Problems, Lecture given at DPG Physics School."},{"key":"ref_29","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\/602259.602266"},{"key":"ref_30","unstructured":"Real Datasets for Spatial Databases. Available online: http:\/\/www.cs.fsu.edu\/~lifeifei\/SpatialDataset.htm."},{"key":"ref_31","unstructured":"American Hotel & Lodging Association. Available online: http:\/\/www.ahla.com\/."},{"key":"ref_32","unstructured":"Papadias, D., Zhang, J., Mamoulis, N., and Tao, Y. (2003, January 9\u201312). Query processing in spatial network databases. Proceedings of the 29th International Conference on Very Large Data Bases, Berlin, Germany."},{"key":"ref_33","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."}],"container-title":["ISPRS International Journal of Geo-Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2220-9964\/5\/10\/170\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T19:31:39Z","timestamp":1760211099000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2220-9964\/5\/10\/170"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,9,23]]},"references-count":33,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2016,10]]}},"alternative-id":["ijgi5100170"],"URL":"https:\/\/doi.org\/10.3390\/ijgi5100170","relation":{},"ISSN":["2220-9964"],"issn-type":[{"type":"electronic","value":"2220-9964"}],"subject":[],"published":{"date-parts":[[2016,9,23]]}}}