A Comparative Study of Spatial-Temporal Database Trends

A comparative study is presented on the most known k-nearest neighbor search methods used by spatial-temporal database systems in order to provide the advantages and limitations of each algorithm used in system simulations. The scope is limited to the development of the grid indexing searching technique in terms of three different algorithms, including the well-known CPM, SEA-CNN, and CkNN algorithm. These algorithms don’t make any assumptions about the movement of queries or objects. There are a number of functions proposed, which is used in: 1) partitioning the space around the query point in case of CPM and CkNN algorithms and 2) computing minimum and maximum distances between query and cell/level. All studied algorithms are compared together according to the required number of nearest neighbors, grid granularity, location update rate, speed, and population. An accuracy comparison is done between these algorithms to estimate the performance and determine the searching region error during query processing. Key words: continuous queries; grid index; kNN; NN accuracy; SR error. 1