1. School of Data and Computer Science, Sun Yat-Sen University, Guangzhou 510006, China 2. Guangdong Key Laboratory of Big Data Analysis and Processing, Guangzhou 510006, China 3. Department of Computer Science and Engineering, Chinese University of Hong Kong, Hong Kong 999077, China 4. Department of Computer Science and Engineering, The Hong Kong University of Science and Technology, Hong Kong 999077, China
Optimal location query in road networks is a basic operation in the location intelligence applications. Given a set of clients and servers on a road network, the purpose of optimal location query is to obtain a location for a new server, so that a certain objective function calculated based on the locations of clients and servers is optimal. Existing works assume no labels for servers and that a client only visits the nearest server. These assumptions are not realistic and it renders the existing work not useful in many cases. In this paper, we relax these assumptions and consider the k nearest neighbours (KNN) of clients. We introduce the problem of KNN-based optimal location query (KOLQ) which considers the k nearest servers of clients and labeled servers. We also introduce a variant problem called relocation KOLQ (RKOLQ) which aims at relocating an existing server to an optimal location. Two main analysis algorithms are proposed for these problems. Extensive experiments on the real road networks illustrate the efficiency of our proposed solutions.
S Cabello, JM Diaz-Banez, S Langerman, C Seara, I Ventura. Reverse Facility Location Problems. Ljubljana: University of Ljubljana, Department of Mathematics, 2006
2
J Cardinal, S Langerman. Min-max-min geometric facility location problems. In: Proceedings of European Workshop on Computational Geometry. 2006, 149–152
3
K R A Jakob, P M Pruzan. The simple plant location problem: survey and synthesis. European Journal of Operational Research, 1983, 12: 36–81 https://doi.org/10.1016/0377-2217(83)90181-9
X K Xiao, B Yao, F F Li. Optimal location queries in road network databases. In: Proceedings of IEEE International Conference on Data Engineering. 2011, 804–815 https://doi.org/10.1109/ICDE.2011.5767845
6
M Van Kreveld, O Schwarzkopf, M de Berg, M Overmars. Computational Geometry Algorithms and Applications. Heidelberg: Springer, 2000
7
B Yao, X K Xiao, F F Li, Y F Wu. Dynamic monitoring of optimal locations in road network databases. The VLDB Journal—The International Journal on Very Large Data Bases, 2014, 23(5): 697–720 https://doi.org/10.1007/s00778-013-0347-5
8
J Z Qi, R Zhang, L Kulik, D Lin, Y Xue. The min-dist location selection query. In: Proceedings of IEEE International Conference on Data Engineering. 2012, 366–377 https://doi.org/10.1109/ICDE.2012.45
9
J Z Qi, R Zhang, Y Q Wang, A Y Xue, G Yu, L Kulik. The min-dist location selection and facility replacement queries. World Wide Web, 2014, 17(6): 1261–1293 https://doi.org/10.1007/s11280-013-0223-7
10
Z Chen, Y B Liu, R C W Wong, J M Xiong, G L Mai, C Long. Efficient algorithms for optimal location queries in road networks. In: Proceedings of the ACM SIGMOD International Conference on Management of Data. 2014, 123–134 https://doi.org/10.1145/2588555.2612172
11
Z T Chen, Y B Liu, R C W Wong, J M Xiong, G L Mai, C Long. Optimal location queries in road networks. ACM Transactions on Database Systems, 2015, 40(3): 17 https://doi.org/10.1145/2818179
12
Y Gu, H Zhang, Z Wang, G Yu. Efficient moving k nearest neighbor queries over line segment objects. World Wide Web, 2016, 19(4): 653–677 https://doi.org/10.1007/s11280-015-0351-3
13
J T Cui, M Wang, H Li, Y Cai. Place your next branch with MILE-RUN: min-dist location selection over user movement. Information Sciences, 2018, 463: 1–20 https://doi.org/10.1016/j.ins.2018.06.036
14
S Shokeen. A study on fast food consumption pattern in India. International Journal of Research and Engineering, 2016, 3(12): 10–15
15
Z T Chen, Y B Liu, A W C Fu, R C W Wong, G N Dai. KOLQ in a road network. In: Proceedings of IEEE International Conference on Mobile Data Management. 2019, 81–90 https://doi.org/10.1109/MDM.2019.00-71
16
J Sankaranarayanan, H Samet, H Alborzi. Path oracles for spatial networks. Proceedings of the VLDB Endowment, 2009, 2(1): 1210–1221 https://doi.org/10.14778/1687627.1687763
17
H Hu, D L Lee, V Lee. Distance indexing on road networks. In: Proceedings of the International Conference on Very Large Data Bases. 2006, 894–905
18
H Samet, J Sankaranarayanan, H Alborzi. Scalable network distance browsing in spatial databases. In: Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data. 2008, 43–54 https://doi.org/10.1145/1376616.1376623
19
K Mouratidis, M L Yiu, D Papadias, N Mamoulis. Continuous nearest neighbor monitoring in road networks. In: Proceedings of the 32nd International Conference on Very Large Data Bases. 2006, 43–54
20
M A Cheema, W Zhang, X Lin, Y Zhang, X F Li. Continuous reverse knearest neighbors queries in euclidean space and in spatial networks. The VLDB Journal—The International Journal on Very Large Data Bases, 2012, 21(1): 69–95 https://doi.org/10.1007/s00778-011-0235-9
21
D Yan, Z Zhao, W Ng. Efficient algorithms for finding optimal meeting point on road networks. Proceedings of the VLDB Endowment, 2011, 4(11): 968–979 https://doi.org/10.14778/3402707.3402734
22
J Z Qi, Z H Xu, Y Xue, Z Y Wen. A branch and bound method for mindist location selection queries. In: Proceedings of the 23rd Australasian Database Conference–Volume 124. 2012, 51–60
23
J Huang, Z Y Wen, J Z Qi, R Zhang, J Chen, Z He. Top-kmost influential locations selection. In: Proceedings of the 20th ACM International Conference on Information and Knowledge Management. 2011, 2377–2380 https://doi.org/10.1145/2063576.2063971
24
Y J Gao, S Y Qi, L Chen, B H Zheng, X H Li. On efficient k-optimallocation- selection query processing in metric spaces. Information Sciences, 2015, 298: 98–117 https://doi.org/10.1016/j.ins.2014.11.038
25
R C W Wong, M T Ozsu, A W C Fu, P S Yu, L Liu. Efficient method for maximizing bichromatic reverse nearest neighbor. Proceedings of the VLDB Endowment, 2009, 2(1): 1126–1137 https://doi.org/10.14778/1687627.1687754
26
R C W Wong, M T Ozsu, A W C Fu, P S Yu, L Liu, Y B Liu. Maximizing bichromatic reverse nearest neighbor for Lp-norm in two-and threedimensional spaces. The VLDB Journal—The International Journal on Very Large Data Bases, 2011, 20(6): 893–919 https://doi.org/10.1007/s00778-011-0230-1
27
D Yan, R CW Wong, W Ng. Efficient methods for finding influential locations with adaptive grids. In: Proceedings of the 20th ACM International Conference on Information and Knowledge Management. 2011, 1475–1484 https://doi.org/10.1145/2063576.2063788
28
Y B Liu, R C W Wong, K Wang, Z J Li, C Chen, Z T Chen. A new approach for maximizing bichromatic reverse nearest neighbor search. Knowledge and Information Systems, 2013, 36(1): 23–58 https://doi.org/10.1007/s10115-012-0527-4
29
Z N Zhou, W Wu, X H Li, M L Li, W Hsu. Maxfirst for maxbrknn. In: Proceedings of IEEE International Conference on Data Engineering. 2011, 828–839 https://doi.org/10.1109/ICDE.2011.5767892
30
R F Liu, A W C Fu, Z T Chen, L Huang Sl, Y B Liu. Finding multiple new optimal locations in a road network. In: Proceedings of the 24th ACMSIGSPATIAL International Conference on Advances in Geographic Information Systems. 2016, 1–10 https://doi.org/10.1145/2996913.2996927
31
P Ghaemi, K Shahabi, J P Wilson, F B Kashani. A comparative study of two approaches for supporting optimal network location queries. GeoInformatica, 2014, 18(2): 229–251 https://doi.org/10.1007/s10707-013-0179-x
32
J Gamper, M Bohlen, M Innerebner. Scalable computation of isochrones with network expiration. In: Proceedings of International Conference on Scientific and Statistical Database Management. 2012, 526–543 https://doi.org/10.1007/978-3-642-31235-9_35
33
Z D Xu, H A Jacobsen. Processing proximity relations in road networks. In: Proceedings of the ACM SIGMOD International Conference on Management of Data. 2010, 243–254 https://doi.org/10.1145/1807167.1807196
34
E Yilmaz, S Elbasi, H Ferhatosmanoglu. Predicting optimal facility location without customer locations. In: Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2017, 2121–2130 https://doi.org/10.1145/3097983.3098198
35
Y Du, D H Zhang, T Xia. The optimal-location query. In: Proceedings of International Symposium on Spatial and Temporal Databases. 2005, 163–180 https://doi.org/10.1007/11535331_10
36
D H Zhang, Y Du, T Xia, Y F Tao. Progressive computation of the min-dist optimal-location query. In: Proceedings of the International Conference on Very Large Data Bases. 2006, 643–654
37
ML Yiu, N Mamoulis, D Papadias. Aggregate nearest neighbor queries in road networks. IEEE Transactions on Knowledge and Data Engineering, 2005, 17(6): 820–833 https://doi.org/10.1109/TKDE.2005.87
38
D Papadias, Y F Tao, K Mouratidis, K Hui. Aggregate nearest neighbor queries in spatial databases. ACM Transactions on Database Systems, 2005, 30(2): 529–576 https://doi.org/10.1145/1071610.1071616
F Korn, S Muthukrishnan. Influence sets based on reverse nearest neighbor queries. ACM Sigmod Record, 2000, 29(2): 201–212 https://doi.org/10.1145/335191.335415
41
A Vlachou, C Doulkeridis, Y Kotidis, K Norvag. Monochromatic and bichromatic reverse top-k queries. IEEE Transactions on Knowledge and Data Engineering, 2011, 23(8): 1215–1229 https://doi.org/10.1109/TKDE.2011.50
42
T Bernecker, T Emrich, H P Kriegel, M Renz, S Zankl, A Zufle. Efficient probabilistic reverse nearest neighbor query processing on uncertain data. Proceedings of the VLDB Endowment, 2011, 4(10): 669–680 https://doi.org/10.14778/2021017.2021024
43
M A Cheema, X Lin, W Wang, W J Zhang, J Pei. Probabilistic reverse nearest neighbor queries on uncertain data. IEEE Transactions on Knowledge and Data Engineering, 2009, 22(4): 550–564 https://doi.org/10.1109/TKDE.2009.108
44
L Xu, G L Mai, Z T Chen, Y B Liu, G N Dai. MinSum based optimal location query in road networks. In: Proceedings of International Conference on Database Systems for Advanced Applications. 2017, 441–457 https://doi.org/10.1007/978-3-319-55699-4_27
45
E W Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1959, 1(1): 269–271 https://doi.org/10.1007/BF01386390
