Research Papers
       
     Reverse chronological order, no editorializing, papers in PS/PDF format.

                                                         Unpublished
  1. Estimating Aggregate Properties on Probabilistic Streams.   A. McGregor, S. Muthukrishnan. cs.DS/0612031
  2. Approximate Histogram and Wavelet Summaries of Streaming Data. S. Muthukrishan and M. Strauss. DIMACS TR 2004-52.
  3. Radial histograms for spatial streams.   G. Cormode and S. Muthukrishnan. DIMACS TR 2003-11.
  4. QUICKSAND: Quick summary and analysis of network data . DIMACS TR 2001-43. A. Gilbert, Y. Kotidis, S. Muthukrishnan and M. Strauss. Cached.
  5. Support for erroneous packet reporting in 802.11 data networks. IEEE 802.11e Wireless LAN Working Group Meeting, Jan 2002.  S. Diggavi, X. Gao, S. Muthukrishnan and M. Sherman.
  6. S. Bellovin , A. Buchsbaum, and S. Muthukrishnan, TCP Compression Filter . Internet Draft 1999. Cached.
  7. S. Bellovin, A. Buchsbaum, and S. Muthukrishnan, TCP Filters . Internet Draft 1999. Cached.    

                                           2009
  1. General Auction Mechanism for Search Advertising. G. Aggarwal, S. Muthukrishnan, D. Pal, M. Pal. WWW 09.
  2. Bid Optimization in Broad-Match Ad Auctions. E. Even-Dar, Y. Mansour, V. Mirrokni, S. Muthukrishnan, U. Nadav.  
  3. Optimal Cache-Aware Suffix Selection. G. Francheschini, R. Grossi and S. Muthukrishnan. STACS 09.
  4. An online mechanism for Ad Slot Reservations with Cancellations. F. Constantin, J. Feldman, S. Muthukrishnan and M. Pal. SODA 09.
                                           2008                    
  1. Internet Ad Auctions: Insights and Directions.S. Muthukrishnan:  ICALP (1) 2008.
  2. Algorithmic Methods for Sponsored Search Advertising. J. Feldman and S. Muthukrishnan.  Chapter in Book: Performance Modeling and Engineering. 
  3. Position Auctions with Bidder-Specific Minimum Prices. E. Even-Dar, J. Feldman, Y. Mansour and S Muthukrishnan. WINE 2008.
  4. Sponsored Search Auctions with Markovian Users. G. Aggarwal, J. Feldman, S Muthukrishnan and M. Pal. WINE 2008
  5. Range Medians. S. Har-Peled and S. Muthukrishnan. ESA 08.
  6. On distributing symmetric streaming computations. J. Feldman, S. Muthukrishnan, A. Sidiropoulos, C. Stein and Z. Svitkina. SODA 08.
  7. Algorithms for distributed, functional monitoring. G. Cormode, S. Muthukrishnan,and K. Yi.  SODA 08. This material is based upon work supported by the National Science Foundation under Grant No. 0414852.
  8. J. Feldman, S. Muthukrishnan, E. Nikolova, M. Pál: A Truthful Mechanism for Offline Ad Slot Scheduling. SAGT 2008.
  9. Summarizing Two-Dimensional Data with Skyline-Based Statistical Descriptors. Graham Cormode, Flip Korn, S. Muthukrishnan, Divesh Srivastava. SSDBM 08.
  10. Query-aware partitioning for monitoring massive network data streams. T. Johnson, S. Muthukrishnan, V. Shkapenyuk, Oliver Spatscheck. SIGMOD 2008. This material is based upon work supported by the National Science Foundation under Grant No. 0414852.
  11. On Signatures for Communication Graphs.  G. Cormode, F. Korn, S. Muthukrishnan, Y. Wu. ICDE 2008.
  12. Query-Aware Partitioning for Monitoring Massive Network Data Streams.  T. Johnson, S. Muthukrishnan, V. Shkapenyuk, O. Spatscheck. ICDE 2008. (Short)
  13. The Magnus-Derek game. Z. Nedev and S. Muthukrishnan.  Theor. Comput. Sci. 393(1-3): 124-132 (2008)  JOURNAL.
                                           2007                                 

  1. Radix sorting with no extra space, G. Franceschini, S Muthukrishnan and M. Patrascu. ESA 2007.
  2. Stochastic Models for Budget Optimization in Search-Based Advertising. S. Muthukrishnan, M. Pal and Z. Svitkina. WINE 2007,  Workshop on Sponsored Search Auctions, WWW 2007.
  3. In-place suffix sorting. G. Francheschini and S. Muthukrishnan. ICALP 2007.
  4. Optimal suffix selection. G.  Franceschini and S. Muthukrishnan. STOC 2007.
  5. Estimating statistical aggregates on probabilistic data streams. T.S. Jayram, A. McGregor, S. Muthukrishnan and E. Vee. PODS 2007.
  6. Budget optimization in search-based advertising auctions. J. Feldman, S. Muthukrishnan, M. Pal and C. Stein. EC 2007.
  7. Data streaming algorithms for data in motion. M. Hoffmann, S. Muthukrishnan and R. Raman. ESCAPE 2007.
  8. Sequential Change Detection on Data Streams. S. Muthukrishnan, E. Berg and Y. Wu.  ICDM Workshop on Data Stream Mining & Mgmt. "This material is based upon work supported by the National Science Foundation under Grant No. 0414852."
  9. No blog is an island: Analyzing connections across information networks. S. Bhagat, G. Cormode, S. Muthukrishnan, I. Rozenbaum and H. Xue. ICWSM 2007.
  10. How to scalably skip past streams. S. Bhattacharyya, A. Madeira, S. Muthukrishnan, T. Ye. WSSP 2007. With ICDE 2007.
  11. Query-aware sampling for data streams. T. Johnson, S. Muthukrishnan, V. Shkapenyuk and O. Spatscheck. WSSP 2007. With ICDE 2007. "This material is based upon work supported by the National Science Foundation under Grant No. 0414852."
  12. Conquering the Divide: Continuous Clustering of Distributed Data Streams. G. Cormode, S. Muthukrishnan, W. Zhuang. ICDE 2007. "This material is based upon work supported by the National Science Foundation under Grant No. 0414852."
  13. Monitoring Regular Expressions on Out-of-Order Streams. I. Rozenbaum, T. Johnson, S. Muthukrishnan. ICDE 2007. POSTER. "This material is based upon work supported by the National Science Foundation under Grant No. 0414852."
  14. The string edit distance matching problem with moves. G. Cormode and S. Muthukrishnan. Transactions of Algorithms. Vol 3, No 1. 2007.  JOURNAL. (Invited from SODA 2002).    
  15. A data structure for a sequence of string accesses in external memory. .V. Ciriani, P. Ferragina, F. Luzzio and S. Muthukrishnan. Transactions of Algorithms. Vol 3, No 1. 2007. JOURNAL.
                                          2006  
  1. Some Algorithmic Problems and Results in Compressed Sensing. S. Muthukrishnan.  Allerton Conf 2006.  This material is based upon work supported by the National Science Foundation under Grant No. 0354690."
  2. Bidding to the Top: VCG and Equilibria of Position-Based Auctions.  G. Aggarwal, J. Feldman, S. Muthukrishnan. WAOA 2006. TR at arXiv.
  3. Subspace Sampling and Relative-Error Matrix Approximation: Column-Row-Based Methods. P. Drineas, M. Mahoney, S. Muthukrishnan. ESA 2006: 304-314. DIMACS TR 2006-04.
  4. Subspace Sampling and Relative-Error Matrix Approximation: Column-Based Methods. P. Drineas, M. Mahoney, S. Muthukrishnan. RANDOM 2006.
  5. Combinatorial algorithms for compressed sensing. G. Cormode and S. Muthukrishnan.  SIROCCO 2006. DIMACS TR 2005-25. 
  6. Modeling skew in data streams. F. Korn, S. Muthukrishnan and Y. Wu. SIGMOD 2006. 
  7. Space- and time-efficient deterministic algorithms for biased quantiles over data streams. G. Cormode, F. Korn, S. Muthukrishnan and D. Srivastava. PODS 2006.
  8. Compressing and searching XML data via two zips. P. Ferragina, F. Luccio, G. Manzini and S. Muthukrishnan. WWW 2006.   
  9. Estimating Entropy and Entropy Norm on Data Streams. A. Chakrabarti, Khanh Do Ba and S. Muthukrishnan. STACS 2006.  DIMACS TR 2005-33.
  10. Sampling algorithms for L_2 regression and applications. P. Drineas, M. Mahoney and S. Muthukrishnan. SODA 2006.
  11. What's different: Distributed continuous monitoring of duplicate-resilient aggregates on data streams. G. Cormode, S. Muthukrishnan and W. Zhuang. ICDE 2006. "This material is based upon work supported by the National Science Foundation under Grant No. 0414852."
  12. Special Issue on CPM Conf. Theoretical Computer Science Edited by S. Cenk Sahinalp, U. Dogrusoz and S. Muthukrishnan. JOURNAL.
  13. The Graham-Knowlton Problem Revisited. N. Goyal, S. Lodha, S. Muthukrishnan. Theory Comput. Syst. 39(3): 399-412 (2006). JOURNAL.
                                          2005
 
  1. Streams, security and scalability.  T. Johnson, S. Muthukrishnan, O. Spatscheck and D. Srivastava.  Proc.  of 19th Ann. IFIP Conference on Data and Applications Security, Lecture Notes in Computer Science 3654, Springer-Verlag, 1-15, 2005. 
  2. Subquadratic Algorithms for Workload-Aware Haar Wavelet Synopses. S. Muthukrishnan. FSTTCS 2005.  DIMACS TR 2004-42, 2004-25.
  3. Structuring labeled trees for optimal succinctness, and beyond. P. Ferragina and F. Luccio and G. Manzini and S. Muthukrishnan. FOCS 2005.
  4. Workload-Optimal Histograms on Streams. S. Muthukrishnan, M. Strauss and X. Zheng. ESA 2005.  Fuller version at DIMACS TR 2005-19.
  5. Summarizing and mining  inverse distributions on data streams via dynamic inverse sampling. G. Cormode, S. Muthukrishnan and I. Rozenbaum. VLDB 2005 .  DIMACS TR 2005-11 has fuller version.
  6. A heartbeat mechanism and its application in Gigascope.   T. Johnson, S. Muthukrishnan, O. Spatscheck and V. Shkapenyuk. VLDB 2005.
  7. Detecting malicious network traffic using inverse distributions of packet contents. D. Geiger, V. Karamcheti, Z. Kedem and S. Muthukrishnan. MineNet 05 .
  8. Improved time bounds for near-optimal sparse Fourier representations. A. Gilbert, S. Muthukrishnan and M. Strauss. SPIE Conf , Wavelets.
  9. Space Efficient Mining of Multigraph Streams. G. Cormode, S. Muthukrishan. PODS 2005 .
  10. Sampling Algorithms in a Stream Operator.  T. Johnson, S. Muthukrishnan, I. Rozenbaum. SIGMOD 2005 .
  11. Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles. G. Cormode, M. Garofalakis,  S. Muthukrishnan,  R. Rastogi  SIGMOD 2005. "This material is based upon work supported by the National Science Foundation under Grant No. 0414852."
  12. Efficient string matching algorithms for combinatorial universal denoising . S. Chen, S. Diggavi, S. Dusad and S. Muthukrishnan. DCC 2005 .
  13. Summarizing and Mining Skewed Data Streams. G. Cormode and S. Muthukrishnan. SDM 2005 .
  14. MoDB: Database systems for synthesizing human motion. T. Edmunds, S. Muthukrishnan, S. Sadhukha and S. Sueda. ICDE 2005 . DEMO. VIDEO: mov , avi
  15. Effective Computation of Biased Quantiles over Data Streams. G. Cormode, F. Korn, S. Muthukrishnan, D. Srivastava. ICDE 2005 .
  16. Substring compression problems. G. Cormode and S. Muthukrishnan. SODA 2005 .
  17. The Bin-Covering Technique for Thresholding Random Geometric Graph Properties. S. Muthukrishnan and G. Pandurangan.  SODA 2005 .
  18. Improved Range-Summable Random Variable Construction Algorithms . A. R. Calderbank, A. Gilbert, K. Levchenko, S. Muthukrishnan and M. Strauss. SODA 2005 . 
  19. What's hot and what's not: tracking most frequent items dynamically. G. Cormode, S. Muthukrishnan.  ACM Trans. Database Syst. 30(1): 249-278 (2005). JOURNAL. 
  20. Domain-driven data synopses for dynamic quantiles. A. Gilbert, Y. Kotidis, S. Muthukrishnan and M. Strauss. 17(7), July 2005. TKDE. JOURNAL.   
  21. An improved data stream summary: the count-min sketch and its applications. J. Algorithms, 55(1): 58--75, April 2005,  G. Cormode and S. Muthukrishnan.JOURNAL.  
  22. Approximation algorithms for array partitioning problems.  J. Algorithms, 54(1): 85--104, Jan 2005, S. Muthukrishnan and T. Suel. JOURNAL.
  23. Parallel scheduling problems in next generation wireless networks.    Networks , 45(1), 9--22, Jan 2005.  L. Becchetti, S. Leonardi, A. Marchetti-Spaccamela, A. Vitaletti, S. Diggavi, S. Muthukrishnan, T. Nandagopal. JOURNAL.    

    24.                                          2004
  1. Wireless in loco sensor data collection and applications. S. Chen, A. Gaur, S. Muthukrishnan and D. Rosenbluth. MOBEA II , WWW04.
  2. The Graham-Knowlton problem revisited. N. Goyal, S. Lodha and S. Muthukrishnan. FUN 2004.  
  3. How to increase acceptance ratio of conferencers? A. Czumaj, G. Cormode and S. Muthukrishnan FUN 2004.
  4. Mining deviants in time-series data streams. S. Muthukrishnan, R. Shah, J. Vitter. SSDBM 2004 .  DIMACS TR.
  5. Holistic UDAFs at streaming speeds.   T. Johnson, G. Cormode, F. Korn, S. Muthukrishnan, O. Spatscheck, D. Srivastava: SIGMOD 2004   
  6. Diamond in the Rough: Finding Hierarchical Heavy Hitters in Multi-Dimensional Data .  G. Cormode, F. Korn, S. Muthukrishnan, D. Srivastava,  SIGMOD 2004.
  7. What is new: Finding significant differences in network data streams. G. Cormode and S. Muthukrishnan. INFOCOM 2004.  
  8. An improved data stream summary: The Count-Min sketch and its applications.  LATIN 2004. G. Cormode and S. Muthukrishnan.
  9. Sublinear methods for detecting periodic trends in data streams. LATIN 2004. F. Ergun, S. Muthukrishnan and C. Sahinalp.
  10. Online Scheduling to Minimize Average Stretch. S. Muthukrishnan, R. Rajaraman, A. Shaheen, J. Gehrke. SIAM J. Comput. 34 (2): 433-452 (2004).  JOURNAL.
  11. An efficient algorithm for sequence comparison with block reversals . TCS , 321(1), 95-101, 2004. S. Muthukrishnan and S. Cenk Sahinalp.JOURNAL. (Invited from LATIN 2002).    
  12. Approximation algorithms for average stretch scheduling. J. of Scheduling , 7(3): 195--222. M. Bender, S. Muthukrishnan and R. Rajaraman. JOURNAL.
  13. Parallel two dimensional witness computation. I&C.  188(1): 20--67. R. Cole, Z. Galil, R. Hariharan, S. Muthukrishnan and  K. Park. JOURNAL. 
                                                        2003
  1. Maintenance of Multidimensional Histograms. S. Muthukrishnan and M. Strauss. FST&TCS 2003. 
  2. Comparing Sequences with Segment Rearrangements. F. Ergun, S. Muthukrishnan and S. Sahinalp.  FST&TCS 2003.
  3. Estimating dominance norms of multiple data streams.  G. Cormode and S. Muthukrishnan.  European Symposium on Algorithms (ESA) 2003. Also, DIMACS TR 2002-35. 
  4. Monitoring data quality problems in network traffic databases. VLDB 2003.  F. Korn, S. Muthukrishnan and Y. Zhu.
  5. Finding hierarchical heavy hitters in data streams. VLDB 2003. G. Cormode, F. Korn, S. Muthukrishnan and D. Srivastava.
  6. Improved sparse approximation over quasi-coherent dictionaries.   Intl Conf on Image processing ( ICIP 2003) A. Gilbert, S. Muthukrishnan, M. Strauss and J. Tropp.
  7. What is hot and what is not: Tracking most frequent items dynamically. PODS 2003. G. Cormode and S.Muthukrishnan. 
  8. IPSOFACTO: A visual correlation tool for aggregate network traffic data. SIGMOD 2003 demo. F. Korn, S. Muthukrishnan and Y. Zhu.  
  9. Reliable transport mechanisms for wireless data networks. IEEE Intl Conf on Communications (ICC ), 2003. S. Diggavi, X. Gao and S. Muthukrishnan.
  10. Rangesum histograms . SODA 2003. S. Muthukrishnan and M. Strauss. 
  11. Inferring tree topologies using flow tests. SODA 2003. S. Muthukrishnan, T. Suel and R. Vingralek. 
  12. Approximation of functions over redundant dictionaries using coherence. SODA 2003. A. Gilbert, S. Muthukrishnan and M. Strauss.  
  13. Generalized substring selectivity estimation. JCSS. Feb 2003. 66(1) 98--132. Z. Chen, F. Korn, N. Koudas and S. Muthukrishnan. JOURNAL. (Invited from PODS 2000).
  14. Efficient approximation of correlated sums on data streams. TKDE (May/June)  15(3) 569--572. R. Ananthakrishna, A. Das, J. Gehrke, F. Korn, S. Muthukrishnan, D. Srivastava.  JOURNAL
  15. One-pass wavelet decompositions of data streams. TKDE  (May/June)  541--554. 15(3) A. Gilbert, Y. Kotidis, S. Muthukrishnan and M. Strauss. JOURNAL
  16. Comparing data stream using hamming norms (How to zero in)  TKDE  (May/June)  529--540. 15(3) G. Cormode, M.Datar, P. Indyk and S. Muthukrishnan. JOURNAL   
  17. Approximation algorithms for MAX-MIN tiling. Piotr Berman , Bhaskar DasGupta , S. Muthukrishnan:  J. Algorithms  47(2): 122-134 (2003)   JOURNAL.
  18. Two-dimensional substring indexing.  JCSS June 2003. 66(4): 763--774.  P. Ferragina, N. Koudas, S. Muthukrishnan and D. Srivastava .   JOURNAL.   (Invited from PODS 2001).  
                                          2002
  1. Static optimality theorem for external memory string access. FOCS 2002. V. Ciriani, P. Ferragina, F. Luccio, and S. Muthukrishnan.
  2. Estimating rarity and similarity on data stream windows . ESA 2002. M. Datar and S. Muthukrishnan.
  3. Range Searching in Categorical Data: Colored Range Searching on Grid . ESA 2002. P. Agarwal, S. Govindarajan and S. Muthukrishnan.
  4. Reverse nearest neighbor aggregates over data streams.   VLDB 2002. F. Korn, S. Muthukrishnan and D. Srivastava.
  5. Comparing data stream using hamming norms (How to zero in) VLDB 2002. G. Cormode, M.Datar, P. Indyk and S. Muthukrishnan. 
  6. How to summarize the Universe: Dynamic maintenance of quantiles. VLDB 2002. A. Gilbert, Y. Kotidis, S. Muthukrishnan and M. Strauss. 
  7. Parallel scheduling in next generation wireless networks. SPAA 2002. TR version. L. Becchetti, S. Diggavi, S. Leonardi, A. Marchetti-Spaccamela,  S. Muthukrishnan, T. Nandagopal and A. Vitaletti.
  8. Histogramming data streams with fast per-item processing. (prelim version)   ICALP 2002. S. Guha, P. Indyk, S. Muthukrishnan and M. Strauss.
  9. Simple and practical sequence nearest neighbors with block operations. CPM 2002. S. Muthukrishnan and S. C. Sahinalp.
  10. An improved algorithm for sequence comparison with block reversals. LATIN 2002. S. Muthukrishnan and S. C. Sahinalp.
  11. Fast, small space algorithms for approximate histogram maintenance. STOC 2002.   A.  Gilbert, S. Guha, P. Indyk, Y. Kotidis, S. Muthukrishnan, M.  Strauss.
  12. Near-optimal sparse fourier representations via sampling. STOC 2002. A. Gilbert, S. Guha, P. Indyk, S. Muthukrishnan and M.  Strauss.
  13. Mining database structure, or to How to build a data quality browser. SIGMOD 2002. T. Dasu, T. Johnson, S. Muthukrishnan and V. Shkapenyuk. 
  14. Fast mining of massive tabular data via approximate distance computations. ICDE 2002. G. Cormode, P. Indyk, N. Koudas and S. Muthukrishnan.
  15. Efficient algorithms for document retrieval problems. SODA 2002.