Optimal location query based on k nearest neighbours

Abstract

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.

Keywords

optimal location query / k nearest neighbours / road network

References

[1] Cabello S, Diaz-Banez JM, Langerman S, Seara C, Ventura I. Reverse Facility Location Problems. Ljubljana: University of Ljubljana, Department of Mathematics, 2006

[2] Cardinal J, Langerman S. Min-max-min geometric facility location problems. In: Proceedings of European Workshop on Computational Geometry. 2006, 149–152

[3] Jakob K R A, Pruzan P M. The simple plant location problem: survey and synthesis. European Journal of Operational Research, 1983, 12: 36–81

[4] Tansel B C, Francis R L, Lowe T J. Location on networks: a survey. Management Science, 1983, 29(4): 498–511

[5] Xiao X K, Yao B, Li F F. Optimal location queries in road network databases. In: Proceedings of IEEE International Conference on Data Engineering. 2011, 804–815

[6] Van Kreveld M, Schwarzkopf O, de Berg M, Overmars M. Computational Geometry Algorithms and Applications. Heidelberg: Springer, 2000

[7] Yao B, Xiao X K, Li F F, Wu Y F. 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

[8] Qi J Z, Zhang R, Kulik L, Lin D, Xue Y. The min-dist location selection query. In: Proceedings of IEEE International Conference on Data Engineering. 2012, 366–377

[9] Qi J Z, Zhang R, Wang Y Q, Xue A Y, Yu G, Kulik L. The min-dist location selection and facility replacement queries. World Wide Web, 2014, 17(6): 1261–1293

[10] Chen Z, Liu Y B, Wong R C W, Xiong J M, Mai G L, Long C. Efficient algorithms for optimal location queries in road networks. In: Proceedings of the ACM SIGMOD International Conference on Management of Data. 2014, 123–134

[11] Chen Z T, Liu Y B, Wong R C W, Xiong J M, Mai G L, Long C. Optimal location queries in road networks. ACM Transactions on Database Systems, 2015, 40(3): 17

[12] Gu Y, Zhang H, Wang Z, Yu G. Efficient moving k nearest neighbor queries over line segment objects. World Wide Web, 2016, 19(4): 653–677

[13] Cui J T, Wang M, Li H, Cai Y. Place your next branch with MILE-RUN: min-dist location selection over user movement. Information Sciences, 2018, 463: 1–20

[14] Shokeen S. A study on fast food consumption pattern in India. International Journal of Research and Engineering, 2016, 3(12): 10–15

[15] Chen Z T, Liu Y B, Fu A W C, Wong R C W, Dai G N. KOLQ in a road network. In: Proceedings of IEEE International Conference on Mobile Data Management. 2019, 81–90

[16] Sankaranarayanan J, Samet H, Alborzi H. Path oracles for spatial networks. Proceedings of the VLDB Endowment, 2009, 2(1): 1210–1221

[17] Hu H, Lee D L, Lee V. Distance indexing on road networks. In: Proceedings of the International Conference on Very Large Data Bases. 2006, 894–905

[18] Samet H, Sankaranarayanan J, Alborzi H. Scalable network distance browsing in spatial databases. In: Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data. 2008, 43–54

[19] Mouratidis K, Yiu M L, Papadias D, Mamoulis N. Continuous nearest neighbor monitoring in road networks. In: Proceedings of the 32nd International Conference on Very Large Data Bases. 2006, 43–54

[20] Cheema M A, Zhang W, Lin X, Zhang Y, Li X F. 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

[21] Yan D, Zhao Z, Ng W. Efficient algorithms for finding optimal meeting point on road networks. Proceedings of the VLDB Endowment, 2011, 4(11): 968–979

[22] Qi J Z, Xu Z H, Xue Y, Wen Z Y. A branch and bound method for mindist location selection queries. In: Proceedings of the 23rd Australasian Database Conference–Volume 124. 2012, 51–60

[23] Huang J, Wen Z Y, Qi J Z, Zhang R, Chen J, He Z. Top-kmost influential locations selection. In: Proceedings of the 20th ACM International Conference on Information and Knowledge Management. 2011, 2377–2380

