时间序列挖掘和相似性查找技术的研究
|
摘要
时间序列(Time Series)是一种重要的数据对象，在现实生活中的许多领域中都广泛存在，如股票价格，商品销售数据，气象数据等等。随着时间推移，这类数据的存储规模呈现爆炸式地增长。因此，对这些海量的时序数据如何进行有效的知识发现，挖掘其内在的各种变化模式；对于用户给定具有各种抽象含义的变化模式，如何在海量时间序列库中进行相似性的检索等应用分析，是一个挑战性的、具有重要意义的理论和实际应用课题，对于我们正确认识事物变化，科学进行决策，识别各种异常行为等具有重要的指导意义。
本文在分析时间序列特点和实际应用需求的基础上，针对时间序列的挖掘与相似性查找一些关键技术进行了研究，具体包括特征模式挖掘、多序列关联模式挖掘、相似性模式查找等方面，所做的工作和取得的创新成果体现在以下三个方面：
1)时间序列特征模式挖掘研究
首次提出了一种基于互关联后继树模型的时序特征模式挖掘方法。不同于传统处理模式，该方法在序列分段上，采用了一种新颖的、基于重要点的时间序列线段化算法；再符号化过程中，采用基于相对斜率的局部符号化方法。既减少计算复杂度，又避免了噪声的影响。在挖掘算法实现上，根据序列特征模式的有序性和重复性，提出了一种无须生成大量的候选模式集的互关联后继树挖掘算法，极大地提高了挖掘效率。实验结果表明，挖掘结果不仅是一种图形化的描述，而且还具有明确的实际含义，大大有利于在实际中的应用。
2)多时间序列间关联模式挖掘研究
针对更有分析价值的多序列关联模式，进一步提出一种新颖的关联模式挖掘方法。该方法利用Allen区间逻辑关系来描述时间序列模式的关联关系，避免了传统方法在关联关系描述的上非同步性；然后通过时间观测窗口，来构造出一种包含并行模式和串行模式的特殊形式模式序列；最后，在此基础上构造一种广义的互关联后继树模型，然后用前面挖掘思路实现关联模式的挖掘。实验结果显示，该新方法比传统的Apriori算法具有更好的挖掘效率和挖掘效果。
3)时间序列相似性查找研究
分析比较了根据时间序列与全文序列的异同，采用了全文索引技术，首次提出了一种基于互关联后继树的时间序列相似性查找方法。该方法提出通过基于
摘要
重要点分段技术的分段动态挖掘距离作为相似性度量，既保证了度量的鲁棒性，
又减少计算复杂度;利用各个分段的抽取六个主要特征，将时间序列转化成一种
特定的符号序列，在此基础上利用海量全文索引结构实现了相似性的索引查找。
在理论上证明了该方法不仅保证索引查找的结果不会出现任何错误的丢失，而且
在实验结果上也显示该方法比传统的方法具有明显的优势。
Time series is a kind of important data existing in a lot of fields, such as stock, weather, etc. With time moving, this data of time series will explode increasing. So it is important and challenging subject to research how discovery valuable knowledge in large-scale time series database, and how to search based similarity while user give a graphic query pattern. These researches will help us to discover changing or developing principle of things, support to decision-making, etc.
The thesis addresses several key technical problems of pattern mining and its search based similarity in time series, which covers feature patterns and relationship patterns mining, pattern search based similarity in time series and stream time series and issues concerning application system implementation oriented to analysis. Major contributions of this thesis include:
1. Research of mining feature patterns in time series
A novel method is proposed to discovery frequent pattern from time series. Different to exiting methods, it first segments time series based on a series of perceptually important points, and then time series are converted into meaningful symbols sequences in terms of domain knowledge and the relative scope of each linear segment. After that, we designed a new data model, called Inter-Related Successive Trees IRST, to find frequent patterns from multiple time series without generation lots of candidate patterns. Experiment illustrates that the method is simpler and more flexible, efficient and useful, compared with the previous methods.
2. Research of Mining Relationship Patterns in Multiple Time Series
An algorithm for discovery frequent patterns in multiple time series will be proposed. In this algorithm, firstly the states relationship between in time series is represented to Allen temporal logic, then use a sliding windows to examine the order or occur relationship of states and obtain a particularly sequence. On the basis of the sequence, we developed a called GIRST model to achieve finding the frequent relationship patterns in multiple time series. Experiments shows, compared with the previous methods, the method is more simple, efficient and more applied value.
3. Research of similar search in time series
A novel method is proposed to fast search similar pattern in time series using full
text index technique. The method first segments time series based on a series of perceptually important points, use segment dynamic time warping distance as measurement, and then time series are converted into meaningful symbol sequences in terms of the segment's features and MATH categorization. After that, use above index model-IRST, to achieve fast similarity retrieval in multiple time series. The method is proved not any false dismiss in the theory and experiments show it has more efficient search and allows different lengths matching, compared with the previous methods.
本文在分析时间序列特点和实际应用需求的基础上，针对时间序列的挖掘与相似性查找一些关键技术进行了研究，具体包括特征模式挖掘、多序列关联模式挖掘、相似性模式查找等方面，所做的工作和取得的创新成果体现在以下三个方面：
1)时间序列特征模式挖掘研究
首次提出了一种基于互关联后继树模型的时序特征模式挖掘方法。不同于传统处理模式，该方法在序列分段上，采用了一种新颖的、基于重要点的时间序列线段化算法；再符号化过程中，采用基于相对斜率的局部符号化方法。既减少计算复杂度，又避免了噪声的影响。在挖掘算法实现上，根据序列特征模式的有序性和重复性，提出了一种无须生成大量的候选模式集的互关联后继树挖掘算法，极大地提高了挖掘效率。实验结果表明，挖掘结果不仅是一种图形化的描述，而且还具有明确的实际含义，大大有利于在实际中的应用。
2)多时间序列间关联模式挖掘研究
针对更有分析价值的多序列关联模式，进一步提出一种新颖的关联模式挖掘方法。该方法利用Allen区间逻辑关系来描述时间序列模式的关联关系，避免了传统方法在关联关系描述的上非同步性；然后通过时间观测窗口，来构造出一种包含并行模式和串行模式的特殊形式模式序列；最后，在此基础上构造一种广义的互关联后继树模型，然后用前面挖掘思路实现关联模式的挖掘。实验结果显示，该新方法比传统的Apriori算法具有更好的挖掘效率和挖掘效果。
3)时间序列相似性查找研究
分析比较了根据时间序列与全文序列的异同，采用了全文索引技术，首次提出了一种基于互关联后继树的时间序列相似性查找方法。该方法提出通过基于
摘要
重要点分段技术的分段动态挖掘距离作为相似性度量，既保证了度量的鲁棒性，
又减少计算复杂度;利用各个分段的抽取六个主要特征，将时间序列转化成一种
特定的符号序列，在此基础上利用海量全文索引结构实现了相似性的索引查找。
在理论上证明了该方法不仅保证索引查找的结果不会出现任何错误的丢失，而且
在实验结果上也显示该方法比传统的方法具有明显的优势。
Time series is a kind of important data existing in a lot of fields, such as stock, weather, etc. With time moving, this data of time series will explode increasing. So it is important and challenging subject to research how discovery valuable knowledge in large-scale time series database, and how to search based similarity while user give a graphic query pattern. These researches will help us to discover changing or developing principle of things, support to decision-making, etc.
The thesis addresses several key technical problems of pattern mining and its search based similarity in time series, which covers feature patterns and relationship patterns mining, pattern search based similarity in time series and stream time series and issues concerning application system implementation oriented to analysis. Major contributions of this thesis include:
1. Research of mining feature patterns in time series
A novel method is proposed to discovery frequent pattern from time series. Different to exiting methods, it first segments time series based on a series of perceptually important points, and then time series are converted into meaningful symbols sequences in terms of domain knowledge and the relative scope of each linear segment. After that, we designed a new data model, called Inter-Related Successive Trees IRST, to find frequent patterns from multiple time series without generation lots of candidate patterns. Experiment illustrates that the method is simpler and more flexible, efficient and useful, compared with the previous methods.
2. Research of Mining Relationship Patterns in Multiple Time Series
An algorithm for discovery frequent patterns in multiple time series will be proposed. In this algorithm, firstly the states relationship between in time series is represented to Allen temporal logic, then use a sliding windows to examine the order or occur relationship of states and obtain a particularly sequence. On the basis of the sequence, we developed a called GIRST model to achieve finding the frequent relationship patterns in multiple time series. Experiments shows, compared with the previous methods, the method is more simple, efficient and more applied value.
3. Research of similar search in time series
A novel method is proposed to fast search similar pattern in time series using full
text index technique. The method first segments time series based on a series of perceptually important points, use segment dynamic time warping distance as measurement, and then time series are converted into meaningful symbol sequences in terms of the segment's features and MATH categorization. After that, use above index model-IRST, to achieve fast similarity retrieval in multiple time series. The method is proved not any false dismiss in the theory and experiments show it has more efficient search and allows different lengths matching, compared with the previous methods.
引文
[ACD83]安鸿志，陈兆国，杜金观，潘一民，时间序列的分析与应用，科学出版社，1983年。
[AFS93] R. Agrawal, C. Faloutsos; and A. Swami. Efficient Similarity Search in Sequence Databases. In Int. Conference on Foundations of Data Organization (FODO) 1993.
[AI93] R. Agrawal, T. Imielinski, A. Swami. Mining association rules sets of items in large databases. Proceedings of the ACM SIGMOD Conference on Management of Data (SIGMOD'93). Washington, DC: ACM, 1993.
[A1183] J F Allen. Maintaining Knowledge About Temporal Intervals. Communications of ACM, 1983, 26(11): 823～843.
[AS95] Agrawal R, Srikant. Mining Sequential Patterns. In Proc.95 Int'1 Conf Data Engineering, Taibei, Taiwan, March, 5,1995.
[AS96] Agrawal R, Srikant R. Fast Discovery of Association Rules.In Fayyad.Ⅱ 1996
[AWS92] Ahlberg, C., Williamson, C., and Shneiderman, B., Dynamic queries for information exploration: An implementation and evaluation, Proc. ACM CHI'92: Human Factors in Computing Systems, 619-626, 1992.
[BC94] Donald J. Berndt, James Clifford. Using Dynamic Time Warping to Find Patterns in Time Series. KDD Workshop 1994.
[BDG98] Bela Bollobas, Gautam Das, Dimitrios Gunopulos and Heikki Mannila: Time Series Similarity Problems and Well-Separated Geometric Sets. 13~(th) Annual ACM Symposium on Computational Geometry 1998
[Bjo96] Bjorvand, A, T, Time series and rough sets, Master's thesis, Department of Computer Systems and Telematics, The Norwegian Institute of Technology 1996.
[BO93] B.L. Bowerman and R.T. Oconnel, Forcasting and Time Series: an Applied Approach, 3rd ed.Belmont, California:Duxbury Press, 1993
[BP85] C. Burrus and T. Parks. DFT/FFT and Convolution Algorithnas. John Wiley and Sons, 1985
[BW01] S. Babu and J. Widom. Continuous queries over data streams. In SIGMOD Record, Sept. 2001.
[BWJ97] C. Bettini, X. Wang, S. Jajodia, Satisfiability of Quantitative Temporal Constraints with Multiple Granularities. Third International Conference on
Principles and Practice of Constraint Programming (CP97), Schloss Hagenberg, Austria October 29-November 1, 1997.
[BWJ98a] C. Bettini, X. Wang, S. Jajodia, Mining Temporal Relationships with Multiple Granularities in Time Sequences, IEEE Data Engineering Bulletin, Volume 21 Number 1,1998
[BWJ98b] C. Bettini, X. Wang, S. Jajodia, A General Framework for Time Granularity and Its Application to Temporal Reasoning, Annals of Mathematics and Artificial Intelligence. Vol. 22. 1998.
[CC94] W. W. Chu, K. Chiang. Abstraction of High Level Concepts from Numerical Values in Databases. In Proceedings of the 11th AAAI Workshop on Knowledge Discovery in Databases, Las Vegas, 1994, 67～73.
[CDT00] J. Chen, D. J. Dewitt, F. Tian and Y. Wang. NiagaraCQ: a scalable continuous query system for Internet databases. In Proc. of the ACM. SIGMOD Conference, pages379-390, 2000.
[CDN02] J. Chen, D. J. Detitt, and J.F. Naughton. Design and evaluation of alternative selection placement strategies in optimizing continuous queries. In ICDE Conference, 2002
[CDZ97] 陈文伟，邓苏，张维明．数据开采与知识发现综述，计算机世界专题综述，1997， 6，30
[CF99] Chan, K. & Fu, A. W. (1999). Efficient time series matching by wavelets. In proceedings of the 15th IEEE Int'1 Conference on Data Engineering. Sydney, Australia, Mar 23-26. pp 126-133.
[CW99] K. K.W. Chu and M. H.Wong. Fast time-series searching with scaling and shifting. In PODS, Philedelphia, PA, 1999.
[DLM98] G. Das, K. Lin, H. Mannila, G. Renganathan, P. Smyth: Rule Discovery from Time Series.KDD 1998: 16-22.
[FCL01] T.C. Fu, F.L. Chung, R. Luk and V. Ng, "Pattern Discovery from Stock Time Series Using Self-Organizing Maps," Workshop Notes of KDD2001 Workshop on Temporal Data Mining, 26-29 Aug., San Francisco, pp.27-37, 2001.
[FL95] Christos Faloutsos, King-Ip Lin: FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets. SIGMOD Conference 1995: 163-174.
[FPS96] U.M.Fayyad, G.Piatetsky-Shapiro and P.Smyth, From data mining to knowledge discovery: An Overview. In U.M,Fayyad, G.Piatesky-Shapiro, et al eds, Advances in Knowledge Discovery and Data Mining, pp. 1-34, AAAI/MIT
Press, Menlo Park, Ca, 1996.
[Fra01] H Frank. Learning Temporal Rules from State Sequences. IJCAI Workshop on Learning from Temporal and Spatial Data. U.S.A. Seatle, 2001,45～51.
[FRM94] C. Faloutsos, M. Ranganathan, and Y. Manolopoulos. Fast Subsequence Matching in Time-Series Databases. In Proc. of 1994 ACM SIGMOD Int. Conf. on Management of Data.
[Fun73] Hunkhouser, H.G, Historical Development of the Graphical Representation of Statistical Data. Osiris. 3(1): 269-405. Reprinted Brugge, Belgium; St. Catherine Press 1937.
[FXJ00] 深圳汇天奇电脑有限公司，分析家证券投资分析系统3．0使用说明书，2000。
[GD01] Dimitros Gunopulos,Gautam Das. Time Series Similarity Measure: In Proceedings of the 2001 ACM SIGMOD International Conference on Management of Data, 2001.
[Gib93] Gibson, W. MIMSY: A System for Analyzing Time Series Data in the Stock Market Domain. Master's thesis, University of Wisconsin, Dept. of Computer Science, 1993
[GK95] Dina Q. Goldin, Paris C. Kanellakis. On Similarity Queries for Time-Series Data: Constraint Specification and Implementation. CP 1995.
[GLM99] L. Gyorfi, G. Lugosi and G. Morvai. A simple randomized algorithm for sequential prediction of ergodic time series. IEEE Transactions on Information Theory, 45(7): 2642-2650, 1999.
[GSB01] T. V. Gestel, J. Suykens, D. E. Baestaens,.A. Lamberechts, G. Lanckriet, B. Vandaele, D. B. Moor, and J. Vandewalle. Financial time series prediction using least squares Suport Vector Machines within the evidence framework. IEEE Transactions on Neural Network, 12(4): 809-821, 2001.
[GT92] Granger. C. W. J and Terasvirta, T. Modelling Nonlinear Economic Relationships, Oxford University Press, Oxford, 1992.
[GW02] Like Gao, X. Scan Wang Continually Evaluating Similarity Based Pattern Queries on a Streaming Time Series In SIGMOD Conference, 2002.
[Het03] Magnus Lie Hetland. A survey of recent methods for efficient retrieval of similar time sequences. To appear in Mark Last, Abraham Kandel, and Horst Bunke, editors, Data Mining in Time Series Databases. World Scientific, 2003.
[HK01] J. Han and M. Kamber. Data mining: concepts & techniques. Morgan
Kaufmann Publishers, 2001
[HM99] Hunter, J. & McIntosh, N. Knowledge-based event detection in complex time series data. Artificial Intelligence in Medicine. pp. 271-280. Springer. 1999
[Hop01] F. Hoppner. Learning Temporal Rules from State Sequences. IJCAI Workshop on Learning from Temporal and Spatial Data Seatle, August 2001.
[HP97] Heikki Mannila and Pirjo Ronkainen, Similarity of Event Sequences. In Proceedings of the Fourth International Workshop on Temporal Representation and Reasoning (TIME/97), May 1997, Daytona Beach, Florida, USA., pp.136-139.
[HS01] H. Hochheiser and B. shneiderman. Interactive exploration of time-series data. In Proc. Discovery Science 4~(th) International conference 2001, editors (Jantke, K.P. and Shinohara, A.), springer-Verlag, Berlin, pp 441-446.
[Hu02] 胡运发．互关联后继树——一种新型全文数据库数学模型．技术报告．复旦大学计算机有信息技术系．2002．3
[JD88] Jain, A, K. and Dubes, R. C. Algorithms for Clustering Data, Englewood Cliffs, NJ: Prentice-Hall. 1988.
[KCH02] Eamonn Keogh, Selina Chu, David Hart and Michael Pazzarfi An Online Algorithm for Segmenting Time Series
[Keo01] Eamonn Keogh, A Tutorial on Indexing and Mining Time Series Data in The 2001 IEEE International Conference on Data Mining November 29, San Jose
[Keo97] Keogh, E. Fast similarity search in the presence of longitudinal scaling in time series database, In Proceedings of the 9~(th) International Conference on Tools with Artificial Intelligence. pp.578-584. IEEE Press 1997
[KK96] Julian Kulkarn, Richark King. Business Intelligence Systems and Data Mining. ASAS Institute White Paper. 1996
[KL99] I. Kim and S. R. Lee. A fuzzy time series prediction method based on consecutive values. In Fuzzy Systems Conferences Proceedings, Vol. 2, 703-707
[KP00] Keogh & Pazzani, Scaling up Dynamic Time Warping for Datamining Applications. In 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Boston, 2000.
[KP98] Eamonn J. Keogh, Michael J. Pazzani: An Enhanced Representation of Time Series Which Allows Fast and Accurate Classification, Clustering and Relevance Feedback. KDD 1998: 239-243.
[KP98] Eamonn J. Keogh, Michael J. Pazzani: An Enhanced Representation of Time Series Which Allows Fast and Accurate Classification, Clustering and Relevance Feedback. KDD 1998: 239-243.
[KP99] Keogh & Pazzani. Relevance feedback retrieval of time series. The 22th International ACM-SIGIR Conference on Research and Development in Information Retrieval, 1999.
[KPC01] S.-W Kim, S. Park, W. Chu. An Index-Based Approach for Similarity Search Supporting Time Warping in Large Sequence Databases. ICDE 2001.
[KR90] Kaufman, L., and Rousseauw, P. J. Finding Groups in Data: An Introduction to Cluster Analysis John Wiley and Sons 1990.
[KS01] T. Kahveci and A. Singh. Variable length queries for time series data. In ICDE, Heidelberg, Germany, 2001.
[KS97] Eamonn J. Keogh, Padhraic Smyth: A Probabilistie Approach to Fast Pattern Matching in Time Series Databases. KDD 1997: 24-30,
[LPBZ96] L. Liu, C. Pu, R. S. Barga, and T. Zhou. Differential evaluation of continual queries. In International Conference on Distributed Computing Systems, pages 458-465,1996.
[LPT99] L. Liu, C. Pu, and W. Tang. Continual queries for Internet scale event-driven information delivery. IEEE TKDE, 11 (4):610-628,1999
[LTX02]李斌，谭立湘，解光军，李海鹰，庄镇泉，非同步多时间序列中频繁模式的发现算法，软件学报，13(03)410-416，2002
[LTZ00] 李斌，谭立湘，章劲松等，面向数据挖掘的时间序列符号化方法研究，电路与系统学报，2000,5(2)；9-14．
[MF02] S. Madden and M. J. Franklin. Fjording the stream: An architecture for queries over streaming sensor data. In ICDE Conference, 2002
[MTV94] Mannila H, Toivonen H, Inkeri Verkamo A. Efficient algorithms for discovery association rules. In; Proceedings of AAAI Workshop on Knowledge Discovery in Database July 1994. 181-192
[MTV95] H. Mannila, H. Toivonen, and A. I. Verkamo, Discovering Frequent episodes in Sequences. In Proc. Of KDD-95, pp210-215, Montreal, Canada, Aug,1995.
[MXZ01] 马志锋，邢汉承，郑晓妹，一种基于Rough集的时间序列数据挖掘策略，系统工程理论与实践2001年12期
[NHH98] Ng.M.K., Huang, Z., and Hegland. M. Data-mining massive time series
astronomical data sets-a case study. Proceedings of the 2~(nd) Pacific-Asia Conference on Knowledge Discovery and Data Mining, 401-402, Melbourne, Australia.
[OC96] Oates, T., Cohen, P.R. Searching for structure in multiple streams of data. In: Proceedings of the 13~(th) International Conference on Machine Learning. Morgan Kaufmann Publishers, Inc., 1996
[OS75] A. Oppenheim and R.Schafer. Digital Signal Processing, Prentice-Hall, Inc., 1975
[PF98] Povinelli, R. J. and Feng, X., Temporal Pattern Identification of Time Series Data Using Pattern Wavelets and Genetic Algorithms, Artificial Neural Networks in Engineering, St. Louis, Missouri, 691-696.
[PG00] S. Poliker and A. Geva. A new algorithm for time series prediction by temporal fuzzy clustering. In Proceedings. 15~(th) International Conference on Pattern Recognition, vol. 2, 728-731, 2000
[PKC01] K. Par, S. Kim, W. Chu. Segment-Based Approach for Subsequence Searches in Sequence Databases, In proceedings of the 16th ACM Symposium on Applied Computing. Las Vegas, NV, 2001,248～252.
[PKW01] Park, S., Kim, S. W., & Chu, W. W.. Segment-Based Approach for Subsequence Searches in Sequence Databases, To appear in Proceedings of the 16th ACM Symposium on Applied Computing.2001.
[PLC99] Park, S. & Lee, D., & Chu, W. W. Fast Retrieval of Similar Subsequences in Long Sequence Databases", Proceedings of the 3rd IEEE Knowledge and Data Engineering Exchange Workshop. 1999
[PMC] D.S. Parker, R.R. Muntz and H.L. Chau. The tangram stream query processing system. In ICDE Conference, 1999.
[Pou00] A. D. Poularikas, editor. The transforms and applications handbook. CRC Press LLC, 2000
[Pov99] Povinelli, R. J. Time Series Data Mining: Identifying Temporal Patterns for Characterization and Prediction of Time Series Events, PhD Dissertation, Marquette University, Milwaukee, 1999
[PW83] S.M.Pandit and S.M. Wu, Time series and System Analysis,With applications. New York: Wiley, 1983.
[PWZ00] C.-S. Perng, H. Wang, S. R. Zhang, D. Stott Parker Landmarks: a New Model for Similarity-based Pattern Querying in Time Series Databases, ICDE
2000.
[Qiu97] 邱一平，股林高手，复旦大学出版社，1997。
[QL03] Qianlong, http://www.qianlong.com.cn.
[RJ93] L. Rabinar, B.H. Juang. Fundamentals of Speech Recognition. Prentice Hall, 1993.
[RM98] D. Rafiei and Alberto Mendelzon, Efficient Retrieval of Similar Time Sequences Using DFT FODO'98 Conference, Kobe, Japan, November 1998.
[RM98] D. Rafiei and Alberto Mendelzon, Efficient Retrieval of Similar Time Sequences Using DFT FODO'98 Conference, Kobe, Japan, November 1998.
[Sha95] Shatkay, H.. Approximate Queries and Representations for Large Data Sequences. Technical Report cs-95-03, Department of Computer Science, Brown University. 1995
[Spo03] Spotfire. http://www.sporfirecom.
[SZ92] Szladow, A. J.& Ziarko, W, Knowledge-based process control using rough sets, in S.Y. Huang, ed., 'Intelligent Decision Support: Handbook of Applications and Advances of the Rough Set Theory', Kulwer Academic Publishers, chapter 4, 49-60,
[TAA01] Tamer Kahveci, Ambuj K. Singh and Aliekber Gurel. Shift and Scale Invariant Search of Multi-Attribute Time Sequences, Technical Report TRCS01-09, University of California, Santa Barbara, 2001
[TAA02] Kahveci, T., Singh, A. & Gurel, A. An efficient index structure for shift and scale invariant search of multi-attribute time sequences. In proceedings of the 18th Int'1 Conference on Data Engineering, poster paper. San Jose, CA, Feb 26-Mar 1.2002
[TB81] Tiao, G. C. and Box ,G. E.P., Modeling Multiple time series with application, Journal of America Statistiacl Association, vol 76,802-716 1981.
[TGN92] D. Terry. D. Goldberg, D. Nichols and B. Oki. Continuous queries over append-only databases. In Proc. of the ACM SIGMOD Conf. On Management of Data, pages 321-330,1992.
[TKR95] Hannu Toivonen, Mika Klemettinen,Pirjo Ronkaine et.al.Pruning and grouping disovered association Rules In:Mlnet Workshop on Statistics,Machine Learning and Discovery in Database. Heraklion, Crete, April 1995.
[TM99] Bozkaya, T. and Ozsoyoglu, Z.M., "Indexing Large Metric Spaces for
Similarity Search Queries", ACM TODS, 1999.
[TT91] Tiao, G C and Tsay, R.S., Some Advances in Nonlinear and Adaptive Modeling in Time Series Analysis, Technical Report #118, Graduate School of Business, The University of Chicago.
[Tuf83] Tufte, E. The Visual Display of Quantitative Information. Graphics Press. Cheshire, Connecticut. 1983.
[Wei90] Wei, W. W. S, Time Series Analysis: Univariate and Multivariate Methods Addison-Wesley publishing Company, Iac, 1990
[Win77] S. Winograd. Some bilinear forms whose multiplicative complexity depends on the field of constants. Mathematical Systems Theory, 10:169-180,1977.
[WQ99] Welch, D and Quinn, P. http://www.macho.mcmaster.ea/project/overview/status.html, 1999
[WS01] Wattenbeg, M. Sketching a Graph to Query a Time Series Database. In Proceedings of CHI 2001 (Seattle WA, April 2001) ACM Press,2001
[WTL01] L. Wang, K. K. Teo, and Z. Lin. Predicting time series with Wavelet packet neural networks. Proc. International Joint Conference on Neural Networks,3: 1393-1597,2001.
[WW00] Wang, C. & Wang, S.. Supporting content based searches on time Series via approximation. Proceedings of the 12th International Conference on Scientific and Statistical Database Management.2000
[WZZ96] 王耀动，张德远，张海雄，经济时间序列分析，上海财经大学出版社，1996年。
[YC98] Li, C,. Yu, P. & Castelli V.. MALM: A framework for mining sequence database at multiple abstraction levels. Proceedings of the 9th International Conference on Information and Knowledge Management. Pp 267-272.1998.
[YJF98] B. Yi, H.V. Jagadish, C.Faloutsos. Efficient Retrieval of Similar Time Series Under Time Warping. In Int. Conference in Data Engineering, 1998.
[YNM97] Bozkaya, T., Yazdani, N. and Ozsoyoglu, Z.M., "Matching and Indexing Sequences of Different Lengths", Proc.Sixth Int. Conf. on Information and Knowledge Management (CIKM), Las Vegas, Nevada, Nov. 1997.
[YSH01]尹旭日，商琳，何佳洲，陈世福 Rough集挖掘时间序列的研究 南京大学学报(自然科学版)2001．2
[Zen03] Haiquan Zeng, Zhan Shen, Yunfa Hu. Mining Sequence Pattern from Time Series Based on Inter-Relevant Successive Trees Model. In Proceedings of 9th. International Conference on Rough Sets, Fuzzy Sets, Data Mining and Granular
Computing (RSFDGrC'2003), LNCS/LNAI, Spring-Verlag. May 26 to 29, 2003.Chongqing, China.
[AFS93] R. Agrawal, C. Faloutsos; and A. Swami. Efficient Similarity Search in Sequence Databases. In Int. Conference on Foundations of Data Organization (FODO) 1993.
[AI93] R. Agrawal, T. Imielinski, A. Swami. Mining association rules sets of items in large databases. Proceedings of the ACM SIGMOD Conference on Management of Data (SIGMOD'93). Washington, DC: ACM, 1993.
[A1183] J F Allen. Maintaining Knowledge About Temporal Intervals. Communications of ACM, 1983, 26(11): 823～843.
[AS95] Agrawal R, Srikant. Mining Sequential Patterns. In Proc.95 Int'1 Conf Data Engineering, Taibei, Taiwan, March, 5,1995.
[AS96] Agrawal R, Srikant R. Fast Discovery of Association Rules.In Fayyad.Ⅱ 1996
[AWS92] Ahlberg, C., Williamson, C., and Shneiderman, B., Dynamic queries for information exploration: An implementation and evaluation, Proc. ACM CHI'92: Human Factors in Computing Systems, 619-626, 1992.
[BC94] Donald J. Berndt, James Clifford. Using Dynamic Time Warping to Find Patterns in Time Series. KDD Workshop 1994.
[BDG98] Bela Bollobas, Gautam Das, Dimitrios Gunopulos and Heikki Mannila: Time Series Similarity Problems and Well-Separated Geometric Sets. 13~(th) Annual ACM Symposium on Computational Geometry 1998
[Bjo96] Bjorvand, A, T, Time series and rough sets, Master's thesis, Department of Computer Systems and Telematics, The Norwegian Institute of Technology 1996.
[BO93] B.L. Bowerman and R.T. Oconnel, Forcasting and Time Series: an Applied Approach, 3rd ed.Belmont, California:Duxbury Press, 1993
[BP85] C. Burrus and T. Parks. DFT/FFT and Convolution Algorithnas. John Wiley and Sons, 1985
[BW01] S. Babu and J. Widom. Continuous queries over data streams. In SIGMOD Record, Sept. 2001.
[BWJ97] C. Bettini, X. Wang, S. Jajodia, Satisfiability of Quantitative Temporal Constraints with Multiple Granularities. Third International Conference on
Principles and Practice of Constraint Programming (CP97), Schloss Hagenberg, Austria October 29-November 1, 1997.
[BWJ98a] C. Bettini, X. Wang, S. Jajodia, Mining Temporal Relationships with Multiple Granularities in Time Sequences, IEEE Data Engineering Bulletin, Volume 21 Number 1,1998
[BWJ98b] C. Bettini, X. Wang, S. Jajodia, A General Framework for Time Granularity and Its Application to Temporal Reasoning, Annals of Mathematics and Artificial Intelligence. Vol. 22. 1998.
[CC94] W. W. Chu, K. Chiang. Abstraction of High Level Concepts from Numerical Values in Databases. In Proceedings of the 11th AAAI Workshop on Knowledge Discovery in Databases, Las Vegas, 1994, 67～73.
[CDT00] J. Chen, D. J. Dewitt, F. Tian and Y. Wang. NiagaraCQ: a scalable continuous query system for Internet databases. In Proc. of the ACM. SIGMOD Conference, pages379-390, 2000.
[CDN02] J. Chen, D. J. Detitt, and J.F. Naughton. Design and evaluation of alternative selection placement strategies in optimizing continuous queries. In ICDE Conference, 2002
[CDZ97] 陈文伟，邓苏，张维明．数据开采与知识发现综述，计算机世界专题综述，1997， 6，30
[CF99] Chan, K. & Fu, A. W. (1999). Efficient time series matching by wavelets. In proceedings of the 15th IEEE Int'1 Conference on Data Engineering. Sydney, Australia, Mar 23-26. pp 126-133.
[CW99] K. K.W. Chu and M. H.Wong. Fast time-series searching with scaling and shifting. In PODS, Philedelphia, PA, 1999.
[DLM98] G. Das, K. Lin, H. Mannila, G. Renganathan, P. Smyth: Rule Discovery from Time Series.KDD 1998: 16-22.
[FCL01] T.C. Fu, F.L. Chung, R. Luk and V. Ng, "Pattern Discovery from Stock Time Series Using Self-Organizing Maps," Workshop Notes of KDD2001 Workshop on Temporal Data Mining, 26-29 Aug., San Francisco, pp.27-37, 2001.
[FL95] Christos Faloutsos, King-Ip Lin: FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets. SIGMOD Conference 1995: 163-174.
[FPS96] U.M.Fayyad, G.Piatetsky-Shapiro and P.Smyth, From data mining to knowledge discovery: An Overview. In U.M,Fayyad, G.Piatesky-Shapiro, et al eds, Advances in Knowledge Discovery and Data Mining, pp. 1-34, AAAI/MIT
Press, Menlo Park, Ca, 1996.
[Fra01] H Frank. Learning Temporal Rules from State Sequences. IJCAI Workshop on Learning from Temporal and Spatial Data. U.S.A. Seatle, 2001,45～51.
[FRM94] C. Faloutsos, M. Ranganathan, and Y. Manolopoulos. Fast Subsequence Matching in Time-Series Databases. In Proc. of 1994 ACM SIGMOD Int. Conf. on Management of Data.
[Fun73] Hunkhouser, H.G, Historical Development of the Graphical Representation of Statistical Data. Osiris. 3(1): 269-405. Reprinted Brugge, Belgium; St. Catherine Press 1937.
[FXJ00] 深圳汇天奇电脑有限公司，分析家证券投资分析系统3．0使用说明书，2000。
[GD01] Dimitros Gunopulos,Gautam Das. Time Series Similarity Measure: In Proceedings of the 2001 ACM SIGMOD International Conference on Management of Data, 2001.
[Gib93] Gibson, W. MIMSY: A System for Analyzing Time Series Data in the Stock Market Domain. Master's thesis, University of Wisconsin, Dept. of Computer Science, 1993
[GK95] Dina Q. Goldin, Paris C. Kanellakis. On Similarity Queries for Time-Series Data: Constraint Specification and Implementation. CP 1995.
[GLM99] L. Gyorfi, G. Lugosi and G. Morvai. A simple randomized algorithm for sequential prediction of ergodic time series. IEEE Transactions on Information Theory, 45(7): 2642-2650, 1999.
[GSB01] T. V. Gestel, J. Suykens, D. E. Baestaens,.A. Lamberechts, G. Lanckriet, B. Vandaele, D. B. Moor, and J. Vandewalle. Financial time series prediction using least squares Suport Vector Machines within the evidence framework. IEEE Transactions on Neural Network, 12(4): 809-821, 2001.
[GT92] Granger. C. W. J and Terasvirta, T. Modelling Nonlinear Economic Relationships, Oxford University Press, Oxford, 1992.
[GW02] Like Gao, X. Scan Wang Continually Evaluating Similarity Based Pattern Queries on a Streaming Time Series In SIGMOD Conference, 2002.
[Het03] Magnus Lie Hetland. A survey of recent methods for efficient retrieval of similar time sequences. To appear in Mark Last, Abraham Kandel, and Horst Bunke, editors, Data Mining in Time Series Databases. World Scientific, 2003.
[HK01] J. Han and M. Kamber. Data mining: concepts & techniques. Morgan
Kaufmann Publishers, 2001
[HM99] Hunter, J. & McIntosh, N. Knowledge-based event detection in complex time series data. Artificial Intelligence in Medicine. pp. 271-280. Springer. 1999
[Hop01] F. Hoppner. Learning Temporal Rules from State Sequences. IJCAI Workshop on Learning from Temporal and Spatial Data Seatle, August 2001.
[HP97] Heikki Mannila and Pirjo Ronkainen, Similarity of Event Sequences. In Proceedings of the Fourth International Workshop on Temporal Representation and Reasoning (TIME/97), May 1997, Daytona Beach, Florida, USA., pp.136-139.
[HS01] H. Hochheiser and B. shneiderman. Interactive exploration of time-series data. In Proc. Discovery Science 4~(th) International conference 2001, editors (Jantke, K.P. and Shinohara, A.), springer-Verlag, Berlin, pp 441-446.
[Hu02] 胡运发．互关联后继树——一种新型全文数据库数学模型．技术报告．复旦大学计算机有信息技术系．2002．3
[JD88] Jain, A, K. and Dubes, R. C. Algorithms for Clustering Data, Englewood Cliffs, NJ: Prentice-Hall. 1988.
[KCH02] Eamonn Keogh, Selina Chu, David Hart and Michael Pazzarfi An Online Algorithm for Segmenting Time Series
[Keo01] Eamonn Keogh, A Tutorial on Indexing and Mining Time Series Data in The 2001 IEEE International Conference on Data Mining November 29, San Jose
[Keo97] Keogh, E. Fast similarity search in the presence of longitudinal scaling in time series database, In Proceedings of the 9~(th) International Conference on Tools with Artificial Intelligence. pp.578-584. IEEE Press 1997
[KK96] Julian Kulkarn, Richark King. Business Intelligence Systems and Data Mining. ASAS Institute White Paper. 1996
[KL99] I. Kim and S. R. Lee. A fuzzy time series prediction method based on consecutive values. In Fuzzy Systems Conferences Proceedings, Vol. 2, 703-707
[KP00] Keogh & Pazzani, Scaling up Dynamic Time Warping for Datamining Applications. In 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Boston, 2000.
[KP98] Eamonn J. Keogh, Michael J. Pazzani: An Enhanced Representation of Time Series Which Allows Fast and Accurate Classification, Clustering and Relevance Feedback. KDD 1998: 239-243.
[KP98] Eamonn J. Keogh, Michael J. Pazzani: An Enhanced Representation of Time Series Which Allows Fast and Accurate Classification, Clustering and Relevance Feedback. KDD 1998: 239-243.
[KP99] Keogh & Pazzani. Relevance feedback retrieval of time series. The 22th International ACM-SIGIR Conference on Research and Development in Information Retrieval, 1999.
[KPC01] S.-W Kim, S. Park, W. Chu. An Index-Based Approach for Similarity Search Supporting Time Warping in Large Sequence Databases. ICDE 2001.
[KR90] Kaufman, L., and Rousseauw, P. J. Finding Groups in Data: An Introduction to Cluster Analysis John Wiley and Sons 1990.
[KS01] T. Kahveci and A. Singh. Variable length queries for time series data. In ICDE, Heidelberg, Germany, 2001.
[KS97] Eamonn J. Keogh, Padhraic Smyth: A Probabilistie Approach to Fast Pattern Matching in Time Series Databases. KDD 1997: 24-30,
[LPBZ96] L. Liu, C. Pu, R. S. Barga, and T. Zhou. Differential evaluation of continual queries. In International Conference on Distributed Computing Systems, pages 458-465,1996.
[LPT99] L. Liu, C. Pu, and W. Tang. Continual queries for Internet scale event-driven information delivery. IEEE TKDE, 11 (4):610-628,1999
[LTX02]李斌，谭立湘，解光军，李海鹰，庄镇泉，非同步多时间序列中频繁模式的发现算法，软件学报，13(03)410-416，2002
[LTZ00] 李斌，谭立湘，章劲松等，面向数据挖掘的时间序列符号化方法研究，电路与系统学报，2000,5(2)；9-14．
[MF02] S. Madden and M. J. Franklin. Fjording the stream: An architecture for queries over streaming sensor data. In ICDE Conference, 2002
[MTV94] Mannila H, Toivonen H, Inkeri Verkamo A. Efficient algorithms for discovery association rules. In; Proceedings of AAAI Workshop on Knowledge Discovery in Database July 1994. 181-192
[MTV95] H. Mannila, H. Toivonen, and A. I. Verkamo, Discovering Frequent episodes in Sequences. In Proc. Of KDD-95, pp210-215, Montreal, Canada, Aug,1995.
[MXZ01] 马志锋，邢汉承，郑晓妹，一种基于Rough集的时间序列数据挖掘策略，系统工程理论与实践2001年12期
[NHH98] Ng.M.K., Huang, Z., and Hegland. M. Data-mining massive time series
astronomical data sets-a case study. Proceedings of the 2~(nd) Pacific-Asia Conference on Knowledge Discovery and Data Mining, 401-402, Melbourne, Australia.
[OC96] Oates, T., Cohen, P.R. Searching for structure in multiple streams of data. In: Proceedings of the 13~(th) International Conference on Machine Learning. Morgan Kaufmann Publishers, Inc., 1996
[OS75] A. Oppenheim and R.Schafer. Digital Signal Processing, Prentice-Hall, Inc., 1975
[PF98] Povinelli, R. J. and Feng, X., Temporal Pattern Identification of Time Series Data Using Pattern Wavelets and Genetic Algorithms, Artificial Neural Networks in Engineering, St. Louis, Missouri, 691-696.
[PG00] S. Poliker and A. Geva. A new algorithm for time series prediction by temporal fuzzy clustering. In Proceedings. 15~(th) International Conference on Pattern Recognition, vol. 2, 728-731, 2000
[PKC01] K. Par, S. Kim, W. Chu. Segment-Based Approach for Subsequence Searches in Sequence Databases, In proceedings of the 16th ACM Symposium on Applied Computing. Las Vegas, NV, 2001,248～252.
[PKW01] Park, S., Kim, S. W., & Chu, W. W.. Segment-Based Approach for Subsequence Searches in Sequence Databases, To appear in Proceedings of the 16th ACM Symposium on Applied Computing.2001.
[PLC99] Park, S. & Lee, D., & Chu, W. W. Fast Retrieval of Similar Subsequences in Long Sequence Databases", Proceedings of the 3rd IEEE Knowledge and Data Engineering Exchange Workshop. 1999
[PMC] D.S. Parker, R.R. Muntz and H.L. Chau. The tangram stream query processing system. In ICDE Conference, 1999.
[Pou00] A. D. Poularikas, editor. The transforms and applications handbook. CRC Press LLC, 2000
[Pov99] Povinelli, R. J. Time Series Data Mining: Identifying Temporal Patterns for Characterization and Prediction of Time Series Events, PhD Dissertation, Marquette University, Milwaukee, 1999
[PW83] S.M.Pandit and S.M. Wu, Time series and System Analysis,With applications. New York: Wiley, 1983.
[PWZ00] C.-S. Perng, H. Wang, S. R. Zhang, D. Stott Parker Landmarks: a New Model for Similarity-based Pattern Querying in Time Series Databases, ICDE
2000.
[Qiu97] 邱一平，股林高手，复旦大学出版社，1997。
[QL03] Qianlong, http://www.qianlong.com.cn.
[RJ93] L. Rabinar, B.H. Juang. Fundamentals of Speech Recognition. Prentice Hall, 1993.
[RM98] D. Rafiei and Alberto Mendelzon, Efficient Retrieval of Similar Time Sequences Using DFT FODO'98 Conference, Kobe, Japan, November 1998.
[RM98] D. Rafiei and Alberto Mendelzon, Efficient Retrieval of Similar Time Sequences Using DFT FODO'98 Conference, Kobe, Japan, November 1998.
[Sha95] Shatkay, H.. Approximate Queries and Representations for Large Data Sequences. Technical Report cs-95-03, Department of Computer Science, Brown University. 1995
[Spo03] Spotfire. http://www.sporfirecom.
[SZ92] Szladow, A. J.& Ziarko, W, Knowledge-based process control using rough sets, in S.Y. Huang, ed., 'Intelligent Decision Support: Handbook of Applications and Advances of the Rough Set Theory', Kulwer Academic Publishers, chapter 4, 49-60,
[TAA01] Tamer Kahveci, Ambuj K. Singh and Aliekber Gurel. Shift and Scale Invariant Search of Multi-Attribute Time Sequences, Technical Report TRCS01-09, University of California, Santa Barbara, 2001
[TAA02] Kahveci, T., Singh, A. & Gurel, A. An efficient index structure for shift and scale invariant search of multi-attribute time sequences. In proceedings of the 18th Int'1 Conference on Data Engineering, poster paper. San Jose, CA, Feb 26-Mar 1.2002
[TB81] Tiao, G. C. and Box ,G. E.P., Modeling Multiple time series with application, Journal of America Statistiacl Association, vol 76,802-716 1981.
[TGN92] D. Terry. D. Goldberg, D. Nichols and B. Oki. Continuous queries over append-only databases. In Proc. of the ACM SIGMOD Conf. On Management of Data, pages 321-330,1992.
[TKR95] Hannu Toivonen, Mika Klemettinen,Pirjo Ronkaine et.al.Pruning and grouping disovered association Rules In:Mlnet Workshop on Statistics,Machine Learning and Discovery in Database. Heraklion, Crete, April 1995.
[TM99] Bozkaya, T. and Ozsoyoglu, Z.M., "Indexing Large Metric Spaces for
Similarity Search Queries", ACM TODS, 1999.
[TT91] Tiao, G C and Tsay, R.S., Some Advances in Nonlinear and Adaptive Modeling in Time Series Analysis, Technical Report #118, Graduate School of Business, The University of Chicago.
[Tuf83] Tufte, E. The Visual Display of Quantitative Information. Graphics Press. Cheshire, Connecticut. 1983.
[Wei90] Wei, W. W. S, Time Series Analysis: Univariate and Multivariate Methods Addison-Wesley publishing Company, Iac, 1990
[Win77] S. Winograd. Some bilinear forms whose multiplicative complexity depends on the field of constants. Mathematical Systems Theory, 10:169-180,1977.
[WQ99] Welch, D and Quinn, P. http://www.macho.mcmaster.ea/project/overview/status.html, 1999
[WS01] Wattenbeg, M. Sketching a Graph to Query a Time Series Database. In Proceedings of CHI 2001 (Seattle WA, April 2001) ACM Press,2001
[WTL01] L. Wang, K. K. Teo, and Z. Lin. Predicting time series with Wavelet packet neural networks. Proc. International Joint Conference on Neural Networks,3: 1393-1597,2001.
[WW00] Wang, C. & Wang, S.. Supporting content based searches on time Series via approximation. Proceedings of the 12th International Conference on Scientific and Statistical Database Management.2000
[WZZ96] 王耀动，张德远，张海雄，经济时间序列分析，上海财经大学出版社，1996年。
[YC98] Li, C,. Yu, P. & Castelli V.. MALM: A framework for mining sequence database at multiple abstraction levels. Proceedings of the 9th International Conference on Information and Knowledge Management. Pp 267-272.1998.
[YJF98] B. Yi, H.V. Jagadish, C.Faloutsos. Efficient Retrieval of Similar Time Series Under Time Warping. In Int. Conference in Data Engineering, 1998.
[YNM97] Bozkaya, T., Yazdani, N. and Ozsoyoglu, Z.M., "Matching and Indexing Sequences of Different Lengths", Proc.Sixth Int. Conf. on Information and Knowledge Management (CIKM), Las Vegas, Nevada, Nov. 1997.
[YSH01]尹旭日，商琳，何佳洲，陈世福 Rough集挖掘时间序列的研究 南京大学学报(自然科学版)2001．2
[Zen03] Haiquan Zeng, Zhan Shen, Yunfa Hu. Mining Sequence Pattern from Time Series Based on Inter-Relevant Successive Trees Model. In Proceedings of 9th. International Conference on Rough Sets, Fuzzy Sets, Data Mining and Granular
Computing (RSFDGrC'2003), LNCS/LNAI, Spring-Verlag. May 26 to 29, 2003.Chongqing, China.