Selected Recent Publications

2010

• Space-efficient Online Approximation of Time Series Data: Streams, Amnesia, and Out-of-order.
  Sorabh Gandhi, Luca Foschini and Subhash Suri.
  26th ICDE, Long Beach, CA, March 1-6, 2010.

• Untangling the Braid: Finding Outliers in a Set of Streams.
  Chiranjeeb Buragohain, Luca Foschini and Subhash Suri.
  ALENEX 2010, SODA Workshop on Algorithm Engineering & Experiments, Austin, TX, Jan 2010.

2009

• Catching Elephants with Mice: Sparse Sampling for Monitoring Sensor Networks
  Sorabh Gandhi, Subhash Suri and Emo Welzl
  ACM Transactions on Sensor Networks, to appear 2009.

• GAMPS: Compressing Multi Sensor Data by Grouping and Amplitude Scaling.
  Sorabh Gandhi, Suman Nath, Subhash Suri and Jie Liu.
  ACM SIGMOD, Providence, RI, June 29 - July 2, 2009.

• Reconstructing Visibility Graphs with Simple Robots.
  Davide Bilo, Yann Disser, Matus Mihalak, Subhash Suri, Elias Vicari and Peter Widmayer.
  SIROCCO 2009 (16th International Colloquium on Structural Information
  and Communication Complexity), Slovenia, May 25-27, 2009.

• On the Limitations of Combinatorial Visibilities.
  Davide Bilo, Yann Disser, Matus Mihalak, Subhash Suri, Elias Vicari and Peter Widmayer.
  25th European Workshop on Computational Geometry, Brussels, Belgium, Mar 16-18, 2009.

• Target Tracking with Binary Proximity Sensors.
  Nisheeth Shrivastava, R. Mudumbai, Upamanyu Madhow and Subhash Suri.
  ACM Transactions on Sensor Networks, to appear 2009.

2008

• eBay in the Sky: Strategy-Proof Wireless Spectrum Auctions.
  Xia Zhou, Sorabh Gandhi, Subhash Suri and Heather Zheng.
  ACM MobiCom, San Francisco, Sept 14-19, 2008.

• Cluster Hull: A Technique for Summarizing Spatial Data Streams.
  John Hershberger, Nisheeth Shrivastava and Subhash Suri.
  ACM Journal of Experimental Algorithmics, Vol 13, 2008

• Bandwidth-Constrained Allocation in Grid Computing
  Anshul Kothari, Subhash Suri, and Yunhong Zhou
  Algorithmica, Vol. 52, 487--501, 2008.

• Formulating and implementing profiling over adaptive ranges
  Shashi Mysore, Banit Agrawal, Tim Sherwood, Nisheeth Shrivastava and Subhash Suri.
  ACM Transactions on Architecture and Code Optimization , Vol. 5, 2008.

• Simple Robots with Minimal Sensing: From Local Visibility to Global Geometry
  Subhash Suri, Elias Vicari, Peter Widmayer
  International Journal of Robotics Research, Vol 27, Sept. 2008.

• Target Counting under Minimal Sensing: Complexity and Approximations.
  Sorabh Gandhi, Rajesh Kumar and Subhash Suri.
  ALGOSENSORS, Reykjavik, Iceland, July 2008.

• Simple Robots in Polygonal Environments: A Hierarchy.
  Jan Brunner, Matus Mihalak, Subhash Suri, Elias Vicari and Peter Widmayer.
  ALGOSENSORS, Reykjavik, Iceland, July 2008.

• Simplified Planar Coresets for Data Streams.
  John Hershberger and Subhash Suri.
  SWAT '08, Gothenburg, Sweden, July 2-4, 2008.

• Angle Optimization in Target Tracking.
  Beat Gfeller, Matus Mihalak, Subhash Suri, Elias Vicari and Peter Widmayer.
  SWAT '08, Gothenburg, Sweden, July 2-4, 2008.

• A game-theoretic analysis of wireless access point selection by mobile users.
  Kimaya Mittal, Elizabeth Belding and Subhash Suri.
  Computer Communications (Elsevier), Vol 31, pp. 2049-2062, 2008.

• Quantiles on Streams.
  Chiranjeeb Buragohain and Subhash Suri
  To appear in Encyclopedia of Database Systems, 2007, Springer.

• Adaptive Sampling for Geometric Problems over Data Streams.
  John Hershberger and Subhash Suri
  To appeara in Computational Geometry: Theory and Applications (Elsevier), 2008.

