Prof. Walid Aref Wins VLDB 10-year Best Paper Award

07-26-2016

Writer(s): Staff Reports

Professor Walid Aref, a member of the CS faculty for more than 16 years, has earned a cornerstone achievement in his career – earning the Very Large Data Bases (VLDB) 10-year best paper award for the enduring legacy of a paper he published in 2006.

His paper titled, “The new Casper: query processing for location services without compromising privacy”, was co-authored with Professors Mohamed Mokbel at the University of Minnesota, and Chi-Yin Chow at City University of Hong Kong. This award is given to authors (of papers presented at the VLBD Conference 10 years ago) whose work has the most impact on database research since then.

Walid’s paper has a story behind it that dates back to 1999, when the NSF started its Information Technology Research (ITR) program. The target of this program was to solicit groundbreaking and innovative research in contrast to incremental or delta research. At the time, Walid had the vision that location data and location services should be ubiquitous. Satellites were already established and out there but at the same time, GPS devices were unnecessarily expensive and not wide spread.

Walid said these scenarios were swirling in his mind. “Why not make location detection devices, especially GPSs, ubiquitous . . . what if all objects in space know their locations . . . what services can be offered . . . how will computing be affected . . . how databases and query processing engines and indexing techniques will scale to accommodate floods of location data,” he wondered. “Of course, smart phones with GPSs were not around in 1999. Most likely, this is what made this project qualify as an NSF-ITR groundbreaking project at the time,” he elaborated.

Walid said he teamed up with Professors Hambrusch and Prabhakar (current CS Department Head) to write a proposal to the NSF ITR program to seek funding for the Pervasive Location-Aware Computing Environment (PLACE) project that addresses database engine and query processing challenges when location data collection becomes ubiquitous. In PLACE, the assumption is that all objects in space, whether mobile or stationary, have a location detection mechanism so that the object is aware of its location.

The critical factor that motived the award-winning Casper paper was that each object in space would not only know its location, but the object would also report its location to the PLACE server. At this point, the PLACE server would know the locations of all objects in space, and hence can provide unique location services. The PLACE server would be receiving “streams” of location data in the form of (object identifier, location coordinates, time) as well as “streams” of user queries that request answers progressively.  Some example queries include, Continuously alert me when someone steps into my backyard, Alert me when one of my pets is away by more than 100 feet from my house, and Continuously report the three-nearest gas stations, as I am driving down the highway, to list a few.

Walid said other location services were envisioned for PLACE, like aiding vision-challenged people to assist them in crossing the road. They surmised this would work because PLACE would know the location of all objects in space around this person and it could allow for the individual to navigate the space safely, or hail a taxi cab without seeing it. PLACE also would give a camera the capabilities to capture the metadata of the objects visible at the scene, by issuing a cone-shaped query to the PLACE server. “While these services are offered today, in 1999, it was a bit of a stretch, and it certainly was a lesson learned in the importance of patenting,” Walid added.

The PLACE project has furthered the success of many published papers, led to the creation of demo systems and prototypes, been the source of well-cited research, and the impetus of several Ph.D. theses. As time evolved, PLACE continued to remain relevant, as many new research challenges emerged. The most important challenge became the issue of privacy. Many individuals feel uncomfortable sending their location information to a global server, as is the case with PLACE. Also, when someone issues a location-based query, their location is revealed. For example, the query Find the three closest restaurants to me also reveals the current location of the person issuing the query. “So, the question arose – how do we process users’ queries and provide them with a wide spectrum of location services without compromising their privacy,” Walid explained.

Walid and his fellow researchers were the first to address this question of location privacy from a database perspective – the subject of their Casper paper that was published at the 2006 VLDB conference in Seoul, Korea (the new Casper paper), and was later demonstrated at the 2007 IEEE International Conference on Data Engineering conference (ICDE), and finally an upgraded version and extension of the Casper algorithms was later published in the ACM Transactions on Database Systems journal (TODS) in 2009 (the Casper* paper). Interestingly, the name “Casper” was inspired by the cartoon character, Casper the Friendly Ghost, who was a 1960’s cartoon that could hide its location and come to the aid of people in need, in various situations.

Fast-forwarding to 2016, the vision of the PLACE project is now a reality. Almost all smart-phones are enabled with location-detection devices and they report the users’ current locations to location servers in a similar way to that of PLACE, e.g., taxi services, traffic and navigation services, flight status services, and gaming services. Enjoyed by millions of players globally, the Pokemon Go craze is a prime example of a location service where individuals are having fun playing a game while at the same time voluntarily exposing their location. This can be quite dangerous, especially for young children. With Casper, individuals can enjoy location services, e.g., games like Pokemon Go in safety, without the threat of having their location revealed. Therefore, with the ubiquitous adoption of location services in almost all aspects of life, the need for location servers to follow Casper-like approaches in offering location services (without compromising privacy) is more important now, than any time before.