Non-dyadic haar wavelets for streaming and sensor data

Chetan Gupta, Choudur Lakshminarayan, Song Wang, Abhay Mehta

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

10 Scopus citations

Abstract

In streaming and sensor data applications, the problems of synopsis construction and outlier detection are important. Due to their low complexity, desirable properties and relative ease of understanding, wavelet based techniques are often used for both synopsis construction and anomaly detection. In streaming data literature, Mallat's algorithm [1] is often used to achieve a Haar wavelet decomposition in O(n) time. However, there is one limitation to this popular technique, in that it leads to a dyadic decomposition of data. We demonstrate that the property of non-dyadicity is of considerable use in synopsis construction and anomaly detection. In this regard we present several application results, a synopsis data structure for streaming data that is an order of magnitude superior to the popular Haar based wavelet technique, a method for finding anomalies for sensor data over non-dyadic hierarchies, etc. In our work, we enable non-dyadicity by proposing a Mallat like construction for a wavelet system that admits non-dyadic basis. Our algorithm builds a non-dyadic hierarchical structure, and is more efficient than the state of the art construction. We prove the correctness of our construction by showing that our basis functions demonstrates the properties of a wavelet system.

Original languageEnglish
Title of host publication26th IEEE International Conference on Data Engineering, ICDE 2010 - Conference Proceedings
Pages569-580
Number of pages12
DOIs
StatePublished - 2010
Event26th IEEE International Conference on Data Engineering, ICDE 2010 - Long Beach, CA, United States
Duration: 1 Mar 20106 Mar 2010

Publication series

NameProceedings - International Conference on Data Engineering
ISSN (Print)1084-4627

Conference

Conference26th IEEE International Conference on Data Engineering, ICDE 2010
Country/TerritoryUnited States
CityLong Beach, CA
Period1/03/106/03/10

Fingerprint

Dive into the research topics of 'Non-dyadic haar wavelets for streaming and sensor data'. Together they form a unique fingerprint.

Cite this