Luis Gravano

Luis Gravano is a computer scientist and professor of computer science at Columbia University whose research spans database systems, information retrieval, web search, and information extraction. He is known for co-developing the Snowball relation-extraction system and, with his doctoral student John Paparrizos, the k-Shape algorithm for time-series clustering, which received the 2025 ACM SIGMOD Test of Time Award.

Beginning in 2012, Gravano led the development of an automated system, deployed by the New York City Department of Health and Mental Hygiene, that detects unreported foodborne illness outbreaks by analyzing Yelp restaurant reviews. The system has identified thousands of complaints and multiple confirmed outbreaks not reported through the city's traditional channels, with results published by the Centers for Disease Control and Prevention and in the Journal of the American Medical Informatics Association.

According to Google Scholar, his publications have received more than 18,000 citations, with an h-index of 58.

Education

Gravano received his Licenciatura en Informática (equivalent to a Bachelor of Science in Computer Science) from the Escuela Superior Latinoamericana de Informática (ESLAI) in Argentina in 1991. He subsequently moved to the United States for graduate studies at Stanford University, where he earned his Master of Science degree in 1994 and his Ph.D. in 1997 under the supervision of Hector Garcia-Molina. His doctoral dissertation, Querying Multiple Document Collections across the Internet, addressed the problem of efficiently routing queries across distributed databases and digital libraries. The system begins with a small set of seed examples, such as known company-headquarters pairs, and iteratively discovers extraction patterns and new entity pairs. A central contribution was the development of confidence-estimation methods to prevent semantic drift, the phenomenon where errors compound through successive iterations. His work on database selection algorithms allowed metasearch systems to route queries to relevant databases based on statistical profiles of their content. Subsequent work modeled how database content summaries change over time, applying survival analysis techniques to determine optimal update schedules; the resulting paper received the IEEE ICDE Best Paper Award in 2005. This work bridged information retrieval ranking techniques with relational database query optimization. A related line of research, on query optimization for text-centric tasks, received the ACM SIGMOD Best Paper Award in 2006. The algorithm uses a shape-based distance measure derived from cross-correlation, making it invariant to phase shifts and amplitude scaling. k-Shape achieves accuracy comparable to methods based on dynamic time warping while offering significantly better computational efficiency. A decade after its introduction, the paper received the 2025 ACM SIGMOD Test of Time Award, which recognizes the SIGMOD paper from 10–12 years prior judged to have had the greatest impact over the intervening decade.

A pilot evaluation conducted between July 2012 and March 2013 found that only about 3 percent of the foodborne illness incidents identified through online reviews had previously been reported through the city's established complaint channels, demonstrating the value of social-media surveillance as a complement to traditional reporting. The findings were published in the Centers for Disease Control and Prevention's Morbidity and Mortality Weekly Report and the Journal of the American Medical Informatics Association,

Awards and honors

Year Award Organization 2025 Test of Time Award (for k-Shape) ACM SIGMOD 2012 Distinguished Faculty Teaching Award Columbia Engineering Alumni Association 2011 Distinguished Teacher Award Columbia Computer Science Department 2006 Best Paper Award (for "To search or to crawl?: towards a query optimizer for text-centric tasks") ACM SIGMOD 2005 Best Paper Award (for "Modeling and Managing Content Changes in Text Databases") IEEE ICDE 2003 Best Student Paper Award IEEE ICDE 1998 NSF CAREER Award National Science Foundation

Selected publications