Modern geographical databases store a rich set of aspatial attributes in addition to geographic data. Retrieving spatial records constrained on spatial and aspatial attributes provides users the ability to perform more interesting spatial analyses via composite spatial searches; e.g., in a real estate database, "Find the nearest homes for sale to my current location that have backyard and whose prices are between $50,000 and $80,000". Efficient processing of such composite searches requires combined indexing strategies of multiple types of data. Existing spatial query engines commonly apply a two-filter approach (spatial filter followed by non-spatial filter, or viceversa), which can incur large performance overheads. On the other hand, the amount of geolocation data in databases is rapidly increasing due in part to advances in geolocation technologies (e.g., GPS- enabled mobile devices) that allow to associate location data to nearly every object or event. Hence, practical spatial databases may face data ingestion challenges of large data volumes. In this dissertation, we first show how indexing spatial data with R-trees (a typical data pre- processing task) can be scaled in MapReduce – a well-adopted parallel programming model, developed by Google, for data intensive problems. Close to linear scalability was observed in index construction tasks over large spatial datasets. Subsequently, we develop novel techniques for simultaneously indexing spatial with textual and numeric data to process k-nearest neighbor searches with aspatial Boolean selection constraints. In particular, numeric ranges are compactly encoded and explicitly indexed. Experimental evaluations with real spatial databases showed query response times within acceptable ranges for interactive search systems.

As características particulares dos dados geográficos constituem a razão pela qual se faz necessário estruturar novos tipos de dados e arquitetar novas formas de armazenamento e acesso aos dados. Este trabalho apresenta uma análise considerando as Arquiteturas Dual e Integrada em relação à forma de gerenciamento e recuperação da informação espacial, em conjunto com as informações não espaciais. Este trabalho aborda os conceitos fundamentais acerca dos Sistemas Gerenciadores de Banco de Dados Geográficos. Para demonstrar como estes conceitos são importantes e influenciam diretamente na eficiência dos mesmos, conclui-se o trabalho com o desenvolvimento de alguns testes de funcionalidade sob duas ferramentas com arquiteturas distintas, são elas: o SPRING, de Arquitetura Dual, e o ORACLE SPATIAL, de Arquitetura Integrada. Os testes de funcionalidade objetivaram verificar se e como as ferramentas em estudo, suportam determinados tipos de consultas espaciais. Para tanto foi escolhido o cenário de Planejamento Urbano e selecionados alguns tipos de consultas envolvendo componentes espaciais, que normalmente são implementadas neste tipo de aplicação. Os resultados obtidos permitem concluir, principalmente, que as ferramentas analisadas suportaram as consultas espaciais utilizadas nos testes - algumas envolvendo o objeto espacial e o atributo ao mesmo tempo - porém, com algumas restrições. Além disso, foi possível fazer algumas considerações em relação à utilização ou não de índices espaciais para otimização das consultas e algumas constatações sobre as arquiteturas de banco de dados geográficos analisadas, em relação à integração dos dados espaciais com os dados não espaciais. / The spatial data complexity justifies the need to develop new spatial data types and to design new structures to store, to query and to handle spatially referenced data inside a database management system (DBMS). This work presents an analysis of these issues considering the different architectures of geographic databases. The Dual and Integrated arquitectures are considered in relation to spatial data and attribute handling. The principal concepts concerning the spatial DBMS are presented. To demonstrate how these concepts are important and influence directly in the efficiency of Geographic Information Systems (GIS) tools, these work concludes with the development of some tests of functionality. Two GIS programs with distinct architectures were tested, and they are: the SPRING, of Dual Architecture, and ORACLE SPATIAL, of Integrated Architecture. The functionality tests aimed to verify if the tools in study support some kind of spatial queries, describing the necessary steps to perform these queries. In order to perform the tests, an Urban Planning application was chosen and some spatial queries were defined and executed.

