An efficient algorithm for attribute-based subsequence matching

详细信息    查看全文

• 作者：Jun-Feng Qu ; ^{qmxwt@163.com" class="auth_mail" title="E-mail the corresponding author} ; Lei Yuan ^{1390405958@qq.com" class="auth_mail" title="E-mail the corresponding author} ; Yannong Huang ^{yannonghuang@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; Zhao Wu ^{wuzhao73@163.com" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Subsequence matching ; Attribute-based sequence
• 刊名：Information Sciences
• 出版年：2016
• 出版时间：20 March 2016
• 年：2016
• 卷：334-335
• 期：Complete
• 页码：323-337
• 全文大小：1081 K

文摘

Subsequence matching plays a fundamental role in the solutions to sequence-related problems such as sequence classification and similarity search. Subsequence matching is to find out expected event sequences from a database with a specified sequence composed of events. One cannot specify some or all of the events in the sequence but can give attribute values of these events in some applications. Therefore, a problem is how to find out expected event sequences from a database with an attribute-based sequence composed of attribute values. We propose an algorithm for the problem. The algorithm uses a list structure to store the temporal information about both sequences and events associated with values in a database. The structure can be compressed using a simple technique. Experimental data show that the proposed algorithm is one to two orders of magnitude faster than the state-of-the-art algorithm, especially for real-world databases, and that the technique is effective.