Research Of Multi-Facility Location Problem Based On Reverse Spatial Queries

In recent years,with the emergence of information publishing methods represented by blogs,social networks,and location-based services(LBS),as well as the development of technologies such as the Internet of Things and cloud computing,we have entered the era of big data.In this context,spatial data began to receive unprecedented attention.Spatial data,namely,data with spatial dimensions,are used to describe objects in real life,indicating the shape,size,location and distribution characteristics of spatial entities.More than 80% of real-life data is related to geographic location.The value of spatial big data lies in the relationship between space and objects,and how to efficiently process spatial big data is the top priority for its contribution to human beings.Nearest Neighbors(NN)query is a traditional problem in computational mathematics,which can be applied to content similarity retrieval,pattern recognition,Geographic Information System(GIS)and so on.On this basis,various spatial queries are also emerging.Given a set of facilities,a set of clients,and a query facility q,a Reverse k Nearest Neighbors(Rk NN)query finds each of the customer points that q is one of its k-nearest objects.Since q has the greatest impact on the clients in the query results,these clients are highly likely to use the facilities at point q.Taking restaurants as an example,in market research,potential customers of a new restaurant q can be assessed by retrieving all customers that consider the restaurant as one of the k nearest neighbors.In addition to the field of facility location problem,Rk NN can also be widely used in more scenarios,such as market forecasting,decision support,database file search,etc.,and has been deeply studied.The facility location problem has a wide range of applications in production and life,logistics,and even military fields,including selecting locations for factories,fire stations,logistic centers and missile warehouses,etc.Site selection is one of the most important long-term decisions.The quality of site selection directly affects the service quality,service efficiency and service cost of facilities,thereby affecting profits and market competitiveness.In this paper,we propose a brand new variant of Rk NN query,namely,maximal group reverse k nearest neighbors(Max Group Rk NN)query.Given a set of clients,a set of candidate facilities and input parameters k and m,Max Group Rk NN query returns a set of m facilities out of the candidates,such that the total number of Rk NNs of the result set is maximized.The Max Group Rk NN query is important for multi-facility location problem,which aims to maximize the total potential clients of a group of facility providing the same service such as chain stores,charging stations and logistic centers.A straightforward solution is to enumerate all possible combinations which is obviously time consuming.In order to address this problem,we present an efficient solution namely MGR,which is based on a well designed pruning technique.The proposed pruning technique is able to filter out the candidates that cannot contribute to the final result and reduce the computation cost dramatically.A detailed theoretical analysis of our method is provided.Moreover,we propose a novel concept called “contribution”,denoting the importance of each candidate point during the pruning process.Based on this concept,we optimize MGR,further increase the pruning rate,and reduce the computation cost.The experimental results also confirm that our proposed method has high efficiency and scalability,can achieve good results in multi-facility location problem,and has broad application prospects in real life.