Approximate Aggregate Processing in Spatio-temporal Databases
(TAO Yufei)

Spatio-temporal databases manage continuously moving objects (e.g., vehicles, aircrafts, hurricanes, etc.), and have received considerable attention in recent years due to the emergence of many novel applications (e.g., traffic supervision, location-based service, flight control, etc.). Although previous research has mostly focused on retrieving individual objects satisfying certain query conditions, in practice most applications are interested in aggregate results. As an example, an analyst monitoring the traffic is interested in the number of vehicles in some region, rather than their respective ids, in order to identify areas of high traffic and potential congestions. In this project, we address various types of spatio-temporal aggregate queries, including those related to k nearest neighbor search (e.g., tracking the distance between a customer and his/her nearest taxi), and joining multiple datasets (e.g., given the taxi and customer data, find the number of the taxi-customer pairs that are close to each other). The goal is to develop specialized algorithms and space-efficient data structures for answering these queries accurately.