Abstract
This paper presents the scalable on-line execution (SOLE) algorithm for continuous and on-line evaluation of concurrent continuous spatio-temporal queries over data streams. Incoming spatio-temporal data streams are processed in-memory against a set of outstanding continuous queries. The SOLE algorithm utilizes the scarce memory resource efficiently by keeping track of only the significant objects. In-memory stored objects are expired (i.e., dropped) from memory once they become insignificant. SOLE is a scalable algorithm where all the continuous outstanding queries share the same buffer pool. In addition, SOLE is presented as a spatio-temporal join between two input streams, a stream of spatio-temporal objects and a stream of spatio-temporal queries. To cope with intervals of high arrival rates of objects and/or queries, SOLE utilizes a load-shedding approach where some of the stored objects are dropped from memory. SOLE is implemented as a pipelined query operator that can be combined with traditional query operators in a query execution plan to support a wide variety of continuous queries. Performance experiments based on a real implementation of SOLE inside a prototype of a data stream management system show the scalability and efficiency of SOLE in highly dynamic environments.
Similar content being viewed by others
References
Abadi, D., Ahmad, Y., Balakrishnan, H., Balazinska, M., Cetintemel, U., Cherniack, M., Hwang, J.H., Janotti, J., Lindner, W., Madden, S., Rasin, A., Stonebraker, M., Tatbul, N., Xing, Y., Zdonik, S.: The design of the borealis stream processing engine. In: Proceedings of the International Conference on Innovative Data Systems Research, CIDR (2005)
Abadi D.J., Carney D., Cetintemel U., Cherniack M., Convey C., Lee S., Stonebraker M., Tatbul N., Zdonik S.B. (2003). Aurora: A new model and architecture for data stream management. VLDB J. 12(2): 120–139
de Almeida, V.T., Güting, R.H.: Supporting uncertainty in moving objects in network databases. In: Proceedings of the ACM Symposium on Advances in Geographic Information Systems, ACM GIS, pp. 31–40. Bremen, Germany (2005)
Arasu, A., Widom, J.: Resource sharing in continuous sliding- window aggregates. In: Proceedings of the International Conference on Very Large Data Bases, VLDB (2004)
Ayad, A., Naughton, J.F.: Static optimization of conjunctive queries with sliding windows over infinite streams. In: Proceedings of the ACM International Conference on Management of Data, SIGMOD (2004)
Babcock, B., Datar, M., Motwani, R.: Load shedding for aggregation queries over data streams. In: Proceedings of the International Conference on Data Engineering, ICDE (2004)
Babu S., Widom J. (2001). Continuous queries over data streams. SIGMOD Record 30(3): 109–120
Brinkhoff T. (2002). A framework for generating network-based moving objects. GeoInformatica 6(2): 153–180
Cai, Y., Hua, K.A., Cao, G.: Processing range-monitoring queries on heterogeneous mobile objects. In: Proceedings of the International Conference on Mobile Data Management, MDM (2004)
Cammert, M., Heinz, C., Krämer, J., Riemenschneider, T., Schwarzkopf, M., Seeger, B., Zeiss, A.: Stream processing in production-to-business software. In: Proceedings of the International Conference on Data Engineering, ICDE. Atlanta (2006)
Cammert, M., Krämer, J., Seeger, B., Vaupel, S.: An approach to adaptive memory management in data stream systems. In: Proceedings of the International Conference on Data Engineering, ICDE. Atlanta (2006)
Chakka, V.P., Everspaugh, A., Patel, J.M.: Indexing large trajectory data sets with SETI. In: Proceedings of the International Conference on Innovative Data Systems Research, CIDR (2003)
Chandrasekaran, S., Cooper, O., Deshpande, A., Franklin, M.J., Hellerstein, J.M., Hong, W., Krishnamurthy, S., Madden, S., Raman, V., Reiss, F., Shah, M.A.: TelegraphCQ: Continuous dataflow processing for an uncertain world. In: Proceedings of the International Conference on Innovative Data Systems Research, CIDR (2003)
Chandrasekaran S., Franklin M.J. (2003). PSoup: A system for streaming queries over streaming data. VLDB J. 12(2): 140–156
Chen, J., DeWitt, D.J., Tian, F., Wang, Y.: NiagaraCQ: a scalable continuous query system for internet databases. In: Proceedings of the ACM International Conference on Management of Data, SIGMOD, pp. 379–390 (2000)
Cheng R., Kalashnikov D.V., Prabhakar S. (2004). Querying imprecise data in moving object environments. IEEE Tran. Knowl. Data Eng. TKDE 16(9): 1112–1127
Dai, X., Yiu, M.L., Mamoulis, N., Tao, Y., Vaitis, M.: Probabilistic spatial queries on existentially uncertain data. In: Proceedings of the International Symposium on Advances in Spatial and Temporal Databases, SSTD, pp. 400–417. Angra dos Reis, Brazil (2005)
Das, A., Gehrke, J., Riedewald, M.: Approximate join processing over data streams. In: Proceedings of the ACM International Conference on Management of Data, SIGMOD, pp. 40–51. San Diego (2003)
Das A., Gehrke J., Riedewald M. (2005). Semantic approximation of data stream joins. IEEE Trans. Knowl. Data Eng. TKDE 17(1): 44–59
Dobra, A., Garofalakis, M.N., Gehrke, J., Rastogi, R.: Static optimization of conjunctive queries with sliding windows over infinite streams. In: Proceedings of the International Conference on Extending Database Technology, EDBT (2004)
Gedik, B., Liu, L.: 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)
Ghanem T.M., Aref W.G., Elmagarmid A.K. (2006). Exploiting Predicate-window Semantics over Data Streams. SIGMOD Record 35(1): 3–8
Golab, L., Ozsu, M.T.: Processing sliding window multi-joins in continuous queries over data streams. In: Proceedings of the International Conference on Very Large Data Bases, VLDB (2003)
Hammad, M.A., Franklin, M.J., Aref, W.G., Elmagarmid, A.K.: Scheduling for shared window joins over data streams. In: Proceedings of the International Conference on Very Large Data Bases, VLDB (2003)
Hammad, M.A., Ghanem, T.M., Aref, W.G., Elmagarmid, A.K., Mokbel, M.F.: Efficient pipelined execution of sliding-window queries over data streams. Tech. Rep. TR CSD-03-035, Purdue University Department of Computer Sciences (2003)
Hammad, M.A., Mokbel, M.F., Ali, M.H., Aref, W.G., Catlin, A.C., Elmagarmid, A.K., Eltabakh, M., Elfeky, M.G., Ghanem, T.M., Gwadera, R., Ilyas, I.F., Marzouk, M., Xiong, X.: Nile: A query processing engine for data streams (Demo). In: Proceedings of the International Conference on Data Engineering, ICDE (2004)
Hu, H., Xu, J., Lee, D.L.: A generic framework for monitoring continuous spatial queries over moving objects. In: Proceedings of the ACM International Conference on Management of Data, SIGMOD. Baltimore (2005)
Iwerks, G.S., Samet, H., Smith, K.: Continuous K-nearest neighbor queries for continuously moving points with updates. In: Proceedings of the International Conference on Very Large Data Bases, VLDB (2003)
Jensen, C.S., Lin, D., Ooi, B.C.: 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ürgen Krämer, B.S.: PIPES—A public infrastructure for and exploring streams. In: Proceedings of the ACM International Conference on Management of Data, SIGMOD, pp. 925–926. Paris (2004)
Kalashnikov D.V., Prabhakar S., Hambrusch S.E. (2004). Main memory evaluation of monitoring queries over moving objects. Distrib. Parallel Databases 15(2): 117–135
Kalashnikov, D.V., Prabhakar, S., Hambrusch, S.E., Aref, W.G.: Efficient evaluation of continuous range queries on moving objects. In: Database and Expert Systems Applications, DEXA, pp. 731–740. Aix-en-Provence, France (2002)
Kwon, D., Lee, S., Lee, S.: Indexing the current positions of moving objects using the lazy update R-tree. In: Proceedings of the International Conference on Mobile Data Management, MDM, pp. 113–120 (2002)
Lazaridis, I., Porkaew, K., Mehrotra, S.: Dynamic queries over mobile objects. In: Proceedings of the International Conference on Extending Database Technology, EDBT, pp. 269–286 (2002)
Lee, M.L., Hsu, W., Jensen, C.S., Cui, B., Teo, K.L.: Supporting frequent updates in R-trees: a bottom-up approach. In: Proceedings of the International Conference on Very Large Data Bases, VLDB (2003)
Madden, S., Shah, M., Hellerstein, J.M., Raman, V.: Continuously adaptive continuous queries over streams. In: Proceedings of the ACM International Conference on Management of Data, SIGMOD, pp. 49–60 (2002)
Mokbel, M.F., Aref, W.G.: GPAC: Generic and progressive processing of mobile queries over mobile data. In: Proceedings of the International Conference on Mobile Data Management, MDM (2005)
Mokbel M.F., Aref W.G. (2005). PLACE: a scalable location-aware database server for spatio-temporal data streams. IEEE Data Eng. Bull. 28(3): 3–10
Mokbel, M.F., Xiong, X., Aref, W.G.: SINA: scalable incremental processing of continuous queries in spatio-temporal databases. In: Proceedings of the ACM International Conference on Management of Data, SIGMOD, pp. 443–454 (2004)
Mokbel, M.F., Xiong, X., Aref, W.G., Hambrusch, S., Prabhakar, S., Hammad, M.: PLACE: a query processor for handling spatio-temporal data streams (demo). In: Proceedings of the International Conference on Very Large Data Bases, VLDB (2004)
Mokbel, M.F., Xiong, X., Hammad, M.A., Aref, W.G.: Continuous query processing of spatio-temporal data streams in PLACE. In: Proceedings of the second workshop on Spatio-Temporal Database Management, STDBM (2004)
Motwani, R., Widom, J., Arasu, A., Babcock, B., Babu, S., Datar, M., Manku, G.S., Olston, C., Rosenstein, J., Varma, R.: 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)
Mouratidis, K., Papadias, D., Hadjieleftheriou, M.: Conceptual partitioning: an efficient method for continuous nearest neighbor monitoring. In: Proceedings of the ACM International Conference on Management of Data, SIGMOD. Baltimore (2005)
Patel, J.M., Chen, Y., Chakka, V.P.: STRIPES: an efficient index for predicted trajectories. In: Proceedings of the ACM International Conference on Management of Data, SIGMOD (2004)
Pfoser, D., Jensen, C.S.: Capturing the uncertainty of representations. In: Proceedings of the International Symposium on Advances in Spatial Databases, SSD, pp. 111–132. Hong Kong (1999)
Prabhakar S., Xia Y., Kalashnikov D.V., Aref W.G., Hambrusch S.E. (2002). Query indexing and velocity constrained indexing: scalable techniques for continuous queries on moving objects. IEEE Trans. Comput. 51(10): 1124–1140
Reiss, F., Hellerstein, J.M.: Data triage: an adaptive architecture for load shedding in TelegraphCQ. In: Proceedings of the International Conference on Data Engineering, ICDE, pp. 155–156. Tokyo (2005)
Saltenis, S., Jensen, C.S., Leutenegger, S.T., Lopez, M.A.: Indexing the positions of continuously moving objects. In: Proceedings of the ACM International Conference on Management of Data, SIGMOD, pp. 331–342 (2000)
Song, Z., Roussopoulos, N.: Hashing moving objects. In: Proceedings of the International Conference on Mobile Data Management, MDM, pp. 161–172 (2001)
Song, Z., Roussopoulos, N.: K-nearest neighbor search for moving query point. In: Proceedings of the International Symposium on Advances in Spatial and Temporal Databases, SSTD, pp. 79–96 (2001)
Tao, Y., Papadias, D., Shen, Q.: Continuous nearest neighbor search. In: Proceedings of the International Conference on Very Large Data Bases, VLDB, pp. 287–298 (2002)
Tao, Y., Papadias, D., Sun, J.: The TPR*-tree: an optimized temporal access method for predictive queries. In: Proceedings of the International Conference on Very Large Data Bases, VLDB (2003)
Tatbul, N., Cetintemel, U., Zdonik, S.B., Cherniack, M., Stonebraker, M.: Load shedding in a data stream Manager. In: Proceedings of the International Conference on Very Large Data Bases, VLDB (2003)
Trajcevski G., Wolfson O., Hinrichs K., Chamberlain S. (2004). Managing uncertainty in moving objects databases. ACM Trans. Database Systems TODS 29(3): 463–507
Trajcevski, G., Wolfson, O., Zhang, F., Chamberlain, S.: The geometry of uncertainty in moving objects databases. In: Proceedings of the International Conference on Extending Database Technology, EDBT, pp. 233–250. Prague, Czech Republic (2002)
Wolfson, O., Yin, H.: Accuracy and resource concumption in tracking and location prediction. In: Proceedings of the International Symposium on Advances in Spatial and Temporal Databases, SSTD, pp. 325–343. Santorini Island (2003)
Xiong, X., Mokbel, M.F., Aref, W.G.: 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)
Xiong, X., Mokbel, M.F., Aref, W.G., Hambrusch, S., Prabhakar, S.: Scalable Spatio-temporal continuous query processing for location-aware services. In: Proceedings of the International Conference on Scientific and Statistical Database Management, SSDBM (2004)
Yu, X., Pu, K.Q., Koudas, N.: Monitoring K-nearest neighbor queries over moving objects. In: Proceedings of the International Conference on Data Engineering, ICDE, pp. 631–642. Tokyo (2005)
Zhang, J., Zhu, M., Papadias, D., Tao, Y., Lee, D.L.: Location-based spatial queries. In: Proceedings of the ACM International Conference on Management of Data, SIGMOD, pp. 443–454 (2003)
Zheng, B., Lee, D.L.: Semantic caching in location-dependent query processing. In: Proceedings of the International Symposium on Advances in Spatial and Temporal Databases, SSTD, pp. 97–116 (2001)
Author information
Authors and Affiliations
Corresponding author
Additional information
This work was supported in part by the National Science Foundation under Grants IIS-0093116, IIS-0209120, and 0010044-CCR.
Rights and permissions
About this article
Cite this article
Mokbel, M.F., Aref, W.G. SOLE: scalable on-line execution of continuous queries on spatio-temporal data streams. The VLDB Journal 17, 971–995 (2008). https://doi.org/10.1007/s00778-007-0046-1
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00778-007-0046-1