我們提出一個新的時間間隔事件序列中搜尋子序列並考慮其持續時間的方法。在時間間隔事件序列中，每個事件和關係片段的持續時間在許多近期應用中受到重視。相較於過往在時間間隔事件的子序列搜尋研究中，著重在事件彼此間的關係，我們更重視事件關係間的時間間隔。在本研究中，透過時間間隔事件序列的不同表示方法，我們提出兩種索引結構，其一稱為事件片段檢索表(Event Slice Index)，可以保證事件間的關係而並顯示持續時間，藉由此索引結構，我們可以從候選序列中快速找到查詢的子序列位於哪個序列片段。另一個索引結構，事件集前綴樹(Label Set Trie)，不同於倒排檢索，此結構不僅使用適當的記憶體及建構時間，而且當詢問長度增長，在查詢時間表現上有更好的效能。我們也提出一種演算法ESS(Event Slice Search)，結合剪枝策略，透過獲得事件片段的持續時間並且利用其持續時間，相較於傳統方法能有更精確且快速的配對，在檢索信息上，使信息檢索更有效率。對於性能評估，我們比較不同演算法搭配不同檢索方法的執行時間及效能。這些實驗顯示S ESS跟R ESS在不同情境下與其他的比較方法相比，在執行時間上和記憶體使用上有更好的效能。

We present a new approach to search the sub-sequence from the Time-Interval based Event database considering Duration match, or called TIED database. In TIED sequences, the duration of each event and each relation segments have attracted considerable attention in many applications lately. In contrast to previous works of sub-sequence search in event interval sequences, which focused on the relation between each event, we care more about their duration within each relation. In this work, through the different representation of TIED sequences, called Event Slice Sequence, we propose two index structures, one called Event Slice Index, which can guarantee the relation between events in sequences and also show the duration in each slice, using this index structure we could quickly find the query in which slice from candidate sequences. The other index structure called Label Set Trie, unlike inverted index, these structure not only used moderate memory and reasonable construction time but also showed the better query time as query length growing. We also propose an algorithm ESS, Event Slice Search, incorporating a pruning strategy through obtaining the duration in event slice and using the duration to search more precise match and faster than the other traditional methodologies.
It lets the retrieval information phrase more efficiently. On the performance part, we revise some previous algorithms to compare with ours. The experiments show that S ESS and R ESS in different situations get the better performance than the other comparison methods in execution time and memory usage.

