Reverse keyword-based location search on road networks
Tóm tắt
Reverse top-k keyword-based location query (RTkKL), aims to find the maximum spatial region such that the query object is contained in the result of any top-k spatial keyword query with users’ queried keywords and any location in the region as arguments. Existing efforts on RTkKL find the objects in the Euclidean space. In this paper, we study the problem of reverse top-k keyword-based location query on road networks. We propose two methods. One is based on mark vertex, and the other is based on bisector. For the mark vertex based method, we identify the mark vertex according to the definition of RTkKL on road networks. Based on the mark vertex, we will get the mark segments in the result. For the bisector-based method, we find the border points for the query q and some objects. With Dijkstra algorithm, we start from the query point q. For each closed edge, whose two adjacent vertices have been extracted from the min heap, we would search the border points on the edge, and count the border points for the adjacent vertex. For each method, we propose effective pruning strategy to reduce the search range and computation cost. Finally, experiments demonstrate the efficiency of the proposed algorithm.
Tài liệu tham khảo
Attique M, Afzal M, Ali F, Mehmood I, Ijaz MF, Cho H-J (2020) Geo-social top-k and skyline keyword queries on road networks. Sensors 20(3):798
Benetis R, Jensen C S, Karčiauskas G, Šaltenis S (2002) Nearest neighbor and reverse nearest neighbor queries for moving objects. In: Proceedings of the international database engineering & applications symposium, Edmonton, Canada, pp 44–53
Borutta F, Nascimento M A, Niedermayer J, Kröger P (2014) Monochromatic RkNN queries in time-dependent road networks. In: Proceedings of the third ACM SIGSPATIAL international workshop on Mobile geographic information systems, Dallas/Fort Worth, TX, USA, pp 26–33
Cary A, Wolfson O, Rishe N (2010) Efficient and scalable method for processing top-k spatial Boolean queries. In: Proceedings of the 22nd international conference on scientific and statistical database management, Heidelberg, Germany, pp 87–95
Cheema M A, Lin X, Zhang W, Zhang Y (2011) Influence zone: efficiently processing reverse k nearest neighbors queries. In: Proceedings of the 27th international conference on data engineering, Hannover, Germany, pp 577–588
Choudhury FM, Culpepper JS, Sellis T, Cao X (2016) Maximizing bichromatic reverse spatial and textual k nearest neighbor queries. Proceedings of the VLDB Endowment 9(6):456–467
Cong G, Jensen CS, Wu D (2009) Efficient retrieval of the top-k most relevant spatial web objects. Proceedings of the VLDB Endowment 2(1):337–348
Dijkstra EW (1959) A note on two problems in connexion with graphs. Numerische Mathematik 1:269–271
Dong Y, Tang J, Wu S, Tian J, Chawla N V, Rao J, Cao H (2012) Link Prediction and recommendation across heterogeneous social networks. In: Proceedings of the 12th IEEE International Conference on Data Mining, Brussels, Belgium, pp 181–190
Felipe I D, Hristidis V, Rishe N (2008) Keyword search on spatial databases. In: Proceedings of the 24th international conference on data engineering, Cancún, Mexico, pp 656–665
Gao Y, Zheng B, Chen G, Lee W-C, Lee K C K, Li Q (2009) Visible reverse k-nearest neighbor queries. In: Proceedings of the 25th international conference on data engineering, Shanghai, China, pp 1203–1206
Gao Y, Zheng B, Chen G, Lee W-C, Lee KCK, Li Q (2009) Visible reverse k-nearest neighbor query processing in spatial databases. IEEE Trans Knowl Data Eng 21(9):1314–1327
Gao Y, Qin X, Zheng B, Chen G (2015) Efficient reverse top-k Boolean spatial keyword queries on road networks. IEEE Trans Knowl Data Eng 27(5):1205–1218
Guo L, Shao J, Aung HH, Tan K-L (2015) Efficient continuous top-k spatial keyword queries on road networks. Geoinformatica 19(1):29–60
Hopcroft J, Lou T, Tang J (2011) Who will follow you back? Reciprocal relationship prediction. In: Proceedings of the 20th ACM conference on information and knowledge management, Glasgow, United Kingdom, pp 1137–1146
Kolahdouzan M, Shahabi C (2004) Voronoi-based K nearest neighbor search for spatial network databases. In: Proceedings of the thirtieth international conference on very large data bases, Toronto, Canada, pp 840–851
Korn F, Muthukrishnan S (2000) Influence sets based on reverse nearest neighbor queries. In: Proceedings of the 2000 ACM SIGMOD international conference on Management of Data, Dallas, Texas, USA, pp 201–212
Korn F, Muthukrishnan S, Srivastava D (2002) Reverse nearest neighbor aggregates over data streams. In: Proceedings of the 28th international conference on very large data bases, Hong Kong, pp 814–825
Lee KCK, Zheng B, Lee W-C (2008) Ranked reverse nearest neighbor search. IEEE Trans Knowl Data Eng 20(7):894–910
Li F, Cheng D, Hadjieleftheriou M, Kollios G, Teng S-H (2005) On trip planning queries in spatial databases. In: Proceedings of the 9th international symposium on advances in spatial and temporal databases. Angra dos Reis, Brazil, pp 273–290
Li J, Li Y, Shen P, Xia X, Zong C, Xia C (2018) Reverse k nearest neighbor queries in time-dependent road networks. In: Proceedings of 20th IEEE international conference on high performance computing and communications; 16th IEEE international conference on Smart City; 4th IEEE international conference on data science and systems, Exeter, United Kingdom, pp 1064–1069
Lian X, Chen L (2009) Efficient processing of probabilistic reverse nearest neighbor queries over uncertain data. VLDB J 18(3):787–808
Liu Q, Gao Y, Chen G, Zheng B, Zhou L (2016) Answering why-not and why questions on reverse top-k queries. VLDB J 25:867–892
Liu Q, Feng Z, Xie X, Xu J, Lin X, Jensen C S (2018) iZone: Efficient influence zone evaluation over geo-textual data. In: Proceeding of the 34th IEEE international conference on data engineering, Paris, France, pp 1645–1648
Liu Q, Zhu Z, Xu J, Gao Y (2021) MaxiZone: Maximizing influence zone over geo-textual data. IEEE Trans Knowl Data Eng. 33(10):3381–3393
Lou T, Tang J, Hopcroft J, Fang Z, Ding X (2013) Learning to predict reciprocity and triadic closure in social networks. ACM Trans Knowl Discov Data 7(2):5:1–5:25
Lu J, Lu Y, Cong G (2011) Reverse spatial and textual k nearest neighbor search. In: Proceedings of the ACM SIGMOD international conference on Management of Data, Athens, Greece, pp 349–360
Luo C, Li J, Li G, Wei W, Li Y, Li J (2016) Efficient reverse spatial and textual k nearest neighbor queries on road networks. Knowl-Based Syst 93:121–134
Stanoi I, Agrawal D, Abbadi A E (2000) Reverse nearest neighbor queries for dynamic databases. In: Proceedings of 2000 ACM SIGMOD workshop on research issues in data mining and knowledge discovery, Dallas, Texas, USA, pp 44–53
Tao Y, Papadias D, Lian X (2004) Reverse kNN search in arbitrary dimensionality. In: Proceedings of the thirtieth international conference on very large data bases, Toronto, Canada, pp 744–755
Wang S, Bao Z, Culpepper JS, Sellis T, Cong G (2018) Reverse k nearest neighbor search over trajectories. IEEE Trans Knowl Data Eng 30(4):757–771
Wu W, Yang F, Chan C-Y, Tan K-L (2008) FINCH: evaluating reverse k-nearest-neighbor queries on location data. Proceedings of the VLDB Endowment 1(1):1056–1067
Xie X, Yiu ML, Cheng R, Lu H (2014) Scalable evaluation of trajectory queries over imprecise location data. IEEE Trans Knowl Data Eng 26(8):2029–2044
Xie X, Lin X, Xu J, Jensen C S (2017) Reverse keyword-based location search. In: Proceeding of the 33rd IEEE international conference on data engineering, San Diego, CA, USA, pp 375–386
Yang C, Lin K-I (2001) An index structure for efficient reverse nearest neighbor queries. In: Proceedings of the 17th international conference on data engineering, Heidelberg, Germany, pp 485–492
Yang S, Cheema MA, Lin X, Zhang Y, Zhang W (2017) Reverse k nearest neighbors queries and spatial reverse top-k queries. VLDB J 26(2):151–176
Yiu ML, Papadias D, Mamoulis N, Tao Y (2006) Reverse nearest neighbors in large graphs. IEEE Trans Knowl Data Eng 18(4):540–553
Zhang J, Fang Z, Chen W, Tang J (2015) Diffusion of “following” links in microblogging networks. IEEE Trans Knowl Data Eng 27(8):2093–2106
Zhao P, Fang HS, Sheng VS, Li Z, Xu J, Wu J, Cui Z (2017) Monochromatic and bichromatic ranked reverse Boolean spatial keyword nearest neighbors search. World Wide Web 20(1):39–59
Zhao J, Gao Y, Chen G, Jensen C S, Chen R, Cai D (2017) Reverse top-k geo-social keyword queries in road networks. In: Proceedings of the 33rd IEEE international conference on data engineering, San Diego, CA, USA, pp 387–398
Zhong Z, Lin X, He L (2020) Answering range-based reverse kNN and why-not reverse kNN queries. Front Comput Sci 14(1):233–235