Funded by the National Science Foundation
co-PI: Walid Najjar Award Number: 1144158Web Page:
http://www.cs.ucr.edu/~tsotras/fpga
Project Summary:
The wide adoption of GPS and sensor technologies has created many applications that collect and maintain very large repositories of data in the form of trajectories. To better analyze such data, a user can pose complex pattern queries using a high level region-based representation that abstracts trajectories by the temporally ordered sequence of spatial regions (or areas/points of interest) they visited. For example: “find moving objects that first passed by the train station, then by the town center and were always within a mile from the harbor”. Temporal and counter constraints, as well as region variables and region hierarchies can be added to create very powerful queries. Similarly, one can formulate join queries that identify pairs of trajectories with similar behavior, etc. While such pattern-based queries are critical in analyzing vast trajectory archives, traditional methods fail to scale due to the large computational effort and size of the data. Adding more resources (i.e., many processors) will not eliminate the bottleneck (each processor still uses multiple clock cycles per operation) and may also create a large communication overhead between the processors. Instead, this project takes a different, “high risk-high payoff” approach by using reconfigurable hardware, namely, Field Programmable Gate Arrays (FPGAs). FPGAs are code accelerators where a portion of the application is mapped as a circuit on the FPGA; thus they avoid the traditional load/store operations in the datapath that traditional CPUs perform. Such processing has the potential to provide orders of magnitude performance improvement, leading to further discoveries from vast amounts of data. The intellectual merit of this project emanates from the novel solutions needed: efficient FPGA designs to support region variables, time and counter constraints, region hierarchies, as well trajectory joins. If successful, this project has the potential to revolutionize the way queries over large trajectory data archives are processed. There is a broad range of applications (scientific, educational, and economic activities) that will be impacted from the fast processing provided by the FPGA filtering approach. Providing orders of magnitude speed improvement will have a profound effect in these applications. The combination of two distinct technologies (Databases and FPGAs) is an ideal vehicle for training graduate/undergraduate students and for transferring gained experience into relevant courses. For further information see the project web site at the URL: http://www.cs.ucr.edu/~tsotras/fpga/index.html