|
|
|
An evaluation and query algorithm for the influence of spatial location based on RkNN |
Jingke XU1,2,3( ), Yidan ZHAO2, Ge YU1 |
1. School of Computer Science and Engineering, Northeastern University, Shenyang 110819, China
2. School of Information and Control Engineering, Shenyang Jianzhu University, Shenyang 110168, China
3. Liaoning Province Big Data Management and Analysis Laboratory of Urban Construction, Shenyang 110168, China |
|
|
|
|
Abstract This paper is devoted to the investigation of the evaluation and query algorithm problem for the influence of spatial location based on RkNN (reverse k nearest neighbor). On the one hand, an object can make contribution to multiple locations. However, for the existing measures for evaluating the influence of spatial location, an object only makes contribution to one location, and its influence is usually measured by the number of spatial objects in the region. In this case, a new measure for evaluating the influence of spatial location based on the RkNN is proposed. Since the weight of the contribution is determined by the distance between the object and the location, the influence weight definition is given, which meets the actual applications. On the other hand, a query algorithm for the influence of spatial location is introduced based on the proposed measure. Firstly, an algorithm named INCH (INtersection’s Convex Hull) is applied to get candidate regions, where all objects are candidates. Then, kNN and Range-k are used to refine results. Then, according to the proposed measure, the weights of objects in RkNN results are computed, and the influence of the location is accumulated. The experimental results on the real data show that the optimized algorithms outperform the basic algorithm on efficiency. In addition, in order to provide the best customer service in the location problem andmake the best use of all infrastructures, a location algorithm with the query is presented based on RkNN. The influence of each facility is calculated in the location program and the equilibrium coefficient is used to evaluate the reasonability of the location in the paper. The smaller the equilibrium coefficient is, the more reasonability the program is. The actual application shows that the location based on influence makes the location algorithm more reasonable and available.
|
| Keywords
spatial data
reverse k nearest neighbor
influence of spatial location
location algorithm
|
|
Corresponding Author(s):
Jingke XU
|
|
Just Accepted Date: 04 March 2020
Issue Date: 01 December 2020
|
|
| 1 |
J Zhang. Approximating the two-level facility location problem via a quasi-greedy approach. In: Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms. 2004, 801–810
|
| 2 |
D Sun, Z Hao. Group nearest neighbor queries based on voronoi diagrams. Application Research of Computers, 2010, 47(7): 1244–1251
|
| 3 |
Z Hao, Y Liu. Reverse nearest neighbor search in spatial database. Computer Science, 2005, 32(11): 115–118
|
| 4 |
R Farahani, N Asgari, N Heidari, M Hosseininia, M Goh. Covering problems in facility location: a review. Computers & Industrial Engineering, 2012, 62(1): 368–407
https://doi.org/10.1016/j.cie.2011.08.020
|
| 5 |
T Xia, D Zhang, E Kanoulas, Y Du. On computing top-t most influential spatial sites. In: Proceedings of the International Conference on Very Large Data Bases. 2005, 946–957
|
| 6 |
D Zhang, Y Du, T Xia, Y Tao. Progressive computation of the min-dist optimal-location query. In: Proceedings of the International Conference on Very Large Data Bases. 2006, 643–654
|
| 7 |
F Korn, S Muthukrishnan. Influence sets based on reverse nearest neighbor queries. In: Proceedings of the ACM Sigmod International Conference on Management of Data. 2000, 201–212
https://doi.org/10.1145/335191.335415
|
| 8 |
C Yang, K Lin. An index structure for efficient reverse nearest neighbor queries. In: Proceedings of the 17th International Conference on Data Engineering. 2001, 485–492
|
| 9 |
Y Tao, D Papadias, X Lian. Reverse kNN search inarbitrary dimensionality. In: Proceedings of the International Conference on Very Large Data Bases. 2004, 744–755
https://doi.org/10.1016/B978-012088469-8.50066-8
|
| 10 |
W Wu, F Yang, C Chan, K Tan. Finch: evaluating reverse k-nearestneighborqueries onlocation data. In: Proceedings of the International Conference on Very Large Data Bases. 2008, 1056–1067
https://doi.org/10.14778/1453856.1453970
|
| 11 |
M L Brandeau, S S Chiu. An overview of representative problems in location research. Management Science, 1989, 35(6): 645–674
https://doi.org/10.1287/mnsc.35.6.645
|
| 12 |
I Dogan. Analysis of facility location model using bayesian networks. Expert Systems with Applications, 2012, 39(1): 1092–1104
https://doi.org/10.1016/j.eswa.2011.07.109
|
| 13 |
W Bo, Y Chao, H Song, P Dong. Research on nested public facility location problem based on hierarchical model. Journal of Wuhan University of Technology (Information & Management Engineering), 2012, 34(2): 218–222
|
| 14 |
W Shui, H Ye, S Zhang. Research on dynamic location model and algorithm of logistics distribution center. Application Research of Computers, 2010, 27(12): 4476–4491
|
| 15 |
X Song, C Yu, H Sun, J Xu. GrKNN: group reverse k-nearest-neighbor query in spatial databases. Chinese Journal of Computers, 2010, 33(12): 2229–2238
https://doi.org/10.3724/SP.J.1016.2010.02229
|
| 16 |
J Xu, X Xia, H Sun, S Wang, G Yu. Research on influence evaluation based on RkNN and its application in location problem. In: Proceedings of the 14thWeb Information Systems and Applications Conference. 2018, 153–157
https://doi.org/10.1109/WISA.2017.40
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
| |
Shared |
|
|
|
|
| |
Discussed |
|
|
|
|
