|
 ABSTRACT
This paper intoduces the Scalable INcremental hash-based Algorithm (SINA, for short); a new algorithm for evaluting a set of concurrent continuous spatio-temporal queries. SINA is designed with two goals in mind: (1) Scalability in terms of the number of concurrent continuous spatio-temporal queries, and (2) Incremental evaluation of continyous spatio-temporal queries. SINA achieves scalability by empolying a shared execution paradigm where the execution of continuous spatio-temporal queries is abstracted as a spatial join between a set of moving objects and a set of moving queries. Incremental evaluation is achived by computing only the updates of the previously reported answer. We introduce two types of updaes, namely positive and negative updates. Positive or negative updates indicate that a certain object should be added to or removed from the previously reported answer, respectively. SINA manages the computation of postive and negative updates via three phases: the hashing phase, the invalidation phase, and the joining phase. the hashing phase employs an in-memory hash-based join algorithm that results in a set a positive upldates. The invalidation phase is triggered every T seconds or when the memory is fully occupied to produce a set of negative updates. Finally, the joining phase is triggered by the end of the invalidation phase to produce a set of both positive and negative updates that result from joining in-memory data with in-disk data. Experimental results show that SINA is scalable and is more efficient than other index-based spatio-temporal algorithms.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
 |
1
|
Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States
|
| |
2
|
|
| |
3
|
|
| |
4
|
Thomas Brinkhoff , Hans-Peter Kriegel , Bernhard Seeger, Efficient processing of spatial joins using R-trees, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.237-246, May 25-28, 1993, Washington, D.C., United States
|
| |
5
|
Ying Cai, Kien A. Hua, and Guohong Cao. Processing Range-Monitoring Queries on Heterogeneous Mobile Objects, in Mobile Data Management, MDM, 2004.
|
| |
6
|
Sirish Chandrasekaran and Micheal J. Franklin. Streaming Queries over Streaming Data. In VLDB, 2002.
|
| |
7
|
Jianjun Chen , David J. DeWitt , Feng Tian , Yuan Wang, NiagaraCQ: a scalable continuous query system for Internet databases, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.379-390, May 15-18, 2000, Dallas, Texas, United States
|
| |
8
|
Bugra Gedik and Ling Liu. MobiEyes: Distributed Processing of Continuously Moving Queries on Moving Objects in a Mobile System. In EDBT, 2004.
|
| |
9
|
|
| |
10
|
Marios Hadjieleftheriou, George Kollios, Dimitrios Gunopulos, and Vassilis J. Tsotras. On-Line Discovery of Dense Areas in Spatio-temporal Databases. In SSTD, 2003.
|
| |
11
|
|
| |
12
|
Moustafa A. Hammad, Micheal J. Franklin, Walid G. Aref, and Ahmed K. Elmagarmid. Scheduling for Shared Window Joins over Data Streams. In VLDB, 2003.
|
| |
13
|
|
| |
14
|
|
| |
15
|
|
| |
16
|
Mong-Li Lee, Wynne Hsu, Christian, S. Jensen, and Keng Lik Teo. Supporting Frequent Updates in R-Tree: A Bottom-Up Approach. In VLDB, 2003.
|
| |
17
|
Mohamed F. Mokbel, Thanaa, M. Ghanem, and Walid G. Aref. Spatio-temporal Access Methods. IEEE Data Engineering Bulletin, 26(2), 2003.
|
| |
18
|
|
| |
19
|
|
| |
20
|
|
| |
21
|
Simonas Šaltenis , Christian S. Jensen , Scott T. Leutenegger , Mario A. Lopez, Indexing the positions of continuously moving objects, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.331-342, May 15-18, 2000, Dallas, Texas, United States
|
| |
22
|
|
| |
23
|
|
| |
24
|
|
| |
25
|
Jimeng Sun , Dimitris Papadias , Yufei Tao , Bin Liu, Querying about the Past, the Present, and the Future in Spatio-Temporal Databases, Proceedings of the 20th International Conference on Data Engineering, p.202, March 30-April 02, 2004
|
| |
26
|
Yufei Tao, Dimitris Papadias, and Qiongmao Shen. Continuous Nearest Neighbour Search. In VLDB, 2002.
|
| |
27
|
Yufei Tao, Dimitris Papadias, and Jimeng Sun. The TPR*-Tree: An Optimized Spatio-temporal Access Method for Predictive Queries. In VLDB, 2003.
|
| |
28
|
Douglas Terry , David Goldberg , David Nichols , Brian Oki, Continuous queries over append-only databases, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.321-330, June 02-05, 1992, San Diego, California, United States
|
| |
29
|
Tolga Urhan and Michael J. Franklin. XJoin: A Reactively-Scheduled Pipelined Join Operator. IEEE Data Engineering Bulletin, 23(2), 2000.
|
| |
30
|
|
| |
31
|
Ouri Wolfson and Huabei Yin. Accuracy and Resource Concumption in Tracking and Location Prediction. In SSTD, 2003.
|
| |
32
|
Jun Zhang , Manli Zhu , Dimitris Papadias , Yufei Tao , Dik Lun Lee, Location-based spatial queries, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California
[doi> 10.1145/872757.872812]
|
| |
33
|
|
CITED BY 50
|
|
|
|
|
|
|
|
|
|
|
Mourad Ouzzani , Walid G. Aref , Elisa Bertino , Ann Christine Catlin , Christopher W. Clifton , Wing-Kai Hon , Ahmed K. Elmagarmid , Arif Ghafoor , Susanne E. Hambrusch , Sunil Prabhakar , Jeffrey S. Vitter , Xiang Zhang, The Indiana Center for Database Systems at Purdue University, ACM SIGMOD Record, v.34 n.2, June 2005
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Goce Trajcevski , Hu Cao , Peter Scheuermanny , Ouri Wolfsonz , Dennis Vaccaro, On-line data reduction and the quality of history in moving objects databases, Proceedings of the 5th ACM international workshop on Data engineering for wireless and mobile access, June 25-25, 2006, Chicago, Illinois, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Mohamed F. Mokbel , Xiaopeng Xiong , Walid G. Aref , Susanne E. Hambrusch , Sunil Prabhakar , Moustafa A. Hammad, PLACE: a query processor for handling real-time spatio-temporal data streams, Proceedings of the Thirtieth international conference on Very large data bases, p.1377-1380, August 31-September 03, 2004, Toronto, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Hyo-Sang Lim , Jae-Gil Lee , Min-Jae Lee , Kyu-Young Whang , Il-Yeol Song, Continuous query processing in data streams using duality of data and queries, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA
|
|
|
|
|
|
|
|
|
|
|
|
Ken C. K. Lee , Josh Schiffman , Baihua Zheng , Wang-Chien Lee , Hong Va Leong, Round-Eye: A system for tracking nearest surrounders in moving object environments, Journal of Systems and Software, v.80 n.12, p.2063-2076, December, 2007
|
|
|
|
|
|
Dragan Stojanovic , Apostolos N. Papadopoulos , Bratislav Predic , Slobodanka Djordjevic-Kajan , Alexandros Nanopoulos, Continuous range monitoring of mobile objects in road networks, Data & Knowledge Engineering, v.64 n.1, p.77-100, January, 2008
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Ying Cai , Toby Xu, Design, analysis, and implementation of a large-scale real-time location-based information sharing system, Proceeding of the 6th international conference on Mobile systems, applications, and services, June 17-20, 2008, Breckenridge, CO, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Goce Trajcevski , Roberto Tamassia , Hui Ding , Peter Scheuermann , Isabel F. Cruz, Continuous probabilistic nearest-neighbor queries for uncertain trajectories, Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, March 24-26, 2009, Saint Petersburg, Russia
|
|
|
|
|
|
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf