SING: Sequence Indexing Using GPUs
Authors:
- 1 April 2021
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1883-1888
Abstract
Data series similarity search is a core operation for several data series analysis applications across many domains. This has attracted lots of interest that led to the development of several indexing techniques. Nevertheless, these techniques fail to deliver the similarity search time performance that is needed for interactive exploration, or analysis of large data series collections. We propose SING, the first data series index designed to take advantage of Graphics Processing Units (GPUs). SING is an in-memory index that uses CPU+GPU co-processing (as well as SIMD, multi-core and multi-socket architectures), in order to accelerate similarity search. Our experimental evaluation with synthetic and real datasets shows that SING is up to 5.1x faster than the state-of-the-art parallel in-memory approach, and up to 62x faster than the state-of-the-art parallel serial scan algorithm. SING achieves exact similarity search query times as low as 32msec on 100GB datasets, which enables interactive data exploration on very large data series collections.Keywords
This publication has 45 references indexed in Scilit:
- Practical Data Prediction for Real-World Wireless Sensor NetworksIEEE Transactions on Knowledge and Data Engineering, 2015
- Computational Intelligence Challenges and Applications on Large-Scale Astronomical Time Series DatabasesIEEE Computational Intelligence Magazine, 2014
- A data-adaptive and dynamic segmentation index for whole matching on time seriesProceedings of the VLDB Endowment, 2013
- Beyond one billion time series: indexing and mining very large time series collections with $i$ SAX2+Knowledge and Information Systems, 2013
- A disk-aware algorithm for time series motif discoveryData Mining and Knowledge Discovery, 2010
- Anomaly detectionACM Computing Surveys, 2009
- iSAX: disk-aware mining and indexing of massive time series datasetsData Mining and Knowledge Discovery, 2009
- Dimensionality Reduction for Fast Similarity Search in Large Time Series DatabasesKnowledge and Information Systems, 2001
- Similarity-based queries for time series dataACM SIGMOD Record, 1997
- Efficient similarity search in sequence databases1993