Nina Mishra
SENIOR RESEARCHER
.
Background
Data mining, machine learning, and privacy-preserving algorithms
Research Interests
The design and analysis of algorithms for unearthing patterns in massively large, dynamic datasets, specifically:
- Internet: Many new data sets are generated by virtue of the Internet. My work investigates algorithms for mining this data, for example, to improve web search or to discover communities in social networks.
- Scalability: Modern data sets are massively large and often streaming. Given a known algorithm that only works on a small, static data set, I think about how best to modify the algorithm for a large, dynamic data set, while also approximately retaining its original functionality.
- Clustering: A process that, given a collection of points, groups similar points together and places dissimilar points apart. The points can vary from vertices in a graph to points in a metric space. I study algorithms for efficiently discovering good clusters.
- Privacy: Many data sets that are mined today contain confidential information. My research seeks to strike a fine balance between simultaneously enabling the discovery of large-scale statistical patterns while disabling the recovery of private information.
Biography
- Search Labs, Microsoft Research. 2007-present.
- Associate Professor, CS Department, University of Virginia, 2005-2008.
- Acting Faculty, CS Department, Stanford University, 2002-2005.
- Senior Research Scientist, HP Labs, 1997-2005.
- PhD Computer Science, University of Illinois at Urbana-Champaign, 1997
Publications
- James Cook, Krishnaram Kenthapadi, and Nina Mishra, Group Chats on Twitter, in International World Wide Web Conference (WWW), ACM, May 2013
- Samuel Ieong, Nina Mishra, and Or Sheffet, Predicting Preference Flips in Commerce Search, in International Conference on Machine Learning (ICML), June 2012
- Samuel Ieong, Nina Mishra, Eldar Sadikov, and Li Zhang, Domain bias in web search, in International Conference on Web Search and Data Mining (WSDM), ACM, February 2012
- Krishnaram Kenthapadi, Aleksandra Korolova, Ilya Mironov, and Nina Mishra, Privacy via the Johnson-Lindenstrauss Transform, in Journal of Privacy and Confidentiality, 2012
- Srikanth Jagabathula, Nina Mishra, and Sreenivas Gollapudi, Shopping for Products You Don't Know You Need, in WSDM (Web Search and Data Mining), February 2011
- Shubha Nabar and Nina Mishra, Releasing Private Contingency Tables, in Journal of Privacy and Confidentiality, August 2010
- Gagan Aggarwal, Nina Mishra, and Benny Pinkas, Secure Computation of the Median (and Other Elements of Specified Ranks), in Journal of Cryptology, February 2010
- Umar Syed, Alex Slivkins, and Nina Mishra, Adapting to the Shifting Intent of Search Queries, in NIPS (Neural Information Processing Systems Conference), December 2009
- Aleksandra Korolova, Krishnaram Kenthapadi, Nina Mishra, and Alex Ntoulas, Releasing Search Queries and Clicks Privately, in International World Wide Web Conference (WWW), ACM, April 2009
- Rakesh Agrawal, Alan Halverson, Krishnaram Kenthapadi, Nina Mishra, and Panayiotis Tsaparas, Generating Labels from Clicks, in International Conference on Web Search and Data Mining (WSDM), ACM, February 2009
- Nina Mishra, Robert Schreiber, Isabelle Stanton, and Robert E. Tarjan, Finding Strongly-Knit Clusters in Social Networks, in Internet Mathematics, 2009
- Westley Weimer and Nina Mishra, Privately Finding Specifications, in IEEE Trans. Software Eng, vol. 34, no. 1, pp. 21–32, 2008
- Shubha Nabar, Krishnaram Kenthapadi, Nina Mishra, and Rajeev Motwani, A Survey of Query Auditing Techniques for Data Privacy, in Privacy-Preserving Data Mining: Models and Algorithms, Kluwer Academic Publishers, 2008
- Nina Mishra, Robert Schreiber, Isabelle Stanton, and Robert E. Tarjan, Clustering Social Networks, in WAW, 2007
- Nina Mishra and Mark Sandler, Privacy via pseudorandom sketches, in Proceedings of the Twenty-Fifth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, Chicago, IL, USA June 26–28, 2006, 2006
- Kamalika Chaudhuri and Nina Mishra, When Random Sampling Preserves Privacy, in CRYPTO, 2006
- Shubha U. Nabar, Bhaskara Marthi, Krishnaram Kenthapadi, Nina Mishra, and Rajeev Motwani, Towards Robustness in Query Auditing, in VLDB, Very Large Data Bases Endowment Inc., 2006
- Nina Mishra, Robert Schreiber, and Robert E. Tarjan, Finding Closely-Related Groups of Objects in Very Large Datasets, in Hewlett-Packard Technical Conference (HP TechCon), 2006
- Nina Mishra, Rajeev Motwani, and Serge Vassilvitskii, Sublinear Projective Clustering with Outliers, in 15th Annual Fall Workshop on Computational Geometry and Visualization, 2005
- Krishnaram Kenthapadi, Nina Mishra, and Kobbi Nissim, Simulatable Auditing, in PODS, Association for Computing Machinery, Inc., 2005
- Gagan Aggarwal, Nina Mishra, and Benny Pinkas, Secure Computation of the k th-Ranked Element, in EUROCRYPT, 2004
- Gagan Aggarwal, Mayank Bawa, Prasanna Ganesan, Hector Garcia-Molina, Krishnaram Kenthapadi, Nina Mishra, Rajeev Motwani, Utkarsh Srivastava, Dilys Thomas, Jennifer Widom, and Ying Xu, Vision Paper: Enabling Privacy for the Paranoids, in VLDB, Very Large Data Bases Endowment Inc., 2004
- Nina Mishra, Dana Ron, and Ram Swaminathan, A New Conceptual Clustering Framework, in Machine Learning, vol. 56, no. 1-3, pp. 115–151, 2004
- Haym Hirsh, Nina Mishra, and Leonard Pitt, Version Spaces and the Consistency Problem, in Artificial Intelligence, vol. 156, no. 2, pp. 115–138, 2004
- Nina Mishra and Rajeev Motwani, Introduction: Special Issue on Theoretical Advances in Data Clustering, in Machine Learning, vol. 56, no. 1-3, pp. 5–7, 2004
Professional Activities
Editorial Boards
- Machine Learning journal, 2002-present
- IEEE TKDE (Transactions on Knowledge and Data Engineering), 2005-2007.
- IEEE Intelligent Systems, 2005-present
- Journal of Privacy and Confidentiality, 2006-present
Program Chair
- ICML'03, with Tom Fawcett
Program Committees
- PODS’09: Principles of Database Systems
- AAAI'08: Conference on Artificial Intelligence
- KDD'08: Knowledge Discovery and Data Mining
- KDD'07: Knowledge Discovery and Data Mining
- KDD'06: Knowledge Discovery and Data Mining
- ICML'06: International Conference on Machine Learning
- ICML'05: International Conference on Machine Learning
- KDD'05: Knowledge Discovery and Data Mining
- SDM'05: SIAM International Conference on Data Mining
- KDD'04: Knowledge Discovery and Data Mining
- SDM'03: SIAM International Conference on Data Mining
- ICDM'02: IEEE International Conference on Data Mining
- SDM'02: SIAM International Conference on Data Mining
- KDD'01: Knowledge Discovery and Data Mining
- IJCAI'01: International Joint Conference on Artificial Intelligence
- ICML'00: International Conference on Machine Learning
NSF Panelist: 2002, 2004, 2007.
Advisory Board,ICML'04
Teaching
- CS302: Theory of Computation. University of Virginia. Spring 2007.
- CS651: Internet Algorithms. University of Virginia. Fall, 2006.
- CS851: Data Mining Algorithms. University of Virginia. Spring, 2006.
- CS369C: Clustering Algorithms. Stanford University. Spring, 2005.
- CS369: A Study of Perturbation Techniques for Data Privacy.With Cynthia Dwork and Kobbi Nissim. Stanford University. Spring, 2004.
- CS361A: Advanced Algorithms for Internet Applications. With Rajeev Motwani. Stanford University. Autumn, 2002.
