About Me
I am a Postdoctoral Researcher at
the
Department of Computer
Science,
Duke University
working with
Prof. Pankaj
K. Agarwal.
I am coordinating
the
algorithms seminar this
semester with
Sungjin
Im.
Education
 PhD  December 2011
Computer
Science, The University
of Arizona, Tucson, AZ,
USA. Advisor: Prof. Alon
Efrat
 Master of Science  December 2008
Computer Science, The University of Arizona, Tucson, AZ, USA.
 Bachelor of Engineering  June 2006
SSN College of
Engineering, Anna
University, Chennai, India.
Research Interests
Algorithms (particularly
computational geometry and graph theory), with applications to
optimization problems arising in various applications such as
Wired/Wireless/Sensor networks, Geographic Information Systems,
spatial and spatiotemporal databases, etc.
Journal Publications

Pankaj K. Agarwal, Alon Efrat, Shashidhara Ganjugunte, David Hay, Swaminathan Sankararaman and Gil Zussman
IEEE/ACM Transactions on Networking, Accepted for Publication, 2012.
Abstract:Telecommunications networks, and in particular optical WDM networks, are vulnerable to largescale failures in their physical infrastructure, resulting from physical attacks (such as an Electromagnetic Pulse attack) or natural disasters (such as solar flares, earthquakes, and floods). Such events happen at specific geographical locations and disrupt specific parts of the network but their effects cannot be determined exactly in advance. Therefore, we provide a unified framework to model network vulnerability when the event has a probabilistic nature, defined by an arbitrary probability density function. Our framework captures scenarios with a number of simultaneous attacks, when network components consist of several dependent subcomponents, and in which either a 1+1 or a 1:1 protection plan is in place. We use computational geometric tools to provide efficient algorithms to identify vulnerable points within the network under various metrics. Then, we obtain numerical results for specific backbone networks, demonstrating the applicability of our algorithms to realworld scenarios. Our novel approach allows to identify locations which require additional protection efforts (e.g., equipment shielding). Overall, the paper demonstrates that using computational geometric techniques can significantly contribute to our understanding of network resilience.
hide details read details

Esther M. Arkin, Alon Efrat, Joseph S. B. Mitchell, Valentin Polishchuk, Srinivasan Ramasubramanian, Swaminathan Sankararaman and Javad Taheri
Elsevier Ad Hoc Networks, In Press (available online), 2011.
Abstract:In this paper, we study the fundamental optimization problem in wireless sensor networks of basestation positioning such that data from the sensors may be transmitted to it in an energyefficient manner. We primarily consider the setting where a sensor transmits all of its data directly to the basestation or relays it via one other node. This setting provides two benefits: low dutycycling due to limited synchronization requirements between nodes and low endtoend delay due to the limited number of hops in the routes. Given the battery limitations of the sensor nodes, our objective is to maximize the network lifetime. First, we present efficient algorithms for computing a transmission scheme for the sensors given a fixed basestation and show how to implement these in a distributed fashion with only a constant number of messages per sensor. Next, we show that the optimization problem for the setting where sensors may transmit data through more than 2 hops is NPHard. Finally, we present efficient algorithms for the problem of locating the basestation and simultaneously finding a transmission scheme. We compare our algorithms with linearprogramming based algorithms for more general settings through extensive simulations and outline the benefits of the different approaches.
doi: 10.1016/j.adhoc.2011.09.010
hide details read details

