Spatial Location Selection Over Moving Objects

Among the most fundamental problems in spatial decision,location selection(LS)plays an important role in a wide spectrum of applications,such as urban planning,logistics,mar-keting,location-based services,etc.Location selection problems aim to select the optimal location(s)to build facility(s)for maximizing profits:reducing the cost to access the services for objects,or making as many objects be served as possible.Fuelled by rapid developments in positioning and hardware technologies,a steady growth of applications for moving ob-jects are becoming the norm in today's information era.Nevertheless,the state-of-the-art location selection techniques cannot be applied in the increasingly widespread moving sce-narios,as they are stationary objects-oriented,whose single point model fails to describe the mobility of objects.To bridge the gap between existing LS techniques and application scenarios where objects are mobile,this dissertation takes the first step to movement-aware location selection problems,including maximum influence-based(Max-inf)LS,minimum distance-based(Min-dist)LS and facility relocation(FR)problems.We characterize the spa-tial features of objects'movements in terms of different probability models,and re-depict the distance measure and influence relationship between a location and a moving object.Based on that,novel solutions to movement-aware location selection,along with novel pruning rules,spatial index structures,upper bounds and optimization strategies,are proposed to tackle the high computational overhead that is caused by mobility.The developed models and techniques are able to make more reasonable decisions on location selection and open avenues to access the movement-aware location selection problem.The main contributions in this dissertation work are as follows.The first effort of the dissertation concentrates on a mobility-aware Max-inf problem,called PRIME-LS.Differing from traditional Max-inf,PRIME-LS models an object with multiple positions,each of which exhibits impact on the decision making.We use a distance-based cumulative probability model to describe influence behavior between a facility and all po-sitions of an object,which allows an object can be influenced by multiple facilities.To evaluate the probabilistic influence,a novel distance measure called minMaxRadius is de-veloped.Two novel pruning rules,Influence Arcs and Non-influence Boundary,are designed on top of minMaxRadius.To solve PRIME-LS efficiently,an algorithm called PINOCCHIO is presented,which comprises of the two pruning rules and two optimization strategies.Ex-perimental studies show PRIME-LS significantly improves the effectiveness of the mined optimal location compared to traditional range-based and nearest-neighbor-based semantics by 10%-35%.The pruning techniques can avoid nearly 67%unnecessary position valida-tion.Together with optimization strategies,PINOCCHIO reduces the running time by orders of magnitude.It also reveals two insights.On one hand,for the number of positions in an object,a reasonable range(24-48)is suggested such that we can achieve a tradeoff between accuracy of mobility and computational cost.On the other hand,if we expect a certain num-ber of moving objects to be influenced,the mined optimal locations do not vary much no matter how we choose the parameters of PRIME-LS.The second part of the dissertation studies a movement-aware Min-dist LS problem,named as MILE-RUN.Challenges introduced by MILE-RUN are solved via a novel framework.To eliminate some positions of a moving objects which are not/poorly contributive for decision,such as points with GPS errors and visited occasionally,we utilize Kernel method to model a user's frequent activity areas as reference locations with different presence probabilities.To model the uncertain movement,we rank candidates by expected values following possible world semantics.A transformation from the aspect of reference location is leveraged to reduce the complexity from exponential to linear.To handle the costly overhead owing to network distance,we present two groups of algorithms.Based on spatial locality,the first group use R-tree and a carefully designed local network index.Series of expected distance upper bounds are presented for avoiding unnecessary computations.The latter group uses network extension scheme without index.We also study the NP-hard problem of k-collective MILE-RUN,and present greedy heuristic with a provable approximation bound[(k-1)k]~k.Experiments demonstrate the framework is available for both undirected and directed road networks and more efficient compared to the baseline method by orders of magnitude,where more that 95%candidate locations are pruned by proposed algorithms with upper bounds.The comparison with the state-of-the-art techniques shows that our proposed algorithms are superior in most cases.The last part of the dissertation turns our attention to movement-aware Min-dist facility re-location problem,called MOTION-FR.As the main concern is also Min-dist,we employ a framework similar to MILE-RUN,where user movement is modeled following reference locations and possible world.In addition to candidate location,facility relocation consid-ers obsolete facility,which makes the problem more challenging.We present a framework FROST taking facility-substitute relationship into consideration.FROST comprises of two kinds of algorithms,index-based and index-free.The former is for the cases where facilities and users'movement are known apriori and the latter solves MOTION-FR in an online man-ner.We further generalize the problem to k-MOTION-FR.Due to its NP-hardness,we devise a greedy approximate solution by extending the sub-local network based algorithm.We the-oretically and empirically prove the benefit of each greedy step is monotonically decreasing in most cases.Experimental studies demonstrate the superiority of FROST compared to the baseline method by orders of magnitude.The comparison with the stationary facility relo-cation model also shows that the presented MOTION-FR is more appropriate and accurate in mobile scenarios.Notably,both experiments for MOTION-FR and MILE-RUN indicate that reference locations,nearby which users conduct their daily activities,are indeed closely related for choosing an optimal result.