The Research Of Large-scale Spatial Nearest Neighbor Query In Cloud Environments

With the increasing availability of mobile internet and internet of things, the amount of spatial data is growing larger and larger. It poses new requirements and challenges for index and query processing on large scale spatial data. Nearest Neighbor queries are of particular interest in a wide range of applications such as data mining, decision support systems and profile based marketing etc. A major downside of the existing index and NN is its inherent sequential nature and using in-memory algorithm, which limits its applicability to large scale spatial datasets. In this paper we investigate how to perform scalable spatial index and queries in distributed environment.Firstly, we present a novel distributed spatial data index:Inverted Grid Index, which is a combination of distributed inverted index and spatial grid partition. The loose coupling and shared nothing architecture of Inverted Grid Index scales well.Secondly, we illustrate the implementations of novel parallel circletrip and distributed kNN algorithm which are based on our index structure under cloud computing environment. We present the proof of convergence for the kNN algorithms and efficiency and scalability in comparison to the state-of-the-art algorithms in distributed computing environments.Finally, we investigate the Basic-SRNN initialization query method based on the inverted grid index and two optimization methods Lazy-SRNN and Eager-SRNN are proposed to effectively process scalable Multi-dimensional RNN queries. Among them, Lazy-SRNN prunes the search space when all data points are discovered in one pass; Eager-SRNN attempts to prune spatial objects incrementally as soon as they are visited. We present the proof of accuracy and completeness. Extensive experiments using both real and synthetic datasets demonstrated that our proposed SRNN query methods outperform the state-of-the-art algorithms under different experimental setting.