Efficient discovery of longest-lasting correlation in sequence databases
Li Y.1; Leong Hou U.1; Yiu M.L.2; Gong Z.1
Source PublicationVLDB Journal
ISSN0949877X 10668888

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.

KeywordLongest-lasting Correlated Subsequences Similarity Search Time Series Analysis
URLView the original
Indexed BySCIE
WOS Research AreaComputer Science
WOS SubjectComputer Science, Hardware & Architecture ; Computer Science, Information Systems
WOS IDWOS:000387501000002
Fulltext Access
Citation statistics
Cited Times [WOS]:4   [WOS Record]     [Related Records in WOS]
Document TypeJournal article
Affiliation1.Universidade de Macau
2.Hong Kong Polytechnic University
First Author AffilicationUniversity of Macau
Recommended Citation
GB/T 7714
Li Y.,Leong Hou U.,Yiu M.L.,et al. Efficient discovery of longest-lasting correlation in sequence databases[J]. VLDB Journal,2016,25(6):767-790.
APA Li Y.,Leong Hou U.,Yiu M.L.,&Gong Z..(2016).Efficient discovery of longest-lasting correlation in sequence databases.VLDB Journal,25(6),767-790.
MLA Li Y.,et al."Efficient discovery of longest-lasting correlation in sequence databases".VLDB Journal 25.6(2016):767-790.
Files in This Item:
There are no files associated with this item.
Related Services
Recommend this item
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Li Y.]'s Articles
[Leong Hou U.]'s Articles
[Yiu M.L.]'s Articles
Baidu academic
Similar articles in Baidu academic
[Li Y.]'s Articles
[Leong Hou U.]'s Articles
[Yiu M.L.]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Li Y.]'s Articles
[Leong Hou U.]'s Articles
[Yiu M.L.]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.