Please use this identifier to cite or link to this item:

Tree-based partition querying: a methodology for computing medoids in large spatial datasets

Authors Mouratidis, Kyriakos
Papadias, Dimitris
Papadimitriou, Spiros
Issue Date 2008
Source VLDB JOURNAL , v. 17, (4), 2008, JUL, p. 923-945
Summary Besides traditional domains (e.g., resource allocation, data mining applications), algorithms for medoid computation and related problems will play an important role in numerous emerging fields, such as location based services and sensor networks. Since the k-medoid problem is NP-hard, all existing work deals with approximate solutions on relatively small datasets. This paper aims at efficient methods for very large spatial databases, motivated by: (1) the high and ever increasing availability of spatial data, and (2) the need for novel query types and improved services. The proposed solutions exploit the intrinsic grouping properties of a data partition index in order to read only a small part of the dataset. 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). In addition, we study medoid-aggregate queries, where k is not known in advance, but we are asked to compute a medoid set that leads to an average distance close to a user-specified value. Similarly, medoid-optimization queries aim at minimizing both the number of medoids k and the average distance. We also consider the max version for the aforementioned problems, where the goal is to minimize the maximum (instead of the average) distance between any object and its closest medoid. Finally, we investigate bichromatic and weighted medoid versions for all query types, as well as, maximum capacity and dynamic medoids.
ISSN 1066-8888
Rights The original publication is available at
Language English
Format Article
Access View full-text via DOI
View full-text via Web of Science
View full-text via Scopus
Files in this item:
File Description Size Format
VLDBJ07Medoids1.pdf 300822 B Adobe PDF