Efficient discovery of longest-lasting correlation in sequence databases

详细信息    查看全文

• 作者：Yuhong Li ; Leong Hou U ; Man Lung Yiu ; Zhiguo Gong
• 关键词：Time series analysis ; Similarity search ; Longest ; lasting correlated subsequences
• 刊名：The VLDB Journal
• 出版年：2016
• 出版时间：December 2016
• 年：2016
• 卷：25
• 期：6
• 页码：767-790
• 全文大小：3,691 KB
• 刊物类别：Computer Science
• 刊物主题：Database Management
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：0949-877X
• 卷排序：25

文摘

The search for similar subsequences is a core module for various analytical tasks in sequence databases. Typically, the similarity computations require users to set a length. However, there is no robust means by which to define the proper length for different application needs. In this study, we examine a new query that is capable of returning the longest-lasting highly correlated subsequences in a sequence database, which is particularly helpful to analyses without prior knowledge regarding the query length. A baseline, yet expensive, solution is to calculate the correlations for every possible subsequence length. To boost performance, we study a space-constrained index that provides a tight correlation bound for subsequences of similar lengths and offset by intraobject and interobject grouping techniques. To the best of our knowledge, this is the first index to support a normalized distance metric of arbitrary length subsequences. In addition, we study the use of a smart cache for disk-resident data (e.g., millions of sequence objects) and a graph processing unit-based parallel processing technique for frequently updated data (e.g., nonindexable streaming sequences) to compute the longest-lasting highly correlated subsequences. Extensive experimental evaluation on both real and synthetic sequence datasets verifies the efficiency and effectiveness of our proposed methods.