Swaminathan Sankararaman, Alon Efrat, Srinivasan Ramasubramanian and Pankaj K. Agarwal
Elsevier Ad Hoc Networks, In Press (available online), 2011.
Abstract:Multichannel wireless networks are increasingly deployed as infrastructure networks, e.g. in metro areas. Network nodes frequently employ directional antennas to improve spatial throughput. In such networks, between two nodes, it is of interest to compute a path with a channel assignment for the links such that the path and link bandwidths are the same. This is achieved when any two consecutive links are assigned different channels, termed as ``ChannelDiscontinuityConstraint'' (CDC). CDCpaths are also useful in TDMA systems, where, preferably, consecutive links are assigned different timeslots. In the first part of this paper, we develop a \(t\)spanner for CDCpaths using spatial properties; a subnetwork containing \(O(n/\theta)\) links, for any \(\theta>0\), such that CDCpaths increase in cost by at most a factor \(t=(12\sin (\theta/2))^{2}\). We propose a novel distributed algorithm to compute the spanner using an expected number of \(O(n\log n)\) fixedsize messages. In the second part, we present a distributed algorithm to find minimumcost CDCpaths between two nodes using \(O(n^2)\) fixedsize messages, by developing an extension of Edmonds' algorithm for minimumcost perfect matching. In a centralized implementation, our algorithm runs in \(O(n^2)\) time improving the previous best algorithm which requires \(O(n^3)\) running time. Moreover, this running time improves to \(O(n/\theta)\) when used in conjunction with the spanner developed.
doi: 10.1016/j.adhoc.2011.04.011
hide details read details
Conference/Workshop Publications

Alon Efrat, Joseph S. B. Mitchell, Parrish Myers and Swaminathan Sankararaman
Proceedings pf the 20th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS), 2012.
Abstract:We propose algorithms for computing optimal trajectories of a group of flying observers (such as helicopters or UAVs) searching for a lost child in a hilly terrain. Very few assumptions are made about the speed or direction of the child's motion and whether it might (either deliberately or accidentally) try to avoid being found. This framework can also be applied to seekers searching for hostile evaders, such as smugglers/criminals, or friendly evaders, such as lost hikers. Based on the features of the area of the terrain where the pursuit takes place, and the visibility and motion characteristics of the UAVs, we show how to plan their synchronized trajectories in a way that maximizes the likelihood of a successful pursuit, while minimizing their battery or fuel usage, which may, in turn, enable a longer pursuit. Our algorithm explores useful I/Oefficient data structures and branchcutting (search pruning) techniques to achieve further speedup by limiting the storage requirements and the total number of graph nodes searched, respectively.
hide details read details

Swaminathan Sankararaman, Karim AbuAffash, Alon Efrat, Sylvester ErikssonBique, Valentin Polishchuk, Srinivasan Ramasubramanian and Michael Segal
Proceedings of the 13th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), 2012.
Abstract:In this paper, we study strategies for allocating and managing friendly jammers, so as to create virtual barriers that would prevent hostile eavesdroppers from tapping sensitive wireless communication. Our scheme precludes the use of any encryption technique. Applications include domains such as (i) protecting the privacy of storage locations where RFID tags are used for item identification, (ii) secure reading of RFID tags embedded in credit cards, (iii) protecting data transmitted through wireless networks, sensor networks, etc. By carefully managing jammers to produce noise, we show how to reduce the SINR of eavesdroppers to below a threshold for successful reception, without jeopardizing network performance. We present algorithms targeted towards optimizing power allocation and number of jammers needed in several settings. Experimental simulations back up our results.
doi: 10.1145/2248371.2248383
hide details read details

Pankaj K. Agarwal, Alon Efrat, Swaminathan Sankararaman and Wuzhou Zhang
Proceedings of the 31st ACM Symposium on Principles of Database Systems (PODS), 2012.
Abstract:Nearestneighbor queries, which ask for returning the nearest neighbor of a query point in a set of points, are important and widely studied in many fields because of a wide range of applications. In many of these applications, such as sensor databases, location based services, face recognition, and mobile data, the location of data is imprecise. We therefore study nearest neighbor queries in a probabilistic framework in which the location of each input point and/or query point is specified as a probability density function and the goal is to return the point that minimizes the expected distance, which we refer to as the expected nearest neighbor (ENN). We present methods for computing an exact ENN or an \(\varepsilon\)approximate ENN, for a given error parameter \(0\leq \varepsilon\leq 1\), under different distance functions. These methods build an index of nearlinear size and answer ENN queries in polylogarithmic or sublinear time, depending on the underlying function. As far as we know, these are the first nontrivial methods for answering exact or \(\varepsilon\)approximate ENN queries with provable performance guarantees.
doi: 10.1145/2213556.2213588
hide details read details

