Lab News


2016-07-19: VLDB 10-Year Best-Paper Award

Walid, Prof. Mohamed Mokbel at the University of Minnesota, and Prof. Chi-Yin Chow (Ted) at City University of Hong Kong won the VLDB 10-year best paper award for their 2006 VLDB paper titled: “The New Casper: Query Processing for Location Services Without Compromising Privacy”.  According to the VLDB (Very Large Data Bases) endowment web site (, this award is established for the author(s), whose paper appeared in the VLDB conference 10 years ago, that has the most impact on database research since then.


This paper has a long story behind it that dates back to 1999 when the NSF started its ITR program (ITR is short for Information Technology Research). 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 widely spread. So, why not make location detection devices, especially GPSs, ubiquitous? What if all objects in space know their locations? What services can be offered? How computing will be affected? How databases and query processing engines and indexing techniques will scale to accommodate floods of location data?  Of course, smart devices with GPSs were not there yet as of 1999. Probably, this is what made this project qualify as an NSF-ITR groundbreaking project at the time. Professors Susanne Hambrusch, Sunil Prabhakar, and Walid teamed up to write a proposal to the NSF ITR program to seek funding for the PLACE project (PLACE is short for Pervasive Location-Aware Computing Environment) 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 location detection mechanisms so that each object is aware of its location. But now comes the critical part that motived the Casper paper. Not only that each object in PLACE will know its location, but also the object will report its location to the PLACE server. Now, the PLACE server will know the location of literally everyone, and at all times. The PLACE server will 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. Examples of these progressive or “continuous” queries are: “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”, “as I am driving on the highway, continuously report the three-nearest gas stations or hotels”, etc. Other location services were envisioned given PLACE including  (1) Assisting the visually-challenged in crossing the road (since PLACE knows the location of all objects in space around this person, it can allow the person navigate the space safely, stop a taxi cab without seeing it, etc.), (2) As one takes a photo, the camera would label all the objects at the scene by issuing a cone-shaped query to the PLACE server to get all the objects’ names in the scene, among other services. These services are offered nowadays, but back in 1999, it was a bit of a stretch (Lesson to be learned about patenting J).


Many good papers, demo systems and prototypes, as well as nice well-cited research, and several Ph.D. theses, have resulted from the PLACE project. However, many new research challenges emerged as well. The most important challenge is that of privacy. Many people feel uncomfortable sending their location information to a global server as is the case with the PLACE server. Also, when someone issues a location-based query, this person’s location is revealed. For example, the query “Find the three closest restaurants to me”, reveals the person’s current location. So, the question is: How can we process users’ queries and provide them with a wide spectrum of location services without compromising the users’ privacy? Mohamed, Ted, and Walid were the first to address this question of location privacy from a database perspective. This was the subject of their Casper paper that was published at the 2006 VLDB Conference in Seoul, Korea (the “New Casper” paper). A prototype of Casper was later demonstrated at the 2007 IEEE ICDE Conference, and finally an upgraded version and extension of the Casper algorithms were later published in the ACM TODS Journal in 2009 (the Casper* paper). The name “Casper” was inspired by the famous 1960’s cartoon character Casper, the friendly ghost. Being a ghost, Casper can hide its location while still hiding its location. The New Casper location-based server acts the same. It does not reveal users’ locations yet provides them with location services without compromising the users’ privacy.  The VLDB 2006 New Casper paper has had a broad impact once published and has been widely cited since then.


Fast-forwarding to 2016, the vision of the PLACE project is now a reality. Almost all smart-phone devices 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, monitoring rare species and flocks, and gaming services. The need for nowadays location servers to follow Casper-like approaches in offering location services without compromising privacy is quite obvious now and is a necessity.


2016: Summer Internship News: Saber and Samy are heading to MSR in two different groups, Yongyang is heading to Facebook!


2016-4: Congratulations to Mingjie and team for the IEEE TKDE paper. Here is the paper.


2016-3: Our two demos are accepted into ICDE 2016. Congratulations to Samy and Elkindi and all team members! Here are the two demos: (Cruncher). (ORLF).


2016-2: Our accepted WSDM 2016 paper is here. Kangaroo: Workload-Aware Processing of Range Queries in Hadoop. (Kangaroo-paper).


2015-11-16: Our paper titled “Graph Indexing for Shortest-Path Finding over Dynamic Sub-Graphs” got accepted as full paper into SIGMOD 2016. Job well done Saber and Ahmed! (paper)


2015-11-5: Congratulations! Our Limo Demo paper at SIGSPATIAL 2015 got the best demo award. Here is Limo’s website:

The purpose of LIMO is to teach Computer Programming to Freshmen students using Maps and Globes as a programming toy. This prototype implementation of LIME uses Google Earth and Google Maps as the programming toy.


2015-10-12: Congratulations! Our paper titled: “Kangaroo: Workload-Aware Processing of Range Data and Range Queries in Hadoop” has been accepted to WSDM 2016 as a full paper (18.2% acceptance rate).


2015-10-07: Some Source codes for some of the recent papers and demos:

AQWA: (VLDB 2015 Demo and VLDB 2016 full papers)

JISC: (EDBT 2014 paper)

Two-kNN work:  (VLDB 2012 paper)

kNN & Relational with the cost model (ACM SIGSPATIAL 2015 and EDBT 2015 papers)


2015-08-26: Congratulations to Ahmed Aly for successfully defending his Ph.D.  Ahmed is heading to Google!


2015-08-10: Our AQWA paper got accepted to VLDB 2016 as a full paper! Congratulations to Ahmed Aly and company! Here is the source code for AQWA on Hadoop and the AQWA paper.


2015-06: The Tornado system demo paper got accepted to VLDB 2015. Congratulations to all the Tornado team members! Here is the demo paper. The source code is to be published soon!


2015-06: The AQWA demo paper got accepted to VLDB 2015. Congratulations! Here is the demo paper and the source code for AQWA.


2015-05: Summer internships: Amgad is heading to Microsoft, Mingjie is heading to IBM Almaden Research Center, Amr is heading to Yahoo! With best wishes to all for a productive summer.


2014-12-09: Our SISAP 2014 paper got the best paper award.


20xx: The SP-GiST software package, which is part of Walid’s NSF CAREER grant, is now part of the public distribution of PostgreSQL. Thanks to Ihab for a first experimental implementation inside Wisconsin’s Predator, to Ramy and Tabakh for an industrial strength implementation inside PostgreSQL (The ICDE2006 paper), and to the help of researchers from Moscow State University to take the PostgreSQL SPGiST codebase to the next level to make it into the public distribution of  PostgreSQL.