HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE Journal/Magazine Articles >

Please use this identifier to cite or link to this item:
Title: Tree-based partition querying : a methodology for computing medoids in large spatial datasets
Authors: Papadias, Dimitris
Mouratidis, Kyriakos
Papadimitriou, Spiros
Keywords: Spatial databases
Query processing
Medoid queries
Issue Date: 2008
Citation: The VLDB journal : the international journal on very large data bases, July 2008, v.17, no. 4, p. 923-945
Abstract: 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: (i) the high and ever increasing availability of spatial data, and (ii) 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.
Rights: The original publication is available at
Appears in Collections:CSE Journal/Magazine Articles

Files in This Item:

File Description SizeFormat
VLDBJ07Medoids1.pdf293KbAdobe PDFView/Open

All items in this Repository are protected by copyright, with all rights reserved.