Publications

  1. On the Midpath Tree Conjecture: A Counter-Example [ps] [pdf]

with M. Farach-Colton, in Symposium  on Discrete Algorithms (SODA) 2001.

  1. On the Complexity of Ordinal Clustering [ps] [pdf]

with M. Farach-Colton,  Journal of Classification 2006.

  1.  Efficient Dissemination of Personalized Information Using Content-Based Multicast  [ps] [pdf]

with R. Jain and F. Anjum. InfoCom 2002.  Journal: TMC 2004.

  1. Algorithms for Efficient Filtering in Content-Based Multicast [ps] [pdf]

with S. Langerman and S. Lodha,  ESA 2001.  (Winner of the Best Student Paper Award)

  1. Undiscretized Dynamic Programming: Faster Algorithms for Facility Location and Related Problems on Trees [ps] [pdf]

 with M. Farach-Colton.  SODA 2002. Journal: in prep.

  1. Faster Algorithms for k-median problem on trees with smaller heights [ps] [pdf]

Purdue University Tech Report DCS-03-030.

  1. Ordered Pattern Matching: Towards a Full-text Retrieval [ps] [pdf]

Purdue University Tech Report DCS-06-013.

  1. Online Algorithms for Prefetching and Caching in Parallel Disks [ps] [pdf]

With P. J. Varman and J. S. Vitter, SPAA 2004.

  1. Bulk Operations for Space Partitioning Trees [ps] [pdf]

With T. Ghanem, M. Mokbel, W. Aref and J. S. Vitter, ICDE 2004.

  1. Mining Deviants in Time Series Data Streams [ps] [pdf]

 with S. Muthukrishnan and J. S. Vitter, SSDBM 2004.

  1. Rank-aware Query Optimization [ps] [pdf]

with  I. Ilyas, W. Aref, J. S. Vitter and A. Elmagarmid, SIGMOD 2004, Journal : TODS 2006.

  1. Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data [ps] [pdf]

with R. Cheng, Y. Xia, S. Prabhakar and J. S. Vitter, VLDB 2004.  Journal: in prep.

  1. Change Tolerant Indexing for Coevolving Data [ps] [pdf]

with R. Cheng, Y. Xia and S. Prabhakar, ICDE 2005.

  1. Indexing Continuously Changing Data with Mean-Variance Tree[ps] [pdf]

with Y. Xia, S. Lei, S. Prabhakar and R. Cheng, SAC 2005. Journal : CIC 2005.

  1. On the Competitive Online Read-many Parallel Disks Scheduling [ps] [pdf]

With P. J. Varman and J. S. Vitter, SPAA 2005.

  1. Tight Competitive Ratios for Parallel Disk Prefetching and Caching [ps] [pdf]

With W. Hon, P. J. Varman and J. S. Vitter, Submitted. Journal: in prep.

  1. Compressed Data Structures: Data-aware Measures and Dictionaries [ps] [pdf]

 with A. Gupta, W. Hon and J. S. Vitter, DCC 2006. Journal : TCS (under revision).

  1. Compressed dictionaries: Space Measures, Data Sets and Experiments [ps] [pdf]

With A. Gupta, W. Hon and J. S. Vitter, WEA 2006.

  1. Efficient Join Processing over Uncertain-Valued Attributes [ps] [pdf]

With R. Cheng, Y. Xia,  S. Singh,  S. Prabhakar, J. S. Vitter,  CIKM 2006.

  1. Indexing Uncertain Categorical Data [ps] [pdf]

With S. Singh, C. Mayfield, S. Prabhakar, S. Hambrusch, ICDE 2007.

  1. SBC-tree: Efficient Indexing for RLE-Compressed Strings [ps] [pdf]

With M. Eltabakh, W. Hon, W. Aref and J. S. Vitter, submitted.

  1. Dynamic Rank/Select Dictionaries with applications to XML indexing [ps] [pdf]

With A. Gupta, W. Hon, J. S. Vitter, submitted. Journal:  in prep.

  1. Cache Oblivious Approximate String Dictionary [ps] [pdf]

With W. Hon, T. Lam, S. Tam, J. S. Vitter, submitted.

  1. Unified Model for Uncertain Data Management in Relational Databases

With S. Singh, C. Mayfield, S. Prabhakar, S. Hambrusch, J. Neville, R. Cheng, submitted.

  1. Compressed Text Indexing and Range Searching

With Y. Chien, W. Hon, J. S. Vitter, submitted

 


Doctoral Thesis

Undiscretized Dynamic Programming and Ordinal Embeddings  [ps] [pdf]
Committee: Martin Farach-Colton (Chair), Vasek Chvatal, S. Muthukrishnan, Sampath Kannan


Other Technical Writings
 

  1. Master's essay:

Optimization Problems in SONET/WDM Ring architecture [ps] [pdf]

under Vasek Chvatal

  1. Bachelor's Project:

Enumerating Independent Sets in Trees and Chordal Graphs [ps] [pdf]

under A. A. Diwan

  1. Bachelor's Seminar:

Rapidly Mixing Markov Chains [ps] [pdf]

under Ketan Mulmuley and Sundar Vishwanathan

[Back]