Optimal-location-selection query processing in spatial databases

This paper introduces and solves a novel type of spatial queries, namely, Optimal-Location-Selection (OLS) search, which has many applications in real life. Given a data object set D-A, a target object set D-B, a spatial region R, and a critical distance d-c in a multidimensional space, an OLS query retrieves those target objects in D-B that are outside R but have maximal optimality. Here, the optimality of a target object b \in D-B located outside R is defined as the number of the data objects from D-A that are inside R and meanwhile have their distances to b not exceeding d-c. When there is a tie, the accumulated distance from the data objects to b serves as the tie breaker, and the one with smaller distance has the better optimality. In this paper, we present the optimality metric, formalize the OLS query, and propose several algorithms for processing OLS queries efficiently. A comprehensive experimental evaluation has been conducted using both real and synthetic data sets to demonstrate the efficiency and effectiveness of the proposed algorithms. © 2006 IEEE.