On the Complexity of Mining Temporal Trends
Jozef Wijsen, Robert Meersman · 1997
We investigate the computational complexity of mining certain trends in temporal databases. A simple example of such trend might be "In general, salaries of employees do not decrease." The trends considered are formalized by the construct of trend dependency (TD). TD's can compare attributes over time by using operators of f!; =;?;; 6=g. TD satisfaction is characterized by a support and confidence. As TD's may express meaningful trends, mining them is significant. The TD mining problem studied is the following task: Given a temporal database, find the TD of a specified form that holds with the highest confidence and with support greater than or equal to a specified minimum threshold. This problem is called TDMINE. Unlike most other work in data mining, we primarily focus on the computational complexity of the TDMINE problem---rather than on the performance of algorithms to solve it. Both the number of tuples (cardinality) and the number of attributes can be taken as the "size" of TDMIN...