Pagrindinis šio darbo tikslas yra išnagrinėti judančių objektų indeksavimo duomenų bazėse problemas, siūlomus sprendimus bei palyginti keleto iš jų veiksmingumą. Įvairiais pjūviais buvo lyginami praeities duomenis indeksuojantys R ir iš jo išvesti STR bei TB medžiai. Eksperimentai atlikti naudojant sugeneruotus judančių objektų duomenis. Gauti rezultatai parodė, kad indeksų veiksmingas priklauso nuo tam tikrų sąlygų ir aplinkybių, kuriomis jie naudojami. / Over the past few years, there has been a continuous improvement in the wireless communications and the positioning technologies. As a result, tracking the changing positions of continuously moving objects is becoming increasingly feasible and necessary. Databases that deal with objects that change their location and/or shape over time are called spatio-temporal databases. Traditional database approaches for effective information retrieval cannot be used as the moving objects database is highly dynamic. A need for so called spatio-temporal indexing techniques comes to scene. Mainly, by the problem they are addressed to, indices are divided into two groups: a) indexing the past and b) indexing the current and predicted future positions. Also the have been proposed techniques covering both problems. This work is a survey for well known and used indices. Also there is a performance comparison between several past indexing methods. STR Tree, TB Tree and the predecessor of many indices, the R Tree are compared in various aspects using generated datasets of simulated objects movement.

For many applications of location-based services, such as friend finding, buddy tracking,information sharing and cooperative caching in ad hoc networks, it is often important to be able to identify whether the positions of a given set of moving objects are within close proximity. To compute these kinds of proximity relations among large populations of moving objects, continuously available location position information of these objects must be correlated against each other to identify whether a given set of objects are in the specified proximity relation. In this dissertation, we state this problem, referring to it as the location constraint matching problem, both in the Euclidean space and the road network space. In the Euclidean space, we present an adaptive solution to this problem for various environments. We also study the position uncertainty associated with the constraint matching. For the road network space, where the object can only move along the edges of the road network, we propose an efficient algorithm based on graph partitioning, which dramatically restricts the search space and enhances performance. Our approaches reduce the constraint processing time by 80% for Euclidean space and by 90% for road network space respectively. The logical combination of individual constraints with conjunction, disjunction and negation results in more expressive constraint expressions than are possible based on single constraints. We model constraint expressions with Binary Decision Diagrams (BDD). Furthermore, we exploit the shared execution of constraint combinations based on the BDD modeling. All the algorithms for various aspects of the constraint processing are integrated in the research prototype L-ToPSS (Location-based Toronto Publish/Subscribe System). Through experimental study and the development of an analytical model, we show that the proposed solution scales to large numbers of constraints and large numbers of moving objects.

For many applications of location-based services, such as friend finding, buddy tracking,information sharing and cooperative caching in ad hoc networks, it is often important to be able to identify whether the positions of a given set of moving objects are within close proximity. To compute these kinds of proximity relations among large populations of moving objects, continuously available location position information of these objects must be correlated against each other to identify whether a given set of objects are in the specified proximity relation. In this dissertation, we state this problem, referring to it as the location constraint matching problem, both in the Euclidean space and the road network space. In the Euclidean space, we present an adaptive solution to this problem for various environments. We also study the position uncertainty associated with the constraint matching. For the road network space, where the object can only move along the edges of the road network, we propose an efficient algorithm based on graph partitioning, which dramatically restricts the search space and enhances performance. Our approaches reduce the constraint processing time by 80% for Euclidean space and by 90% for road network space respectively. The logical combination of individual constraints with conjunction, disjunction and negation results in more expressive constraint expressions than are possible based on single constraints. We model constraint expressions with Binary Decision Diagrams (BDD). Furthermore, we exploit the shared execution of constraint combinations based on the BDD modeling. All the algorithms for various aspects of the constraint processing are integrated in the research prototype L-ToPSS (Location-based Toronto Publish/Subscribe System). Through experimental study and the development of an analytical model, we show that the proposed solution scales to large numbers of constraints and large numbers of moving objects.

La numérisation de nos espaces de vie et de mobilités s’est largement accentuée durant la dernière décennie. La multiplication des capteurs de toute nature permettant de percevoir et de mesurer notre espace physique en est le levier principal. L’ensemble de ces systèmes produit aujourd’hui de grands volumes de données hétérogènes sans cesse croissants, ce qui soulève de nombreux enjeux scientifiques et d'ingénierie en termes de stockage et de traitement pour la gestion et l’analyse de mobilités. Les travaux dans le domaine d’analyse des données spatio-temporelles ont largement été orientés soit vers la fouille de données historiques archivées, soit vers le traitement continu. Afin d’éviter les écueils de plus en plus prégnants dus à l’augmentation de ces volumes de données et de leur vélocité (temps de traitement trop long, modèles conceptuellement plus adaptés, analyse approximative des données), nous proposons la conception d’une approche hybride distribuée permettant le traitement combiné de flux temps-réel et de données archivées. L’objectif de cette thèse est donc de développer un nouveau système de gestion et de traitement distribué pour l’analyse des mobilités en particulier maritimes. La solution proposée répond principalement à des contraintes de temps-réel, les données archivées et les informations qui en sont extraites permettant d'améliorer la qualité de réponse. Une proposition de paradigme d'événements est également développée pour permettre ce traitement hybride mais aussi pour caractériser et identifier plus facilement des comportements types d'objets mobiles. Enfin, une requête appliquée sur des zones de couverture de signal pour des objets mobiles a été étudiée et testée sur des données maritimes mettant en exergue le besoin d'une approche hybride pour le traitement de trajectoires. / Over the past few years, the rapid prolifération of sensors and devices recording positioning information regularly produces very large volumes of heterogeneous data. This leads to many research challenges as the storage, distribution, management,Processing and analysis of the large mobility data generated still needs to be solved. Current works related to the manipulation of mobility data have been directed towards either mining archived historical data or continuous processing of incoming data streams.The aim of this research is to design a holistic System whose objective is to provide a combined processing of real time data streams and archived data positions. The proposed solution is real-time oriented, historical data and informations extracted from them allowing to enhance quality of the answers to queries. A event paradigm is discussed to facilitate the hybrid approach and to identify typical moving objects behaviors. Finally, a query concerning signal coverage of moving objects has been studied and applied to maritime data showing the relevance of a hybrid approach to deal with moving object data processing.

