Publication Type

Journal Article

Version

acceptedVersion

Publication Date

3-2015

Abstract

This paper studies the problem of k-optimal-location-selection (kOLS) retrieval in metric spaces. Given a set DA of customers, a set DB of locations, a constrained region R , and a critical distance dc, a metric kOLS (MkOLS) query retrieves k locations in DB that are outside R but have the maximal optimality scores. Here, the optimality score of a location l∈DB located outside R is defined as the number of the customers in DA that are inside R and meanwhile have their distances to l bounded by dc according to a certain similarity metric (e.g., L1-norm, L2-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.

Keywords

Optimal location selection, k-optimal-location-selection query, Metric spaces, Query processing, Spatial database

Discipline

Databases and Information Systems | Numerical Analysis and Scientific Computing

Research Areas

Data Science and Engineering

Publication

Information Sciences

Volume

298

First Page

98

Last Page

117

ISSN

0020-0255

Identifier

10.1016/j.ins.2014.11.038

Publisher

Elsevier

Copyright Owner and License

Authors

Additional URL

https://doi.org/10.1016/j.ins.2014.11.038

Download

Share

COinS