• Detecting Cuts in Sensor Networks,
  Nisheeth Shrivastava, Subhash Suri, and Csaba Toth
  ACM Transactions on Sensor Networks, Vol. 4 (2), pp. 1--25, Mar 2008.

• Towards Real-Time Dynamic Spectrum Auctions,
  Sorabh Gandhi, Chiranjeeb Buragohain, Lili Cao, Heather Zheng and Subhash Suri.
  Computer Networks (Special Issue on Cognitive Wireless Networks), Vol. 52 (4), pp. 879--897, March 2008.

2007

• Catching Elephants with Mice: Sparse Sampling for Monitoring Sensor Networks
  Sorabh Gandhi, Subhash Suri and Emo Welzl
  5th ACM Conference on Embedded Networked Sensor Systems (SenSys) , Nov. 6-9, 2007, Sydney, Australia.

• Attribute-based access to distributed data over P2P networks,
  Divyakant Agrawal, Amr El Abbadi and Subhash Suri.
  Int. J. Computational Science and Engineering, Vol. 3(2), pp. 112--123, 2007.

• Finding the k Shortest Simple Paths: A New Algorithm and its Implementation.
  John Hershberger, Matthew Maxel and Subhash Suri.
  To appear in ACM Transactions on Algorithms, 2007.

• Simple Robots with Minimal Sensing: From Local Visibility to Global Geometry
  Subhash Suri, Elias Vicari, Peter Widmayer
  22nd Conference on Artificial Intelligence (AAAI-07), July 22-26, Vancouver, Canada.

• Counting Targets with Mobile Sensors in an Unknown Environment
  Beat Gfeller, Matus Mihalak, Subhash Suri, Elias Vicari and Peter Widmayer
  ALGOSENSORS, July 2007, Wroclaw, Poland.

• Improved Throughput Bounds for Interference-aware Routing in Wireless Networks
  Chiranjeeb Buraagohain, Subhash Suri, Csaba Toth, Yunhong Zhou
  13th Computing and Combinatorics Conference (COCOON-07), July 16-19, Banff, Canada.

• Approximate Isocontours and Spatial Summaries for Sensor Networks.
  Sorabh Gandhi, John Hershberger, and Subhash Suri.
  (Best Paper Award.) IPSN '07, April 25-27, Cambridge, MA.

• Tracking Multiple Targets Using Binary Proximity Sensors.
  Jaspreet Singh, Rajesh Kumar, Upamanyu Madhow, Subhash Suri, and Richard Cagley.
  IPSN '07, April 25-27, Cambridge, MA.

• A General Framework for Clearing Auction of Wireless Spectrum.
  Sorabh Gandhi, Chiranjeeb Buragohain, Lili Cao, Haitao Zheng and Subhash Suri.
  (Best Student Paper Award.) IEEE DySPAN'07, April 17-20, Dublin, Ireland, 2007.

• Space Efficient Streaming Algorithms for the Maximum Error Histogram.
  Chiranjeeb Buragohain, Nisheeth Shrivastava and Subhash Suri.
  IEEE ICDE '07, April 16-20, Istambul, Turkey, 2007.

• Selfish Load Balancing and Atomic Congestion Games.
  Subhash Suri, Csaba D. Toth, and Yunhong Zhou.
  Algorithmica, Vol. 47(1), pages 79-96, Jan. 2007.

• On the difficulty of some shortest path problems.
  John Hershberger, Subhash Suri, Amit M. Bhosle.
  ACM Transactions on Algorithms, Vol. 3(1), 2007.

2006

• Target Tracking with Binary Proximity Sensors: fundamental limits, minimal descriptions, and algorithms.
  Nisheeth Shrivastava, R. Mudumbai, Upamanyu Madhow and Subhash Suri.
  ACM SenSys '06, Nov. 1-3, Boulder, 2006.

• Search-quality Tradeoffs for Routing in Non-ideal Wireless Networks.
  Chiranjeeb Buragohain, Divy Agrawal, and Subhash Suri.
  IEEE SECON '06, Sept 25-28, Virginia.

• Adaptive Spatial Partitioning for Multidimensional Data Streams.
  John Hershberger, Nisheeth Shrivastava, Subhash Suri and Csaba Toth.
  Algorithmica, Volume 46(1), pages 97-117, Sept 2006.

• Contour Approximation in Sensor Networks.
  Chiranjeeb Buragohain, Sorabh Gandhi, John Hershberger and Subhash Suri.
  DCOSS '06, June 18-20, San Francisco.

• Distributed Navigation Algorithms for Sensor Networks.
  Chiranjeeb Buragohain, Divy Agrawal and Subhash Suri.
  INFOCOM '06, Apr 25-27, Barcelona.