Submitted by Daniele Amaral (daniee_ni@hotmail.com) on 2016-10-07T20:05:05Z No. of bitstreams: 1 DissCJN.pdf: 5948964 bytes, checksum: e7e719e26b50a85697e7934bde411070 (MD5) / Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2016-10-20T19:30:58Z (GMT) No. of bitstreams: 1 DissCJN.pdf: 5948964 bytes, checksum: e7e719e26b50a85697e7934bde411070 (MD5) / Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2016-10-20T19:31:04Z (GMT) No. of bitstreams: 1 DissCJN.pdf: 5948964 bytes, checksum: e7e719e26b50a85697e7934bde411070 (MD5) / Made available in DSpace on 2016-10-20T19:31:09Z (GMT). No. of bitstreams: 1 DissCJN.pdf: 5948964 bytes, checksum: e7e719e26b50a85697e7934bde411070 (MD5) Previous issue date: 2016-03-08 / Não recebi financiamento / By providing ever-growing processing capabilities, many database technologies have been becoming important support tools to enterprises and institutions. The need to include (and control) new data types to the existing database technologies has brought also new challenges and research areas, arising the spatial, temporal, and spatiotemporal databases. Besides that, new analytical capabilities were required facilitating the birth of the data warehouse technology and, once more, the need to include spatial or temporal data (or both) to it, thus originating the spatial, temporal, and spatio-temporal data warehouses. The queries used in each database type had also evolved, culminating in the STOLAP (Spatio Temporal OLAP) queries, which are composed of predicates dealing with conventional, spatial, and temporal data with the possibility of having their execution aided by specialized index structures. This work’s intention is to investigate how the execution of each predicate affects the performance of STOLAP queries by varying the used indexes, their execution order and the query’s selectivity. Bitmap Join Indexes will help in conventional predicate’s execution and in some portions of the temporal processing, which will also count with the use of SQL queries for some of the alternatives used in this research. The SB-index and HSB-index will aid the spatial processing while the STB-index will be used to process temporal and spatial predicates together. The expected result is an analysis of the best predicate order while running the queries also considering their selectivity. Another contribution of this work is the evolution of the HSB-index to a hierarchized version called HSTB-index, which should complement the execution options. / Por proverem uma capacidade de processamento de dados cada vez maior, várias tecnologias de bancos de dados têm se tornado importantes ferramentas de apoio a empresas e instituições. A necessidade de se incluir e controlar novos tipos de dados aos bancos de dados já existentes fizeram também surgir novos desafios e novas linhas de pesquisa, como é o caso dos bancos de dados espaciais, temporais e espaçotemporais. Além disso, novas capacidades analíticas foram se fazendo necessárias culminando com o surgimento dos data warehouses e, mais uma vez, com a necessidade de se incluir dados espaciais e temporais (ou ambos) surgindo os data warehouses espaciais, temporais e espaço-temporais. As consultas relacionadas a cada tipo de banco de dados também evoluíram culminando com as consultas STOLAP (Spatio-Temporal OLAP) que são compostas basicamente por predicados envolvendo dados convencionais, espaciais e temporais e cujo processamento pode ser auxiliado por estruturas de indexação especializadas. Este trabalho pretende investigar como a execução de cada um dos tipos de predicados afeta o desempenho de consultas STOLAP variando-se os índices utilizados, a ordem de execução dos predicados e a seletividade das consultas. Índices Bitmap de Junção auxiliarão na execução dos predicados convencionais e de algumas partes dos predicados temporais que também contarão com o auxílio de consultas SQL, enquanto os índices SB-index e HSB-index serão utilizados para auxiliar na execução dos predicados espaciais das consultas. O STB-index também será utilizado nas comparações e envolve ambos os predicados espacial e temporal. Espera-se obter uma análise das melhores opções de combinação de execução dos predicados em consultas STOLAP tendo em vista também a seletividade das consultas. Outra contribuição deste trabalho é a evolução do HSB-index para uma versão hierarquizada chamada HSTB-index e que servirá para complementar as opções de processamento de consultas STOLAP.

This work treats the representation of moving objects and operations over these objects. Intro­duces the support for spatio-temporal data in Oracle Database 10g and presents two designs of moving objects database structure. Upon these designs a database was implemented using the user-defined data types. Sample application provides a graphical output of stored spatial data and allows us to call an implemented spatio-temporal operations. Finally, an evaluation of achieved results is done and possible extensions of project are discussed.