Point-to-Network Join and Spatiotemporal aggregations


With the increasing availability of locating and navigation technologies on portable wireless devices, huge amounts of location data are being captured at ever growing rates. Spatial and temporal aggregations in an Online Analytical Processing (OLAP) setting for the large-scale ubiquitous urban sensing data play an important role in understanding urban dynamics and facilitating various decision making. Unfortunately, existing spatial, temporal and spatiotemporal OLAP techniques are mostly based on traditional computing frameworks, i.e., disk-resident systems on uniprocessors based on serial algorithms, which makes them incapable of handling large-scale data on parallel hardware architectures that have already been equipped with commodity computers. In this study, we report our designs, implementations and experiments on developing a data management platform and a set of parallel techniques to support high-performance online spatial and temporal aggregations on multi-core CPUs and many-core Graphics Processing Units (GPUs). Our experiment results have shown that we are able to spatially associate nearly 170 million taxi pickup location points with their nearest street segments among 147,011 candidates in about 5-25 seconds on both an Nvidia Quadro 6000 GPU device and Intel Xeon dual E5405 quad-core CPUs when their Vector Processing Units (VPUs) are utilized for computing intensive tasks. After spatially associating points with road segments, spatial, temporal and spatiotemporal aggregations are reduced to relational aggregations and can be processed in the order of a fraction of a second on both GPUs and multi-core CPUs.  In addition to demonstrating the feasibility of building a high-performance OLAP system for processing large-scale taxi trip data for real-time, interactive data explorations, our work also opens the paths to achieving even higher OLAP query efficiency for BigData applications through integrating domain-specific data management platforms, novel parallel data structures and algorithm designs, and, hardware architecture friendly implementations. 

Related Publications:
1) Jianting Zhang, Simin You and Le Gruenwald (2012). High-Performance Online Spatial and Temporal Aggregations on Multi-core CPUs and Many-Core GPUs. To appear in Proceedings of ACM DOLAP workshop[Link]
2) Jianting Zhang, Simin You and Le Gruenwald (2014).  Parallel Online Spatial and Temporal Aggregations on Multi-core CPUs and Many-Core GPUs.  Information System (Elsevier journal), Vol. 44, pp. 134-154. [Link (21 formatted pages)] [Manuscript (33 unformatted pages)].