Monitoring Median Queries over Moving Objects |
| |
Authors: | XU Hu LU Yan-sheng LI Zhi-cheng |
| |
Institution: | School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074, China |
| |
Abstract: | The k-median problem has attracted a number of researchers. However, few of them have considered both the dynamic environment and the issue of accuracy. In this paper, a new type of query is studied, called continuous median monitoring (CMM) query. It considers the k-median problem under dynamic environment with an accuracy guarantee. A continuous group nearest neighbor based (CGB) algorithm and an average distance medoid (ADM) algorithm are proposed to solve the CMM problem. ADM is a hill climbing schemed algorithm and achieves a rapid converging speed by checking only qualified candidates. Experiments show that ADM is more efficient than CGB and outperforms the classical PAM (partitioning around medoids) and CLARANS (clustering large applications based on randomized search) algorithms with various parameter settings. |
| |
Keywords: | Spatial databases Query processing Nearest neighbor query k-Median problem |
本文献已被 维普 万方数据 等数据库收录! |
|