skip to main content
10.1145/1254850.1254861acmconferencesArticle/Chapter ViewAbstractPublication PagesmodConference Proceedingsconference-collections
Article

Continuous monitoring of skyline query over highly dynamic moving objects

Published: 10 June 2007 Publication History

Abstract

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 grid-based algorithm is efficient and significantly outperforms existing methods adopted for the application.

References

[1]
S. Borzsonyi, D. Kossmann, and K. Stocker, The skyline operator, ICDE, pp. 421--430, 2001.
[2]
K. Tan, P. Eng, and B. Ooi, Efficient progressive skyline computation. VLDB, pp. 301--310, 2001.
[3]
D. Kossmann, et al. Shooting stars in the sky: an online algorithm for skyline queries, VLDB, pp. 275--286, 2002.
[4]
D. Papadias, et al. Progressive skyline computation in database systems. TODS, 30(1), pp. 41--82, 2005.
[5]
W. Balke, et al. Efficient distributed skylining for web information systems. EDBT, pp. 256--273, 2004.
[6]
P. Wu et al. Parallelizing Skyline Queries for Scalable Distribution. EDBT, pp. 112--130, 2006.
[7]
K. Hose. Processing Skyline Queries in P2P Systems. VLDB 2005 PhD Workshop, pp. 36--40, 2005.
[8]
Y. Tao and D. Papadias. Maintaining sliding window skylines on data streams. TKDE, 18(3), pp. 377--391, 2006.
[9]
X. Lin, et al. Stabbing the sky: efficient skyline computation over sliding windows. ICDE, pp. 502--513, 2005.
[10]
Zhiyong Huang et al. Continuous Skyline Queries for Moving Objects. TKDE. 18(12), pp. 1645--1658, 2006.
[11]
X. Yu, et al. Monitoring k-nearest neighbor queries over moving objects. ICDE, pp 631--642, 2005.
[12]
K. Mouratidis, et. al. Conceptual partitioning: An efficient method for continuous nearest neighbor monitoring. SIGMOD, pp 634--645, 2005.
[13]
K. Mouratidis, et al, Continuous monitoring of top-k queries over sliding windows. SIGMOD, pp. 635--646, 2006.
[14]
J. Orenstein and T. Merrett, A class of data structures for associative searching. PODS, pp. 181--190, 1984.
[15]
D. Kalashnikov, et al, Main Memory Evaluation of Monitoring Queries Over Moving Objects. Distributed Parallel Databases, 15(2), pp. 117--135, 2004.

Cited By

View all
  • (2019)Distributed Continuous Range-Skyline Query Monitoring Over the Internet of Mobile ThingsIEEE Internet of Things Journal10.1109/JIOT.2019.29093936:4(6652-6667)Online publication date: Aug-2019
  • (2019)A Grid-Based Approach in Answering Top-k Dominating Queries on Groups2019 12th International Conference on Information & Communication Technology and System (ICTS)10.1109/ICTS.2019.8850985(343-348)Online publication date: Jul-2019
  • (2018)BJR-tree: fast skyline computation algorithm using dominance relation-based tree structureInternational Journal of Data Science and Analytics10.1007/s41060-018-0098-x7:1(17-34)Online publication date: 31-Jan-2018
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
MobiDE '07: Proceedings of the 6th ACM international workshop on Data engineering for wireless and mobile access
June 2007
86 pages
ISBN:9781595937650
DOI:10.1145/1254850
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

In-Cooperation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 June 2007

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. continuous query
  2. moving objects
  3. skyline

Qualifiers

  • Article

Conference

MobiDE07
Sponsor:

Acceptance Rates

Overall Acceptance Rate 23 of 59 submissions, 39%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)4
  • Downloads (Last 6 weeks)0
Reflects downloads up to 18 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2019)Distributed Continuous Range-Skyline Query Monitoring Over the Internet of Mobile ThingsIEEE Internet of Things Journal10.1109/JIOT.2019.29093936:4(6652-6667)Online publication date: Aug-2019
  • (2019)A Grid-Based Approach in Answering Top-k Dominating Queries on Groups2019 12th International Conference on Information & Communication Technology and System (ICTS)10.1109/ICTS.2019.8850985(343-348)Online publication date: Jul-2019
  • (2018)BJR-tree: fast skyline computation algorithm using dominance relation-based tree structureInternational Journal of Data Science and Analytics10.1007/s41060-018-0098-x7:1(17-34)Online publication date: 31-Jan-2018
  • (2017)An Efficient Indexing Method for Skyline Computations with Partially Ordered DomainsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2017.265690629:5(963-976)Online publication date: 1-May-2017
  • (2017)BJR-Tree: Fast Skyline Computation Algorithm for Serendipitous Searching Problems2017 IEEE International Conference on Data Science and Advanced Analytics (DSAA)10.1109/DSAA.2017.15(272-282)Online publication date: Oct-2017
  • (2017)An efficient approach to finding potential products continuouslyInformation Systems10.1016/j.is.2016.10.00365:C(22-35)Online publication date: 1-Apr-2017
  • (2016)Efficient Continuous Skyline Query Processing Scheme over Large Dynamic Data SetsETRI Journal10.4218/etrij.16.0116.001038:6(1197-1206)Online publication date: 1-Dec-2016
  • (2016)A cooperative method for processing range-skyline queries in mobile wireless sensor networksProceedings of the Sixth International Conference on Emerging Databases: Technologies, Applications, and Theory10.1145/3007818.3007820(1-8)Online publication date: 17-Oct-2016
  • (2015)Continuous Skyline Queries for Moving Objects in Road NetworksJournal of Software10.17706/jsw.10.2.190-20010:2(190-200)Online publication date: Feb-2015
  • (2014)Caching Support for Skyline Query Processing with Partially Ordered DomainsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2014.230912526:11(2649-2661)Online publication date: Nov-2014
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media