Research On Facility Replacement Problem In Location Service Application

Optimal location query problem has drew significant research attention due to the proliferation of GPS equipped with intelligent devices and location-based services(e.g.,Gowalla,Foursquare).The Min-dist optimal location query is an important spatial decision problem that has a wide spectrum of applications,such as urban planning,logistics,decision support system,etc.According to evaluation criteria,they are commonly categorized into two major categories,Min-dist and Max-inf.In this paper,we focus on Min-dist facility replacement problem.Given a set O of objects,a set F of facilities and a set P of potential facilities,the Min-dist facility replacement problem aims to find the optimal facility replacement pair<1),>among F and P such that the average distance between objects and their nearest facilities can be minimized.Although plenty of efforts have been proposed to address this problem,they all have two obvious limitations:(1)they assume that the objects are stationary.Unfortunately,in practice,objects(e.g.,human,animals)are mobile in various scenarios;(2)they solve the problem on Euclidean space.However,objects movements between spatial locations in real-world are usually confined to road network.Due to the movements of objects and the movement restrictions,it is non-trivial to find optimal facility replacement pair in state-of-the-art research.Hence,none of existing solutions is applicable.In light of the movements of objects and movement restrictions,we propose mobility aware Min-dist facility replacement problem in road network.To address the efficiency issue caused by mobility and road network,we model the moving objects with the help of kernel method.And then reference location and their corresponding probility can be captured.More importantly,we transform the aspect from possible state into reference location,and the complexity significantly drops from exponential time to polynomial time.However,this can only solve the problem of small set of moving objects.For massive moving object data sets,we propose three efficient algorithms to settle mobility aware Min-dist facility replacement problem in road network:(1)Spatial join pruning algorithm tightens search space through spatial join method with the help of R~*-tree,constructs max heap according to facility replacement pair upper bound value,and then iteratively visits heap top entry until finding the optimal facility replacement pair;(2)Local network pruning algorithm extends local network(local sub-network)for each reference location and records information associated with edge in local network(local sub-network),and then constructs max heap according to upper bound value,we can find optimal facility replacement pair through looking-up tables;(3)Extended network algorithm is designed for online query,the main idea of EN is extending network,recording distance between reference location and its nearest facility,and progressively accumulating value until sub-nearest facilities are found for each reference location.Eventually,we can find the optimal facility replacement pair based on recording hash table.The former two methods assume the existing facilities and moving objects to be known apriori,and they establish the index structure to improve the query efficiency.The last one is online query algorithm without any index.Furthermore,we analyze the time complexity of each algorithm and ensure the efficiency of the algorithm in theory.Exhaustive experiments are conducted in both real-world and synthetic datasets,the results of which demonstrate that our algorithms are more efficient compared to the sequential scan method by orders of magnitude.