As características particulares dos dados geográficos constituem a razão pela qual se faz necessário estruturar novos tipos de dados e arquitetar novas formas de armazenamento e acesso aos dados. Este trabalho apresenta uma análise considerando as Arquiteturas Dual e Integrada em relação à forma de gerenciamento e recuperação da informação espacial, em conjunto com as informações não espaciais. Este trabalho aborda os conceitos fundamentais acerca dos Sistemas Gerenciadores de Banco de Dados Geográficos. Para demonstrar como estes conceitos são importantes e influenciam diretamente na eficiência dos mesmos, conclui-se o trabalho com o desenvolvimento de alguns testes de funcionalidade sob duas ferramentas com arquiteturas distintas, são elas: o SPRING, de Arquitetura Dual, e o ORACLE SPATIAL, de Arquitetura Integrada. Os testes de funcionalidade objetivaram verificar se e como as ferramentas em estudo, suportam determinados tipos de consultas espaciais. Para tanto foi escolhido o cenário de Planejamento Urbano e selecionados alguns tipos de consultas envolvendo componentes espaciais, que normalmente são implementadas neste tipo de aplicação. Os resultados obtidos permitem concluir, principalmente, que as ferramentas analisadas suportaram as consultas espaciais utilizadas nos testes - algumas envolvendo o objeto espacial e o atributo ao mesmo tempo - porém, com algumas restrições. Além disso, foi possível fazer algumas considerações em relação à utilização ou não de índices espaciais para otimização das consultas e algumas constatações sobre as arquiteturas de banco de dados geográficos analisadas, em relação à integração dos dados espaciais com os dados não espaciais. / The spatial data complexity justifies the need to develop new spatial data types and to design new structures to store, to query and to handle spatially referenced data inside a database management system (DBMS). This work presents an analysis of these issues considering the different architectures of geographic databases. The Dual and Integrated arquitectures are considered in relation to spatial data and attribute handling. The principal concepts concerning the spatial DBMS are presented. To demonstrate how these concepts are important and influence directly in the efficiency of Geographic Information Systems (GIS) tools, these work concludes with the development of some tests of functionality. Two GIS programs with distinct architectures were tested, and they are: the SPRING, of Dual Architecture, and ORACLE SPATIAL, of Integrated Architecture. The functionality tests aimed to verify if the tools in study support some kind of spatial queries, describing the necessary steps to perform these queries. In order to perform the tests, an Urban Planning application was chosen and some spatial queries were defined and executed.

With the exponential growth of the usage of web-based map services, the web GIS application has become more and more popular. Spatial data index, search, analysis, visualization and the resource management of such services are becoming increasingly important to deliver user-desired Quality of Service. First, spatial indexing is typically time-consuming and is not available to end-users. To address this, we introduce TerraFly sksOpen, an open-sourced an Online Indexing and Querying System for Big Geospatial Data. Integrated with the TerraFly Geospatial database [1-9], sksOpen is an efficient indexing and query engine for processing Top-k Spatial Boolean Queries. Further, we provide ergonomic visualization of query results on interactive maps to facilitate the user’s data analysis. Second, due to the highly complex and dynamic nature of GIS systems, it is quite challenging for the end users to quickly understand and analyze the spatial data, and to efficiently share their own data and analysis results with others. Built on the TerraFly Geo spatial database, TerraFly GeoCloud is an extra layer running upon the TerraFly map and can efficiently support many different visualization functions and spatial data analysis models. Furthermore, users can create unique URLs to visualize and share the analysis results. TerraFly GeoCloud also enables the MapQL technology to customize map visualization using SQL-like statements [10]. Third, map systems often serve dynamic web workloads and involve multiple CPU and I/O intensive tiers, which make it challenging to meet the response time targets of map requests while using the resources efficiently. Virtualization facilitates the deployment of web map services and improves their resource utilization through encapsulation and consolidation. Autonomic resource management allows resources to be automatically provisioned to a map service and its internal tiers on demand. v-TerraFly are techniques to predict the demand of map workloads online and optimize resource allocations, considering both response time and data freshness as the QoS target. The proposed v-TerraFly system is prototyped on TerraFly, a production web map service, and evaluated using real TerraFly workloads. The results show that v-TerraFly can accurately predict the workload demands: 18.91% more accurate; and efficiently allocate resources to meet the QoS target: improves the QoS by 26.19% and saves resource usages by 20.83% compared to traditional peak load-based resource allocation.

