Summary
In terms of a general time theory which addresses time-elements as typed point-based intervals, a formal characterization of time-series and state-sequences is introduced. Based on this framework, the subsequence matching problem is specially tackled by means of being transferred into bipartite graph matching problem. Then a hybrid similarity model with high tolerance of inversion, crossover and noise is proposed for matching the corresponding bipartite graphs involving both temporal and non-temporal measurements. Experimental results on reconstructed time-series data from UCI KDD Archive demonstrate that such an approach is more effective comparing with the traditional similarity model based algorithms, promising robust techniques for lager time-series databases and real-life applications such as Content-based Video Retrieval (CBVR), etc.
This research is supported in part by National Nature Science Foundation of China (No. 60772122).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Adjeroh, D., Lee, M., King, I.: A distance measure for video sequences. Computer Vision and Image Understanding 75(1-2), 25–45 (1999)
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, October 13-15, 1993, pp. 69–84 (1993)
Allen, J.: Towards a General Theory of Action and Time. Artificial Intelligence 23, 123–154 (1984)
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 (1990)
http://kdd.ics.uci.edu/databases/synthetic_control/synthetic_control.html
Keogh, E.: Exact indexing of dynamic time warping. In: Proc. of the 28th Int’l Conf. on Very Large Data Bases, Hong Kong, China, August 20-23, 2002, pp. 406–417 (2002)
Ma, J., Hayes, P.: Primitive Intervals Vs Point-Based Intervals: Rivals Or Allies? The Computer Journal 49(1), 32–41 (2006)
Ma, J., Bie, R., Zhao, G.: An ontological Characterization of Time-series and State-sequences for Data Mining. In: Proc. of the 5th International Conference on Fuzzy Systems and Knowledge Discovery, Jinan, Shandong, October 18-20, 2008, pp. 325–329 (2008)
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, June 4-6, 2002, pp. 382–393 (2002)
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 (2001)
Shanahan, M.: A Circumscriptive Calculus of Events. Artificial Intelligence 77, 29–384 (1995)
Shao, J., Huang, Z., Shen, H., Zhou, X., Lim, E., Li, Y.: Batch nearest neighbor search for video retrieval. IEEE Transactions on Multimedia 10(3), 409–420 (2008)
Shen, H., Shao, J., Huang, Z., Xiaofang, Z.: Effective and Efficient Query Processing for Video Subsequence Identification. IEEE Transactions on Knowledge and Data Engineering 21(3), 321–334 (2009)
Shier, D.: Matchings and assignments. In: Gross, J.L., Yellen, J. (eds.) Handbook of Graph Theory, pp. 1103–1116. CRC Press, Boca Raton (2004)
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, February 26 - March 1, 2002, pp. 673–684 (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Zheng, A., Ma, J., Petridis, M., Tang, J., Luo, B. (2009). A Robust Approach to Subsequence Matching. In: Lee, R., Ishii, N. (eds) Software Engineering Research, Management and Applications 2009. Studies in Computational Intelligence, vol 253. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-05441-9_4
Download citation
DOI: https://doi.org/10.1007/978-3-642-05441-9_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-05440-2
Online ISBN: 978-3-642-05441-9
eBook Packages: EngineeringEngineering (R0)