Durable queries over non-synchronized temporal data
Tóm tắt
Temporal data are ubiquitous nowadays and efficient management of temporal data is of key importance. A temporal data typically describes the evolution of an object over time. One of the most useful queries over temporal data are the durable top-k queries. Given a time window, a durable top-k query finds the objects that are frequently among the best. Existing solutions to durable top-k queries assume that all temporal data are sampled at the same time points (i.e., at any time, there is a corresponding observed value for every temporal data). However, in many practical applications, temporal data are collected from multiple data sources with different sampling rates. In this light, we investigate the efficient processing of durable top-k queries over temporal data with different sampling rates. We propose an efficient sweep line algorithm to process durable top-k queries over non-synchronized temporal data. We conduct extensive experiments on two real datasets to test the performance of our proposed method. The results show that our methods outperforms the baseline solutions by a large margin.
Tài liệu tham khảo
Deng, D., Leung, C.K., Zhao, C., Wen, Y., Zheng, H.: Spatial-Temporal Data Science of COVID-19 Data. In: BigdataSE (2021)
Hu, T., Wang, S., She, B., Zhang, M., Huang, X., Cui, Y., Khuri, J., Hu, Y, Fu, X, Wang, X., Wang, P., Zhu, X., Bao, S., Guan, W., Li, Z.: Human mobility data in the COVID-19 pandemic: characteristics, applications, and challenges. Int. J. Digit. Earth 14(9), 1126–1147 (2021)
Niu, Z., Wu, J., Liu, X., Huang, L., Nielsen, P. S.: Understanding energy demand behaviors through spatio-temporal smart meter data analysis. Energy 226, 120493 (2021)
Lin, W., Wu, D, Boulet, B.: Spatial-temporal residential short-term load forecasting via graph neural networks. IEEE Trans. Smart Grid 12(6), 5373–5384 (2021)
Yuan, H., Li, G.: A survey of traffic prediction: from spatio-temporal data to intelligent transportation. Data Sci. Eng. 6, 63–85 (2021)
Zhang, X., Huang, C., Xu, Y., Xia, L., Dai, P., Bo, L., Zhang, J., Zheng, Y.: Traffic flow forecasting with spatial-temporal graph diffusion network. In: AAAI (2021)
Liu, X., Hadiatullah, H., Tai, P., Yanling, X u, Zhang, X., Schnelle-Kreis, J., Schloter-Hai, B., Zimmermann, R.: Air pollution in Germany: spatio-temporal variations and their driving factors based on continous data from 2008 to 2018. Environ. Pollut. 276, 116732 (2021)
Zhao, S., Liu, S., Hou, X., Cheng, F., Wu, X., Dong, S., Beazley, R.: Temporal dynamics of SO2 and NOx pollution and contributions of driving forces in urban areas in China. Environ. Pollut. 242, 239–248 (2018)
Atluri, G., Karpatne, A., Kumar, V.: Spatio-temporal data mining: a survey of problems and methods. ACM Comput. Surv. 51(4), Article 83 (2018)
Lee, M. L., Hsu, W., Li, L., Tok, W. H.: Consistent Top-K Queries over Time. In: DASFAA (2009)
Jestes, J., Phillips, J.M., Li, F., Tang, M.: Ranking large temporal data. PVLDB 5(11), 1412–1423 (2012)
Leong Hou, U, Mamoulis, N., Berberich, K., Bedathur, S.: Durable Top-K search in document archives. In: SIGMOD (2010)
Wang, H., Cai, Y., Yang, Y., Zhang, S., Mamoulis, N.: Durable queries over historical time series. TKDE 26(3), 595–607 (2014)
Wang, H., Ou, J., Yuan, Y.: Strategy of data processing for GPS rover and reference receivers using different sampling rates. IEEE Trans. Geosci. Remote Sens. 49(3), 1144–1149 (2011)
Han, S u, Zheng, K., Huang, J., Wang, H., Zhou, X.: Calibrating trajectory data for spatio-temporal similarity analysis. VLDB J 24, 93–116 (2015)
Horn, M., Moor, M., Bock, C., Rieck, B., Borgwardt, K.: Set functions for time series. In: ICML (2020)
Elmeleegy, H., Elmagarmid, A.K., Cecchet, E., Aref, W.G., Zwaenepoel, W.: Online piece-wise linear approximation of numerical streams with precision guarantees. In: VLDB (2009)
Ge, L., Ke, Y i, Cheng, Siu-Wing, Li, Z., Fan, W., He, C., Mu, Y.: Piecewise Linear Approximation of Streaming Time Series Data with Max-Error Guarantees. In: ICDE (2015)
de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational geometry: Algorithms and Applications. Springer, 3rd edn (2008)
Li, F., Yi, K., Le, W.: Top-k queries on temporal data. VLDB J 19(5), 715–733 (2010)
Cho, E., Myers, S.A., Leskovec, J.: Friendship and Mobility: User Movement in Location-Based Social Networks. In: KDD (2011)
Ruz, G.A., Henríquez, P.A., Mascareño, A.: Sentiment analysis of twitter data during critical events through Bayesian networks classifiers. FGCS 106, 92–104 (2020)
Li, K, Chen, L., Shang, S., Wang, H., Liu, Y., Kalnis, P., Yao, B.: Towards Controlling the Transmission of Diseases: Continuous Exposure Discovery over Massive-Scale Moving Objects. In: IJCAI (2022)
Yang, C., Chen, L., Wang, H., Shang, S.: Towards Efficient Selection of Activity Trajectories Based on Discovery and Coverage. In: AAAI (2021)
Chen, L., Shang, S., Jensen, C.S., Yao, B., Shao, L.: Parallel Semantic Trajectory Similarity Join. In: ICDE (2020)
Shang, S., Chen, L., Zheng, K., Jensen, C.S., Wei, Z., Kalnis, P.: Parallel trajectory-to-location join. TKDE 31(6), 1194–1207 (2019)
Rao, X., Wang, H., Zhang, L., Li, J., Shang, S., Han, P.: FOGS: First-Order Gradient Supervision with Learning-Based Graph for Traffic Flow Forecasting. In: IJCAI (2022)
Alaee, S., Mercer, R., Kamgar, K., Keogh, E.: Time series motifs discovery under DTW allows more robust discovery of conserved structure. DMKD 35, 863–910 (2021)
Imani, S., Madrid, F., Ding, W., Crouter, S.E., Keogh, E.: Introducing time series snippets: a new primitive for summarizing long time series. DMKD 34, 1713–1743 (2020)
Yang, C., Deng, D., Shang, S., Shao, L.: Efficient locality-sensitive hashing over high-dimensional data streams. In: ICDE (2020)
Yang, C., Chen, L., Shang, S., Zhu, F., Li, L., Shao, L.: Toward efficient navigation of massive-scale geo-textual streams. In: IJCAI (2019)
Keogh, E., Chu, S., Hart, D., Pazzani, M.: An online algorithm for segmenting time series. In: ICDE (2001)
Jiang, B., Pei, J.: Online interval skyline queries on time series. In: ICDE (2009)
Gao, J., Agarwal, P.K., Yang, J.: Durable top-k queries on temporal data. PVLDB 11(13), 2223–2235 (2018)
Gao, J., Sintos, S., Agarwal, P.K., Yang, J.: Durable Top-K instant-stamped temporal records with user-specified scoring functions. In: ICDE (2021)
Chen, L., Shang, S., Zhang, Z., Cao, X., Jensen, C.S., Kalnis, P.: Location-aware Top-K term Publish/Subscribe. In: ICDE (2018)
Chen, L., Shang, S., Yao, B., Zheng, K.: Spatio-temporal top-k term search over sliding window. WWW 22(5), 1953–1970 (2019)
Chen, L., Shang, S.: Approximate spatio-temporal top-k publish/subscribe. WWW 22(5), 2153–2175 (2019)