Contact Information:
email: rina@microsoft.com
phone: 650-693-2886

Publications:

• Sreenivas Gollapudi and Rina Panigrahy, The power of two min-hashes in similarity search among hierarchical data objects, PODS 2008, To appear.
• Atish Das Sarma, Sreneivas Gollapudi, and Rina Panigrahy, Estimating PageRank on Graph Streams, PODS 2008. (Best Paper Award) [PPT ]
• "Using Bloom filters to speed-up HITS-like ranking algorithms" with Sreenivas Gollapudi, Marc Najork. WAW 2007: 195-201.
• "Trace reconstruction with constant deletion probability and related results" with Thomas Holenstein and Michael Mitzenmacher and Udi Wieder, SODA 2008.
• "Finding Frequent Elements in non-bursty Streams" with Dilys Thomas. ESA 2007. [PPT ]
• "On Finding Frequent Elements in a Data Stream" with Ravi Kumar. RANDOM 2007 [PPT ]
• "Hashing Searching Sketching". Ph.D. Thesis, Stanford University. [PPT ]
• "An Improved Construction for Counting Bloom Filters" with F. Bonomi, M. Mitzenmacher, S. Singh, and G. Varghese. ESA 2006.
• "Compact Approximate Representations of Concurrent State Machines for Network Applications" with Flavio Bonomi, Michael Mitzenmacher, Sushil Singh, and George Varghese, Proceedings of the ACM SIGCOMM Conference, Pisa, Italy, September 2006.
• "A Dictionary for Approximate String Search and Longest Prefix Search" with S. Gollapudi. CIKM 2006.
• "Exploiting Asymmetry in Hierarchical Topic Extraction" with S. Gollapudi. CIKM 2006.
• "Estimating Corpus Size via Queries" with A. Broder, M. Fontoura, V. Josifovski, R. Kumar and R. Motwani. CIKM 2006
• "Lower bounds on Locality Sensitive Hashing". SOCG 2006.
• "Improved algorithms for Nearest neighbor search in high dimensions". LATIN 2008. [PPT ]
• "Near-Perfect Fractional Matching via Balls-and-Bins" with Rajeev Motwani and Ying Xu. RANDOM 2006.
• "Entropy based Nearest Neighbor Search in High Dimensions". SODA 2006.
• "Balanced Allocation on Graphs" with Krishnaram Kenthapadi. SODA 2006. (Student Best Paper Award)
• "Analyzing the Efficiency of BitTorrent and Related Peer-to-Peer Networks" with David Arthur. SODA 2006.
• "Efficient Hashing with Lookups in two Memory Accesses". SODA 2005.
• "Efficient Multicast on a Terabit Router" with Punit Bhargava and Sriram C. Krishnan. Hot Interconnects 2004.
• "Better streaming algorithms for clustering problems" with Moses Charikar and Liadan O'Callaghan. STOC 2003.
• "Computing Shortest Paths with Uncertainty" with Tomas Feder, Rajeev Motwani, Liadan O'Callaghan, chris Olston. STACS 2003.
• "Representing Graph Metrics with Fewest Edges" with Tomas Feder, Adam Meyerson, Rajeev Motwani, Liadan O'Callaghan. STACS 2003.
• Sorting and Searching using Ternary CAMs Rina Panigrahy, Samar Sharma (Cisco Systems). Hot Interconnects 2002. Also in IEEE Micro 23(1): 44-53 (2003)
• Reducing TCAM Power Consumption and Increasing Throughput Rina Panigrahy, Samar Sharma (Cisco Systems). Hot Interconnects 2002
• David Karger, Eric Lehman, Tom Leighton, Matthew Levine, Daniel Lewin, and Rina Panigrahy. Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the World Wide Web. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 654-663, El Paso, Texas, 4-6 May 1997.
• Object Accessibility for Java is Decidable. (with R. Motwani, V. Saraswat, and S. Venkatasubrmanian)
  Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, 2000.
• Computing the Median with Uncertainty. (with T. Feder, R. Motwani, C. Olston, and J. Widom)
  Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, 2000.
• Web Caching With Request Reordering. (with T. Feder, R. Motwani, and A. Zhu)
  Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002.
• New Algorithms for Subset Query, Partial Match, Orthogonal Range Searching and Related Problems,
  with P. Indyk and M. Charikar,
  Proceedings of the 29th International Colloquium on Automata Languages and Programming, 2002.
• Approximating The Smallest Grammar: Kolmogorov Complexity in Natural Models,
  with E. Lehman, D. Liu, M. Charikar, M. Prabhakaran, A. Rasala, A. Sahai, and A. Shelat,
  in Proceedings of the 34th Annual ACM Symposium on Theory of Computing, (2002)..
• Rina Panigrahy and Sundar Vishwanathan, ``An O(log^* n) approximation algorithm for the asymmetric p-center problem,'' Journal of Algorithms, 27:259--268, 1998.