Journal of Information Science and Engineering, Vol. 37 No. 4, pp. 975-990

Efficient Evaluation of Minimum Total Cost Queries on Heterogeneous Neighboring Objects

In recent years, many of the *location-based services* provide information of a single type of spatial objects, based on their spatial closeness to the query object. However, in real-life applications, user may be interested in obtaining information about different types of objects (*e.g.*, hotels, restaurants, and theaters), in terms of their neighboring relationship. Moreover, an important aspect that has not been previously explored is the total cost of experiencing various types of spatial objects. As a result, we present a new type of location-based queries, named the *minimum total cost query* (*MTCQ*), which takes both the neighboring relationship and the total experiencing cost of spatial objects into account. Given the *n* types of spatial objects and a user-defined distance *d*, the *MTCQ* finds a set of *n* objects such that the distance between any pair of objects does not exceed d and their total cost is smallest. To efficiently process the *MTCQ*, we utilize an R-tree-based index, the *R ^{c}*-tree, to manage the spatial objects with their locations and costs. Then, two processing algorithms, namely the

Keywords:
location-based services, minimum total cost query, Rc-tree, top-k-based MTCQ algorithm, enhanced MTCQ algorithm