1] R. Agrawal, C. Faloutsos, and A. Swami. Efficient similarity search in sequence databases. Foundations of data organization and algorithms, pages 69–84, 1993.
[2] R. Agrawal and S. Ieong. Aggregating web offers to determine product prices. In Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 435–443. ACM, 2012.
[3] R. Agrawal and R. Srikant. Mining sequential patterns. In Data Engineering, 1995. Proceedings of the Eleventh International Conference on, pages 3–14. IEEE, 1995.
[4] Z. Al Bawab, G. H. Mills, and J.-F. Crespo. Finding trending local topics in search queries for personalization of a recommendation system. In Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 397–405. ACM, 2012.
[5] J. M. Ale and G. H. Rossi. An approach to discovering temporal association rules. In Proceedings of the 2000 ACM Symposium on Applied computing-Volume 1, pages 294–300. ACM, 2000.
[6] J. Allen. Maintaining knowledge about temporal intervals. Communication of ACM, 26(11):832–843, 1983.
[7] S. Aseervatham, A. Osmani, and E. Viennet. bitspade: A lattice-based sequential pattern mining algorithm using bitmap representation. In Data Mining, 2006. ICDM’06. Sixth International Conference on, pages 792–797. IEEE, 2006.
[8] S. Aseervatham, A. Osmani, and E. Viennet. bitSPADE: A lattice-based sequential pattern mining algorithm using bitmap representation. In Proceedings of the 16th IEEE International Conference on Data Mining, pages 792–797, 2006.
[9] J. Ayres, J. Flannick, J. Gehrke, and T. Yiu. Sequential pattern mining using a bitmap representation. In Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 429–435. ACM, 2002.
[10] E. Bakshy, I. Rosenn, C. Marlow, and L. Adamic. The role of social networks in information diffusion. In Proceedings of the 21st international conference on World Wide Web, pages 519–528. ACM, 2012.
[11] I. Batal, D. Fradkin, J. Harrison, F. Moerchen, and M. Hauskrecht. Mining recent temporal patterns for event detection in multivariate time series data. In Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 280–288. ACM, 2012.
[12] I. Batal, D. Fradkin, J. Harrison, F. Moerchen, and M. Hauskrecht. Mining recent temporal patterns for event detection in multivariate time series data. In Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 280–288, 2012.
[13] R. Bellman and R. Kalaba. On adaptive control processes. IRE Transactions on Automatic Control, 4(2):1–9, 1959.
[14] B. Berendt. Explaining preferred mental models in allen inferences with a metrical model of imagery. In Proceedings of the Eighteenth Annual Conference of the Cognitive Science Society, pages 489–494, 1996.
[15] B. Bergen and N. Chang. Embodied construction grammar in simulation-based language understanding. Construction grammars: Cognitive grounding and theoretical extensions, 3:147–190, 2005.
[16] D. J. Berndt and J. Clifford. Using dynamic time warping to find patterns in time series. In KDD workshop, volume 10, pages 359–370. Seattle, WA, 1994.
[17] H. Cao, N. Mamoulis, and D. W. Cheung. Mining frequent spatio-temporal sequential patterns. In Data Mining, Fifth IEEE International Conference on, pages 8–pp. IEEE, 2005.
[18] K.-Y. Chen, B. P. Jaysawal, J.-W. Huang, and Y.-B. Wu. Mining frequent time intervalbased event with duration patterns from temporal database. In Data Science and Advanced Analytics (DSAA), 2014 International Conference on, pages 548–554. IEEE, 2014.
[19] Y. Chen, S. Chang, C. Chou, W. Peng, and S. Lee. Exploring community structures for influence maximization in social networks. In Proceedings of the 6th SNA-KDD Workshop on Social Network Mining and Analysis held in conjunction with KDD’12 (SNA-KDD’12), pages 1–6, 2012.
[20] Y.-C. Chen, J.-C. Jiang, W.-C. Peng, and S.-Y. Lee. An efficient algorithm for mining time interval-based patterns in large database. In Proceedings of the 19th ACM international conference on Information and knowledge management, pages 49–58. ACM, 2010.
[21] Y.-C. Chen, W.-C. Peng, and S.-Y. Lee. CEMiner – An efficient algorithm for mining closed patterns from time interval-based data. In Proceedings of the 21st IEEE International Conference on Data Mining, pages 121–130, 2011.
[22] Y.-C. Chen, W.-C. Peng, and S.-Y. Lee. Efficient algorithms for influence maximization in social networks. Knowledge and information systems, pages 1–25, 2012.
[23] Y.-C. Chen, W.-Y. Zhu, W.-C. Peng, W.-C. Lee, and S.-Y. Lee. Cim: Community-based influence maximization in social networks. ACM Transactions on Intelligent Systems and Technology (TIST), 5(2):25, 2014.
[24] H. Cheng, X. Yan, and J. Han. Incspan: incremental mining of sequential patterns in large database. In Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 527–532. ACM, 2004.
[25] A. Corradini. Dynamic time warping for off-line recognition of a small gesture vocabulary. In Recognition, Analysis, and Tracking of Faces and Gestures in Real-Time Systems, 2001. Proceedings. IEEE ICCV Workshop on, pages 82–89. IEEE, 2001.
[26] P.-E. Danielsson. Euclidean distance mapping. Computer Graphics and image processing, 14(3):227–248, 1980.
[27] I. Davidson, S. Gilpin, O. Carmichael, and P. Walker. Network discovery via constrained tensor analysis of fmri data. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 194–202. ACM, 2013.
[28] W.-H. Du, J.-W. Rau, J.-W. Huang, and Y.-S. Chen. Improving the quality of tags using state transition on progressive image search and recommendation system. In Systems, Man, and Cybernetics (SMC), 2012 IEEE International Conference on, pages 3233–3238. IEEE, 2012.
[29] C. Faloutsos, M. Ranganathan, and Y. Manolopoulos. Fast subsequence matching in timeseries databases, volume 23. ACM, 1994.
[30] M. N. Garofalakis, R. Rastogi, and K. Shim. Spirit: Sequential pattern mining with regular expression constraints. In VLDB, volume 99, pages 7–10, 1999.
[31] T. D. Gunter and N. P. Terry. The emergence of national electronic health record architectures in the united states and australia: models, costs, and questions. Journal of medical Internet research, 7(1), 2005.
[32] P. Haider, L. Chiarandini, and U. Brefeld. Discriminative clustering for market segmentation. In Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 417–425. ACM, 2012.
[33] J. Han, J. Pei, and M. Kamber. Data mining: concepts and techniques. Elsevier, 2011.
[34] J. Han, J. Pei, Y. Yin, and R. Mao. Mining frequent patterns without candidate generation: A frequent-pattern tree approach. Data mining and knowledge discovery, 8(1):53–87, 2004.
[35] C.-C. Ho, H.-F. Li, F.-F. Kuo, and S.-Y. Lee. Incremental mining of sequential patterns over a stream sliding window. In Data Mining Workshops, 2006. ICDM Workshops 2006. Sixth IEEE International Conference on, pages 677–681. IEEE, 2006.
[36] Y.-H. Hu, T. C.-K. Huang, H.-R. Yang, and Y.-L. Chen. On mining multi-time-interval sequential patterns. Data & Knowledge Engineering, 68(10):1112–1127, 2009.
[37] J.-W. Huang, S.-C. Lin, and M.-S. Chen. Dpsp: Distributed progressive sequential pattern mining on the cloud. Advances in Knowledge Discovery and Data Mining, pages 27–34, 2010.
[38] J.-W. Huang, C.-Y. Tseng, M.-C. Chen, and M.-S. Chen. Pisar: Progressive image search and recommendation system by auto-interpretation and user behavior. In Systems, Man, and Cybernetics (SMC), 2011 IEEE International Conference on, pages 1442–1447. IEEE, 2011.
[39] J.-W. Huang, C.-Y. Tseng, J.-C. Ou, and M.-S. Chen. A general model for sequential pattern mining with a progressive database. IEEE Transactions on Knowledge and Data Engineering, 20(9):1153–1167, 2008.
[40] L. Hui, Y.-C. Chen, J. T.-Y.Weng, and S.-Y. Lee. Incremental mining of temporal patterns in interval-based database. Knowledge and Information Systems, 46(2):423–448, 2016.
[41] J. H. Johnson. Substring matching for clone detection and change tracking. In ICSM, volume 94, pages 120–126, 1994.
[42] P.-s. Kam and A. Fu. Discovering temporal patterns for interval-based events. Data Warehousing and Knowledge Discovery, pages 317–326, 2000.
[43] E. Keogh, K. Chakrabarti, M. Pazzani, and S. Mehrotra. Dimensionality reduction for fast similarity search in large time series databases. Knowledge and information Systems, 3(3):263–286, 2001.
[44] E. Keogh and C. A. Ratanamahatana. Exact indexing of dynamic time warping. Knowledge and information systems, 7(3):358–386, 2005.
[45] J. Z. Kolter and M. J. Johnson. Redd: A public data set for energy disaggregation research. In Workshop on Data Mining Applications in Sustainability (SIGKDD), San Diego, CA, volume 25, pages 59–62, 2011.
[46] R. Kosara and S. Miksch. Visualizing complex notions of time. Studies in health technology and informatics, (1):211–215, 2001.
[47] O. Kostakis and P. Papapetrou. Finding the longest common sub-pattern in sequences of temporal intervals. Data mining and knowledge discovery, 29(5):1178–1210, 2015.
[48] O. Kostakis, P. Papapetrou, and J. Hollm´en. Artemis: Assessing the similarity of eventinterval sequences. Machine Learning and Knowledge Discovery in Databases, pages 229– 244, 2011.
[49] O. K. Kostakis and A. G. Gionis. Subsequence search in event-interval sequences. In Proceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 851–854. ACM, 2015.
[50] A. Kotsifakos, I. Karlsson, P. Papapetrou, V. Athitsos, and D. Gunopulos. Embeddingbased subsequence matching with gaps—range—tolerances: a query-by-humming application. The VLDB Journal—The International Journal on Very Large Data Bases, 24(4):519–536, 2015.
[51] A. Kotsifakos, P. Papapetrou, and V. Athitsos. Ibsm: Interval-based sequence matching. In Proceedings of the 2013 SIAM International Conference on Data Mining, pages 596–604. SIAM, 2013.
[52] A. Kuzmanic and V. Zanchi. Hand shape classification using dtw and lcss as similarity measures for vision-based gesture recognition system. In EUROCON, 2007. The International Conference on” Computer as a Tool”, pages 264–269. IEEE, 2007.
[53] V. C.-C. Liao and M.-S. Chen. Dfsp: a depth-first spelling algorithm for sequential pattern mining of biological sequences. Knowledge and information systems, 38(3):623, 2014.
[54] M.-Y. Lin and S.-Y. Lee. Incremental update on sequential patterns in large databases by implicit merging and efficient counting. Information Systems, 29(5):385–404, 2004.
[55] X. Liu, J. Biagioni, J. Eriksson, Y. Wang, G. Forman, and Y. Zhu. Mining large-scale, sparse gps traces for map inference: comparison of approaches. In Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 669–677. ACM, 2012.
[56] J. Lonardi and P. Patel. Finding motifs in time series. In Proc. of the 2nd Workshop on Temporal Data Mining, pages 53–68, 2002.
[57] Y. Mao, W. Chen, Y. Chen, C. Lu, M. Kollef, and T. Bailey. An integrated data mining approach to real-time clinical monitoring and deterioration warning. In Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining,pages 1140–1148. ACM, 2012.
[58] F. Masseglia, P. Poncelet, and M. Teisseire. Incremental mining of sequential patterns in large databases. Data & Knowledge Engineering, 46(1):97–121, 2003.
[59] F. M¨orchen and D. Fradkin. Robust mining of time intervals with semi-interval partial order patterns. In Proceedings of the 2010 SIAM International Conference on Data Mining, pages 315–326. SIAM, 2010.
[60] F. Morchen and D. Fradkin. Robust mining of time intervals with semi-interval partial order patterns. In Proceedings of the 20th SIAM International Conference on Data Mining, pages 315–326, 2010.
[61] R. Moskovitch and Y. Shahar. Classification-driven temporal discretization of multivariate time series. Data Mining and Knowledge Discovery, 29(4):871–913, 2015.
[62] M. M¨uller. Dtw-based motion comparison and retrieval. Information Retrieval for Music and Motion, pages 211–226, 2007.
[63] M. M¨uller, H. Mattes, and F. Kurth. An efficient multiscale approach to audio synchronization. In ISMIR, pages 192–197. Citeseer, 2006.
[64] S. N. Nguyen, X. Sun, and M. E. Orlowska. Improvements of incspan: Incremental mining of sequential patterns in large database. In PAKDD, volume 5, pages 442–451. Springer, 2005.
[65] F. Pachet, G. Ramalho, and J. Carrive. Representing temporal musical objects and reasoning in the muses system. Journal of new music research, 25(3):252–275, 1996.
[66] P. Papapetrou, G. Kollios, S. Sclaroff, and D. Gunopulos. Discovering frequent arrangements of temporal intervals. In Data Mining, Fifth IEEE International Conference on, pages 8–pp. IEEE, 2005.
[67] P. Papapetrou, G. Kollios, S. Sclaroff, and D. Gunopulos. Mining frequent arrangements of temporal intervals. Knowledge and Information Systems, 21(2):133–171, 2009.
[68] S. Parthasarathy, M. J. Zaki, M. Ogihara, and S. Dwarkadas. Incremental and interactive sequence mining. In Proceedings of the eighth international conference on Information and knowledge management, pages 251–258. ACM, 1999.
[69] D. Patel, W. Hsu, and M. L. Lee. Mining relationships among interval-based events for classification. In Proceedings of the 2008 ACM SIGMOD international conference on Management of data, pages 393–404. ACM, 2008.
[70] J. Pei, J.-W. Han, B. Mortazavi-asl, H. Pinto, Q. Chen, U. Dayal, and M.-C. Hsu. PrefixSpan: Mining sequential patterns efficiently by prefix-projected pattern growth. In Proceedings of the 17th IEEE International Conference on Data Engineering, pages 215–224, 2001.
[71] N. Pissinou, I. Radev, and K. Makki. Spatio-temporal modeling in video and multimedia geographic information systems. GeoInformatica, 5(4):375–409, 2001.
[72] F. Plouraboue. Exact discovery of time series motifs. 2009.
[73] S. Salvador and P. Chan. Toward accurate dynamic time warping in linear time and space. Intelligent Data Analysis, 11(5):561–580, 2007.
[74] I. Savnik. Index data structure for fast subset and superset queries. In International Conference on Availability, Reliability, and Security, pages 134–148. Springer, 2013.
[75] I. Shafer, K. Ren, V. N. Boddeti, Y. Abe, G. R. Ganger, and C. Faloutsos. Rainmon: an integrated approach to mining bursty timeseries monitoring data. In Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1158–1166. ACM, 2012.
[76] K. Shi and K. Ali. Getjar mobile application recommendations with very sparse datasets. In Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 204–212. ACM, 2012.
[77] P. Sondhi, J. Sun, H. Tong, and C. Zhai. Sympgraph: a framework for mining clinical notes through symptom relation graphs. In Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1167–1175. ACM, 2012.
[78] R. Subramanyam, A. Suresh Rao, R. Karnati, S. Suvvari, and D. V. Somayajulu. Mining closed sequential patterns in progressive databases. Journal of Information & Knowledge Management, 12(03):1350024, 2013.
[79] Y. Tabei, A. Kishimoto, M. Kotera, and Y. Yamanishi. Succinct interval-splitting tree for scalable similarity search of compound-protein pairs with property constraints. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 176–184. ACM, 2013.
[80] J. Tang, S. Wu, and J. Sun. Confluence: Conformity influence in large social networks. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 347–355. ACM, 2013.
[81] L.-A. Tang, X. Yu, Q. Gu, J. Han, A. Leung, and T. La Porta. Mining lines in the sand: On trajectory discovery from untrustworthy data in cyber-physical system. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 410–418. ACM, 2013.
[82] C. C. Tappert, C. Y. Suen, and T. Wakahara. The state of the art in online handwriting recognition. IEEE Transactions on pattern analysis and machine intelligence, 12(8):787– 808, 1990.
[83] J. Vial, H. No¸cairi, P. Sassiat, S. Mallipatu, G. Cognon, D. Thi´ebaut, B. Teillet, and D. N. Rutledge. Combination of dynamic time warping and multivariate analysis for the comparison of comprehensive two-dimensional gas chromatograms: application to plant extracts. Journal of Chromatography A, 1216(14):2866–2872, 2009.
[84] J.-Y. Wang and J.-W. Han. BIDE: Efficient mining of frequent closed sequences. In Proceedings of the 20th IEEE International Conference on Data Engineering, pages 79–90, 2004.
[85] K. Wang, Y. Xu, and J. X. Yu. Scalable sequential pattern mining for biological sequences. In Proceedings of the thirteenth ACM international conference on Information and knowledge management, pages 178–187. ACM, 2004.
[86] L.-Y. Wei, Y. Zheng, and W.-C. Peng. Constructing popular routes from uncertain trajectories.
In Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 195–203. ACM, 2012.
[87] J. T.-Y. Weng, L. S.-H. Wu, C.-S. Lee, P. W.-C. Hsu, and A. T. Cheng. Integrative epigenetic profiling analysis identifies dna methylation changes associated with chronic alcohol consumption. Computers in biology and medicine, 64:299–306, 2015.
[88] E. Winarko and J. F. Roddick. Armada–an algorithm for discovering richer relative temporal association rules from interval-based data. Data & Knowledge Engineering, 63(1):76–90, 2007.
[89] S.-Y. Wu and Y.-L. Chen. Mining nonambiguous temporal patterns for interval-based events. IEEE transactions on knowledge and data engineering, 19(6), 2007.
[90] C.-W. Yang, B. P. Jaysawal, and J.-W. Huang. Subsequence search considering duration and relations of events in time interval-based events sequences. In Data Science and Advanced Analytics (DSAA), 2017 IEEE International Conference on, pages 293–302. IEEE, 2017.
[91] X. Yang, A. Ghoting, Y. Ruan, and S. Parthasarathy. A framework for summarizing and analyzing twitter feeds. In Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 370–378. ACM, 2012.
[92] J. Yuan, Y. Zheng, and X. Xie. Discovering regions of different functions in a city using human mobility and pois. In Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 186–194. ACM, 2012.
[93] L. Yuan, Y. Wang, P. M. Thompson, V. A. Narayan, and J. Ye. Multi-source learning for joint analysis of incomplete multi-modality neuroimaging data. In Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1149–1157. ACM, 2012.
[94] W. Zhou, H. Jin, and Y. Liu. Community discovery and profiling with social messages. In Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 388–396. ACM, 2012.
[95] F. Zhu, X. Yan, J. Han, and S. Y. Philip. Efficient discovery of frequent approximate sequential patterns. In Data Mining, 2007. ICDM 2007. Seventh IEEE International Conference on, pages 751–756. IEEE, 2007.