Discovering longestlasting correlation in sequence databases

Yuhong Li, U. Leong Hou, Man Lung Yiu, Zhiguo Gong

Research output: Journal article publicationJournal articleAcademic researchpeer-review

18 Citations (Scopus)

Abstract

Most existing work on sequence databases use correlation (e.g., Euclidean distance and Pearson correlation) as a core function forvarious analytical tasks. Typically, it requires users to set a length for the similarity queries. However, there is no steady way to define the proper length on different application needs. In this work we focus on discovering longest-lasting highly correlated subsequences in sequence databases, which is particularly useful in helping those analyses without prior knowledge about the query length. Surprisingly, there has been limited work on this problem. A baseline solution is to calculate the correlations for every possible subsequence combination. Obviously, the brute force solution is not scalable for large datasets. In this work we study a space-constrained index that gives a tight correlation bound for subsequences of similar length and offset by intra-object grouping and inter-object grouping techniques. To the best of our knowledge, this is the first index to support normalized distance metric of arbitrary length subsequences.Extensive experimental evaluation on both real and synthetic sequence datasets verifies the efficiency and effectiveness of our proposed methods.
Original languageEnglish
Pages (from-to)1666-1677
Number of pages12
JournalProceedings of the VLDB Endowment
Volume6
Issue number14
DOIs
Publication statusPublished - 1 Jan 2013

ASJC Scopus subject areas

  • Computer Science (miscellaneous)
  • Computer Science(all)

Cite this