On efficient k-optimal-location-selection query processing in metric spaces

This paper studies the problem of k-optimal-location-selection (kOLS) retrieval   in metric spaces. Given a set DADA of customers, a set DBDB of locations, a constrained region R  , and a critical distance dcdc, a metric kOLS (MkOLS) query retrieves k   locations in DBDB that are outside R but have the maximal optimality scores  . Here, the optimality score of a location l∈DBl∈DB located outside R   is defined as the number of the customers in DADA that are inside R and meanwhile have their distances to l   bounded by dcdc according to a certain similarity metric (e.g., L1L1-norm, L2L2-norm, etc.). The existing kOLS methods are not sufficient because they are applicable only to the Euclidean space, and are not sensitive to k. In this paper, for the first time, we present an efficient algorithm for kOLS query processing in metric spaces. Our solution employs metric index structures (i.e., M-trees) on the datasets, enables several pruning rules, utilizes the advantages of reuse technique and optimality score estimation, to support a wide range of data types and similarity metrics. In addition, we extend our techniques to tackle two interesting and useful variants, namely, MkOLS queries with multiple or no constrained regions. Extensive experimental evaluation using both real and synthetic data sets demonstrates the effectiveness of the presented pruning rules and the performance of the proposed algorithms.