Publication Type

Conference Proceeding Article

Version

acceptedVersion

Publication Date

8-2005

Abstract

Assume that a franchise plans to open k branches in a city, so that the average distance from each residential block to the closest branch is minimized. This is an instance of the k-medoids problem, where residential blocks constitute the input dataset and the k branch locations correspond to the medoids. Since the problem is NP-hard, research has focused on approximate solutions. Despite an avalanche of methods for small and moderate size datasets, currently there exists no technique applicable to very large databases. In this paper, we provide efficient algorithms that utilize an existing data-partition index to achieve low CPU and I/O cost. In particular, we exploit the intrinsic grouping properties of the index in order to avoid reading the entire dataset. Furthermore, we apply our framework to solve medoid-aggregate queries, where k is not known in advance; instead, we are asked to compute a medoid set that leads to an average distance close to a user-specified parameter T. Compared to previous approaches, we achieve results of comparable or better quality at a small fraction of the CPU and I/O costs (seconds as opposed to hours, and tens of node accesses instead of thousands).

Discipline

Databases and Information Systems | Numerical Analysis and Scientific Computing

Publication

Advances in Spatial and Temporal Databases: 9th International Symposium, SSTD 2005, Angra dos Reis, Brazil, August 22-24, 2005: Proceedings

Volume

3633

First Page

55

Last Page

72

ISBN

9783540319047

Identifier

10.1007/11535331_4

Publisher

Springer Verlag

City or Country

Angra dos Reis, Brazil

Additional URL

http://dx.doi.org/10.1007/11535331_4

Download

Share

COinS