Processing constrainedK closest pairs query in spatial databases
Liu Xiaofeng, Liu Yungsheng, Xiao Yingyuan · Wuhan University Journal of Natural Sciences · 2006
In this paper, constrained K clost pairs query is introduced, which retrieves the K closest pairs satisfying the given spatial constraint from two datasets. For data sets indexed by R-trees in spatial databases, three algorithms are presented for answering this kind of query. Among of them, two-phase Range + Join and Join + Range algorithms adopt the strategy that changes the execution order, of range and closest pairs queries, and constrained heap-based algorithm utilizes extended distance functions to prune search space and minimize the pruning distance. Experimental results show that constrained heap-based algorithms has better applicability and performance than two-phase algorithms.