Search

Spatial database systems and Geographic Information Systems frequently employ disk-based spatial indices like the R-tree and the R*-tree to speed up the processing of spatial queries, such as spatial range queries. Commonly, these indices are originally designed for Hard Disk Drives (HDDs) and thus, they take into account the slow mechanical access and the cost of search and rotational delay of magnetic disks. On the other hand, flash-based Solid State Drives (SSDs) have widely been adopted in local data centers and cloud data centers like the Microsoft Azure environment. Because of intrinsic characteristics of SSDs like the erase-before-update property and the asymmetric costs between reads and writes, the impact of spatial indexing on SSDs needs to be studied. In this article, we conduct an experimental evaluation in order to analyze the performance relation of spatial indexing on HDDs and SSDs. For this purpose, we execute our experiments on a local server equipped with an HDD and an SSD, as well as on virtual machines equipped with HDDs and SSDs and allocated in the Microsoft Azure environment. As a result, we show experimentally that spatial indices originally designed for HDDs should be redesigned for SSDs in order to take into account the intrinsic characteristics of SSDs. This means that a spatial index that showed a good performance on an HDD often did not show the same good performance on an SSD.

Spatial vagueness has been increasingly required by geoscientists to handle vague spatial objects, that is, spatial objects found in real-world phenomena that do not have exact locations, strict boundaries, or sharp interiors. However, there is a gap in the literature in how to handle spatial vagueness in spatial database management systems and Geographical Information Systems (GIS) since they mainly provide support to crisp spatial objects, that is, objects that have well-defined locations, boundaries, and interiors. In this article, we propose VagueGeometry, a novel abstract data type that allows users to manipulate vague spatial objects in spatial applications and GIS. The main advantages of our VagueGeometry are that (i) it offers textual and binary representations for vague spatial objects, (ii) it includes an expressive set of vague spatial operations, (iii) it supports SQL operators, and (iv) its implementation is open source. We also propose an improvement of VagueGeometry to deal efficiently with the processing of vague topological predicates. Experimental results show that VagueGeometry improved the performance of spatial queries with vague topological predicates from 21% up to 98% if compared with functionalities available in current spatial databases.

Crisp spatial objects are geometric features with exact location on the extent and well-known boundaries. On the other hand, vague or fuzzy spatial objects are characterized by uncertain or blurred boundaries and interiors. Despite the importance of fuzzy spatial data in spatial applications, few related work indeed implement them. In addition, related work do not define abstract data types to enable the management of fuzzy spatial objects by using database management systems (DBMS). In this article, we propose the abstract data type FuzzyGeometry to handle fuzzy spatial objects in the PostgreSQL DBMS. Its implementation is open source. It offers management for fuzzy point objects and fuzzy line objects as well as provides several operations to handle them. As a result, users are able to access PostgreSQL in order to use fuzzy spatial objects in spatial queries.

The F-Onion-tree is a robust access method that slices the metric space into disjoint subspaces to provide quick indexing of complex data in the main memory. However, the F-Onion-tree only performs element-by-element insertions into its structure, i.e. it does not introduce a technique to build the index considering all elements of the dataset at once. In this article, we fill this gap. We propose the HeightBL algorithm for bulk-loading F-Onion-trees. Performance tests with real-world data with different volumes and dimensionalities showed that the index produced by the HeightBL algorithm is very compact. Compared with the element-by-element insertion, the size of the index reduced from 53.42% to 71.25%. The experiments also showed that the HeightBL algorithm significantly improved range and k-NN query processing performance. It required from 13.38% up to 99.94% less distance calculations and was from 8.57% up to 99.04% faster than the element-by-element insertion.

A vague spatial data warehouse allows multidimensional queries with spatial predicates to support the analysis of business scores related to vague spatial data, crisp spatial data and conventional data. However, vague spatial data are often represented and stored as multiple geometries and impair the query processing performance. In this paper, we describe an index called VSB-index to improve the query processing performance in vague spatial data warehouses, focusing on range queries and vague regions. We also conduct an experimental evaluation using a real dataset, demonstrating that our VSB-index provided remarkable performance gains up to 94% over existing solutions.

Although the materialization of views reduces the execution time of OLAP queries, the materialization of a large number of views may exceed computer storage thresholds. Thus, given a certain storage cost threshold, there is a need for selecting the best views to be materialized, i.e. views that ?t the storage requirements and provide the lowest response time to process OLAP queries. Several solutions have been proposed in the literature to solve this problem. However, most studies have adopted strictly greedy or purely random approaches. Also, most of them do not encompass the entire cycle of execution of multidimensional analysis, or do not specify and implement the whole cycle of multidimensional query execution. In this paper, we address these issues by proposing a novel method for selecting and materializing views based on OLAP signatures and GRASP (Greedy Randomized Adaptive Search). On the one hand, using OLAP signatures and their relationships with descriptions of the data cube, we are able to identify which views should be materialized for being more beneficial to the user query processing. On the other hand, using GRASP allows us to de?ne a hybrid method, which traverses the solution space in a comprehensive manner as performed in purely random approaches, while examines only the regions of the search space with a great concentration of good solutions generated by a greedy approach. GRASP was compared to other VSP algorithms, namely Pick by Size (PBS) and Ant Colony Optimization (ACO), and performance tests indicated that compared to PBS, the proposed method obtained a time reduction of about 20.4% in query processing. In addition, GRASP was more scalable than PBS, since it selected and materialized a smaller set of views, even when there was a wide range of possible views to be chosen. Also, GRASP obtained nearly the same query runtime of ACO (i.e. a small performance loss of about 2.84% was obtained by GRASP), but a shorter time for the selection of views than the ACO algorithm (i.e. a gain in processing time of about 77% was produced by GRASP).

Graph mining is concerned with mining frequent subgraph patterns over a collection of graphs, aiming to find novel and useful knowledge. It has being used to analyze data from different domains, sometimes using algorithms tailored for a specific area of knowledge. In this paper, we propose a graph-mining algorithm and its application in the biomedical domain. We introduce the ADI-bio structure, which organizes data from a database with information of a disease’s patient, and also the ADI-Minebio algorithm, which performs a search on the proposed ADI-bio structure to find frequent subgraphs. Our approach is based on the ADI (adjacency index) structure and the ADI-Mine algorithm, but specifies a different structure and hence a new way of analyzing data through this structure. We also present a performance study to show the feasibility of our approach.

Geographic Data Warehouses (GDWs) are traditional data warehouses with spatial attributes that are used for defining spatial dimension tables, spatial measures and spatial hierarchies. Non-redundant spatial data warehouse schemas have been recognized as an essential issue in the GDW design. Although the lack of spatial redundancy represents a gain in data storage, it implies in a need for performing expensive join operations to answer a given query that may refer to one or more query windows. In this paper, we investigate to what extent the separate storage of spatial and conventional data is recommended in GDW, according to increasing numbers of query windows. We also investigate if the complexity of the spatial data (i.e. points versus polygons) influences the choice of storing spatial and conventional data in the same or in different dimension tables. Our experimental results indicated that if non-redundant spatial data are represented as point objects, an approach to avoid additional join costs by storing both point data and their descriptive data in a single table should be chosen. The results also showed that redundant GDW schemas introduce a severe drawback, as some spatial analytical queries cannot reuse previously fetched spatial data, impairing query performance. Finally, based on the experimental results, we propose in this paper a set of guidelines for the design of logical GDW schemas, called ``Logical GDW Design Guidelines''.