Continuous Query Processing of Spatio-Temporal Data Streams in PLACE

D. Abadi, Y. Ahmad, H. Balakrishnan, M. Balazinska, U. Cetintemel, M. Cherniack, J.-H. Hwang, J. Janotti, W. Lindner, S. Madden, A. Rasin, M. Stonebraker, N. Tatbul, Y. Xing, and S. Zdonik. “The design of the Borealis stream processing engine,” in Proceedings of the International Conference on Innovative Data Systems Research, CIDR, 2005.

A. Arasu and J. Widom. “Resource sharing in continuous sliding-window aggregates,” in Proceedings of the International Conference on Very Large Data Bases, VLDB, 2004.

A. Arasu, B. Babcock, S. Babu, J. Cieslewicz, M. Datar, K. Ito, R. Motwani, U. Srivastava, and J. Widom. STREAM: The Stanford Data Stream Management System, 2004.

W.G. Aref, S.E. Hambrusch, and S. Prabhakar. “Pervasive Location Aware Computing Environments (PLACE),” http://www.cs.purdue.edu/place/, 2003.

S. Babu and J. Widom. “Continuous queries over data streams,” SIGMOD Record, Vol. 30(3), 2001.

R. Benetis, C.S. Jensen, G. Karciauskas, and S. Saltenis. “Nearest neighbor and reverse nearest neighbor queries for moving objects,” in Proceedings of the International Database Engineering and Applications Symposium, IDEAS, 2002.

T. Brinkhoff. “A framework for generating network-based moving objects,” GeoInformatica, Vol. 6(2), 2002.

Y. Cai, K.A. Hua, and G. Cao. “Processing range-monitoring queries on heterogeneous mobile objects,” in Mobile Data Management, MDM, 2004.

S. Chandrasekaran and M.J. Franklin. “Streaming queries over streaming data,” in Proceedings of the International Conference on Very Large Data Bases, VLDB, 2002.

S. Chandrasekaran and M.J. Franklin. “PSoup: A system for streaming queries over streaming data,” VLDB Journal, Vol. 12(2):140–156, 2003.

S. Chandrasekaran, O. Cooper, A. Deshpande, M.J. Franklin, J.M. Hellerstein, W. Hong, S. Krishnamurthy, S. Madden, V. Raman, F. Reiss, and M.A. Shah. “TelegraphCQ: Continuous dataflow processing for an uncertain world,” in Proceedings of the International Conference on Innovative Data Systems Research, CIDR, 2003.

J. Chen, D.J. DeWitt, F. Tian, and Y. Wang. “NiagaraCQ: A scalable continuous query system for internet databases,” in Proceedings of the ACM International Conference on Management of Data, SIGMOD, 2000.

J. Chen, D.J. DeWitt, and J.F. Naughton. “Design and evaluation of alternative selection placement strategies in optimizing continuous queries,” in Proceedings of the International Conference on Data Engineering, ICDE, 2002.

J. Clifford, C.E. Dyreson, T. Isakowitz, C.S. Jensen, and R.T. Snodgrass. “On the semantics of “now” in databases,” ACM Transactions on Database Systems, TODS, Vol. 22(2), 1997.

G. Cormode and S. Muthukrishnan. “Radial histograms for spatial streams,” Technical Report DIMACS TR: 2003-11, Rutgers University, 2003.

C. Cranor, T. Johnson, O. Spataschek, and V. Shkapenyuk. “Gigascope: A stream database for network applications,” in Proceedings of the ACM International Conference on Management of Data, SIGMOD, 2003.

M. Datar, A. Gionis, P. Indyk, and R. Motwani. “Maintaining stream statistics over sliding windows,” in Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, SODA, 2002.

B. Gedik and L. Liu. “MobiEyes: Distributed processing of continuously moving queries on moving objects in a mobile system,” in Proceedings of the International Conference on Extending Database Technology, EDBT, 2004.

L. Golab and M.T. Ozsu. “Processing sliding window multi-joins in continuous queries over data streams,” in Proceedings of the International Conference on Very Large Data Bases, VLDB, 2003.

L. Golab, S. Garg, and M.T. Ozsu. “On indexing sliding windows over online data streams,” in Proceedings of the International Conference on Extending Database Technology, EDBT, 2004.

M. Hadjieleftheriou, G. Kollios, D. Gunopulos, and V.J. Tsotras. “On-line discovery of dense areas in spatio-temporal databases,” in Proceedings of the International Symposium on Advances in Spatial and Temporal Databases, SSTD, 2003.

S.E. Hambrusch, C.-M. Liu, W.G. Aref, and S. Prabhakar. “Query processing in broadcasted spatial index trees,” in Proceedings of the International Symposium on Advances in Spatial and Temporal Databases, SSTD, 2001.