Anantha R. Krishnan, Swaminathan Sankararaman and Bane Vasic
Proceedings of the 10th International Conference on Telecommunication in Modern Satellite, Cable and Broadcasting Services (TELSIKS), 2011.
Abstract:In this paper, we consider the problem of reconstruction of sparse signals in compressed sensing. In particular, we introduce a novel iterative algorithm based on graphbased decoding of lowdensity paritycheck codes which possesses desirable properties like good performance, low complexity and running time, and ease of implementation. In this work, we outline the reconstruction algorithm, and analyze its performance on some measurement matrices. Furthermore, we also provide some initial results on the theoretical performance limits of this algorithm.
doi: 10.1109/TELSKS.2011.6112021
hide details read details

Pankaj K. Agarwal, Alon Efrat, Shashidhara Ganjugunte, David Hay, Swaminathan Sankararaman and Gil Zussman
Proceedings of the 30th IEEE International Conference on Computer Communications (INFOCOM), 2011.
Abstract:Telecommunications networks, and in particular optical WDM networks, are vulnerable to largescale failures of their physical infrastructure, resulting from physical attacks (such as an Electromagnetic Pulse attack) or natural disasters (such as solar flares, earthquakes, and floods). Such events happen at specific geographical locations and disrupt specific parts of the network but their effects are not deterministic. Therefore, we provide a unified framework to model the network vulnerability when the event has a probabilistic nature, defined by an arbitrary probability density function. Our framework captures scenarios with a number of simultaneous attacks, in which network components consist of several dependent subcomponents, and in which either a 1+1 or a 1:1 protection plan is in place. We use computational geometric tools to provide efficient algorithms to identify vulnerable points within the network under various metrics. Then, we obtain numerical results for specific backbone networks, thereby demonstrating the applicability of our algorithms to realworld scenarios. Our novel approach allows for identifying locations which require additional protection efforts (e.g., equipment shielding). Overall, the paper demonstrates that using computational geometric techniques can significantly contribute to our understanding of network resilience.
doi: 10.1109/INFCOM.2011.5934942
hide details read details

Pankaj K. Agarwal, Alon Efrat, Shashidhara Ganjugunte, David Hay, Swaminathan Sankararaman and Gil Zussman
Proceedings of the 2010 IEEE Military Communications Conference (MILCOM), 2010.
Abstract:Telecommunications networks heavily rely on the physical infrastructure and, are therefore, vulnerable to natural disasters, such as earthquakes or floods, as well as to physical attacks, such as an Electromagnetic Pulse (EMP) attack. Largescale disasters are likely to destroy network equipment and to severely affect interdependent systems such as the powergrid. In turn, longterm outage of the powergrid might cause additional failures to the telecommunication network. In this paper, we model an attack as a disk around its epicenter, and provide efficient algorithms to find vulnerable points within the network, under various metrics. In addition, we consider the case in which multiple disasters happen simultaneously and provide an approximation algorithm to find the points which cause the most significant destruction. Finally, since a network element does not always fail, even when it is close to the attack's epicenter, we consider a simple probabilistic model in which the probability of a network element failure is given. Under this model, we tackle the cases of single and multiple attacks and develop algorithms that identify potential points where an attack is likely to cause a significant damage.
doi: 10.1109/MILCOM.2010.5679556
hide details read details

