Font Size: a A A

Nearest Neighbor Query Processing On Moving Object Trajectory

Posted on:2008-01-30Degree:MasterType:Thesis
Country:ChinaCandidate:C LiFull Text:PDF
GTID:2178360212485022Subject:Computer Science
Abstract/Summary:PDF Full Text Request
With the integration of wireless communications and positioning technologies, the concept of Moving Object Databases (MOD) has become increasingly important, and has posed a great challenge to the database community. Emerging location-dependent services call for new query processing algorithms and techniques to deal with both the spatial and temporal domains. Examples of these new services include traffic monitoring, nearby information accessing and migration patterns analyzing of wild animals. An important class of queries that is definitely useful for MOD processing is the so-called k nearest neighbor (k-NN) queries, where one is interested in finding the A closest trajectories to a predefined query object Q. To our knowledge, in the literature such queries primarily deal with either static or continuously moving query points over stationary datasets, or queries about the future or current positions of a set of continuously moving points. Apparently, these types of queries do not cover NN search on historical trajectories.Motivated by this problem, in this paper, We develop two algorithms based on Best-First traversal paradigm, called BFPkNN and BFTkNN, which handle the ANN retrieval with respect to the static query point and the moving query trajectory, respectively. In addition, we also enable several effective pruning heuristics to prune away all unnecessary nodes such that the memory space consumption and the CPU time can be decreased. The pruning heuristics avoids accessing nodes that cannot contain qualifying entries and discard any unnecessary entries. We also present two algorithms, called HCp-kNN and HCr-kNN, which deal with the problem of efficiently processing historical continuous k-Nearest Neighbor. An effective update strategy to maintain the nearest lists is proposed for continuous ANN search. Furthermore, We introduce and solve the constrained k-nearest neighbor (CANN) query on R-tree-like structures storing historical information about moving object trajectories. We present several algorithms to handle the CANN query problem efficiently. In particular, our techniques process CANN queries by either combining conditions of range and ANNqueries, or by modifying the existing kNN query algorithms. Inadditionally, we present a algorithm to get the partial entry of trajectory segment that are contained in constrained region CR fully and its lifetime is within a specified time extent and a algorithm to get the portion of node N whose temporal extent is within a given time period as well as spatial area is contained in CR.
Keywords/Search Tags:Moving Object Trajectory, TB Tree, k nearest neighbour query, constraint ANN query
PDF Full Text Request
Related items