A GPU-based implementation for range queries on spaghettis data structure

Roberto Uribe-Paredes; Pedro Valero-Lara; Enrique Arias; José L. Sánchez; Diego Cazorla

doi:10.1007/978-3-642-21928-3_45

A GPU-based implementation for range queries on spaghettis data structure

Roberto Uribe-Paredes, Pedro Valero-Lara, Enrique Arias, José L. Sánchez, Diego Cazorla

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

8 Scopus citations

Abstract

Similarity search in a large collection of stored objects in a metric database has become a most interesting problem. The Spaghettis is an efficient metric data structure to index metric spaces. However, for real applications processing large volumes of generated data, query response times can be high enough. In these cases, it is necessary to apply mechanisms in order to significantly reduce the average query time. In this sense, the parallelization of metric structures is an interesting field of research. The recent appearance of GPUs for general purpose computing platforms offers powerful parallel processing capabilities. In this paper we propose a GPU-based implementation for Spaghettis metric structure. Firstly, we have adapted Spaghettis structure to GPU-based platform. Afterwards, we have compared both sequential and GPU-based implementation to analyse the performance, showing significant improvements in terms of time reduction, obtaining values of speed-up close to 10.

Original language	English
Title of host publication	Computational Science and Its Applications, ICCSA 2011 - International Conference, Proceedings
Pages	615-629
Number of pages	15
Edition	PART 1
DOIs	https://doi.org/10.1007/978-3-642-21928-3_45
State	Published - 2011
Externally published	Yes
Event	2011 International Conference on Computational Science and Its Applications, ICCSA 2011 - Santander, Spain Duration: Jun 20 2011 → Jun 23 2011

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Number	PART 1
Volume	6782 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	2011 International Conference on Computational Science and Its Applications, ICCSA 2011
Country/Territory	Spain
City	Santander
Period	06/20/11 → 06/23/11

Funding

This work has been partially funded by research programs PR-F1-02IC-08, University of Magallanes, Chile and 29/C035-1, Academic Unit of Río Turbio, National University of Patagonia Austral, Argentina, and the Spanish project SAT-SIM (ref: CGL2010-20787-C02-02).

Keywords

CUDA
Databases
GPU
algorithms
data structures
metric spaces
parallel processing
similarity search

Access to Document

10.1007/978-3-642-21928-3_45

Cite this

Uribe-Paredes, R., Valero-Lara, P., Arias, E., Sánchez, J. L., & Cazorla, D. (2011). A GPU-based implementation for range queries on spaghettis data structure. In Computational Science and Its Applications, ICCSA 2011 - International Conference, Proceedings (PART 1 ed., pp. 615-629). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6782 LNCS, No. PART 1). https://doi.org/10.1007/978-3-642-21928-3_45

Uribe-Paredes, Roberto ; Valero-Lara, Pedro ; Arias, Enrique et al. / A GPU-based implementation for range queries on spaghettis data structure. Computational Science and Its Applications, ICCSA 2011 - International Conference, Proceedings. PART 1. ed. 2011. pp. 615-629 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1).

@inproceedings{bf24d217d4984106ae5b00e598760e91,

title = "A GPU-based implementation for range queries on spaghettis data structure",

abstract = "Similarity search in a large collection of stored objects in a metric database has become a most interesting problem. The Spaghettis is an efficient metric data structure to index metric spaces. However, for real applications processing large volumes of generated data, query response times can be high enough. In these cases, it is necessary to apply mechanisms in order to significantly reduce the average query time. In this sense, the parallelization of metric structures is an interesting field of research. The recent appearance of GPUs for general purpose computing platforms offers powerful parallel processing capabilities. In this paper we propose a GPU-based implementation for Spaghettis metric structure. Firstly, we have adapted Spaghettis structure to GPU-based platform. Afterwards, we have compared both sequential and GPU-based implementation to analyse the performance, showing significant improvements in terms of time reduction, obtaining values of speed-up close to 10.",

keywords = "CUDA, Databases, GPU, algorithms, data structures, metric spaces, parallel processing, similarity search",

author = "Roberto Uribe-Paredes and Pedro Valero-Lara and Enrique Arias and S{\'a}nchez, {Jos{\'e} L.} and Diego Cazorla",

year = "2011",

doi = "10.1007/978-3-642-21928-3_45",

language = "English",

isbn = "9783642219276",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

number = "PART 1",

pages = "615--629",

booktitle = "Computational Science and Its Applications, ICCSA 2011 - International Conference, Proceedings",

edition = "PART 1",

note = "2011 International Conference on Computational Science and Its Applications, ICCSA 2011 ; Conference date: 20-06-2011 Through 23-06-2011",

}

