Closest Pair Queries with Spatial Constraints

Given two datasets

$\mathcal{D}_{A}$

and

$\mathcal{D}_{B}$

the closest-pair query (CPQ) retrieves the pair (

a

,

b

), where

$a \epsilon \mathcal{D}_{A}$

and

$b \epsilon \mathcal{D}_{B}$

, having the smallest distance between all pairs of objects. An extension to this problem is to generate the

k

closest pairs of objects (

k

-CPQ). In several cases spatial constraints are applied, and object pairs that are retrieved must also satisfy these constraints. Although the application of spatial constraints seems natural towards a more focused search, only recently they have been studied for the CPQ problem with the restriction that

$\mathcal{D}_{A}$

=

$\mathcal{D}_{B}$

. In this work we focus on constrained closest-pair queries (CCPQ), between two distinct datasets

$\mathcal{D}_{A}$

and

$\mathcal{D}_{B}$

, where objects from

$\mathcal{D}_{A}$

must be enclosed by a spatial region

R

. A new algorithm is proposed, which is compared with a modified closest-pair algorithm. The experimental results demonstrate that the proposed approach is superior with respect to CPU and I/O costs.