A concurrency control algorithm for nearest neighbor query
To find the nearest neighbor (NN) objects of a given point is an important query in spatial database systems. The algorithm, designed by Roussopoulos, Kelley and Vincent (Roussopoulos et al., Nearest neighbor queries, in: Proc. ACM SIGMOD Int. Conf. on Management of Data, 1995, pp. 71-79) and called as RKV, can only solve such a query for a single-user environment. However, the performance of RKV is low in a multi-user environment due to its depth-first search. Based on breadth-first search, an NN algorithm (called CC) with concurrency control feature is proposed for a multi-user environment. To compare the strengths and weaknesses of RKV and CC, several experiments were conducted on the efficiency of these two algorithms. The stimulation results indicate that the performance of CC is around two to sevenfold better than that of RKV under various conditions of data contention. (C) 1999 Elsevier Science Inc. All rights reserved.
concurrency control nearest neighbor query performance r-trees simulation