TY - GEN
T1 - Non-dyadic haar wavelets for streaming and sensor data
AU - Gupta, Chetan
AU - Lakshminarayan, Choudur
AU - Wang, Song
AU - Mehta, Abhay
PY - 2010
Y1 - 2010
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=77952786234&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77952786234&partnerID=8YFLogxK
U2 - 10.1109/ICDE.2010.5447828
DO - 10.1109/ICDE.2010.5447828
M3 - Conference contribution
AN - SCOPUS:77952786234
SN - 9781424454440
T3 - Proceedings - International Conference on Data Engineering
SP - 569
EP - 580
BT - 26th IEEE International Conference on Data Engineering, ICDE 2010 - Conference Proceedings
T2 - 26th IEEE International Conference on Data Engineering, ICDE 2010
Y2 - 1 March 2010 through 6 March 2010
ER -