QUIET ZONE: Reducing The Communication Cost of Continuous Spatial Queries
Article No.: 1, Pages 1 - 8
Abstract
The client server model has been extensively used to continuously monitor the results of spatial queries. In this paper, we introduce quiet zone that is aimed to reduce the communication cost in the client server model implemented for continuous spatial queries. A quiet zone is a region such that as long as an object remains inside it, the object does not need to report its location. We present a generic framework to reduce the communication cost of many different variety of continuous spatial queries, such as range query, reverse nearest neighbour query, window query and relaxed reverse nearest neighbour query. We show that the checking cost at objects is reasonably low so that our approach is feasible for devices with limited resources. Our experimental study shows that the proposed algorithm significantly reduces the communication cost.
References
[1]
Rimantas Benetis, Christian S. Jensen, Gytis Karciauskas, and Simonas Saltenis. 2006. Nearest and reverse nearest neighbor queries for moving objects. VLDB J. 15, 3 (2006), 229--249.
[2]
Thomas Brinkhoff. 2002. A Framework for Generating Network-Based Moving Objects. GeoInformatica (2002).
[3]
Ying Cai, Kien A. Hua, and Guohong Cao. 2004. Processing Range-Monitoring Queries on Heterogeneous Mobile Objects. In 5th IEEE International Conference on Mobile Data Management (MDM2004), 19-22 January 2004, Berkeley, CA, USA. 27--38.
[4]
Muhammad Aamir Cheema, Ljiljana Brankovic, Xuemin Lin, Wenjie Zhang, and Wei Wang. 2011. Continuous Monitoring of Distance-Based Range Queries. IEEE Trans. Knowl. Data Eng. 23, 8 (2011), 1182--1199.
[5]
Muhammad Aamir Cheema, Xuemin Lin, Wenjie Zhang, and Ying Zhang. 2011. Influence zone: Efficiently processing reverse k nearest neighbors queries. In Proceedings of the 27th International Conference on Data Engineering, ICDE 2011, April 11-16, 2011, Hannover, Germany. 577--588.
[6]
Muhammad Aamir Cheema, Xuemin Lin, Ying Zhang, Wei Wang, and Wenjie Zhang. 2009. Lazy Updates: An Efficient Technique to Continuously Monitoring Reverse kNN. PVLDB 2, 1 (2009), 1138--1149. http://www.vldb.org/pvldb/2/vldb09-720.pdf
[7]
Muhammad Aamir Cheema, Yidong Yuan, and Xuemin Lin. 2007. CircularTrip: An Effective Algorithm for Continuous k NNQueries. In Advances in Databases: Concepts, Systems and Applications, 12th International Conference on Database Systems for Advanced Applications, DASFAA 2007, Bangkok, Thailand, April 9-12, 2007, Proceedings. 863--869.
[8]
Muhammad Aamir Cheema, Wenjie Zhang, Xuemin Lin, Ying Zhang, and Xuefei Li. 2012. Continuous reverse k nearest neighbors queries in Euclidean space and in spatial networks. VLDB J. 21, 1 (2012), 69--95.
[9]
Tobias Emrich, Hans-Peter Kriegel, Peer Kröger, Matthias Renz, Naixin Xu, and Andreas Züfle. 2010. Reverse k-Nearest Neighbor monitoring on mobile objects. In 18th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems, ACM-GIS 2010, November 3-5, 2010, San Jose, CA, USA, Proceedings. 494--497.
[10]
Bugra Gedik and Ling Liu. 2004. MobiEyes: Distributed Processing of Continuously Moving Queries on Moving Objects in a Mobile System. In Advances in Database Technology - EDBT 2004, 9th International Conference on Extending Database Technology, Heraklion, Crete, Greece, March 14-18, 2004, Proceedings. 67--87.
[11]
Arif Hidayat, Muhammad Aamir Cheema, and David Taniar. 2015. Relaxed Reverse Nearest Neighbors Queries. In Advances in Spatial and Temporal Databases - 14th International Symposium, SSTD 2015, Hong Kong, China, August 26-28, 2015. Proceedings. 61--79.
[12]
Haibo Hu, Jianliang Xu, and Dik Lun Lee. 2005. A Generic Framework for Monitoring Continuous Spatial Queries over Moving Objects. In Proceedings of the ACM SIGMOD International Conference on Management of Data, Baltimore, Maryland, USA, June 14-16, 2005. 479--490.
[13]
Glenn Simmons Iwerks, Hanan Samet, and Kenneth P. Smith. 2003. Continuous K-Nearest Neighbor Queries for Continuously Moving Points with Updates. In VLDB 2003, Proceedings of 29th International Conference on Very Large Data Bases, September 9-12, 2003, Berlin, Germany. 512--523. http://www.vldb.org/conf/2003/papers/S16P02.pdf
[14]
James M. Kang, Mohamed F. Mokbel, Shashi Shekhar, Tian Xia, and Donghui Zhang. 2007. Continuous Evaluation of Monochromatic and Bichromatic Reverse Nearest Neighbors. In Proceedings of the 23rd International Conference on Data Engineering, ICDE 2007, The Marmara Hotel, Istanbul, Turkey, April 15-20, 2007. 806--815.
[15]
Iosif Lazaridis, Kriengkrai Porkaew, and Sharad Mehrotra. 2002. Dynamic Queries over Mobile Objects. In Advances in Database Technology - EDBT 2002, 8th International Conference on Extending Database Technology, Prague, Czech Republic, March 25-27, Proceedings. 269--286.
[16]
Nimrod Megiddo. 1983. Linear-Time Algorithms for Linear Programming in R3 and Related Problems. SIAM J. Comput. 12, 4 (1983), 759--776.
[17]
Mohamed F. Mokbel, Xiaopeng Xiong, and Walid G. Aref. 2004. SINA: Scalable Incremental Processing of Continuous Queries in Spatio-temporal Databases. In Proceedings of the ACM SIGMOD International Conference on Management of Data, Paris, France, June 13-18, 2004. 623--634.
[18]
Kyriakos Mouratidis, Marios Hadjieleftheriou, and Dimitris Papadias. 2005. Conceptual Partitioning: An Efficient Method for Continuous Nearest Neighbor Monitoring. In Proceedings of the ACM SIGMOD International Conference on Management of Data, Baltimore, Maryland, USA, June 14-16, 2005. 634--645.
[19]
Kyriakos Mouratidis, Dimitris Papadias, Spiridon Bakiras, and Yufei Tao. 2005. A Threshold-Based Algorithm for Continuous Monitoring of k Nearest Neighbors. IEEE Trans. Knowl. Data Eng. 17, 11 (2005), 1451--1464.
[20]
OpenStreetMap contributors. 2017. Planet dump retrieved from https://planet.osm.org. https://www.openstreetmap.org. (2017).
[21]
Simonas Saltenis, Christian S. Jensen, Scott T. Leutenegger, and Mario A. López. 2000. Indexing the Positions of Continuously Moving Objects. In Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, May 16-18, 2000, Dallas, Texas, USA. 331--342.
[22]
Yufei Tao, Dimitris Papadias, and Qiongmao Shen. 2002. Continuous Nearest Neighbor Search. In VLDB 2002, Proceedings of 28th International Conference on Very Large Data Bases, August 20-23, 2002, Hong Kong, China. 287--298. http://www.vldb.org/conf/2002/S09P02.pdf
[23]
Haojun Wang, Roger Zimmermann, and Wei-Shinn Ku. 2006. Distributed Continuous Range Query Processing on Moving Objects. In Database and Expert Systems Applications, 17th International Conference, DEXA 2006, Kraków, Poland, September 4-8, 2006, Proceedings. 655--665.
[24]
Xiaoyuan Wang and Wei Wang. 2006. Continuous Expansion: Efficient Processing of Continuous Range Monitoring in Mobile Environments. In Database Systems for Advanced Applications, 11th International Conference, DASFAA 2006, Singapore, April 12-15, 2006, Proceedings. 890--899.
[25]
Wei Wu, Fei Yang, Chee Yong Chan, and Kian-Lee Tan. 2008. Continuous Reverse k-Nearest-Neighbor Monitoring. In 9th International Conference on Mobile Data Management (MDM 2008), Beijing, China, April 27-30, 2008. 132--139.
[26]
Tian Xia and Donghui Zhang. 2006. Continuous Reverse Nearest Neighbor Monitoring. In Proceedings of the 22nd International Conference on Data Engineering, ICDE 2006, 3-8 April 2006, Atlanta, GA, USA. 77.
[27]
Xiaopeng Xiong, Mohamed F. Mokbel, and Walid G. Aref. 2005. SEA-CNN: Scalable Processing of Continuous K-Nearest Neighbor Queries in Spatio-temporal Databases. In Proceedings of the 21st International Conference on Data Engineering, ICDE 2005, 5-8 April 2005, Tokyo, Japan. 643--654.
[28]
Xiaohui Yu, Ken Q. Pu, and Nick Koudas. 2005. Monitoring K-Nearest Neighbor Queries Over Moving Objects. In Proceedings of the 21st International Conference on Data Engineering, ICDE 2005, 5-8 April 2005, Tokyo, Japan. 631--642.
[29]
Jun Zhang, Manli Zhu, Dimitris Papadias, Yufei Tao, and Dik Lun Lee. 2003. Location-based Spatial Queries. In Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, San Diego, California, USA, June 9-12, 2003. 443--454.
- QUIET ZONE: Reducing The Communication Cost of Continuous Spatial Queries
Recommendations
A taxonomy for region queries in spatial databases
In spatial databases, there are two basic types of queries, namely nearest neighbour queries (kNN) and range queries. Spatial range queries are not only finding objects of interest within a certain range or radius, but feature a wide spectrum: from ...
Continuous reverse k nearest neighbors queries in Euclidean space and in spatial networks
In this paper, we study the problem of continuous monitoring of reverse k nearest neighbors queries in Euclidean space as well as in spatial networks. Existing techniques are sensitive toward objects and queries movement. For example, the results of a ...
Continuous monitoring of moving skyline and top-k queries
AbstractGiven a set of criteria, an object o dominates another object if o is more preferable than according to every criterion. A skyline query returns every object that is not dominated by any other object. A top-k query returns k most preferred ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
November 2017
118 pages
ISBN:9781450354950
DOI:10.1145/3152178
Copyright © 2017 ACM.
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
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 07 November 2017
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed limited
Conference
SIGSPATIAL'17
Sponsor:
SIGSPATIAL'17: 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems
November 7 - 10, 2017
CA, Redondo Beach, USA
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 55Total Downloads
- Downloads (Last 12 months)3
- Downloads (Last 6 weeks)0
Reflects downloads up to 09 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in