• Cluster Hull: A Technique for Summarizing Spatial Data Streams.
  John Hershberger, Nisheeth Shrivastava and Subhash Suri.
  ICDE'06, April 3-7, 2006, Atlanta.

• Profiling over Adaptive Ranges.
  Shashi Mysore, Banit Agrawal, Tim Sherwood, Nisheeth Shrivastava and Subhash Suri.
  4th Annual ACM/IEEE International Symposium on Code Generation and Optimization, Mar 26-29, New York, NY.
  Received the Best Paper Award.

• Summarizing Spatial Data Streams Using ClusterHulls.
  Nisheeth Shrivastava, John Hershberger, and Subhash Suri.
  ALENEX '06, Jan 21-25, Miami.
  Invited to Special Issue of ACM Journal of Experimental Algorithms.

• Fast Packet Classification for Two-Dimensional Conflict-Free Filters.
  Florin Baboescu, Priyank Warkhede, Subhash Suri, George Varghese.
  Computer Networks, Aug. 2005.

• Range Counting over Multidimensional Data Streams.
  Subhash Suri, Csaba Toth and Yunhong Zhou.
  Invited paper to Special Issue of Discrete and Computational Geometry, accepted 2005.

• Interval Subset Sum and Uniform-Price Auction Clearing .
  Anshul Kothari, Subhash Suri and Yunhong Zhou.
  COCOON 2005, August 16-19, 2005, Kunming, China.

• Space Complexity of Hierarchical Heavy Hitters in Multi-Dimensional Data Streams.
  John Hershberger, Nisheeth Shrivastava, Subhash Suri and Csaba Toth.
  ACM PODS '05, June 13-15, Baltimore.

• Fishing for Patterns in Data Streams.
  John Hershberger, Nisheeth Shrivastava, Subhash Suri and Csaba Toth.
  Workshop on Massive Geometric Data Sets, June 9, Pisa, Italy.

• Summarizing Spatial Data Streams.
  John Hershberger, Nisheeth Shrivastava and Subhash Suri.
  Workshop on Massive Geometric Data Sets, June 9, Pisa, Italy.

• Binary Space Partitions of Orthogonal Subdivisions.
  John Hershberger, Subhash Suri and Csaba Toth.
  To appear in SIAM J. of Computing, 2005.

• Detecting Cuts in Sensor Networks.
  Nisheeth Shrivastava, Subhash Suri and Csaba Toth.
  IPSN '05, April 25-27, Los Angeles.

• Power Aware Routing for Sensor Databases.
  Chiranjeeb Buragohain, Divy Agrawal and Subhash Suri.
  INFOCOM '05, Mar 13-17, Miami.

• Attribute-Based Access to Distributed Data over P2P Networks.
  Divy Agrawal, Amr El Abbadi and Subhash Suri.
  Workshop on Databases in Networked Information Systems, Japan, Mar 28-30, 2005.

2004

• Adaptive Spatial Partitioning for Multidimensional Data Streams.
  John Hershberger, Nisheeth Shrivastava, Subhash Suri and Csaba Toth.
  ISAAC '04, Dec. 20-22, Hong Kong.

• Medians and Beyond: New Aggregation Techniques for Sensor Networks.
  Nisheeth Shrivastava, Chiranjeeb Buragohain, Divy Agrawal, Subhash Suri.
  ACM SenSys '04, Nov. 3-5, Baltimore, MD.

• Congestion Games, Load Balancing, and Price of Anarchy.
  Anshul Kothari, Subhash Suri, Csaba D. Toth, and Yunhong Zhou.
  CAAN '04 (Workshop on Combinatorial and Algorithmic Aspects of Networking), Aug 5-7, Banff, Alberta.

• Selfish Load Balancing and Atomic Congestion Games..
  Subhash Suri, Csaba Toth and Yunhong Zhou.
  ACM SPAA '04 (Symp. on Parallelism in Algorithms & Architectures) June 27--30, Barcelona.

• Adaptive Sampling for Geometric Problems over Data Streams.
  John Hershberger and Subhash Suri.
  ACM PODS '04 (Symp. on Principles of Database Systems) June 13-18, Paris, France.

• Range Counting over Multidimensional Data Streams.
  Subhash Suri, Csaba Toth and Yunhong Zhou.
  ACM Symposium on Computational Geometry '04 June 9--11, New York.

• Binary Space Partitions of Orthogonal Subdivisions.
  John Hershberger, Subhash Suri and Csaba Toth.
  ACM Symposium on Computational Geometry '04 June 9--11, New York.

