Remember Me
Or use your Academic/Social account:


Or use your Academic/Social account:


You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.


Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message


Verify Password:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Zheng, Aihua (2012)
Languages: English
Types: Doctoral thesis
Subjects: QA
Time-series and state-sequences are ubiquitous patterns in temporal logic and are widely used to present temporal data in data mining. Generally speaking, there are three known choices for the time primitive: points, intervals, points and intervals. In this thesis, a formal characterization of time-series and state-sequences is presented for both complete and incomplete situations, where a state-sequence is defined as a list of sequential data validated on the corresponding time-series. In addition, subsequence matching is addressed to associate the state-sequences, where both non-temporal aspects as well as rich temporal aspects including temporal order, temporal duration and temporal gap should be taken into account.\ud \ud Firstly, based on the typed point based time-elements and time-series, a formal characterization of time-series and state-sequences is introduced for both complete and incomplete situations, where a state-sequence is defined as a list of sequential data validated on the corresponding time-series. A time-series is formalized as a tetrad (T, R, Tdur, Tgap), which denotes: the temporal order of time- elements; the temporal relationship between time-elements; the temporal duration of each time-element and the temporal gap between each adjacent pair of time-elements respectively.\ud \ud Secondly, benefiting from the formal characterization of time-series and state-sequences, a general similarity measurement (GSM) that takes into account both non-temporal and rich temporal information, including temporal order as well as temporal duration and temporal gap, is introduced for subsequence matching. This measurement is general enough to subsume most of the popular existing measurements as special cases. In particular, a new conception of temporal common subsequence is proposed. Furthermore, a new LCS-based algorithm named Optimal Temporal Common Subsequence (OTCS), which takes into account rich temporal information, is designed. The experimental results on 6 benchmark datasets demonstrate the effectiveness and robustness of GSM and its new case OTCS. Compared with binary-value distance measurements, GSM can distinguish between the distance caused by different states in the same operation; compared with the real-penalty distance measurements, it can filter out the noise that may push the similarity into abnormal levels.\ud \ud Finally, two case studies are investigated for temporal pattern recognition: basketball zone-defence detection and video copy detection.\ud \ud In the case of basketball zone-defence detection, the computational technique and algorithm for detecting zone-defence patterns from basketball videos is introduced, where the Laplacian Matrix-based algorithm is extended to take into account the effects from zoom and single defender‘s translation in zone-defence graph matching and a set of character-angle based features was proposed to describe the zone-defence graph. The experimental results show that the approach explored is useful in helping the coach of the defensive side check whether the players are keeping to the correct zone-defence strategy, as well as detecting the strategy of the opponent side. It can describe the structure relationship between defender-lines for basketball zone-defence, and has a robust performance in both simulation and real-life applications, especially when disturbances exist.\ud \ud In the case of video copy detection, a framework for subsequence matching is introduced. A hybrid similarity framework addressing both non-temporal and temporal relationships between state-sequences, represented by bipartite graphs, is proposed. The experimental results using real-life video databases demonstrated that the proposed similarity framework is robust to states alignment with different numbers and different values, and various reordering including inversion and crossover.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • [1] Adjeroh D, Lee M & King I.: A distance measure for video sequences. Computer Vision and Image Understanding. 75(1-2), 1999, pp: 25-45.
    • [2] Agrawal R, Faloutsos C, & Swami A.: Efficient similarity search in sequence databases. In Proc. of the 4th Int'l Conf. on Foundations of Data Organization and Algorithms, Chicago, Illinois, USA , Oct 13-15, 1993, pp:69-84.
    • [3] Allen J.: Towards a General Theory of Action and Time. Artificial Intelligence 23, 1984, pp:123-154.
    • [4] Beckmann N, Kriegel H, Schneider R & Seeger B.: The r*-tree: An efficient and robust access method for points and rectangles. In Proc. of the 1990 ACM SIGMOD Int'l Conf. on Management of Data, Atlantic City, NJ, May 23-25, 1990. pp:322-331.
    • [5] http://kdd.ics.uci.edu/databases/synthetic_control/synthetic_control.html
    • [6] Keogh E.: Exact indexing of dynamic time warping. in Proc. of the 28th Int'l Conf. on Very Large Data Bases, Hong Kong, China, Aug20-23, 2002, pp:406-417.
    • [7] Ma J & Hayes P.: Primitive Intervals Vs Point-Based Intervals: Rivals Or Allies?. the Computer Journal, 49(1), 2006, pp:32-41.
    • [8] Ma J, Bie R, Zhao G.: An ontological Characterization of Time-series and State-sequences for Data Mining. Proc. of the 5th International Conference on Fuzzy Systems and Knowledge Discovery, Jinan, Shandong, Oct 18-20, 2008, pp:325-329.
    • [9] Moon Y, Whang K & Han W.: General Match A Subsequence Matching Method in Time-Series Databases Based on Generalized Windows. In Proc. of the 8th ACM SIGMOD Int'l Conf. on Management of data, Madison, Wisconsin, USA, Jun 4-6, 2002, pp:382 - 393.
    • [10] Moon Y, Whang K & Loh W.: Duality-based subsequence matching in time-series databases. In Proc. of the 17th Int'l Conf. on Data Engineering, Santa Barbara, California, May 21-24, 2001, pp: 263-272.
    • [11] Shanahan M.: A Circumscriptive Calculus of Events. Artificial Intelligence 77, 1995, pp:29-384.
    • [12] Shao J, Huang Z, Shen H, Zhou X, Lim E & Li Y.: Batch nearest neighbour search for video retrieval. IEEE Transactions on Multimedia, 10(3), 2008, pp:409-420.
    • [13] Shen H, Shao J, Huang Z & Xiaofang Zhou.: Effective and Efficient Query Processing for Video Subsequence Identification. IEEE Transactions on Knowledge and Data Engineering, 21(3), 2009, pp:321-334.
    • [14] Shier D.: Matchings and assignments. in Handbook of Graph Theory, J. L. Gross and J. Yellen, Eds. CRC Press, 2004, pp:1103-1116.
    • [15] Vlachos M, Gunopulos D & Kollios G.: Discovering similar multidimensional trajectories. In Proc. of the 18th Int'l Conf. on Data Engineering, San Jose, CA,USA, Feb 26-Mar 1 2002, pp:673-684.
    • J. Allen. ―Towards a General Theory of Action and Time‖, Artificial Intelligence, 23, pp:123-154, 1984.
    • M. Shanahan. ―A Circumscriptive Calculus of Events‖, Artificial Intelligence, 77, pp:29-384, 1995.
    • J. Ma, R. Bie, G. Zhao, ―An ontological Characterization of Time-series and State-sequences for Data Mining‖, Proc. of the 5th International Conference on Fuzzy Systems and Knowledge Discovery (FSKD'08), IEEE Press, Oct. pp:325-329, 2008.
  • No related research data.
  • Discovered through pilot similarity algorithms. Send us your feedback.

Share - Bookmark

Cite this article