Parallel processing of spatial batch-queries using $${\text {xBR}}^+$$ xBR
- PDF / 873,686 Bytes
- 21 Pages / 595.276 x 790.866 pts Page_size
- 75 Downloads / 222 Views
(0123456789().,-volV)(0123456789(). ,- volV)
Parallel processing of spatial batch-queries using xBR + -trees in solidstate drives George Roumelis1 • Polychronis Velentzas1 • Michael Vassilakopoulos1 Athanasios Fevgas1 • Yannis Manolopoulos3
•
Antonio Corral2
•
Received: 9 May 2019 / Revised: 24 October 2019 / Accepted: 30 October 2019 Springer Science+Business Media, LLC, part of Springer Nature 2019
Abstract Efficient query processing in spatial databases is of vital importance for numerous modern applications. In most cases, such processing is accomplished by taking advantage of spatial indexes. The xBRþ -tree is an index for point data which has been shown to outperform indexes belonging to the R-tree family. On the other hand, Solid-State Drives (SSDs) are secondary storage devices that exhibit higher (especially read) performance than Hard Disk Drives and nowadays are being used in database systems. Regarding query processing, the higher performance of SSDs is maximized when large sequences of queries (batch queries) are executed by exploiting the massive I/O advantages of SSDs. Moreover, nowadays each CPU contains multiple cores which can be utilized to perform calculations in parallel and further improve performance of query processing. In this paper, we present algorithms for processing common spatial (point-location, window and distance-range) batch queries using xBRþ -trees in SSDs. Next, we transform these algorithms to additionally take advantage of the multiple CPU cores. Moreover, utilizing small and large datasets, we experimentally study the performance of these new, SSD based, algorithms against processing of batch queries by repeatedly applying existing algorithms for these queries. We further study the performance of the algorithms that utilize parallelism against the ones taking advantage of SSDs only. Our experiments show that the new algorithms taking advantage of SSDs and even further the ones that also utilize multiple cores prevail performance-wise. Nevertheless, we discuss how these new parallel algorithms can be extended to work in a distributed environment, taking advantage of parallelism between machines, while processing data of larger scales. Keywords Spatial indexes xBRþ -trees Query processing Solid-state drives Multi-core CPUs
1
Data Structuring and Eng. Lab., Department of Electrical and Computer Engineering, University of Thessaly, 38221 Volos, Greece
George Roumelis [email protected]
2
Department on Informatics, University of Almeria, 04120 Almerı´a, Spain
Polychronis Velentzas [email protected]
3
Faculty of Pure and Applied Sciences, Open University of Cyprus, Nicosia, Cyprus
& Michael Vassilakopoulos [email protected]
Antonio Corral [email protected] Athanasios Fevgas [email protected] Yannis Manolopoulos [email protected]
123
Cluster Computing
1 Introduction Nowadays, the volume of available spatial data (e.g. location, routing, navigation data, etc.) is continuously increasing world-wide. To exploit these data, efficient processing of spatial
Data Loading...