[24] Gao Y J, Qi S Y, Chen L, Zheng B H, Li X H. On efficient k-optimallocation- selection query processing in metric spaces. Information Sciences, 2015, 298: 98–117

[25] Wong R C W, Ozsu M T, Fu A W C, Yu P S, Liu L. Efficient method for maximizing bichromatic reverse nearest neighbor. Proceedings of the VLDB Endowment, 2009, 2(1): 1126–1137

[26] Wong R C W, Ozsu M T, Fu A W C, Yu P S, Liu L, Liu Y B. 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

[27] Yan D, Wong R CW, Ng W. 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

[28] Liu Y B, Wong R C W, Wang K, Li Z J, Chen C, Chen Z T. A new approach for maximizing bichromatic reverse nearest neighbor search. Knowledge and Information Systems, 2013, 36(1): 23–58

[29] Zhou Z N, Wu W, Li X H, Li M L, Hsu W. Maxfirst for maxbrknn. In: Proceedings of IEEE International Conference on Data Engineering. 2011, 828–839

[30] Liu R F, Fu A W C, Chen Z T, Huang Sl L, Liu Y B. 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

[31] Ghaemi P, Shahabi K, Wilson J P, Kashani F B. A comparative study of two approaches for supporting optimal network location queries. GeoInformatica, 2014, 18(2): 229–251

[32] Gamper J, Bohlen M, Innerebner M. Scalable computation of isochrones with network expiration. In: Proceedings of International Conference on Scientific and Statistical Database Management. 2012, 526–543

[33] Xu Z D, Jacobsen H A. Processing proximity relations in road networks. In: Proceedings of the ACM SIGMOD International Conference on Management of Data. 2010, 243–254

[34] Yilmaz E, Elbasi S, Ferhatosmanoglu H. 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

[35] Du Y, Zhang D H, Xia T. The optimal-location query. In: Proceedings of International Symposium on Spatial and Temporal Databases. 2005, 163–180

[36] Zhang D H, Du Y, Xia T, Tao Y F. Progressive computation of the min-dist optimal-location query. In: Proceedings of the International Conference on Very Large Data Bases. 2006, 643–654

[37] Yiu ML, Mamoulis N, Papadias D. Aggregate nearest neighbor queries in road networks. IEEE Transactions on Knowledge and Data Engineering, 2005, 17(6): 820–833

[38] Papadias D, Tao Y F, Mouratidis K, Hui K. Aggregate nearest neighbor queries in spatial databases. ACM Transactions on Database Systems, 2005, 30(2): 529–576

[39] Elmongui H G, Mokbel M F, Aref W G. Continuous aggregate nearest neighbor queries. GeoInformatica, 2013, 17(1): 63–95

[40] Korn F, Muthukrishnan S. Influence sets based on reverse nearest neighbor queries. ACM Sigmod Record, 2000, 29(2): 201–212

[41] Vlachou A, Doulkeridis C, Kotidis Y, Norvag K. Monochromatic and bichromatic reverse top-k queries. IEEE Transactions on Knowledge and Data Engineering, 2011, 23(8): 1215–1229

[42] Bernecker T, Emrich T, Kriegel H P, Renz M, Zankl S, Zufle A. Efficient probabilistic reverse nearest neighbor query processing on uncertain data. Proceedings of the VLDB Endowment, 2011, 4(10): 669–680

[43] Cheema M A, Lin X, Wang W, Zhang W J, Pei J. Probabilistic reverse nearest neighbor queries on uncertain data. IEEE Transactions on Knowledge and Data Engineering, 2009, 22(4): 550–564

[44] Xu L, Mai G L, Chen Z T, Liu Y B, Dai G N. MinSum based optimal location query in road networks. In: Proceedings of International Conference on Database Systems for Advanced Applications. 2017, 441–457

[45] Dijkstra E W. A note on two problems in connexion with graphs. Numerische Mathematik, 1959, 1(1): 269–271

RIGHTS & PERMISSIONS

Higher Education Press