• Uncoordinated Load Balancing and Congestion Games in P2P Systems.
  Subhash Suri, Csaba Toth and Yunhong Zhou.
  IPTPS '04 (3rd International Workshop on Peer-to-Peer Systems), February 26-27, San Diego.

• Towards Realisitic Mobility Models for Mobile Ad hoc Networks.
  Amit Jardosh, Elizabeth Belding-Royer, Kevin Almeroth and Subhash Suri.
  Mobicom 2003, Sept. 14-19, San Diego.

• A Game-Theoretic Framework for Incentives in P2P Systems.
  Chiranjeeb Buragohain, Divy Agrawal and Subhash Suri.
  IEEE P2P 2003 , Sept. 1-3, Linkoping, Sweden.

• Range Addressable Network: A P2P Cache Architecture for Data Ranges.
  Anshul Kothari, Divy Agrawal, Abhishek Gupta and Subhash Suri.
  IEEE P2P 2003 , Sept. 1-3, Linkoping, Sweden.

• Bandwidth Constrained Allocation in Grid Computing.
  Anshul Kothari, Subhash Suri, and Yunhong Zhou.
  WADS 2003: July 30- Aug 1, Ottawa.

• Convex Hulls and Related Problems in Data Streams.
  John Hershberger and Subhash Suri.
  MPDS 2003: ACM SIGMOD/PODS Workshop on Management & Processing of Data Streams, June 8, 2003.

• Approximately-Strategyproof and Tractable Multi-Unit Auctions.
  Anshul Kothari, David Parkes, and Subhash Suri.
  ACM Conference on Electronic Commerce 2003, June 9-12, San Diego

• Solving Combinatorial Exchanges: Optimality via a Few Partial Bids.
  Anshul Kothari, Tuomas Sandholm and Subhash Suri.
  ACM Conference on Electronic Commerce 2003 (poster), June 9-12, San Diego

• On the Difficulty of Some Shortest Path Problems.
  John Hershberger, Subhash Suri and Amit Bhosle.
  STACS-2003, Feb 27 - Mar 1, Berlin

• Finding the K Shortest Simple Paths: A New Algorithm and its Implementation.
  John Hershberger, Matthew Maxel and Subhash Suri.
  ALENEX 2003, Jan 11-14, Baltimore.

• Binary Space Partitions for 3D Subdivisions.
  John Hershberger and Subhash Suri.
  SODA 2003, Jan 12-14, Baltimore.

2002

• Winner Determination in Combinatorial Auction Generalizations.
  Tuomas Sandholm, Subhash Suri, Andrew Gilpin and David Levine.
  AAMAS-2002: Autonomous Agents and Multiagent Systems, Italy.

• Optimal Clearing of Supply/Demand Curves.
  Tuomas Sandholm and Subhash Suri.
  ISAAC: Proc. of 13th Annual International Symposium on Algorithms and Computation, Vancouver, Canada, November 20-23, 2002.

• Algorithms for a Minimum Volume Simplex in Three Dimensions.
  Yunhong Zhou and Subhash Suri.
  SIAM Journal on Computing, Vol. 31 (5), pp. 1339--1357, 2002.

• Silo, Rainbow, and Caching Token: Schemes for Scalable Fault-Tolerant Stream Caching.
  Youngsu Chae, Katherine Guo, Milind M. Buddhikot, Subhash Suri, and Ellen Zegura.
  IEEE Journal on Selected Areas in Communications, Vol. 20 (7), pp.~1328--1344, Sept 2002.

• CABOB: A Fast Optimal Algorithm for Combinatorial Auctions.
  Tuomas Sandholm, Subhash Suri, Andrew Gilpin and David Levine.
  IJCAI-2001: 17th International Joint Conference on Artificial Intelligence

2001

• Vickrey Prices and Shortest Paths: What is an edge worth?.
  John Hershberger and Subhash Suri.
  FOCS-2001: 42nd Annual Symposium on Foundations of Computer Science

• Fast Packet Classification for Two-Dimensional Conflict-Free Filters.
  Priyank Warkhede, Subhash Suri, George Varghese.
  IEEE INFOCOM 2001.

• A Lower Bound for Multicast Key Distribution.
  Jack Snoeyink, Subhash Suri, George Varghese.
  IEEE INFOCOM 2001.

• Fast Firewall Implementations for Software and Hardware-Based Routers.
  Lili Qiu, George Varghese, and Subhash Suri.
  Proc. of 9th International Conference on Network Protocol, 2001.