My Research Activities
My interests are broadly in the design and analysis of algorithms. I am especially interested in distributed algorithms, network algorithms, and randomized algorithms. I worked on developing and analyzing distributed algorithms for general communication networks and wireless ad hoc networks (especially wireless sensor networks). I am also interested in data mining.
I am working with Professor Gopal Pandurangan at the Network Algorithms and Analysis Lab (NAAL). Our current research effort focuses on design and theoretical analysis of distributed algorithms for general point-to-point communication networks and wireless sensor networks such as distributed approximation algorithm for minimum spanning trees and k-connected subgraph problems.
Distributed Algorithms and Wireless Ad Hoc Sensor Networks:
During my PhD research work, I worked on developing distributed algorithms for various problems, specifically the minimum spanning tree (MST) problem and the k-connected subgraph problem. For general networks (point-to-point communication model), we developed a distributed approximation algorithm for MST, which is significantly faster than the existing MST algorithms. We also developed a distributed k-connected subgraph algorithm, which is, to the best of our knowledge, is the first non-trivial distributed algorithm for the k-connected subgraph problem. I also worked on distributed algorithms for wireless sensor networks (wireless local broadcast model). To build a data aggregation tree, we developed energy-efficient distributed approximation algorithm for constructing MST in a sensor network. For data aggregation such as sum, min, max, count, and average, it can be shown that MST is the optimal data aggregation tree. We analyzed our algorithms for both arbitrary distribution of the sensor nodes and random uniform distribution of the nodes in a unit square (a popular model for wireless ad hoc networks). We also worked on network monitoring for general communication networks and developed an efficient distributed network monitoring algorithm using edge routers only. This problem becomes easier if we are allowed to use core routers. However, we avoided using busy core router for monitoring purposes to allow the network to operate effectively.
Data Mining:
During my masters program, I worked on data mining of remotely sensed image data. We modified the k-nearest neighbor classification technique for spatial data and obtained a better classifier accuracy. To improve the running time of the classification algorithm, we used a data-mining-ready structure called P-tree. I also worked on using neural networks in data mining: using neural networks for classification, prediction, feature extraction, and extracting classification rules from a trained neural network.