Mining for outliers in sequential databases

Pei Sun, Sanjay Chawla, Bavani Arunasalam

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

82 Scopus citations


The mining of outliers (or anomaly detection) in large databases continues to remain an active area of research with many potential applications. Over the last several years many novel methods have been proposed to efficiently and accurately mine for outliers. In this paper we propose a unique approach to mine for sequential outliers using Probabilistic Suffix Trees (PST). The key insight that underpins our work is that we can distinguish outliers from non-outliers by only examining the nodes close to the root of the PST. Thus, if the goal is to just mine outliers, then we can drastically reduce the size of the PST and reduce its construction and query time. In our experiments, we show that on a real data set consisting of protein sequences, by retaining less than 5% of the original PST we can retrieve all the outliers that were reported by the full-sized PST. We also carry out a detailed comparison between two measures of sequence similarity: the normalized probability and the odds and show that while the current research literature in PST favours the odds, for outlier detection it is normalized probability which gives far superior results. We provide an information theoretic argument based on entropy to explain the success of the normalized probability measure. Finally, we describe a more efficient implementation of the PST algorithm, which dramatically reduces its construction time compared to the implementation of Bejerano [3].

Original languageEnglish
Title of host publicationProceedings of the Sixth SIAM International Conference on Data Mining
PublisherSociety for Industrial and Applied Mathematics
Number of pages12
ISBN (Print)089871611X, 9780898716115
StatePublished - 2006
Externally publishedYes
EventSixth SIAM International Conference on Data Mining - Bethesda, MD, United States
Duration: Apr 20 2006Apr 22 2006

Publication series

NameProceedings of the Sixth SIAM International Conference on Data Mining


ConferenceSixth SIAM International Conference on Data Mining
Country/TerritoryUnited States
CityBethesda, MD


Dive into the research topics of 'Mining for outliers in sequential databases'. Together they form a unique fingerprint.

Cite this