Researchers have been investigating the optimal route query problem for a long time. Optimal route queries are categorized as either unconstrained or constrained queries. Many main memory based algorithms have been developed to deal with the optimal route query problem. Among these, Dijkstra's shortest path algorithm is one of the most popular algorithms for the unconstrained route query problem. The constrained route query problem is more complicated than the unconstrained one, and some constrained route query problems such as the Traveling Salesman Problem and Hamiltonian Path Problem are NP-hard. There are many algorithms dealing with the constrained route query problem, but most of them only solve a specific case. In addition, all of them require that the entire graph resides in the main memory. Recently, due to the need of applications in very large graphs, such as the digital maps managed by Geographic Information Systems (GIS), several disk-based algorithms have been derived by using divide-and-conquer techniques to solve the shortest path problem in a very large graph. However, until now little research has been conducted on the disk-based constrained problem. <br /><br /> This thesis presents two algorithms: 1) a new disk-based shortest path algorithm (DiskSPNN), and 2) a new disk-based optimal path algorithm (DiskOP) that answers an optimal route query without passing a set of forbidden edges in a very large graph. Both algorithms fit within the same divide-and-conquer framework as the existing disk-based shortest path algorithms proposed by Ning Zhang and Heechul Lim. Several techniques, including query super graph, successor fragment and open boundary node pruning are proposed to improve the performance of the previous disk-based shortest path algorithms. Furthermore, these techniques are applied to the DiskOP algorithm with minor changes. The proposed DiskOP algorithm depends on the concept of collecting a set of boundary vertices and simultaneously relaxing their adjacent super edges. Even if the forbidden edges are distributed in all the fragments of a graph, the DiskOP algorithm requires little memory. Our experimental results indicate that the DiskSPNN algorithm performs better than the original ones with respect to the I/O cost as well as the running time, and the DiskOP algorithm successfully solves a specific constrained route query problem in a very large graph.

Researchers have been investigating the optimal route query problem for a long time. Optimal route queries are categorized as either unconstrained or constrained queries. Many main memory based algorithms have been developed to deal with the optimal route query problem. Among these, Dijkstra's shortest path algorithm is one of the most popular algorithms for the unconstrained route query problem. The constrained route query problem is more complicated than the unconstrained one, and some constrained route query problems such as the Traveling Salesman Problem and Hamiltonian Path Problem are NP-hard. There are many algorithms dealing with the constrained route query problem, but most of them only solve a specific case. In addition, all of them require that the entire graph resides in the main memory. Recently, due to the need of applications in very large graphs, such as the digital maps managed by Geographic Information Systems (GIS), several disk-based algorithms have been derived by using divide-and-conquer techniques to solve the shortest path problem in a very large graph. However, until now little research has been conducted on the disk-based constrained problem. <br /><br /> This thesis presents two algorithms: 1) a new disk-based shortest path algorithm (DiskSPNN), and 2) a new disk-based optimal path algorithm (DiskOP) that answers an optimal route query without passing a set of forbidden edges in a very large graph. Both algorithms fit within the same divide-and-conquer framework as the existing disk-based shortest path algorithms proposed by Ning Zhang and Heechul Lim. Several techniques, including query super graph, successor fragment and open boundary node pruning are proposed to improve the performance of the previous disk-based shortest path algorithms. Furthermore, these techniques are applied to the DiskOP algorithm with minor changes. The proposed DiskOP algorithm depends on the concept of collecting a set of boundary vertices and simultaneously relaxing their adjacent super edges. Even if the forbidden edges are distributed in all the fragments of a graph, the DiskOP algorithm requires little memory. Our experimental results indicate that the DiskSPNN algorithm performs better than the original ones with respect to the I/O cost as well as the running time, and the DiskOP algorithm successfully solves a specific constrained route query problem in a very large graph.

A co-location pattern is a set of spatial features frequently located together in space. A frequent pattern is a set of items that frequently appears in a transaction database. Since its introduction, the paradigm of frequent pattern mining has undergone a shift from candidate generation-and-test based approaches to projection based approaches. Co-location patterns resemble frequent patterns in many aspects. However, the lack of transaction concept, which is crucial in frequent pattern mining, makes the similar shift of paradigm in co-location pattern mining very difficult. This thesis investigates a projection based co-location pattern mining paradigm. In particular, a FP-tree based co-location mining framework and an algorithm called FP-CM, for FP-tree based co-location miner, are proposed. It is proved that FP-CM is complete, correct, and only requires a small constant number of database scans. The experimental results show that FP-CM outperforms candidate generation-and-test based co-location miner by an order of magnitude.

