Fast Mining of Complex Time-Stamped Events

Given a collection of complex, time-stamped events, how do we find patterns and anomalies? Events could be meetings with one or more persons with one or more agenda items at zero or more locations (e.g., teleconferences), or they could be publications with authors, keywords, publishers, etc. In such settings, we want to solve the following problems: (1) find time stamps that look similar to each other and group them; (2) find anomalies; (3) provide interpretations of the clusters and anomalies by annotating them; (4) automatically find the right time-granularity in which to do analysis. Moreover, we want fast, scalable algorithms for all these problems. We address the above challenges through two main ideas. The first (T3) is to turn the problem into a graph analysis problem, by carefully treating each time stamp as a node in a graph. This viewpoint brings to bear the vast machinery of graph analysis methods (PageRank, graph partitioning, proximity analysis, and CenterPiece Subgraphs, to name a few). Thus, T3 can automatically group the time stamps into meaningful clusters and spot anomalies. Moreover, it can select representative events/persons/locations for each cluster and each anomaly, as their interpretations. The second idea (MT3) is to use temporal multi-resolution analysis (e.g., minutes, hours, days). We show that MT3 can quickly derive results from finer-to-coarser resolutions, achieving up to 2 orders of magnitude speedups. We verify the effectiveness as well as efficiency of T3 and MT3 on several real datasets.