M.A. Hammad, W.G. Aref, and A.K. Elmagarmid. “Stream window join: Tracking moving objects in sensor-network databases,” in Proceedings of the International Conference on Scientific and Statistical Database Management, SSDBM, 2003.

M.A. Hammad, M.J. Franklin, W.G. Aref, and A.K. Elmagarmid. “Scheduling for shared window joins over data streams,” in Proceedings of the International Conference on Very Large Data Bases, VLDB, 2003.

M.A. Hammad, T.M. Ghanem, W.G. Aref, A.K. Elmagarmid, and M.F. Mokbel. Efficient Pipelined Execution of Sliding-Window Queries Over Data Streams. Technical Report TR CSD-03-035, Purdue University Department of Computer Sciences, 2003.

M.A. Hammad, M.F. Mokbel, M.H. Ali, W.G. Aref, A.C. Catlin, A.K. Elmagarmid, M. Eltabakh, M.G. Elfeky, T.M. Ghanem, R. Gwadera, I.F. Ilyas, M. Marzouk, and X. Xiong. “Nile: A query processing engine for data streams (demo),” in Proceedings of the International Conference on Data Engineering, ICDE, 2004.

J. Hershberger and S. Suri. “Adaptive sampling for geometric problems over data streams,” in Proceedings of the ACM Symposium on Principles of Database Systems, PODS, 2004.

G.S. Iwerks, H. Samet, and K. Smith. “Continuous k-nearest neighbor queries for continuously moving points with updates,” in Proceedings of the International Conference on Very Large Data Bases, VLDB, 2003.

C.S. Jensen, D. Lin, and B.C. Ooi. “Query and update efficient B+tree based indexing of moving objects,” in Proceedings of the International Conference on Very Large Data Bases, VLDB, 2004.

J. Kang, J.F. Naughton, and S. Viglas. “Evaluating window joins over unbounded streams,” in Proceedings of the International Conference on Data Engineering, ICDE, 2003.

D. Kwon, S. Lee, and S. Lee. “Indexing the current positions of moving objects using the lazy update R-tree,” in Mobile Data Management, MDM, 2002.

I. Lazaridis, K. Porkaew, and S. Mehrotra. “Dynamic queries over mobile objects,” in Proceedings of the International Conference on Extending Database Technology, EDBT, 2002.

M.-L. Lee, W. Hsu, C.S. Jensen, and K.L. Teo. “Supporting frequent updates in R-trees: A bottom-up approach,” in Proceedings of the International Conference on Very Large Data Bases, VLDB, 2003.

S. Madden, M. Shah, J.M. Hellerstein, and V. Raman. “Continuously adaptive continuous queries over streams,” in Proceedings of the ACM International Conference on Management of Data, SIGMOD, 2002.

M.F. Mokbel and W.G. Aref. “GPAC: Generic and progressive processing of mobile queries over mobile data,” in Mobile Data Management, MDM, 2005.

M.F. Mokbel, W.G. Aref, S.E. Hambrusch, and S. Prabhakarx. “Towards scalable location-aware services: requirements and research issues,” in Proceedings of the ACM Symposium on Advances in Geographic Information Systems, ACM GIS, 2003.

M.F. Mokbel, T.M. Ghanem, and W.G. Aref. “Spatio-temporal access methods,” IEEE Data Engineering Bulletin, Vol. 26(2), 2003.

M.F. Mokbel, X. Xiong, and W.G. Aref. “SINA: Scalable incremental processing of continuous queries in spatio-temporal databases,” in Proceedings of the ACM International Conference on Management of Data, SIGMOD, 2004.

M.F. Mokbel, X. Xiong, W.G. Aref, S. Hambrusch, S. Prabhakar, and M. Hammad. “PLACE: A query processor for handling real-time spatio-temporal data streams (demo),” in Proceedings of the International Conference on Very Large Data Bases, VLDB, 2004.

M.F. Mokbel, X. Xiong, M.A. Hammad, and W.G. Aref. “Continuous query processing of spatio-temporal data streams in PLACE,” in Proceedings of the second workshop on Spatio-Temporal Database Management, STDBM, 2004.

R. Motwani, J. Widom, A. Arasu, B. Babcock, S. Babu, M. Datar, G.S. Manku, C. Olston, J. Rosenstein, and R. Varma. “Query processing, approximation, and resource management in a data stream management system,” in Proceedings of the International Conference on Innovative Data Systems Research, CIDR, 2003.

T. Nadeem, S. Dashtinezhad, C. Liao, and L. Iftode. “TrafficView: A scalable traffic monitoring system,” in Mobile Data Management, MDM, 2004.

D. Pfoser, C.S. Jensen, and Y. Theodoridis. “Novel approaches in query processing for moving object trajectories,” in Proceedings of the International Conference on Very Large Data Bases, VLDB, 2000.

