Note on:

     "Discovering Temporal Patterns in Multiple Granularities",
     Yingjiu Li, X. Sean Wang, Sushil Jajodia,
     International Workshop on Temporal, Spatial and Spatio-Temporal
     Data Mining, TSDM2000
     
I do not have an electronic copy of this paper.

Other papers I've read by Wang and Jajodia:

      "Discovering Frequent Event Patterns with Multiple Granularities
      in Time Sequences"
      
      "Discovering Calendar-based Temporal Association Rules"

The authors note that temporal patterns occurring in an irregular span
of time "has to be captured with a use of granularities." That is if
say an event happened the first of every month for example, the number
of days between each event would be between 28 and 31 days and would
not be found as a pattern without the use of granularities. I would
say this is false. The pattern may be captured using a relative
temporal representation as well.

The paper's main concern is "given a set of events, how we can quickly
discover their repetition pattern in terms of multiple granularities."

The authors give another example of a pattern happening every
Monday. It doesn't quite fit into my current understanding of
granularities. See the Related presentation in the documents -
presentations section of this web site. Later they specify a pattern
" which specifies the first day of each
month in the year 2000. In this context the previous examples make
sense. 

All the input needed in the algorithms presented in this paper can be
thought of as a template. Given a calendar expression, such as shown above,
a constraint such as , and a
data set of time-stamped events, the search space of all
patterns becomes small enough to search efficiently. An important note
which the authors echo in the conclusion section of the paper is that
the events in the patterns to look for are specified by the user. This
makes the template formed by the input very restrictive.

The authors propose Proposition 1 which seems a rewording of the
Apriori Principle made to fit the calendar expression definition they
use. A Proposition 2 also seems a rewording for a different point of
view of what to prune.

A rooted tree structure for storing the data set compactly is
introduced. It maps the multiple granularities of the valid calendar
expression and stores counts of the events that occur along that time
line. To count support one simply sums the counts for the events in
the appropriate nodes of the tree. though it takes time to build this
structure and memory to store it, the time benefits of scanning the
database once are obvious. Might ASAS benefit from such a data
structure? Instead of a single time line and multiple granularities
ASAS deals with many time lines, as many as there are instances in the
data set. So how could we store the counts of events happening? We
might consider using a data structure to represent the different
temporal relationships possible between events. Different level of the
tree might represent different numbers of events in a single item
set. With one event, no temporal relationship need be expressed. With
two events there are thirteen relationships, hence thirteen root nodes
of the tree. To build the second level of the tree the number of event
represented increments by one. How many different temporal relations
can that one new event have with the other two event already
represented in the first level? It depends on the temporal
relationship expressed at the node we are building the child nodes
for. The process is the same as generating candidates item sets in
ASAS. See the explanation provided in the Thesis Report for details,
or the code for implementation. How deep to build the tree? To
represent the entire data set it may be very deep. How to avoid
scanning the data set again for regular items? How to efficiently use
the tree for checking support for a particular pattern? Could we avoid
generating candidates altogether and simply walk the tree looking for
frequent item sets?

The size of the data sets used to test the three proposed algorithms
are large enough to be comparable to data sets used in ASAS. 

The authors note how the algorithms perform linearly as the size of
the input data grows, even exponentially. This seems to be an expected
outcome since the tree in which the data set is stored does not change
its size in terms of number of nodes with the size of the data set but
rather with the calendar expression used.