Optimal Point Selection In Spatial Database

With the rapid developments of computer?Internet?mobile communication and positioning technologies,large volume of location data and high dimensional spatial data(picture?text)have been produced from terminal devices and social network platforms.The data is big volume?high-dimensional?heterogeneous.Hence,we need a more efficient,effective and generic spatial data processing model to mine the latent information from these data,so that we can help the corpora-tion to make wise decisions.It has become a major challenge to efficiently and intelligently build indexes and perform query processing,aiming to obtain valuable information,discover the evolu-tion law.Optimal point selection has been extensively studied in spatial database literature these years.On one hand,the development of mobile devices,GPS and social media has accelerated the development of optimal point selection query.As a result when indexing and processing these data sets,the query situations and the structure of data sets need to be considered.However,there are few works focus on processing these complicated situations.On the other hand,for different query situations,different optimization and prune strategies are needed.The existing works mainly focus on one special objective,which makes them lack of scalability and efficiency.Especially,when dealing with high-dimensional or road network date sets,the existing algorithms' efficiency and accuracy both degrade dramatically.Motivated by these reasons,this thesis systematically explores optimal point selection tech-nologies in spatial data bases.They are mainly as follows:1.Single optimal point query in Euclidean space based on Maximize Bichromatic Reverse Nearest Neighbor search:In order to improve the efficiency and accuracy of the existing methods and based on the classic methods in computational geometry,this thesis proposes a Maximize Bichromatic Reverse Nearest Neighbor query based method to select the optimal location.The method includes:sweep line,space partition and upper bound estimation and "arc intersection" method to calculate the influence value of the location point.The proposed algorithms are much more efficient and effective.2.Single optimal point query in three-dimensional spaces based on Maximize Bichromatic Re-verse Nearest Neighbor search:The thesis first extends the Maximize Bichromatic Reverse Nearest Neighbor query to high dimensional space.Based on the spatial properties of the problem,the thesis proposes a "fine grained" high dimension dividing method,and it is easy to be extended to higher dimensions if choosing a proper index structure.This work is important for the research of optimal point query in high-dimensional space.3.Capacity constraint optimal point selection in Euclidean space:This thesis first solves the capacity constraint MaxBRNN query.After studying the related problems(FLP problems)in Operation Research and analyzing their drawbacks,this thesis proposes three efficient algorithms to assign data points and search for a optimal service point location:the baseline algorithm,a progressive search algorithm and a pruning algorithm.The experiments result shows that the proposed algorithms are efficient and can find out the optimal point and the corresponding assignment strategies.4.Group optimal point selection in Euclidean and road network spaces based on clustering method:The thesis also studies the group optimal points selection problem.The proposed clustering based algorithms are more efficient with higher accuracy compared to the existing group optimal points selection algorithms.And the thesis also extends this query to the road networks.This thesis studies the OLS query in different query spaces.It first studies the OLS query in two and three dimensional spaces,and then extends it to the capacity constraint space.At last,the group OLS query is studied,and the thesis also extends it to road networks.The future work includes,the OLS query in high dimensional and metric space,and how to use distributed framework to solve our queries more efficiently.