S. Prabhakar, Y. Xia, D.V. Kalashnikov, W.G. Aref, and S.E. Hambrusch. “Query indexing and velocity constrained indexing: Scalable techniques for continuous queries on moving objects,” IEEE Transactions on Computers, Vol. 51(10), 2002.

B. Reinwald and H. Pirahesh. “SQL open heterogeneous data access,” in Proceedings of the ACM International Conference on Management of Data, SIGMOD, 1998.

B. Reinwald, H. Pirahesh, G. Krishnamoorthy, G. Lapis, B.T. Tran, and S. Vora. “Heterogeneous query processing through SQL table functions,” in Proceedings of the International Conference on Data Engineering, ICDE, 1999.

S. Saltenis and C.S. Jensen. “Indexing of moving objects for location-based services,” in Proceedings of the International Conference on Data Engineering, ICDE, 2002.

S. Saltenis, C.S. Jensen, S.T. Leutenegger, and M.A. Lopez. “Indexing the positions of continuously moving objects,” in Proceedings of the ACM International Conference on Management of Data, SIGMOD, 2000.

H. Samet. “The quadtree and related hierarchical data structures,” ACM Computing Surveys, Vol. 16(2), 1984.

P. Seshadri. “Predator: A resource for database research,” SIGMOD Record, Vol. 27(1):16–20, 1998.

Z. Song and N. Roussopoulos. “k-nearest neighbor search for moving query point,” in Proceedings of the International Symposium on Advances in Spatial and Temporal Databases, SSTD, 2001.

U. Srivastava and J. Widom. “Memory-limited execution of windowed stream joins,” in Proceedings of the International Conference on Very Large Data Bases, VLDB, 2004.

J. Sun, D. Papadias, Y. Tao, and B. Liu. “Querying about the past, the present and the future in spatio-temporal databases,” in Proceedings of the International Conference on Data Engineering, ICDE, 2004.

G. Swedberg. “Ericsson's mobile location solution,” Ericsson Review, 1999.

Y. Tao, D. Papadias, and Q. Shen. “Continuous nearest neighbor search,” in Proceedings of the International Conference on Very Large Data Bases, VLDB, 2002.

Y. Tao, D. Papadias, and J. Sun. “The TPR*-tree: An optimized spatiotemporal access method for predictive queries,” in Proceedings of the International Conference on Very Large Data Bases, VLDB, 2003.

Y. Tao, J. Sun, and D. Papadias. “Analysis of predictive spatio-temporal queries,” ACM Transactions on Database Systems, TODS, Vol. 28(4), 2003.

Y. Tao, G. Kollios, J. Considine, F. Li, and D. Papadias. “Spatio-temporal aggregation using sketches,” in Proceedings of the International Conference on Data Engineering, ICDE, 2004.

N. Tatbul, U. Cetintemel, S.B. Zdonik, M. Cherniack, and M. Stonebraker. “Load shedding in a data stream manager,” in Proceedings of the International Conference on Very Large Data Bases, VLDB, 2003.

Y. Theodoridis. “Ten benchmark database queries for location-based services,” The Computer Journal, Vol. 46(6):713–725, 2003.

P.A. Tucker, D. Maier, T. Sheard, and L. Fegaras. “Exploiting punctuation semantics in continuous data streams,” IEEE Transactions on Knowledge and Data Engineering, TKDE, Vol. 15(3):555–568, 2003.

O. Wolfson, B. Xu, S. Chamberlain, and L. Jiang. “Moving objects databases: Issues and solutions,” in Proceedings of the International Conference on Scientific and Statistical Database Management, SSDBM, 1998.

O. Wolfson, A.P. Sistla, B. Xu, J. Zhou, and S. Chamberlain. “DOMINO: Databases for moving objects tracking (demo),” in Proceedings of the ACM International Conference on Management of Data, SIGMOD, 1999.

X. Xiong, M.F. Mokbel, W.G. Aref, S. Hambrusch, and S. Prabhakar. “Scalable spatio-temporal continuous query processing for location-aware services,” in Proceedings of the International Conference on Scientific and Statistical Database Management, SSDBM, 2004.

X. Xiong, M.F. Mokbel, and W.G. Aref. “SEA-CNN: Scalable processing of continuous k-nearest neighbor queries in spatio-temporal databases,” in Proceedings of the International Conference on Data Engineering, ICDE, 2005.

Y. Yao and J. Gehrke. “The cougar approach to in-network query processing in sensor networks,” SIGMOD Record, Vol. 31(3), 2002.

J. Zhang, M. Zhu, D. Papadias, Y. Tao, and D.L. Lee. “Location-based spatial queries,” in Proceedings of the ACM International Conference on Management of Data, SIGMOD, 2003.

B. Zheng and D.L. Lee. “Semantic caching in location-dependent query processing,” in Proceedings of the International Symposium on Advances in Spatial and Temporal Databases, SSTD, 2001.