*by Maja Dimitrijevic (joint work with Raymond Ng)*

By discovering patterns in 2D motion trajectories, the user may gain a better understanding of the object flow in time and space, or be able to predict future movements of the objects. We analyze 2D motion trajectories of hockey player teams, acquired by a semi-automatic tracking system developed in the LCI lab. Expecting that the hockey player trajectories should not be random, and the trajectories of the players of the same or opposing teams should be correlated, our goal is to discover patterns that contain trajectory segments of different players, occurring frequently in the same game, satisfying certain time constraints.

I will present the algorithm that we use for finding such patterns of maximal length. The algorithm grows the patterns level-wise, in the manner similar to sequential pattern finding in conventional transaction databases. However, instead of a boolean function, determining whether an item contained in a pattern belongs to a database transaction or not, we allow a pattern to belong to a transaction with a certain degree. This degree is defined with respect to the similarity measure between the trajectory segment related to the item and corresponding part of a trajectory in the database transaction.

I will show some of our results, including samples of discovered patterns, as well as experimental evaluation of the algorithm efficiency.