Esther M. Arkin, Alon Efrat, Joseph S. B. Mitchell, Valentin Polishchuk, Srinivasan Ramasubramanian, Swaminathan Sankararaman and Javad Taheri
Proceedings of the 6th ACM SIGACT/SIGMOBILE International Workshop on Foundations of Mobile Computing (DIALMPOMC), 2010.
Abstract:We study the problem of transmitting data from a set of sensors to a basestation where the data is to be gathered. Each sensor continuously generates data and has to transmit it through the network (via other sensor nodes) to the basestation. Considering the battery limitations of the sensors, our goal is to find an optimum location of the basestation and a corresponding data transmission scheme for routing the data from the sensors, such that the network is operating for the longest possible time. We focus mainly on tree networks for 2level trees, with at most 2 hops from sensor to the basestation. For such networks we give efficient algorithms for forwarding data from sensors to the basestation and for locating the basestation optimally for maximizing network lifetime. Further, we show that determining a transmission protocol for trees with 3 or more levels is NPhard. We demonstrate the effectiveness of our methods with experimental results on simulated data, comparing our 2level tree algorithm with methods based on linear programming.
doi: 10.1145/1860684.1860692
hide details read details

Swaminathan Sankararaman, Alon Efrat, Srinivasan Ramasubramanian and Pankaj K. Agarwal
Proceedings of the 29th IEEE International Conference on Computer Communications (INFOCOM), MiniConference, 2010.
Abstract:Multichannel wireless networks are increasingly being employed as infrastructure networks, e.g. in metro areas. Nodes in these networks frequently employ directional antennas to improve spatial throughput. In such networks, given a source and destination, it is of interest to compute an optimal path and channel assignment on every link in the path such that the path bandwidth is the same as that of the link bandwidth and such a path satisfies the constraint that no two consecutive links on the path are assigned the same channel, referred to as ``Channel Discontinuity Constraint'' (CDC). CDCpaths are also quite useful for TDMA system, where preferably every consecutive links along a path are assigned different time slots. This paper contains several contributions. We first present an \(O(N^2)\) distributed algorithm for discovering the shortest CDCpath between given source and destination. For use in wireless networks, we explain how spatial properties can be used for dramatically expedite the algorithm. This improves the running time of the \(O(N^3)\) centralized algorithm of Ahuja et al. for finding the minimumweight CDCpath. Our second result is a generalized \(t\)spanner for CDCpath; For any \(\theta>0\) we show how to construct a subnetwork containing only \(O(N/\theta)\) edges, such that that length of shortest CDCpaths between arbitrary sources and destinations increases by only a factor of at most \(1/(12\sin (\theta/2))^2\). This scheme can be implemented in a distributed manner with a message complexity of \(O(N\log N)\) and it is highly dynamic, so addition/deletion of nodes are easily handled in a distributed manner. An important conclusion of this scheme is in the case of directional antennas are used. In this case, it is enough to consider only the two closest nodes in each cone.
doi: 10.1109/INFCOM.2010.5462188
hide details read details
Manuscripts

Swaminathan Sankararaman, Pankaj
K. Agarwal, Thomas Mølhave and Arnold P. Boedihardjo
arXiv:1303.1585 [cs.CG], 2013.
Abstract:With recent advances in sensing and tracking technology, trajectory data is becoming increasingly pervasive and analysis of trajectory data is becoming exceedingly important. A fundamental problem in analyzing trajectory data is that of identifying common patterns between pairs or among groups of trajectories. In this paper, we consider the problem of identifying similar portions between a pair of trajectories, each observed as a sequence of points sampled from it.
We present new measures of trajectory similarity  both local and global  between a pair of trajectories to distinguish between similar and dissimilar portions. Our model is robust under noise and outliers, it does not make any assumptions on the sampling rates on either trajectory, and it works even if they are partially observed. Additionally, the model also yields a scalar similarity score which can be used to rank multiple pairs of trajectories according to similarity, e.g. in clustering applications. We also present efficient algorithms for computing the similarity under our measures; the worstcase running time is quadratic in the number of sample points.
Finally, we present an extensive experimental study evaluating the
effectiveness of our approach on real datasets, comparing with it
with earlier approaches, and illustrating many issues that arise in
trajectory data. Our experiments show that our approach is highly
accurate in distinguishing similar and dissimilar portions as
compared to earlier methods even with sparse sampling.
hide details read details

