𝔖 Bobbio Scriptorium
✦   LIBER   ✦

[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


[ACM Press the 3rd ACM international wor
✍ Keays, Roger; Rakotonirainy, Andry πŸ“‚ Article πŸ“… 2003 πŸ› ACM Press 🌐 English βš– 149 KB

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.