Finding Top-k Sequences over Data Streams according to Temporal Conditional Preferences

• Marcos Roberto Ribeiro Institudo Federal de Minas Gerais / Universidade Federal de Uberlândia
• Maria Camila N. Barioni Universidade Federal de Uberlândia
• Sandra de Amo Universidade Federal de Uberlândia
• Claudia Roncancio Université Grenoble Alpes / CNRS
• Cyril Labbé Université Grenoble Alpes / CNRS

DOI: https://doi.org/10.5753/sbbd.2018.22220

Resumo

Recently, several research works have been conducted on processing of preference queries over data streams. Preference queries are useful for many application domains where users aim to find out the closest data items to their wishes. This paper presents a new operator for the StreamPref language that can be employed to obtain the top-k data stream sequences according to temporal conditional preferences. Temporal conditional preferences can allow a user to express how past instants of a data stream may influence his preferences at a present instant. In order to evaluate this new operator, two new algorithm strategies are also presented. The extensive set of experiments performed show that the incremental strategy presents a superior performance in all experimental settings. Moreover, the results achieved show that the proposed operator has a superior performance when compared to the equivalent operation in CQL.

Palavras-chave: Top-k sequences, data streams, temporal data

Referências

Arasu, A., Babcock, B., Babu, S., Cieslewicz, J., Datar, M., Ito, K., Motwani, R., Srivastava, U., and Widom, J. (2016). STREAM: The Stanford Data Stream Management System, pages 317–336. Springer, Berlin, Heidelberg.

Arasu, A., Babu, S., and Widom, J. (2006). The CQL continuous query language: semantic foundations and query execution. The VLDB Journal, 15(2):121–142.

Börzsönyi, S., Kossmann, D., and Stocker, K. (2001). The skyline operator. In ICDE, pages 421–430, Heidelberg, Germany.

Chan, C.-Y., Jagadish, H. V., Tan, K.-L., Tung, A. K. H., and Zhang, Z. (2006). Finding k-dominant skylines in high dimensional space. In ACM SIGMOD International Conference on Management of Data, pages 503–514, Chicago, USA.

de Amo, S. and Bueno, M. L. P. (2011). Continuous processing of conditional preference queries. In SBBD, Florianópolis, Brasil.

de Amo, S. and Giacometti, A. (2007). Temporal conditional preferences over sequences of objects. In ICTAI, pages 246–253, Patras, Greece.

de Amo, S. and Ribeiro, M. R. (2009). CPref-SQL: A query language supporting conditional preferences. In ACM SAC, pages 1573–1577, Honolulu, Hawaii, USA.

Kontaki, M., Papadopoulos, A. N., and Manolopoulos, Y. (2012). Continuous top-k dominating queries. IEEE Trans. on Knowledge and Data Eng. (TKDE), 24(5):840–853.

Lin, X., Yuan, Y., Wang, W., and Lu, H. (2005). Stabbing the sky: Efficient skyline computation over sliding windows. In ICDE, pages 502–513, Tokyo, Japan.

Petit, L., de Amo, S., Roncancio, C., and Labbé, C. (2012). Top-k context-aware queries on streams. In DEXA, pages 397–411, Vienna, Austria.

Ribeiro, M. R., Barioni, M. C. N., de Amo, S., Roncancio, C., and Labbé, C. (2017a). Reasoning with temporal preferences over data streams. In FLAIRS, Marco Island, USA.

Ribeiro, M. R., Barioni, M. C. N., de Amo, S., Roncancio, C., and Labbé, C. (2017b). Temporal conditional preference queries on streams. In International Conference on Database and Expert Systems Applications (DEXA), Lyon, France.

Ribeiro, M. R., Pereira, F. S. F., and Dias, V. V. S. (2016). Efficient algorithms for processing preference queries. In ACM SAC, pages 972–979, Pisa, Italy.

Santoso, B. J. and Chiu, G.-M. (2014). Close dominance graph: An efficient framework for answering continuous top-dominating queries. IEEE Transactions on Knowledge and Data Engineering (TKDE), 26(8):1853–1865.

Tao, Y. and Papadias, D. (2006). Maintaining sliding window skylines on data streams. IEEE TKDE, 18(3):377–391.

Yiu, M. L. and Mamoulis, N. (2007). Efficient processing of top-k dominating queries on multi-dimensional data. In International Conference on Very Large Data Bases (VLDB), pages 483–494, Vienna, Austria.