I've worked on several research projects in academia in the areas of Network Monitoring, Distributed Data Mining and Sensor Networks.

Detecting exploit patterns from network flow streams (PhD Thesis): Network-based Intrusion Detection Systems (NIDS) try to detect malicious activities by monitoring network traffic. Research on network traffic measurement has identified various patterns that the typical exploits on today's Internet exhibit. The goal of our research is to devise single-pass (online) data stream algorithms for detecting these patterns from network traffic flow data, using a workspace that is much smaller than the size of the traffic flow. We aim to design algorithms with a provable guarantee on the space and time requirements and the degree of approximation in the estimates returned. A detailed proposal of the work can be found here. The following projects are all parts of this work:

Space-efficient Tracking of Persistent Items in Massive Data Streams (Fall 2009-Fall 2010, with Srikanta Tirthapura and Jaideep Chandrashekar, formerly from Intel Labs Berkeley): The details are here.

A Generic Framework for Detecting Top-k Items from a Stream (Summer 2009): We propose a generic framework for identifying the k most frequent items from a network data stream in a single pass, using a workspace much smaller than the stream itself. We observed that any small-space sketch that approximately maintains the frequencies of the items appearing in a stream can be utilized to extract the top-k items. We show theoretically how the Misra-Gries sketch and the count-min sketch can fit into this framework, analyze the space-complexities of both, and present experimental results on packet traces from a backbone network link. With the realistic assumption that the frequencies of the items follow a Zipfian distribution, we fully present an algorithm, based on the Misra-Gries sketch, that takes only O(k^O(1)/ε) space and guarantees that the solution provided is ε-approximate. Under identical input distribution, the space-requirement of the top-k algorithm provided by Charikar et al is logarithmic in the size of the stream, so our algorithm achieves significant space-reduction; and does not demand any apriori knowledge from the user about the size of the stream. An extended abstract of this work got accepted in the ACM Student Research Competition, 2010. Here are the C++-based simulations of a naive and our small-space algorithm.

Finding Correlated Heavy-Hitters over Data Streams (Fall 2008-Summer 2009, with Srikanta Tirthapura): We consider online mining of correlated heavy-hitters (CHH) from network data streams. Given a multi-dimensional dataset, a correlated aggregate query first filters a subset by applying a predicate along a primary dimension, and then computes aggregates along some secondary dimension of that subset data. Previous work has focused on computing the correlated sum (or count) where the predicate for the primary dimension involved a basic aggregate that can be maintained exactly in small space (e.g., minimum, maximum or average). To our knowledge, our work is the first to address queries of the following form: "On a stream of (x, y) tuples, maintain the y-values that occur frequently alongwith the x-values that appear frequently in the stream". Previous techniques for correlated aggregates cannot handle queries of this form, since even for a one-dimensional stream, heavy-hitters cannot be maintained exactly using small space.

Our online data stream algorithm is easy to implement and uses workspace which is orders of magnitude smaller than the stream itself. We present provable guarantees on the maximum error estimates, as well as experimental results, that demonstrate the space-accuracy trade-off, on more than one billion packet headers from a backbone network link. The theoretical and experimental results are in this paper that got published in IPCCC 2009. Here are the C++-based simulations of a naive and our small-space algorithm.

Computing Frequent Elements using Gossip (Fall 2007-Spring 2009, with Srikanta Tirthapura): Due to the large scale of P2P and sensor networks, the values of aggregate functions over the data in the whole network are often more important than individual data at nodes. For example, in a P2P file-sharing network (like Gnutella or Napster), an administrator may be typically interested in identifying the most frequently accessed items over the whole network. Any reliance on central coordination limits the system’s scalability, therefore gossip-based protocols are emerging as an important communication paradigm. In gossip-based protocols, each node contacts one or a few nodes in each round (usually chosen at random), and exchanges information with these nodes. This mechanism leads to high fault-tolerance and self-stabilization. We designed efficient randomized distributed algorithms for identifying the frequently occurring data elements with probabilistic guarantees on accuracy, where the nodes exchange small-sized "sketches" or synopses of their individual data sets through gossip algorithms. The theoretical results are in this paper that we published in SIROCCO 2008. A Java-based simulation of the algorithm can be downloaded from here.

Distributed Lightweight Directories for Tracking Mobile Objects in Sensor Networks (Fall 2006-Summer 2007, with Srikanta Tirthapura and Bojian Xu): Most practical techniques for locating remote objects in a distributed system suffer from problems of scalability and locality of reference. We are implementing the Arrow distributed directory protocol, a scalable and local mechanism for ensuring mutually exclusive access to mobile objects. This directory has communication complexity optimal within a factor of (1+MST-stretch(G))/2, where MST-stretch(G) is the minimum spanning tree stretch of the underlying network. In Arrow protocol, local change in the object’s position does not result in a global change in the network. This has been deployed on a fixed spanning-tree-based network of MICA2 motes, where the presence of the object is detected by measuring the amount of ambient light using MTS300 photo sensors, and the node detecting the object transmits this information to its neighbours so that the pointers are updated appropriately.