The Research And Application Of Optimal Regions Search Problem On Spatial Data

With the development and popularity of GIS,there comes a huge amount of spatial data.Analysis of spatial data is a popular research direction and has a wide application.Our research mainly focus on the optimal regions search problem,and we propose an effective algorithm to solve this problem.First,we propose a strategy to query the optimal available service point for each customer point.By combining CPM algorithm with Strip-PlaneScan algorithm,we develop an algorithm called Strip-CPM to complete this query.Take the allocation of car parking as an example,a parking lot that can accommodate k cars should be allocated to the nearest k cars around it.Each car need to find the nearest parking lot which has not been occupied by k cars.Applying grid index structure,Strip-CPM algorithm adopts CPM algorithm to process kNN query of service point and Strip-PlaneScan algorithm to process NN query of customer point.By judging and processing whether the query results of customer point and service point are the required results,Strip-CPM algorithm finally allocate the all customer points to the service points.The problem of group optimal region search for bichromatic reverse nearest neighbors is to find k regions such that setting up a new service site within each region might collectively attract the maximal number of customers by proximity.In this paper,we propose both accurate and approximate algorithms to solve this generalized problem.The accurate algorithm utilizes a brute-force search method with pruning strategies.The approximate algorithm adopts a clustering-based approach,which restricts the combinational search space within representative regions of clusters,and has an accuracy bound.Extensive experiment results show that the approximate clustering-based algorithm is effective and efficient,and its actual output results are close to the accurate algorithm.