Temporal Evolution of Complex Data

• Isis Caroline Oliveira de Sousa Fogaça Universidade Federal de São Carlos
• Renato Bueno Universidade Federal de São Carlos

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

Resumo

Monitoring the temporal evolution of data is essential in many areas of application of databases, such as medicine, agriculture and meteorology. Complex data are usually represented in metric spaces, where only the elements and the distances between them are available, which makes it impossible to represent trajectories considering a temporal dimension. In this paper we propose to map the metric data to multidimensional spaces so that we can estimate the element's status at a given time, based on known states of the same element. As it is not possible to create the complex data equivalent to its estimated position, we propose to apply similarity queries using this position as query center. We evaluated three types of similarity queries: k-NN, kAndRange and kAndRev.

Palavras-chave: Temporal databases, complex data, similarity queries

Referências

Arantes, A., Vieira, M., Traina Jr., C., and Traina, A. (2004). Efficient algorithms to execute complex similarity queries in RDBMS. J. Braz. Comp. Soc., 9:5–24.

Bueno, R., Kaster, D. S., Traina, A. J. M., and Traina Jr., C. (2009). Time-aware similarity search: a metric-temporal representation for complex data. In 11th International Symposium on Advances in Spatial and Temporal Databases (SSTD 2009), pages 302–319, Aalborg, Denmark. Springer.

Bustos, C., Navarro, G., Reyes, N., and Paredes, R. (2015). An empirical evaluation of intrinsic dimension estimators. In Similarity Search and Applications, pages 125–137, Cham. Springer International Publishing.

Chávez, E., Navarro, G., Baeza-Yates, R., and Marroqu´ın, J. L. (2001). Searching in metric spaces. ACM Comput. Surv., 33(3):273–321.

Cox, M. A. A. and Cox, T. F. (2008). Multidimensional Scaling, pages 315–347. Springer Berlin Heidelberg, Berlin, Heidelberg.

Faloutsos, C. and Lin, K.-I. (1995). Fastmap: A fast algorithm for indexing, data-mining and visualization of traditional and multimedia datasets. SIGMOD Rec., 24(2):163– 174.

Geusebroek, J., Burghouts, G. J., and Smeulders, A.W. M. (2005). The amsterdam library of object images. Int. J. Comput. Vis., 61(1):103–112.

Hjaltason, G. R. and Samet, H. (2003). Properties of embedding methods for similarity searching in metric spaces. IEEE Transactions on Pattern Analysis and Machine Intelligence, 25(5):530–549.

Sousa, E. P. M., Traina Jr., C., Traina, A. J. M., Wu, L., and Faloutsos, C. (2007). A fast and effective method to find correlations among attributes in databases. Data Min. Knowl. Discov., 14(3):367–407.

Tao, Y., Yiu, M. L., and Mamoulis, N. (2006). Reverse nearest neighbor search in metric spaces. IEEE Trans. on Knowl. and Data Eng., 18(9):1239–1252.

Traina Jr., C., Filho, R. F. S., Traina, A. J. M., Vieira, M. R., and Faloutsos, C. (2007). The omni-family of all-purpose access methods: a simple and effective way to make similarity search more efficient. VLDB J., 16(4):483–505.

Traina Jr., C., Traina, A. J. M., and Faloutsos, C. (2000). Distance exponent: A new concept for selectivity estimation in metric trees. In 16th International Conference on Data Engineering, San Diego, California, USA, page 195. IEEE Computer Society.

Vieira, M. R., Traina Jr., C., Traina, A. J. M., Arantes, A. S., and Faloutsos, C. (2007). Boosting k-nearest neighbor queries estimating suitable query radii. In 19th International Conference on Scientific and Statistical Database Management, SSDBM, page 10. IEEE Computer Society.