Overview

IOT is ubiquitous now a days. With time series data pouring in from all possible sources, there is an increasing need to process the data at near real time. However, the transmission, storage and compute cost associated with this data is ever increasing.

Functional Data Structure for Time Series

In this talk, we will look at functional implementation of discrete wavelet transforms implemented using Haskell. We will use Haar wavelets for the the demo. The high and low pass filter definition of a wavelet allows a very simple functional implementation of Haar wavelet transform.

Wavelet Transform

We will look at simple recursive definition for forward and reverse wavelet transforms. The wavelet transform is very simple to implement in O(N) time complexity using recursive definition, and higher order functions.

Wavelet as a Container

Though, these transform functions are good for bulk transform i.e. to convert incoming data to/from wavelet space at once, they are not good for point queries. We will look at how we can partition a wavelet vector in dyadic ranges, and dynamically construct orthonormal basis of the wavelet by directly querying only log N coefficients.

Wavelet Approximation

The wavelet container that we constructed can be sparse. i.e. it is possible to prune the coefficients that are not contributing to approximation, and still use the wavelet container.

Wavelet Sketching

Sketches are random algorithms to estimate the result with a given accuracy with high probability.

We can use sum-of-square energy function property to prune the coefficients. Finally we use sublinear AMS sketching algorithm to predict the energy, and prune the coefficients efficiently in log N time rather than O(N) time. This allows us to quickly prune the wavelet container by getting rid of large number of coefficients. This allows very compact representation of the time series data that allows point queries.

We show Haskell implementation

• Sketch as a class, and linear properties of Sketch
• Implementation of AMS using hash functions, and probability distributions
• Using AMS with hash bucketing to prune wavelet coefficents

Use Case

We will look at a historical stock data, and use wavelet transform and sketching to reduce the data size.

Current Status

Currently being studied at my organization, such functional application is found to be useful in representing data for quick analytics.

The session will present design and implementation of Hspark. A library that implements a framework to enable running a distributed map-reduce job over a set of nodes. The session will also showcase an extensible DSL to specify distributed map-reduce job.

The session will focus mainly on 

• Creation of DSL (Specification) for map reduce. The DSL is similar (actually based on) Apache Spark
• Translation of DSL into scheduling the jobs across the nodes, and
• Executing and handling failures.

Current implementation of hspark is at https://github.com/yogeshsajanikar/hspark and implements first two points mentioned above. Currently, I am trying to enforce it with separation of execution framework so that failures can be handled correctly.

Note that this project was implemented as a part of course project for CS240H at Stanford. The implementation details can be found at http://www.scs.stanford.edu/16wi-cs240h/projects/sajanikar.pdf