With hundreds of millions of users reporting locations and embracing mobile technologies, Location Based Services (LBSs) are raising new challenges. In this dissertation, we address three emerging problems in location services, where geolocation data plays a central role. First, to handle the unprecedented growth of generated geolocation data, existing location services rely on geospatial database systems. However, their inability to leverage combined geographical and textual information in analytical queries (e.g. spatial similarity joins) remains an open problem. To address this, we introduce SpsJoin, a framework for computing spatial set-similarity joins. SpsJoin handles combined similarity queries that involve textual and spatial constraints simultaneously. LBSs use this system to tackle different types of problems, such as deduplication, geolocation enhancement and record linkage. We define the spatial set-similarity join problem in a general case and propose an algorithm for its efficient computation. Our solution utilizes parallel computing with MapReduce to handle scalability issues in large geospatial databases. Second, applications that use geolocation data are seldom concerned with ensuring the privacy of participating users. To motivate participation and address privacy concerns, we propose iSafe, a privacy preserving algorithm for computing safety snapshots of co-located mobile devices as well as geosocial network users. iSafe combines geolocation data extracted from crime datasets and geosocial networks such as Yelp. In order to enhance iSafe's ability to compute safety recommendations, even when crime information is incomplete or sparse, we need to identify relationships between Yelp venues and crime indices at their locations. To achieve this, we use SpsJoin on two datasets (Yelp venues and geolocated businesses) to find venues that have not been reviewed and to further compute the crime indices of their locations. Our results show a statistically significant dependence between location crime indices and Yelp features. Third, review centered LBSs (e.g., Yelp) are increasingly becoming targets of malicious campaigns that aim to bias the public image of represented businesses. Although Yelp actively attempts to detect and filter fraudulent reviews, our experiments showed that Yelp is still vulnerable. Fraudulent LBS information also impacts the ability of iSafe to provide correct safety values. We take steps toward addressing this problem by proposing SpiDeR, an algorithm that takes advantage of the richness of information available in Yelp to detect abnormal review patterns. We propose a fake venue detection solution that applies SpsJoin on Yelp and U.S. housing datasets. We validate the proposed solutions using ground truth data extracted by our experiments and reviews filtered by Yelp.

Regular path queries (RPQs), expressed as regular expressions over the alphabet of database edge-labels, are commonly used for guided navigation of graph databases. RPQs are the basic building block of almost all the query languages for graph databases, providing the user with a nice and simple way to express recursion. While convenient to use, RPQs are notorious for their high computational demand. Except for few theoretical works, there has been little work evaluating RPQs on databases of great practical interest, such as large spatial networks. In this thesis, we present a grid-aware, fault tolerant distributed algorithm for answering RPQs on spatial networks. We engineer each part of the algorithm to account for the assumed computational-grid setting. We experimentally evaluate our algorithm, and show that for typical user queries, our algorithm satisfies the desiderata for distributed computing in general, and computational-grids in particular.

The aim of the thesis is to develop a method to identify driving lanes based on aerial images and existing spatial data. The proposed method uses up to date available data in which it identifies road surface marking (RSM). Polygons classified as RSM are further processed to obtain their vector line representation as the first partial result. While processing RSM vectors further, borders of driving lanes are modelled as the second partial result. Furthermore, attempts were done to be able to automatically distinguish between solid and broken lines for a higher amount of information contained in the resulting dataset. Proposed algorithms were tested in 20 case study areas and results are presented further in this thesis. The overall correctness as well as the positional accuracy proves effectivity of the method. However, several shortcomings were identified and are discussed as well as possible solutions for them are suggested. The text is accompanied by more than 70 figures to offer a clear perspective on the topic. The thesis is organised as follows: First, Introduction and Literature review are presented including the problem background, author's motivation, state of the art and contribution of the thesis. Secondly, technical and legal requirements of RSM are presented as well as theoretical concepts and...