Study On Moving K Neareast Neighbor Query Processing Techniques In Constrained Space

Along with the development of moving position locating and spatial indexing technology, location based service(LBS) is gaining more and more attentions in increasing areas, such as outdoor sports, touring, logistics industry and even computer games. The rapid development of LBS will surely cause great revolution on people’s life and industry. How to response on user’s query about he/she’s neighbor information is one of the fundamental service of the LBS area. And this problem received wide attention from academic circles and industrial circles. People can gain he/she’s own position by devices of GPS, mobile network positioning or RFID tags. The user concerned objects are stored in databases previously. Aiming at different query types, the data in databases can be indexed previously to improve the query processing efficiency. However, the various types of constrained spaces and the various types of queries make this problem difficulty. How to model, pre-process and real-time process these queries remain a problem that urgently needs to be resolved. As a fundamental query type of LBS, moving k nearest neighbor query needs especially attention to be studied.This dissertation concludes the characteristics and properties of different types of constrained spaces, and analyze and summarize the related work on moving k nearest neighbor query. We propose corresponding solutions aiming at different types of constrained spaces and construct a characteristic processing framework. These techniques can efficiently inprove the accuracy and performance of moving k nearest neighbor queries, and thus supporting moving k nearest neighbor queries in constrained spaces.Specifically, this dissertation deeply studies moving k nearest neighbor queries in different types of spaces, such as obstructed space, uncertain space and weighted space. At the mean time, we also extend our study to moving path nearest neighbor query. The main content of this dissertation includes:(1) k nearest neighbor query in obstructed space. We analyze the characters of moving k nearest neighbor query, and propose a method which can calculate the safe region of the moving query point efficiently. Then the method is extended to the obstructed space. Based on the study of obstructed space, we propose several useful properties of this kind of space and gives proper proofs. Different from previous processing methods that can only handle queries in ideal Euclidean space, our method can handlle queries in obstructed space efficiently.(2) k nearest neighbor query in uncertain space. We study the k neareast neighbor query in obstacle existing uncertain space. The theoretical data model of obstacles and uncertain objects is established. We further propose the k nearest neighbor query on uncertain objects. A pruning method is produced to enhance the processing performance. Based on this method, an efficient uncertain space distance based algorithm is proposed to process moving k queries. Besides that, we also design a novel method to handle safe region creation problem.(3) k nearest neighbor query in weighted space. We study the unique properties of MkNN problem in weighted space. Based on the concept of combination regions, we design an efficient data indexing structed, namely weighted indexing map(WIM), which can eliminate most unnecessary MkNN processing time. We also propose a WIM based algorithm, which is called wNeighbors. The experiments show that this algorithm can handle moving k nearest neighbor query in wieghted regions efficently.(4) k path nearest neighbor query. We abstract the distance functions in different constrained spaces based on their different characters. We also study an efficient prunning method based on the distance function. On the basis of object nearest path distance, we propose the petal edge and sweeping circle concepts and design a method to create safe regions by these concepts.In conclusion, this dissertation aims at the specific features and challenges of k nearest neighbor queries and studies the key technologies of moving k nearest neighbor queries, covering the techniques of data pre-processing, real time calculation and safe region creation. And thus, efficient and robust moving k nearest neighbor query processing method can be offered for different constrained spaces and real time moving queries. The study of this dissertation provide powerful support for LBS services, and improve user’s ability to get knowledge of his vicinity.