[ACM Press the 6th ACM international workshop - Beijing, China (2007.06.10-2007.06.10)] Proceedings of the 6th ACM international workshop on Data engineering for wireless and mobile access - MobiDE '07 - Continuous monitoring of skyline query over highly dynamic moving objects
β Scribed by Tian, Li; Wang, Le; Zou, Peng; Jia, Yan; Li, Aiping
- Book ID
- 121361382
- Publisher
- ACM Press
- Year
- 2007
- Weight
- 400 KB
- Category
- Article
- ISBN
- 159593765X
No coin nor oath required. For personal study only.
β¦ Synopsis
We address the problem of continuous skyline computation on highly dynamic moving objects (i.e. objects with dynamic dimensions move in an unrestricted and unpredictable fashion), which is quite a different scenario from existing literatures on skyline algorithms. We propose a continuous skyline query processing strategy for static query point, and the main idea is as follows: (1) The work space is divided into lots of regular grids, and the valid objects are indexed by this data structure. (2) Some grids are organized as the influence region, while the rest compose of the free region. The algorithm achieves low running time by handling movements only from objects that fall in the influence region, while data changes in the free region are omitted with correctness guarantee. (3) The initialization module adopts an efficient method to obtain the initial result without having to process all the data points; after that the maintenance module updates the change of skyline and influence region dynamically when data changes. We analyze the space and time costs of the proposed method and conduct an extensive experiment, which indicates that our gridbased algorithm is efficient and significantly outperforms existing methods adopted for the application.
π SIMILAR VOLUMES
Edited By Sujata Banerjee, Mitch Cherniack, And Alexandros Labrinidis ; Sponsored By Acm Sigmobile In Cooperation With Acm Sigmod ; With Industrial Supporters, Abc Virtual ... [et Al.] ; And The General Support Of The National Science Foundation. ... Held In Conjunction With Mobicom 2003--abstract.