Swaminathan Sankararaman, Alon Efrat, Srinivasan Ramasubramanian and Javad Taheri
arXiv:0911.4332 [cs.NI], 2009.
Abstract:Sensor networks are particularly applicable to the tracking of objects in motion. For such applications, it may not necessary that the whole region be covered by sensors as long as the uncovered region is not too large. This notion has been formalized by Balasubramanian et.al. as the problem of \(\kappa\)weak coverage. This model of coverage provides guarantees about the regions in which the objects may move undetected. In this paper, we analyse the theoretical aspects of the problem and provide guarantees about the lifetime achievable. We introduce a number of practical algorithms and analyse their significance. The main contribution is a novel linear programming based algorithm which provides nearoptimal lifetime. Through extensive experimentation, we analyse the performance of these algorithms based on several parameters defined.
hide details read details
Dissertations/Theses

Swaminathan Sankararaman
Ph.D. Dissertation, The University of Arizona, 2011.
Abstract:Wireless communications has a wide range of applications including cellular telephones, wireless networking and security systems. Typical systems work through radio frequency communication and this is heavily dependent on the geographic characteristics of the environment. This dissertation discusses the application of geometric optimization in wireless networks where the communication ``links'' are not static but may be dynamically changing. We show how to exploit the geometric properties of these networks to model their behavior. In the first part of the dissertation, we consider the problem of interferenceaware routing in Multichannel mesh networks employing directional antennas to improve spatial throughput. In such networks, optimal routes are paths with a channel assignment for the links such that the path and link bandwidths are the same. We develop a method to perform topology control while taking into account interference by constructing a spanner; a subnetwork containing \(O(n/\theta)\) links, where \(n\) is the network size and \(\theta\) is a tunable parameter, such that path costs increase by at most a constant factor. In second part, we study the problem of basestation positioning in Sensor Networks such that we achieve energyefficient data transmission from the sensors. Given the battery limitations of the sensors, our objective is to maximize the network lifetime. First, we present efficient algorithms for computing a transmission scheme given a fixed basestation and also provide a distributed implementation. Next, we present efficient algorithms for the problem of locating the basestation and simultaneously finding a transmission scheme. We compare our algorithms with linearprogramming based algorithms through simulations. In the third part, we study strategies for managing friendly jammers to create virtual barriers preventing eavesdroppers from tapping sensitive RFID communication. Our scheme precludes the use of encryption. Applications domains include (i) privacy of inventory management systems, (ii) credit card communications, (iii) secure communication in any wireless networks without encryption. By carefully managing jammers producing noise, we show how to degrade the signal at eavesdroppers sufficiently, without jeopardizing network performance. We present algorithms targeted towards optimizing the number and power of jammers. Experimental simulations back up our results.
hide details read details

Swaminathan Sankararaman
M.S. Thesis, The University of Arizona, 2008.
Abstract:Multichannel wireless networks are increasingly being employed as infrastructure networks in metro areas. In addition, nodes in these networks employ directional antennas to improve spatial throughput. In such networks, given a source and destination, it is of interest to compute an optimal path and channel assignment on every link in the path such that the path bandwidth is the same as that of the link bandwidth and such a path must satisfy the constraint that no two consecutive links on the path are assigned the same channel, referred to as ``Channel Discontinuity Constraint'', CDC. This work presents an efficient distributed algorithm for the problem of finding minimum hop CDCpaths in wireless networks assuming that all the nodes employ the same transmission range. This algorithm is based on Edmonds' algorithm for maximum cardinality matching using an expansion graph on the network known as the EdmondsSzeider expansion. We show that the message complexity of the algorithm developed in this work is quadratic in the number of nodes in the network.
hide details read details