Search

Algorithms for answering the k nearest-neighbor (k-NN) query are widely used for queries in spatial databases and for distance classification of a group of query points against a reference dataset to derive the dominating feature class. GPU devices have significantly more processing cores than CPUs and faster device memory than the main memory accessed by CPUs, thus, providing higher computing power for processing demanding queries like the k-NN. However, since device and/or main memory may not be able to host an entire, rather big, reference and query datasets, storing these datasets in a fast secondary device, like a solid state disk (SSD), and partially retrieve the required, at each stage, partitions is, in many practical cases, a feasible solution. We propose and implement the first GPU-based algorithms for processing the k-NN query for big reference and query spatial data stored on SSDs. Based on 3d synthetic and real big spatial data, we experimentally compare these algorithms and highlight the most efficient algorithmic variation. This variation utilizes a CUDA feature known as Concurrent Kernel Execution, to further improve its performance. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Spatial indexes are important in spatial databases for efficient execution of queries involving spatial constraints. The xBR + -tree is a balanced, disk-resident, Quadtree-based index for point data, which is very efficient for processing spatial queries. Bulk-loading refers to the process of creating an index from scratch as a whole, when the dataset to be indexed is available beforehand, instead of creating (loading) the index gradually, when the dataset items are available one-by-one. Bulk insertion refers to the process of updating an existing index by inserting a large batch of new data, treating the items of this batch as a whole and not by inserting these items one-by-one. In this paper, we modify previous bulk-loading and bulk-insertion algorithms for xBR + -trees to achieve higher performance by taking advantage of the special features of Solid State Drives (SSDs). SSDs have attracted database developers, mainly due to their higher read performance (thanks to their internal parallelism) than Hard Disk Drives. Using real and artificial datasets of various cardinalities, we experimentally compare the modified algorithms against their predecessors and show that the modified algorithms are clear winners regarding performance. [ABSTRACT FROM AUTHOR]

Indexing data on flash-based Solid State Drives (SSDs) is an important paradigm recently applied in spatial data management. During last years, the design of new spatial access methods for SSDs, named flash-aware spatial indices, has attracted the attention of many researchers, mainly to exploit the advantages of SSDs in spatial query processing. eFIND is a generic framework for transforming a disk-based spatial index into a flash-aware one, taking into account the intrinsic characteristics of SSDs. In this article, we present a systematic approach for porting disk-based data-driven and space-driven access methods to SSDs, through the eFIND framework. We also present the actual porting of representatives data-driven (R-trees, R*-trees, and Hilbert R-trees) and space-driven (xBR+-trees) access methods through this framework. Moreover, we present an extensive experimental evaluation that compares the performance of these ported indices when inserting and querying synthetic and real point datasets. The main conclusions of this experimental study are that the eFIND R-tree excels in insertions, the eFIND xBR+-tree is the fastest for different types of spatial queries, and the eFIND Hilbert R-tree is efficient for processing intersection range queries. [ABSTRACT FROM AUTHOR]