A GPU-based index to support interactive spatio-temporal queries over historical data
Authors:
- 1 May 2016
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1086-1097
Abstract
There are increasing volumes of spatio-temporal data from various sources such as sensors, social networks and urban environments. Analysis of such data requires flexible exploration and visualizations, but queries that span multiple geographical regions over multiple time slices are expensive to compute, making it challenging to attain interactive speeds for large data sets. In this paper, we propose a new indexing scheme that makes use of modern GPUs to efficiently support spatio-temporal queries over point data. The index covers multiple dimensions, thus allowing simultaneous filtering of spatial and temporal attributes. It uses a block-based storage structure to speed up OLAP-type queries over historical data, and supports query processing over in-memory and disk-resident data. We present different query execution algorithms that we designed to allow the index to be used in different hardware configurations, including CPU-only, GPU-only, and a combination of CPU and GPU. To demonstrate the effectiveness of our techniques, we implemented them on top of MongoDB and performed an experimental evaluation using two real-world data sets: New York City's (NYC) taxi data - consisting of over 868 million taxi trips spanning a period of five years, and Twitter posts - over 1.1 billion tweets collected over a period of 14 months. Our results show that our GPU-based index obtains interactive, sub-second response times for queries over large data sets and leads to at least two orders of magnitude speedup over spatial indexes implemented in existing open-source and commercial database systems.Keywords
This publication has 35 references indexed in Scilit:
- Visual Exploration of Big Spatio-Temporal Urban Data: A Study of New York City Taxi TripsIEEE Transactions on Visualization and Computer Graphics, 2013
- Nanocubes for Real-Time Exploration of Spatiotemporal DatasetsIEEE Transactions on Visualization and Computer Graphics, 2013
- Location-dependent query processingACM Computing Surveys, 2010
- Real-time KD-tree construction on graphics hardwareACM Transactions on Graphics, 2008
- Indexing Multimodal Biometric Databases Using Kd-Tree with Feature Level Fusion2008
- Hardware Acceleration in Commercial Databases2004
- Bkd-Tree: A Dynamic Scalable kd-Tree2003
- R-treesACM SIGMOD Record, 1984
- Multidimensional binary search trees used for associative searchingCommunications of the ACM, 1975
- Quad trees a data structure for retrieval on composite keysActa Informatica, 1974