Dept. of Computer Science, Purdue University 3124 Onyx Street
305 N. University st, West Lafayette, IN 47907 West Lafayette, IN 47906
http://www.cs.purdue.edu/~rahul/ Ph: (765) 464-8866
Email: rahul@cs.purdue.edu DOB: March 25, 1976
US Permanent Resident
- Profile: Applied Theoretician / Applied Algorithmist
- Main research areas: Algorithms, Data Structures, Database Systems
- Specific areas: Algorithms for Parallel Disks, Compressed Data Structures, Uncertain and Ranked Databases
- Collaborative areas: Computer Architecture, Networking, Computational Biology, Data Mining
Doctor of Philosophy (Computer Science) May 2002
Rutgers University, New Brunswick, NJ (GPA : 3.97/4)
Master of Science (Computer Science) March 1999
Rutgers University, New Brunswick, NJ (GPA : 4/4)
Bachelor of Technology (CS&E) May 1997
Indian Institute of Technology, Bombay, India (Rank : 4/36)
Working on compressed data structures, uncertain databases and parallel disks modeling for massive data sets.
Research Staff Member, IBM India Research Lab
August 2004- May 2005
Worked on solving real-world problems involving Text Mining, Clustering and Classification. Working on projects related to structured and unstructured data integration. The work involved building statistical models and applying principles of machine learning, pattern recognition and algorithms to efficiently mine, classify, cluster and index information from text documents.
Worked on external memory algorithms with Prof. Jeff Vitter. Collaborating with different research groups in the computer science department. Working jointly on external memory indexes, databases, data streams and text indexing. The work involved strong problem solving skills and cross-disciplinary collaborative skills.
Topic: Undiscretized Dynamic Programming and Ordinal Embeddings
Advisor: Prof. Martin Farach-Colton
Solved problems on filtering content-based multicast, problems in facility location on trees, covering problems on trees, phylogeny construction and hierarchical ordinal clustering.
Major achievements were:
Designed a framework for placing mobile filters in the content-based multicast tree to save network bandwidth and congestion delays. Designed a series of faster algorithms for optimally placing filters in multicast tree under various cost metrics. Implemented in Java with IBM Aglets.
Worked on approximation/heuristic algorithms for survivable network design; implementation of some of these was done in C. In particular, designed and implemented simpler and faster algorithms for ring loading problem and shortest pair of disjoint paths problem for dual hub benchmark algorithm, as a part of network design toolkit.
Served as Instructor for Discrete Structures and teaching assistant for Design and Analysis of Data Structures and Algorithms (I & II), Discrete Structures, Network and Combinatorial Optimization, Theory of Computation, and Operating Systems.
· Winner of Best Student Paper Award at European Symposium on Algorithms (ESA) 2001.
· Institute Academic Award Winner, IIT Bombay, in academic years 93-94 and 94-95 for excellent academic performance.
· Secured All India 9th Rank at IIT Joint Entrance Examination, 1993, amongst approximately 100,000 students appearing all over the country.
· National Talent Search Scholarship, 1991, Govt. of India (awarded to 750 students nationwide every year)
· (current) V. Pai, M. Thottethodi, R. Shah, TN Vijaykumar, J. Vitter, NSF CCF—0621457, Perfomance Models and Systems Optimization for Disk-Bound Applications, 10/1/06—9/30/09, $889.788.
· (pending) S. Bagchi, Y. Hu, V. Pai, M. Thottethodi, R. Shah, CRI: IAD: A Storage Array Test-bed for I/O Performance, Dependability and File Systems Research and Education.
Journal Publications
· R. Shah, Z. Ramzan, R. Jain, R. Dendukuri, F. Anjum, Efficient Dissemination of Personalized Information Using Content-Based Multicast, In IEEE Trans. on Mobile Computing (TMC) 2004.
· Y. Xia, S. Prabhakar, S. Lei, R. Cheng, R. Shah, Indexing Constantly Changing Data with Mean-Variance Tree, In International Journal of High Performance Computing and Networking (IJHPCN), special issue on Collaborative Internet Computing (CIC) 2005.
· R. Shah, M. Farach-Colton, On the Complexity of Ordinal Clustering, In Journal of Classification 2006.
· I. Ilyas, H. Elmongui, ,W. Aref, A. Elmagarmid, R. Shah, J. Vitter, Adaptive Rank-aware Query Optimization in Relational Databases, In ACM Trans. on Database Systems (TODS) 2006.
· A. Gupta, W. Hon, R. Shah, J. Vitter, Compressed Data Structures: Dictionaries and Data-Aware Measures, In Theoretical Computer Science (TCS) 2006.
Conference Publications -- Algorithms, Data Structures and Networking
· R. Shah, M. Farach-Colton, On the Midpath Tree Conjecture: a Counter-Example, In ACM-SIAM Symposium on Discrete Algorithms (SODA) 2001.
· S. Langerman, S. Lodha, R. Shah, Algorithms for Efficient Filtering in Content-Based Multicast, In European Symposium on Algorithms (ESA) 2001, Winner of Best Student Paper award.
· R. Shah, M. Farach-Colton, Undiscretized Dynamic Programming: Faster Algorithms for Facility Location and Related Problems on Trees, In ACM-SIAM symposium on Discrete Algorithms (SODA) 2002.
· R. Shah, F. Anjum, R. Jain, Efficient Dissemination of Personalized Information Using Content-Based Multicast, In 21st annual joint conference of IEEE Computer and Communications Societies (InfoCom) 2002.
· R. Shah, P. Varman, J. Vitter, Online Algorithms for Prefetching and Caching on Parallel Disks, In ACM Symposium on Parallelism in Algorithms and Architecture (SPAA) 2004.
· A. Gupta, W. Hon, R. Shah, J. Vitter, Compressed Data Structures: Dictionaries and Data-aware Measures, In IEEE Data Compression Conference (DCC) 2006.
· A. Gupta, W. Hon, R. Shah, J. Vitter, Compressed Dictionaries: Space Measures, Data Sets and Experiments, In Workshop on Experimental and Efficient Algorithms (WEA) 2006.
· R. Shah, P. Varman, J. Vitter, On the Online Read-many Parallel Disks Scheduling, In ACM Symposium on Parallelism in Algorithms and Architecture (SPAA) 2005 .
Conference Publications -- Databases, Data Streams and Indexing
· T. Ghanem, R. Shah, M. Mokbel, W. Aref, J. Vitter, Bulk Operations for Space Partitioning Trees, In International Conference on Data Engineering (ICDE) 2004.
· I. Ilyas, R. Shah, W. Aref, J. Vitter, A. Elmagarmid, Rank Aware Query Optimization, In International Conference on Management of Data (SIGMOD) 2004.
· S. Muthukrishnan, R. Shah, J. Vitter, Mining Deviants in Time Series Data Streams, In international conference on Scientific and Statistical Database Management (SSDBM) 2004.
· R. Cheng, Y. Xia, S. Prabhakar, R. Shah, J. Vitter, Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data, In international Conference on Very Large Databases (VLDB) 2004.
· R. Cheng, Y. Xia, S. Prabhakar, R. Shah, Change Tolerant Indexing for Constantly Evolving Data, To appear in international conference on Data Engineering (ICDE) 2005.
· Y. Xia, S. Prabhakar, S. Lei, R. Cheng, R. Shah, Indexing Constantly Changing Data with Mean-Variance Tree, To appear in ACM Symposium on Applied Computing (SAC) 2005.
· R. Cheng, S. Singh, Y. Xia, S. Prabhakar, R. Shah, J. Vitter, Efficient Join-processing over Uncertain Data, In International Conference on Information and Knowledge Management (CIKM) 2006.
· S. Singh, C.Mayfield, S. Prabhakar, R. Shah, S. Hambrusch, Indexing Uncertain Categorical Data, In International Conference on Data Engineering (ICDE) 2007.
Unpublished Manuscripts
· M. Eltabakh, W. Hon, R. Shah, W. Aref, J. Vitter, SBC-tree: Efficient Indexing for RLE-compressed Strings, submitted.
· W. Hon, R. Shah, P. Varman, J. Vitter, Tight Competitive Ratios for Parallel Disk Prefetching and Caching, submitted.
· W. Hon, T. Lam, S. Tam, R. Shah, J. Vitter, Cache Oblivious Approximate String Dictionary, submitted.
· A. Gupta, W. Hon, R. Shah, J. Vitter, Dynamic Rank/Select Dictionaries with Applications to XML Indexing, submitted.
· Y. Chien, W. Hon, R. Shah, J. Vitter, Compressed Text Indexing and Range Searching, submitted.
· S. Singh, C. Mayfield, S. Prabhakar, R. Shah, S. Hambrusch, <title deleted>, submitted.
· S. Singh, C. Mayfield, S. Prabhakar, R. Shah, S. Hambrusch, J. Neville, R. Cheng, Unified Model for Uncertainty Management in Databases. submitted.
Technical Reports/Theses
· R. Shah, Faster Algorithms for the k-Median Problem on Trees with Smaller Heights, CS TR #03-030, Dept. of Computer Science, Purdue University.
· W. Hon, R. Shah, J. Vitter, Ordered Pattern Matching: Towards Full-Text Retrieval, CS TR #06-013, Dept. of Computer Science, Purdue University.
· R. Shah, Undiscretized Dynamic Programming and Ordinal Embeddings, PhD Thesis, Rutgers University, 2002. (Committee: Martin Farach-Colton (chair), S. Muthukrishnan, Sampath Kannan, Vasek Chvatal)
· R. Shah, Optimization Problems in SONET/WDM Ring Architecture, Master’s Essay, Rutgers University, 1998. (Advisor: Vasek Chvatal)
· R. Shah, Enumerating Independent Sets in Trees and Chordal Graphs, Bachelor’s Project, IIT Bombay, 1997. (Advisor: A. A. Diwan)
· R. Shah, Rapidlly Mixing Markov Chains, Bachelor’s Seminar, IIT Bombay, 1996. (Advisors: K. Mulmuley and S. Vishwanathan)
· Prof. Martin Farach-Colton, Dept. of Computer Sci., Rutgers University, NJ 08854
· Prof. Michael Fredman, Dept. of Computer Sci., Rutgers University, NJ 08854
· Prof. Jeffrey Scott Vitter, Dean, School of Science, Purdue University, IN 47907
· Prof. Sunil Prabhakar, Dept. of Computer science, Purdue University, IN 47907