Let a tuple of n objects obeying a query graph (QG) be called the n-tuple. The "Ddistance-value" of this n-tuple is the value of a linear function of distances of the n objects that make up this n-tuple, according to the edges of the QG. This paper addresses the problem of finding the Kn -tuples between n spatial datasets that have the smallest Ddistance- values, the so-called K-Multi-Way Distance Join Query (K-MWDJQ), where each set is indexed by an R-tree-based structure. This query can be viewed as an extension of K-Closest-Pairs Query (K-CPQ) (4) for n inputs. In addition, a recursive non-incremental branch-and-bound al- gorithm following a Depth-First search for processing synchronously all inputs without producing any intermediate result is proposed. Enhanced pruning techniques are also applied to the n R-trees nodes in order to reduce the total response time of the query, and a global LRU buffer is used to reduce the number of disk accesses. Finally, an experimental study of the proposed algorithm using real spatial datasets is presented.
['Antonio Corral', 'Yannis Manolopoulos', 'Yannis Theodoridis', 'Michael Vassilakopoulos']
Distance Join Queries of Multiple Inputs in Spatial Databases