The Algorithm Research On Continuous K Nearest Neighbor Query Considered Moving State In Road Networks

In database research field, Continuous K nearest neighbor query processingtechnology over moving object has been paid attention, there are many applications for itin our real life, such as the systems of traffic schedule control, digital battlefield, andpersonal location service, should manage related location or trajectory information ofmobile users, but spatial data management for continuous K nearest neighbor queryservices and access to the spatial objects in these applications are constrained in spatialnetwork, such as in the road network. Some problems in some existing methods are notresolved, then continuous K-nearest neighbor processing techniques need to be studied.The query processing techniques for traditional database can not or can not effectively beused, and need to study the novel continuous K nearest neighbor query processingtechniques. Therefore, continuous K nearest neighbor query processing over movingobject in road network is also an urgent requirement for practical application, and it hascertain value of research and practical application to study how to provide variousefficient query processing technologies over moving object in road networks.In this paper, we started to study the key technology of moving object database on thebase of latest research in existing indexing and query processing technologies, such asmotion trajectory model of moving object, indexing technology of moving object,continuous K nearest neighbor query processing techniques and the query processingtechniques for uncertainty, and improved efficiently their drawbacks, subsequently, step bystep proposed location-based continuous K nearest neighbor query processing technologyand indexing method of uncertain objects in road networks to solve the key technology inpractical location-based services query application system. The main work andinnovations include the following:As the data objects move frequently and arbitrarily in road networks, the frequentupdates of object locations make it complicated to process CKNN accurately andefficiently. In this paper, according to the relative moving situation between the movingobjects and the query point, a Moving State of Object (MSO) model is presented toindicate the relative moving state of the object to the query point. With the help of this model, we propose a novel Object Candidate Processing (OCP) algorithm to highly reducethe repetitive query cost with pruning phase and refining phase. Comprehensiveexperiments are conducted and the results verify the effectiveness of the proposedmethods.In some applications (e.g. finding my nearest taxies while I am moving within thenext5minutes), it is not necessary to obtain the accurate result set. For these applications,we introduce a novel technique, which is moving state based approximate CKNN(MACKNN), to approximate the CKNN query results with certain accuracy to make thequery process more efficient by using Moving State of Uncertain Object (MSUO) Model,and guarantee certain accuracy. We evaluate the MACKNN technique with simulationsand compare it with a traditional approach. Experimental results are presented todemonstrate the utility of our new approach.In order to sovle query processing of moving object with uncertain velocity in thepractical application, we studied the problem of processing CKNN query over movingobjects with uncertain velocity in road networks within a given time interval. Weproposed a Distance Interval Model (DIM) to calculate the distance interval for a movingobject with uncertain velocity and direction at a time instant, which involves the minimaland maximal distances between a moving object and the query point. Meanwhile, in orderto efficiently update the informations of moving objects, an index structure TPRuv-Tree isproposed.With the help of calculation methods of DIM and TPRuv-Tree, we developed thePVKNN algorithm to efficiently process a CKNN query. The pruning phase of PVKNNalgorithm is used to prune the objects which are impossible to be the query result withinthe given time interval. Then, the distilling phase is designed to determine the divisiontime subintervals of the given time interval where the qualified object candidates aredistilled, meanwhile the minimal and maximal distances between the moving objects andthe query point can be represented as a linear function of time. Finally, thepossibility-ranking phase is presented to determine the KNN query results with possibilityfor each division time subinterval.