Publication Type

Conference Proceeding Article

Version

submittedVersion

Publication Date

7-2008

Abstract

Sequence, widely appearing in various applications (e.g. event logs, text documents, etc) is an ordered list of objects. Exploring correlated objects in a sequence can provide useful knowledge among the objects, e.g., event causality in event log and word phrases in documents. In this paper, we introduce correlation query that finds correlated pairs of objects often appearing closely to each other in a given sequence. A correlation query is specified by two control parameters, distance bound, the requirement of object closeness, and correlation threshold, the minimum requirement of correlation strength of result pairs. Instead of processing the query by scanning the sequence multiple times, that is called Multi-Scan Algorithm (MSA), we propose One-Scan Algorithm (OSA) and Index-Based Algorithm (IBA). OSA accesses a queried sequence once and IBA considers correlation threshold in the execution and effectively eliminates unneeded candidates from detail examination. An extensive set of experiments is conducted to evaluate all these algorithms. Among them, IBA, significantly outperforming the others, is the most efficient.

Discipline

Software Engineering

Research Areas

Software Systems

Publication

Scientific and Statistical Database Management: 20th International Conference, SSDBM 2008, Hong Kong, July 9-11, 2008: Proceedings

Volume

5069

First Page

436

Last Page

454

ISBN

9783540694977

Identifier

10.1007/978-3-540-69497-7_28

Publisher

Springer Verlag

City or Country

Hong Kong

Additional URL

http://dx.doi.org/10.1007/978-3-540-69497-7_28

Download

Share

COinS