Multi-Way Distance Join Queries in Spatial Databases

Corral, Antonio; Manolopoulos, Yannis; Theodoridis, Yannis; Vassilakopoulos, Michael
December 2004
GeoInformatica;Dec2004, Vol. 8 Issue 4, p373
Academic Journal
Let a tuple of n objects obeying a query graph (QG) be called the n-tuple. The “D_distance-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 K n-tuples between n spatial datasets that have the smallest D_distance-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) [8] for n inputs. In addition, a recursive non-incremental branch-and-bound algorithm following a depth-first search for processing synchronously all inputs without producing any intermediate result is proposed. Enhanced pruning techniques are also applied to n R-trees nodes in order to reduce the total response time and the number of distance computations of the query. Due to the exponential nature of the problem, we also propose a time-based approximate version of the recursive algorithm that combines approximation techniques to adjust the quality of the result and the global processing time. Finally, we give a detailed experimental study of the proposed algorithms using real spatial datasets, highlighting their performance and the quality of the approximate results.


Related Articles

  • A Dual-Bounded Algorithm for the p-Median Problem. Galvão, Roberto O. // Operations Research;Sep/Oct80, Vol. 28 Issue 5, p1112 

    The p-median problem consists of locating p facilities on a network, so that the sum of shortest distances from each of the nodes of the network to its nearest facility is minimized. A dual bound, based on the dual of the LP relaxation of the integer programming formulation of the problem, is...

  • Choosing the Job Sequence and Processing Times to Minimize Total Processing Plus Flow Cost on a Single Machine. Vickson, R. G. // Operations Research;Sep/Oct80, Vol. 28 Issue 5, p1155 

    This paper treats the problem of minimizing the total weighted flow cost plus job-processing cost in a single machine sequencing problem for jobs having processing costs which are linear functions of processing times. The optimal job sequence and processing times are obtainable from the solution...

  • MINIMIZING THE SUM OF THE JOB COMPLETION TIMES IN THE TWO-MACHINE FLOW SHOP BY LAGRANGIAN RELAXATION. van de Velde, S. L. // Annals of Operations Research;1990, Vol. 26 Issue 1-4, p257 

    A branch-and-bound algorithm is presented for the two-machine flow shop problem with the objective of minimizing the sum of the job completion times. Lower bounds and precedence constraints result from a Lagrangian relaxation of this problem. The Lagrangian subproblem turns out to be a linear...

  • Obtaining the efficient set of nonlinear biobjective optimization problems via interval branch-and-bound methods. Fernández, José; Tóth, Boglárka // Computational Optimization & Applications;Apr2009, Vol. 42 Issue 3, p393 

    Obtaining a complete description of the efficient set of multiobjective optimization problems can be of invaluable help to the decision-maker when the objectives conflict and a solution has to be chosen. In this paper we present an interval branch-and-bound algorithm which aims at obtaining a...

  • Augmented Reality Internet Labs versus its Traditional and Virtual Equivalence. Odeh, Salaheddin; Abu Shanab, Shatha; Anabtawi, Mahasen // International Journal of Emerging Technologies in Learning;2015, Vol. 10 Issue 3, p4 

    Engineering is an applied science; it makes science come alive through experiments and labs. Students can only gain practical knowledge that goes beyond mere scientific theory in the educational labs. This can be done using three different types of educational labs: Augmented reality labs,...

  • BRANCH-AND-BOUND AS A HIGHER-ORDER FUNCTION. Mckeown, G. P.; Rayward-Smith, V. J.; Turpin, H. J. // Annals of Operations Research;1991, Vol. 33 Issue 1-4, p379 

    The branch-and-bound paradigm is presented as a higher-order function and illustrated by instantiations, providing two well-known branch-and-bound algorithms for the Steiner tree problem in graphs and one for the travelling salesman problem. We discuss the advantages of such a specification and...

  • Merging and Sorting Applied to the Zero-One Knapsack Problem. Ahrens, J. H.; Finke, G. // Operations Research;Nov/Dec75, Vol. 23 Issue 6, p1099 

    Branch-and-bound algorithms are adequate for the solution of a wide range of 0-1 knapsack problems. It is shown that the simplest method of branching is as good as any. However, problems with highly correlated large weights and values quickly become unsolvable in a reasonable time. This paper...

  • Setup and Open-Stacks Minimization in One-Dimensional Stock Cutting. Belov, Gleb; Scheithauer, Guntram // INFORMS Journal on Computing;Winter2007, Vol. 19 Issue 1, p27 

    The primary objective in cutting and packing problems is trim loss or material input minimization (in stock cutting) or value maximization (in knapsack-type problems). However, in real-life production we usually have many other objectives (costs) and constraints. Probably the most complex...

  • Classical Cuts for Mixed-Integer Programming and Branch-and-Cut. Padberg, Manfred // Annals of Operations Research;Oct2005, Vol. 139 Issue 1-4, p321 

    We review classical valid linear inequalities for mixed-integer programming, i.e., Gomory’s fractional and mixed-integer cuts, and discuss their use in branch-and-cut. In particular, a generalization of the recent mixed-integer rounding (MIR) inequality and a sufficient condition for the...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics