Medoid Computation in Large Spatial Datasets
by Kyriakos MOURATIDIS
| Speaker: |  |
Date: Time: Venue: |
02 March 2007 (Friday)
|
Kyriakos MOURATIDIS |
We look forward to seeing you at this research seminar. |
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 the residential blocks constitute the input dataset and the k branch locations correspond to the medoids. The problem is NP hard, and all existing methods provide approximate solutions for relatively small datasets. In this talk, we present efficient algorithms for k-medoid computation over large spatial databases. 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. Further, we extend our methodology to the max version of 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 versions for all query types, as well as, maximum capacity and dynamic medoids. The paper describing our framework is accepted for publication in the Very Large Data Bases Journal ( VLDBJ ) and is available at: http://www.mysmu.edu/faculty/kyriakos/VLDBJ07-Medoids.pdf
Biography
Kyriakos Mouratidis is an Assistant Professor at the School of Information Systems, Singapore Management University. He received the BSc degree from the Aristotle University of Thessaloniki, Greece (AUTH), and the PhD degree from the Hong Kong University of Science and Technology (HKUST), both in Computer Science. His research interests include spatiotemporal databases, data stream processing, and mobile computing.