Uribe-Paredes, R, Valero-Lara, P, Arias, E, Sánchez, JL & Cazorla, D 2011, A GPU-based implementation for range queries on spaghettis data structure. in Computational Science and Its Applications, ICCSA 2011 - International Conference, Proceedings. PART 1 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 1, vol. 6782 LNCS, pp. 615-629, 2011 International Conference on Computational Science and Its Applications, ICCSA 2011, Santander, Spain, 06/20/11. https://doi.org/10.1007/978-3-642-21928-3_45

A GPU-based implementation for range queries on spaghettis data structure. / Uribe-Paredes, Roberto; Valero-Lara, Pedro; Arias, Enrique et al.
Computational Science and Its Applications, ICCSA 2011 - International Conference, Proceedings. PART 1. ed. 2011. p. 615-629 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6782 LNCS, No. PART 1).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - A GPU-based implementation for range queries on spaghettis data structure

AU - Uribe-Paredes, Roberto

AU - Valero-Lara, Pedro

AU - Arias, Enrique

AU - Sánchez, José L.

AU - Cazorla, Diego

PY - 2011

Y1 - 2011

N2 - Similarity search in a large collection of stored objects in a metric database has become a most interesting problem. The Spaghettis is an efficient metric data structure to index metric spaces. However, for real applications processing large volumes of generated data, query response times can be high enough. In these cases, it is necessary to apply mechanisms in order to significantly reduce the average query time. In this sense, the parallelization of metric structures is an interesting field of research. The recent appearance of GPUs for general purpose computing platforms offers powerful parallel processing capabilities. In this paper we propose a GPU-based implementation for Spaghettis metric structure. Firstly, we have adapted Spaghettis structure to GPU-based platform. Afterwards, we have compared both sequential and GPU-based implementation to analyse the performance, showing significant improvements in terms of time reduction, obtaining values of speed-up close to 10.

AB - Similarity search in a large collection of stored objects in a metric database has become a most interesting problem. The Spaghettis is an efficient metric data structure to index metric spaces. However, for real applications processing large volumes of generated data, query response times can be high enough. In these cases, it is necessary to apply mechanisms in order to significantly reduce the average query time. In this sense, the parallelization of metric structures is an interesting field of research. The recent appearance of GPUs for general purpose computing platforms offers powerful parallel processing capabilities. In this paper we propose a GPU-based implementation for Spaghettis metric structure. Firstly, we have adapted Spaghettis structure to GPU-based platform. Afterwards, we have compared both sequential and GPU-based implementation to analyse the performance, showing significant improvements in terms of time reduction, obtaining values of speed-up close to 10.

KW - CUDA

KW - Databases

KW - GPU

KW - algorithms

KW - data structures

KW - metric spaces

KW - parallel processing

KW - similarity search

UR - http://www.scopus.com/inward/record.url?scp=79960300063&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-21928-3_45

DO - 10.1007/978-3-642-21928-3_45

M3 - Conference contribution

AN - SCOPUS:79960300063

SN - 9783642219276

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 615

EP - 629

BT - Computational Science and Its Applications, ICCSA 2011 - International Conference, Proceedings

T2 - 2011 International Conference on Computational Science and Its Applications, ICCSA 2011

Y2 - 20 June 2011 through 23 June 2011

ER -

Uribe-Paredes R, Valero-Lara P, Arias E, Sánchez JL, Cazorla D. A GPU-based implementation for range queries on spaghettis data structure. In Computational Science and Its Applications, ICCSA 2011 - International Conference, Proceedings. PART 1 ed. 2011. p. 615-629. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1). doi: 10.1007/978-3-642-21928-3_45

A GPU-based implementation for range queries on spaghettis data structure

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this