Given a road network G = (V, E), where V(E) denotes the set of vertices(edges) in G, a set of points of interest P and a query point q residing in G, the reverse furthest neighbors (RFNR) query in road network...Given a road network G = (V, E), where V(E) denotes the set of vertices(edges) in G, a set of points of interest P and a query point q residing in G, the reverse furthest neighbors (RFNR) query in road networks fetches a set of points p ∈ P that take q as their furthest neighbor compared with all points in P ∪ {q}. This is the monochromatic RFNR (MRFNR) query. Another interesting version of RFNR query is the bichromatic reverse furthest neighbor (BRFNR) query. Given two sets of points P and Q, and a query point q ∈ Q, a BRFNR query fetches a set of points p ∈ P that take q as their furthest neighbor compared with all points in Q. This paper presents efficient algorithms for both MRFNR and BRFNR queries, which utilize landmarks and partitioning-based techniques. Experiments on real datasets confirm the efficiency and scalability of proposed algorithms.展开更多
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 ...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 and make 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.展开更多
The continuous top-t most influential place (CTtMIP) query is defined formally and solved efficiently in this paper. A CTtMIP query continuously monitors the t places with the maximum influence from the set of place...The continuous top-t most influential place (CTtMIP) query is defined formally and solved efficiently in this paper. A CTtMIP query continuously monitors the t places with the maximum influence from the set of places, where the influence of a place is defined as the number of its bichromatic reverse k nearest neighbors (BRkNNs). Two new metrics and their corresponding rules are introduced to shrink the search region and reduce the candidates of BRkNNs checked. Extensive experiments confirm that our proposed approach outperforms the state-of-the-art competitor significantly.展开更多
基金This work was supported by the National Natural Science Foundation of China under Grant Nos. U1636210, 61472039, 61373156, 91438121, and 61672351, the National Basic Research 973 Program of China under Grant No. 2015CB352403, the National Key Research and Development Program of China under Grant Nos. 2016YFB0700502, 2016YFC0803000, and 2016YFB0502603, the Scientific Innovation Act of Science and Technology Commission of Shanghai Municipality under Grant No. 15JC1402400, and Microsoft Research Asia.
文摘Given a road network G = (V, E), where V(E) denotes the set of vertices(edges) in G, a set of points of interest P and a query point q residing in G, the reverse furthest neighbors (RFNR) query in road networks fetches a set of points p ∈ P that take q as their furthest neighbor compared with all points in P ∪ {q}. This is the monochromatic RFNR (MRFNR) query. Another interesting version of RFNR query is the bichromatic reverse furthest neighbor (BRFNR) query. Given two sets of points P and Q, and a query point q ∈ Q, a BRFNR query fetches a set of points p ∈ P that take q as their furthest neighbor compared with all points in Q. This paper presents efficient algorithms for both MRFNR and BRFNR queries, which utilize landmarks and partitioning-based techniques. Experiments on real datasets confirm the efficiency and scalability of proposed algorithms.
基金This work was supported by the National Natural Science Foundation of China(Grants Nos.61602323,61703288)Natural Science Foundation of Liaoning Province(2019-MS-264,201602604)Technology Research Project of Education Department of Liaoning(lnqn201913).
文摘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 and make 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.
基金Supported by the National Natural Science Foundation of China (61003049)the Natural Science Foundation of Zhejiang Province (Y110278, 2010QNA5051)Zheda Zijin Plan
文摘The continuous top-t most influential place (CTtMIP) query is defined formally and solved efficiently in this paper. A CTtMIP query continuously monitors the t places with the maximum influence from the set of places, where the influence of a place is defined as the number of its bichromatic reverse k nearest neighbors (BRkNNs). Two new metrics and their corresponding rules are introduced to shrink the search region and reduce the candidates of BRkNNs checked. Extensive experiments confirm that our proposed approach outperforms the state-of-the-art competitor significantly.