Query Optimization Algorithm Of Mobile Object Oriented Real-time Tracking Study

In recent years, wireless communication network has been highly developed aswell as the intelligent mobile terminals. Therefore, the Location Based Services hasbecome an important function of these mobile devices. Searching nearest neighbors bythese mobile devices is regarded as one of the most popular applications in LocationBased Services; studies on it are valuable for scientific research and practice.Due to the popularization of Location Based Services, spatial data is becomingmore and more massive and complicated, traditional nearest neighbor query algorithmcannot appropriate to this condition. Therefore, more and more researchers pay theirattentions to the technology of spatial nearest neighbor query.There are already some method to solve the problem of nearest neighbor query indynamic environment, such as YPK CNNalgorithm， SEA CNNalgorithm andCPM algorithm, CPM algorithm is regarded as the best one among these algorithms.However, too much computation of Euclidean distance is the bottleneck of the CPMalgorithm to perform efficiently. In addition, most moving objects are moving in anunpredictable manner, traditional method cannot perform well in this condition, andthere is few achievement about this issue. For this reason, we also propose an approachto search the nearest neighbor of the unpredictable objects.We introduce the Conceptual Partitioning Module, and analyze the achievementsabout nearest neighbor query, and then adapt the tree structure to index the cells of grid.Instead of power and evolution operations, we use ordinary mathematical operations tobreak the bottleneck of CPM algorithm. Besides, sliding window is also put to use toimprove the algorithm. Finally, we put forward the definition of mathematical exceptionof distance to solve the problem of nearest neighbor query about unpredictable movingobjects.The main achievements of this paper can be summarized as follows:(1) Taking the advantage of sliding windows to optimize continuous nearestneighbor query. (2) Replacing the power and evolution operations with ordinary mathematicaloperations to reduce the amount of calculation of Euclidean distance.(3) Adopting tree structure to index cells so that it can eliminate the cells whichwill not affect the result as early as possible, and consequently drop the cost.(4) Extending the algorithm to the case of nearest neighbor query aboutunpredictable moving objects.(5) Designing and implementing a prototype system for the experimental in thispaper, and then expatiate the three modules of the system: moving objectgenerator, location based server and display terminal. The system is valuablefor experimental and practice.