Dissertations / Theses on the topic 'Database spatio-temporal'

Thesis (M. Phil.)--Hong Kong University of Science and Technology, 2003.<br>Includes bibliographical references (leaves 62-65). Also available in electronic version. Access restricted to campus users.

Thesis (Ph. D.)--Hong Kong University of Science and Technology, 2002.<br>Includes bibliographical references (leaves 208-215). Also available in electronic version. Access restricted to campus users.

Real-time Spatio-Temporal Analytics has become an integral part of Epidemiological studies. The size of the spatio-temporal data has been increasing tremendously over the years, gradually evolving into Big Data. The processing in such domains are highly data and compute intensive. High performance computing resources resources are actively being used to handle such workloads over massive datasets. This confluence of High performance computing and datasets with Big Data characteristics poses great challenges pertaining to data handling and processing. The resource management of supercomputers is in conflict with the data-intensive nature of spatio-temporal analytics. This is further exacerbated due to the fact that the data management is decoupled from the computing resources. Problems of these nature has provided great opportunities in the growth and development of tools and concepts centered around MapReduce based solutions. However, we believe that advanced relational concepts can still be employed to provide an effective solution to handle these issues and challenges. In this study, we explore distributed databases to efficiently handle spatio-temporal Big Data for epidemiological studies. We propose DiceX (Data Intensive Computational Epidemiology using supercomputers), which couples high-performance, Big Data and relational computing by embedding distributed data storage and processing engines within the supercomputer. It is characterized by scalable strategies for data ingestion, unified framework to setup and configure various processing engines, along with the ability to pause, materialize and restore images of a data session. In addition, we have successfully configured DiceX to support approximation algorithms from MADlib Analytics Library [54], primarily Count-Min Sketch or CM Sketch [33][34][35]. DiceX enables a new style of Big Data processing, which is centered around the use of clustered databases and exploits supercomputing resources. It can effectively exploit the cores, memory and compute nodes of supercomputers to scale processing of spatio-temporal queries on datasets of large volume. Thus, it provides a scalable and efficient tool for data management and processing of spatio-temporal data. Although DiceX has been designed for computational epidemiology, it can be easily extended to different data-intensive domains facing similar issues and challenges. We thank our external collaborators and members of the Network Dynamics and Simulation Science Laboratory (NDSSL) for their suggestions and comments. This work has been partially supported by DTRA CNIMS Contract HDTRA1-11-D-0016-0001, DTRA Validation Grant HDTRA1-11-1-0016, NSF - Network Science and Engineering Grant CNS-1011769, NIH and NIGMS - Models of Infectious Disease Agent Study Grant 5U01GM070694-11. Disclaimer: The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of the U.S. Government.<br>Master of Science

La croissance rapide et la complexité de nombreuses villes contemporaines offrent de nombreux défis de recherche pour les scientifiques à la recherche d'une meilleure compréhension des mobilités qui se produisent dans l'espace et dans le temps. A l’heure où de très grandes séries de données de trajectoires en milieu urbain sont disponibles grâce à profusion de nombreux capteurs de positionnement et de services de nombreuses et nouvelles opportunités de recherche et d’application nous sont offertes. Cependant, une bonne intégration de ces données de mobilité nécessite encore l'élaboration de cadres méthodologiques et conceptuels tout comme la mise en oeuvre de bases de données spatio-temporelles qui offriront les capacités appropriées de représentation et de manipulation des données. La recherche développée dans cette thèse introduit une modélisation conceptuelle et une approche de gestion de base de données spatio-temporelles pour représenter et analyser des trajectoires humaines dans des espaces urbains. Le modèle considère les dimensions spatiales, temporelles et sémantiques afin de tenir compte de l’ensemble des propriétés issues des informations de mobilité. Plusieurs abstractions de données de mobilité et des outils de manipulation de données sont développés et expérimentés à partir d’une large base de données de trajectoires disponibles dans la ville de Pékin. L'intérêt de l'approche est double: il montre d’une part que de larges ensembles de données de mobilité peuvent être intégrés au sein de SGBD spatiotemporels extensibles; d’autre part des outils de manipulation et d’interrogation spécifiques peuvent être dérivés à partir de fonctions intégrées au sein d’un langage d’interrogation. Le potentiel de l’approche est illustré par une série d’interrogations qui montrent comment à partir d’une large base de données de trajectoires quelques patrons de déplacements peuvent être obtenus<br>Massive trajectory datasets generated in modern cities generate not only novel research opportunities but also important methodological challenges for academics and decision-makers searching for a better understanding of travel patterns in space and time. This PhD research is oriented towards the conceptual and GIS-based modeling of human displacements derived from large sets of urban trajectories. The motivation behind this study originates from the necessity to search for and explore travel patterns that emerge from citizens acting in the city. Our research introduces a conceptual modelling framework whose objective is to integrate and analyze human displacements within a GIS-based practical solution. The framework combines conceptual and logical models that represent travel trajectories of citizens moving in a given city. The whole approach has been implemented in a geographical database system, experimented in the context of transportation data, and enriched by a series of query interface manipulations and specific functions that illustrate the potential of our whole framework for urban studies. The whole framework has been experimented on top of the Geolife project and large trajectories datasets available in the city of Beijing. Overall, the findings are twofold: first, it appears that our modelling framework can appropriately act as an extensible geographical database support for the integration of large trajectory datasets; second the approach shows that several emerging human displacements can be explored from the manipulation of large urban trajectories

This master's thesis is devoted to the studies of possibilities, which can be used for representation of moving objects data and for querying such spatio-temporal data. It also shows results of the master's thesis created by Ing. Jaroslav Vališ, that should be used for the solution of this master's thesis. But based on the theoretical grounds defined at the beginning of this work was designed and implemented new database extension for saving and querying spatio-temporal data. Special usage of this extension is demonstrated in an example application. This application uses the database extension for the implementation of its own database functions that are domain specific. At the conclusion, there are presented ways of the farther development of this database extension and the results of this master's thesis are there set into the context of the following project, doctoral thesis "Moving objects database".

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.

De nos jours, on a de plus en plus de capteurs qui ont tendance à apporter confort et facilité dans notre vie quotidienne. Ces capteurs sont faciles à déployer et à intégrer dans une variété d’applications (monitoring de bâtiments intelligents, aide à la personne,...). Ces milliers (voire millions)de capteurs sont de plus en plus envahissants et génèrent sans arrêt des masses énormes de données qu’on doit stocker et gérer pour le bon fonctionnement des applications qui en dépendent. A chaque fois qu'un capteur génère une donnée, deux dimensions sont d'un intérêt particulier : la dimension temporelle et la dimension spatiale. Ces deux dimensions permettent d'identifier l'instant de réception et la source émettrice de chaque donnée. Chaque dimension peut se voir associée à une hiérarchie de granularités qui peut varier selon le contexte d'application. Dans cette thèse, nous nous concentrons sur les applications nécessitant une conservation à long terme des données issues des flux de données capteurs. Notre approche vise à contrôler le stockage des données capteurs en ne gardant que les données jugées pertinentes selon la spécification des granularités spatio-temporelles représentatives des besoins applicatifs, afin d’améliorer l'efficacité de certaines requêtes. Notre idée clé consiste à emprunter l'approche déclarative développée pour la conception de bases de données à partir de contraintes et d'étendre les dépendances fonctionnelles avec des composantes spatiales et temporelles afin de revoir le processus classique de normalisation de schéma de base de données. Étant donné des flux de données capteurs, nous considérons à la fois les hiérarchies de granularités spatio-temporelles et les Dépendances Fonctionnelles SpatioTemporelles (DFSTs) comme objets de premier ordre pour concevoir des bases de données de capteurs compatibles avec n'importe quel SGBDR. Nous avons implémenté un prototype de cette architecture qui traite à la fois la conception de la base de données ainsi que le chargement des données. Nous avons mené des expériences avec des flux de donnés synthétiques et réels provenant de bâtiments intelligents. Nous avons comparé notre solution avec la solution de base et nous avons obtenu des résultats prometteurs en termes de performance de requêtes et d'utilisation de la mémoire. Nous avons également étudié le compromis entre la réduction des données et l'approximation des données<br>Nowadays, sensors are cheap, easy to deploy and immediate to integrate into applications. These thousands of sensors are increasingly invasive and are constantly generating enormous amounts of data that must be stored and managed for the proper functioning of the applications depending on them. Sensor data, in addition of being of major interest in real-time applications, e.g. building control, health supervision..., are also important for long-term reporting applications, e.g. reporting, statistics, research data... Whenever a sensor produces data, two dimensions are of particular interest: the temporal dimension to stamp the produced value at a particular time and the spatial dimension to identify the location of the sensor. Both dimensions have different granularities that can be organized into hierarchies specific to the concerned context application. In this PhD thesis, we focus on applications that require long-term storage of sensor data issued from sensor data streams. Since huge amount of sensor data can be generated, our main goal is to select only relevant data to be saved for further usage, in particular long-term query facilities. More precisely, our aim is to develop an approach that controls the storage of sensor data by keeping only the data considered as relevant according to the spatial and temporal granularities representative of the application requirements. In such cases, approximating data in order to reduce the quantity of stored values enhances the efficiency of those queries. Our key idea is to borrow the declarative approach developed in the seventies for database design from constraints and to extend functional dependencies with spatial and temporal components in order to revisit the classical database schema normalization process. Given sensor data streams, we consider both spatio-temporal granularity hierarchies and Spatio-Temporal Functional Dependencies (STFDs) as first class-citizens for designing sensor databases on top of any RDBMS. We propose a specific axiomatisation of STFDs and the associated attribute closure algorithm, leading to a new normalization algorithm. We have implemented a prototype of this architecture to deal with both database design and data loading. We conducted experiments with synthetic and real-life data streams from intelligent buildings

The Basin of Mexico, where the Mexico City Metropolitan Zone (MCMZ) and its 20 million inhabitants are located, has had a two-sided approach towards water management, as it has struggled to drain the lakes that once covered this region while at the same time it started to transport in water from adjacent basins in the 1950s for water supply. In addition, the large amount of water extracted from the Basin's aquifer has caused drawdown of the groundwater table and consequently, land subsidence which reaches 40 cm/yr in some areas.The inhabitants of the Basin of Mexico, which comprises five different political entities and in which different agencies are in charge of water supply rely on the Basin's aquifer system as its main water supply source. After analyzing the existing water management policies in the Basin, this work suggests that in order to improve water management a regional groundwater flow model is needed. In order to develop this regional model, different tasks need to be fulfilled: a regional database is needed and regional estimates of aquifer recharge are also required. In order to develop a regional hydrogeological database in this area, the use of both a Relational Database Management System (RDBMS) and a Geographic Information System (GIS) is proposed in order to improve regional data management in the study area. Data stored in this new database, the Basin of Mexico Hydrogeological Database (BMHDB) comprises data on climatological, borehole and runoff variables, readily providing information for the development of hydrogeological models.This work presents a daily soil water balance which uses different vegetation and soil types as well as the effect of topography on climatological variables and evapotranspiration used to estimate recharge to the regional aquifer. Through the application of this model, it has been shown that the mountains that enclose the Basin of Mexico are the main recharge areas of the Basin's regional aquifer system. The spati<br>La gestion de l'eau dans le bassin de Mexico (où se trouve la zone métropolitaine de la ville de Mexico avec ses 20 millions d'habitants), a eu deux approches opposées: d'abord on a lutté pour vider les lacs qui couvraient cette région auparavant puis dans les années 50 on commencé a importer de l'eau d'autres bassins.De plus, les grandes quantités d'eau extraites de la couche aquifère du bassin ont causé l'abaissement du niveau de la table d'eaux souterraines et par conséquent, l'aisément du terrain jusqu'à 40 cm/année dans quelques secteurs.Les habitants du Bassin de Mexico, qui comprend 5 entités politiques et où plusieurs organismes sont chargés de la gestion de l'eau, obtiennent leur eau essentiellement de l'aquifère. Après analyse des politiques actuelles de gestion de l'eau du bassin, ce travail suggère qu'a fin d'améliorer cette gestion, un modèle régional d'écoulement d'eaux souterraines est nécessaire. A fin de développer ce modèle régional il faut: une base de données hydrogéologiques et des évaluations de la recharge de la couche aquifère. En ce qui concerne la base de données hydrogéologiques régionale, on propose l'utilisation d'une base de données relationnelle et d'un système d'information géographique, ceci a fin d'améliorer la gestion des données. Les données stockées dans cette nouvelle base de données: "Base de Données Hydrogéologiques du Bassin de Mexico" sont des variables climatologiques, de forage et d'écoulement, fournissant aisément des informations pour le développement des modèles hydrogéologiques.Ce travail présente un bilan quotidien de l'eau (qui considère différents types de végétation et de sol ainsi que l'effet de la topographie sur des variables climatologiques et sur l'evapotranspiration) lequel est employé pour estimer la recharge à la couche aquifère régionale. Par l'application de ce modèle, on a montré que les montagnes qui renferment le bassin du Mexique sont les

<p>We have discussed two related topics in this thesis: the design of location models and spatio-temporal databases for indoor positioning systems. We conclude our work with a short recapitulation of the main issues presented and a justification of the limitations, followed by suggestions for further research and our final thoughts. 8.1 Location Modeling Different aspects of location modeling were discussed, among them symbolic, geometric and hybrid location models. We found that only the hybrid form is suited for our purposes, that is to accurately position objects within a domain and relay this information to users in an understandable way. As a modeling technique, we proposed a solution using basic constructs of UML with added extensions. We created a domain model containing objects and relationships between them which we deem as relevant for indoor location aware systems, including the geometric extent of locations and transitions. 8.2 Spatio-Temporal Databases We defined spatio-temporal databases as databases which manage data on geometrical objects that change (movement is also considered as a form of change). Although research in this area has received much attention in the past decade, no functional spatio-temporal systems are available. Purely spatial database systems however are. We therefore proposed a solution based on timestamping spatial data, thus capturing its temporal aspects and in effect making it spatio-temporal. In order to create a conceptual model of such a database for indoor location aware applications, we used our own domain model for location modeling and proposed extensions to it in order to capture specific spatial, temporal and spatio-temporal aspects. We used the conceptual model to create a prototype database, demonstrating the concepts proposed by us.</p>

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.<br>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.

Both the current trends in technology such as smart phones, general mobile devices, stationary sensors and satellites as well as a new user mentality of utilizing this technology to voluntarily share information produce a huge flood of geo-spatial and geo-spatio-temporal data. This data flood provides a tremendous potential of discovering new and possibly useful knowledge. In addition to the fact that measurements are imprecise, due to the physical limitation of the devices, some form of interpolation is needed in-between discrete time instances. From a complementary perspective - to reduce the communication and bandwidth utilization, along with the storage requirements, often the data is subjected to a reduction, thereby eliminating some of the known/recorded values. These issues introduce the notion of uncertainty in the context of spatio-temporal data management - an aspect raising an imminent need for scalable and flexible data management. The main scope of this thesis is to develop effective and efficient techniques for similarity search and data mining in uncertain spatial and spatio-temporal data. In a plethora of research fields and industrial applications, these techniques can substantially improve decision making, minimize risk and unearth valuable insights that would otherwise remain hidden. The challenge of effectiveness in uncertain data is to correctly determine the set of possible results, each associated with the correct probability of being a result, in order to give a user a confidence about the returned results. The contrary challenge of efficiency, is to compute these result and corresponding probabilities in an efficient manner, allowing for reasonable querying and mining times, even for large uncertain databases. The paradigm used to master both challenges, is to identify a small set of equivalent classes of possible worlds, such that members of the same class can be treated as equivalent in the context of a given query predicate or data mining task. In the scope of this work, this paradigm will be formally defined, and applied to the most prominent classes of spatial queries on uncertain data, including range queries, k-nearest neighbor queries, ranking queries and reverse k-nearest neighbor queries. For this purpose, new spatial and probabilistic pruning approaches are developed to further speed up query processing. Furthermore, the proposed paradigm allows to develop the first efficient solution for the problem of frequent co-location mining on uncertain data. Special emphasis is taken on the temporal aspect of applications using modern data collection technologies. While the aforementioned techniques work well for single points of time, the prediction of query results over time remains a challenge. This thesis fills this gap by modeling an uncertain spatio-temporal object as a stochastic process, and by applying the above paradigm to efficiently query, index and mine historical spatio-temporal data.<br>Moderne Technologien, z.B. Sattelitentechnologie und Technologie in Smart Phones, erzeugen eine Flut räumlicher Geo-Daten. Zudem ist in der Gesellschaft ein Trend zu beobachten diese erzeugten Daten freiwillig auf öffentlich zugänglichen Plattformen zur Verfügung zu stellen. Diese Datenflut hat immenses Potential, um neues und nützliches Wissen zu entdecken. Diese Daten sind jedoch grundsätzlich unsichere räumliche Daten. Die Unsicherheit ergibt sich aus mehreren Aspekten. Zum einen kommt es bei Messungen grundsätzlich zu Messungenauigkeiten, zum anderen ist zwischen diskreten Messzeitpunkten eine Interpolation nötig, die zusätzliche Unsicherheit erzeugt. Auerdem werden die Daten oft absichtlich reduziert, um Speicherplatz und Transfervolumen einzusparen, wodurch weitere Information verloren geht. Diese Unsicherheit schafft einen sofortigen Bedarf für skalierbare und flexible Methoden zur Verwaltung und Auswertung solcher Daten. Im Rahmen dieser Arbeit sollen effektive und effiziente Techniken zur Ähnlichkeitssuche und zum Data Mining bei unsicheren räumlichen und unsicheren räumlich-zeitlichen Daten erarbeitet werden. Diese Techniken liefern wertvolles Wissen, das auf verschiedenen Forschungsgebieten, als auch bei industriellen Anwendungen zur Entscheidungsfindung genutzt werden kann. Bei der Entwicklung dieser Techniken gibt es zwei Herausforderungen. Einerseits müssen die entwickelten Techniken effektiv sein, um korrekte Ergebnisse und Wahrscheinlichkeiten dieser Ergebnisse zurückzugeben. Andererseits müssen die entwickelten Techniken effizient sein, um auch in sehr großen Datenbanken Ergebnisse in annehmbarer Zeit zu liefern. Die Dissertation stellt ein neues Paradigma vor, das beide Herausforderungen meistert. Dieses Paradigma identifiziert mögliche Datenbankwelten, die bezüglich des gegebenen Anfrageprädikats äquivalent sind. Es wird formal definiert und auf die relevantesten räumlichen Anfragetypen angewendet, um effiziente Lösungen zu entwickeln. Dazu gehören Bereichanfragen, k-Nächste-Nachbarnanfragen, Rankinganfragen und Reverse k-Nächste-Nachbarnanfragen. Räumliche und probabilistische Pruningkriterien werden entwickelt, um insignifikante Ergebnisse früh auszuschlieen. Zudem wird die erste effiziente Lösung für das Problem des "Spatial Co-location Minings" auf unsicheren Daten präsentiert. Ein besonderer Schwerpunkt dieser Arbeit liegt auf dem temporalen Aspekt moderner Geo-Daten. Während obig genannte Techniken dieser Arbeit für einzelne Zeitpunkt sehr gut funktionieren, ist die effektive und effiziente Verwaltung von unsicheren räumlich zeitlichen Daten immer noch ein weitestgehend ungelöstes Problem. Diese Dissertation löst dieses Problem, indem unsichere räumlich-zeitliche Daten durch stochastische Prozesse modeliert werden. Auf diese stochastischen Prozesse lässt sich das oben genannte Paradigma anwenden, um unsichere räumlich-zeitliche Daten effizient anzufragen, zu indexieren, und zu minen.

The dissertation will outline an object-oriented model from which a next-generation GIS can be derived. The requirements for a spatial information analysis and modeling system can be broken into three primary functional classes: data management (data classification and access), analysis (modeling, optimization, and simulation) and visualization (display of data). These three functional classes can be considered as the primary colors of the spectrum from which the different shades of spatial analysis are composed. Object classes will be developed which will be designed to manipulate the three primary functions as required by the user and the data.

2010 - 2011<br>Intelligent Transportatin Systems have gained a great importance in the last decades given the growing need for security in many public environments, with particular attention for traffic scenarios, which are daily interested by accidents, traffic queues, highway code violations, driving in the wrong lane or on the wrong side, and so on. In the context of camera-based traffic analysis systems, in this thesis I will present a novel indexing scheme for the design of a system for the extraction, the storage and retrieval of moving objects' trajectories from surveillance cameras... [edited by author]<br>X n.s.

In this thesis a natural language query interface is developed for semantic and spatio-temporal querying of MPEG-7 based domain ontologies. The underlying ontology is created by attaching domain ontologies to the core Rhizomik MPEG-7 ontology. The user can pose concept, complex concept (objects connected with an &ldquo<br>AND&rdquo<br>or &ldquo<br>OR&rdquo<br>connector), spatial (left, right . . . ), temporal (before, after, at least 10 minutes before, 5 minutes after . . . ), object trajectory and directional trajectory (east, west, southeast . . . , left, right, upwards . . . ) queries to the system. Furthermore, the system handles the negative meaning in the user input. When the user enters a natural language (NL) input, it is parsed with the link parser. According to query type, the objects, attributes, spatial relation, temporal relation, trajectory relation, time filter and time information are extracted from the parser output by using predefined rules. After the information extraction, SPARQL queries are generated, and executed against the ontology by using an RDF API. Results are retrieved and they are used to calculate spatial, temporal, and trajectory relations between objects. The results satisfying the required relations are displayed in a tabular format and user can navigate through the multimedia content.

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<br>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

Cette thèse propose une infrastructure pour la spécification de gestionnaires de présentations multimédias spatio-temporelles (JAGUAR). Un gestionnaire assure la définition, le stockage, l'interrogation et la mise en forme des présentations qui sont stockées dans un système de gestion de bases de données multimédias. Les gestionnaires spécifiés servent de médiateurs entre des applications multimédias et des sources hétérogènes d'objets réparties et accessibles au travers du Web (via leur URL). Les objets gérés par un gestionnaire pour un ensemble d'applications sont décrits par un schéma de données qui associe à chaque type une présentation par défaut. Ainsi ce schéma définit la manière dont les objets sont vus par les applications. Un modèle spatio-temporel a été défini pour traiter de manière homogène les objets intégrés dans les présentations. Ce modèle permet également de décrire un objet composé en mettant en évidence les relations spatio-temporelles entre ses composants. Nous proposons également le langage OQLiST qui intègre des opérateurs spatiaux et temporels pour la spécification et l'interrogation de présentations. Ainsi, le langage et le modèle permettent de spécifier, d'interroger et de représenter de manière homogène les descriptions inter et intra-médias. Un prototype de gestionnaire a été implanté pour valider l'infrastructure JAGUAR. Il a été adapté à la construction d'applications sur des plates-formes SMIL et Java Media Framework (JMF). Ce gestionnaire a été utilisé pour la spécification et la mise en œuvre d'une application touristique. Il a également été employé pour spécifier un outil de visualisation d'objets stockés dans un entrepôt de données<br>We propose an infrastructure (JAGUAR) for specifying spatio-temporal multimedia presentations managers. These managers are mediators between applications and distributed heterogeneous object sources accessible through the Web (via their URL). A manager is able to define, query, and build presentations that are stored in a multimedia database system. All objects are described by a schema that associates a default presentation to each of them. We defined a spatio-temporal model to integrate objects and presentations. The model describes objects composition through spatio-temporal relations. We also proposed OQLiST a language that provides spatio-temporal operators. Language and model can be used for specifying, querying and representing homogeneously inter and intra-media descriptions. In order to validate the JAGUAR infrastructure, a presentation manager prototype was implemented using SMIL and Java Media Framework (JMF) platforms. The manager has been used for specifying and implementing (1) a touristic application and (2) a visualization tool for objects stored in a data warehouse. For the later, the manager provides a specific schema for the data cube

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)<br>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)<br>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)<br>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<br>Não recebi financiamento<br>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.<br>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.

The video databases and retrieval of data from these databases have become popular in various business areas of work with the improvements in technology. As a kind of video database, video archive systems need user-friendly interfaces to retrieve video frames. In this thesis, an NLP based user interface to a video database system is developed using a content-based spatio-temporal video data model. The data model is focused on the semantic content which includes objects, activities, and spatial properties of objects. Spatio-temporal relationships between video objects and also trajectories of moving objects can be queried with this data model. In this video database system, NL interface enables flexible querying. The queries, which are given as English sentences, are parsed using Link Parser. Not only exact matches but similar objects and activities are also returned from the database with the help of the conceptual ontology module to return all related frames to the user. This module is implemented using a distance-based method of semantic similarity search on the semantic domain-independent ontology, WordNet. The semantic representations of the given queries are extracted from their syntactic structures using information extraction techniques. The extracted semantic representations are used to call the related parts of the underlying spatio-temporal video data model to calculate the results of the queries.

L'introduction du temps dans les bases de données classiques et spatiales apparaît de plus en plus, aujourd'hui, comme une nécessité pour une gestion optimale de l'historicité. En effet, les applications de bases de données spatio-temporelles sont présentes dans un grand nombre d'applications. Le besoin, par exemple, est de sauvegarder l'historique des géométries des parcelles dans le système d'information d'un plan cadastral, la prévention d'incendie dans le système de gestion forestière, le système de navigation des véhicules, etc. Cet historique des phénomènes permet de mieux comprendre ce qui s'est produit dans le passé, de manière à éventuellement anticiper certaines évolutions futures.<p><p>Etant donné ces nouveaux besoins, cette thèse se focalise sur la modélisation et l'implantation des aspects temporels dans bases de données. En effet, la conception d'une application de base de données se fait par un enchaînement de trois phases (conceptuelle, logique et physique). Au niveau conceptuel, plusieurs modèles conceptuels ont été proposés intégrant les caractéristiques temporelles et spatiales.<p><p>Malheureusement, au niveau logique, les modèles de données des SGBD actuels n'offrent pas les concepts nécessaires pour implanter le modèle conceptuel spatio-temporel. Nous proposons donc de nouvelles règles de traductions d'un schéma conceptuel, basé sur le modèle MADS (Modélisation des Applications à des données spatio-temporelles), en un schéma logique MADSLog pour les modèles cibles à savoir :relationnel et relationnel-objet. Chaque règle transforme un concept structurel, temporel et spatial du modèle MADS en un ou plusieurs concepts supportés par la cible. Par exemple, la propriété spatiale définissant la géométrie d'un type d'objet est traduite par la création d'un nouvel attribut de type spatial dans ce type d'objet. Un outil CASE(Computer-Aided Software Engineering) appelé Schema Translateur est développé dans cette thèse implémentant toutes les règles de traductions.<p><p>La traduction de schémas conceptuels en schémas logiques peut impliquer une perte sémantique en raison de la différence de la puissance d'expression entre le modèle conceptuel et le modèle de données des SGBD existants. D'où la nécessité de générer un ensemble de contraintes d'intégrité afin de préserver la sémantique définie dans le schéma conceptuel. Ces contraintes sont exprimées à ce niveau par des formules logiques.<p><p>Avec l'apparition de GML (Geographic Markup Language ) qui est conçu pour la modélisation, le transport et le stockage d'informations géographiques. Nous transformons également le schéma conceptuel MADS en GML. De nouveaux schémas GML temporel et spatial sont définis qui peuvent être employés par n'importe application de base de données spatio-temporelle.<p><p>Au niveau physique, nous proposons une méthode d'adaptation du schéma logique en schéma physique pour le modèle relationnel-objet.<p>Elle permet de définir les tables, les types abstraits, les types d'objets, les domaines, etc. Notre proposition permet aussi la génération des contraintes d'intégrité au niveau physique. En effet, chaque contrainte d'intégrité (structurelle, temporelle ou spatiale) qui est définie en calcul logique est exprimée soit directement par des contraintes déclaratives ou soit par des déclencheurs du SGBD choisi. Les déclencheurs spatiaux sont fondés sur les fonctionnalités prédéfinies dans Oracle, alors que les déclencheurs temporels sont basés sur les opérateurs et méthodes appliquées sur les types temporels.<p><p>Enfin, la traduction de requêtes est une deuxième clef de cette recherche. Le but de la traduction de requêtes, exprimées en algèbre, étant de reconstituer l'information au sens MADS à partir de la base de données stockées dans le SGDB cible. Elle permet de traduire les expressions algébriques MADS, qui sont définies sur le schéma conceptuel et non sur le schéma physique, en requêtes opérationnelles qui peuvent être exécutées sur une base de données spatiale et temporelle sous un SGBD ou un SIG.<p><br>Doctorat en sciences appliquées<br>info:eu-repo/semantics/nonPublished

This thesis deals with knowledge discovery in spatio-temporal data, which is currently a rapidly evolving area of research in information technology. First, it describes the general principles of knowledge discovery, then, after a brief introduction to mining in the temporal and spatial data, it focuses on the overview and description of existing methods for mining in spatio-temporal data. It focuses, in particular, on moving objects data in the form of trajectories with an emphasis on the methods for trajectory outlier detection. The next part of the thesis deals with the process of implementation of the trajectory outlier detection algorithm called TOP-EYE. In order to testing, validation and possibility of using this algorithm is designed and implemented an application for trajectory outlier detection. The algorithm is experimentally evaluated on two different data sets.

The resources required to acquire high quality scientific data in a marine environment can be great. The complication of acquiring data from a platform which pitches, rolls and heaves makes the challenge even greater. The variability of the weather and sea conditions, along with equipment failures, seemingly conspire against the marine scientist. There is a great need for good quality-control measures, accurate electronic record keeping, and effective voyage management at sea if a good outcome from an expensive sea voyage is to be expected. Typically, the plethora of navigation, data acquisition, quality control, Geographical Information Systems and databases used at sea on the world’s research vessels do not allow an intuitive, holistic, spatial and temporal view of real-time data. “How close are we to the ship track from our last visit to the region?” or “What was the deployment depth of the instrument when we were last at this site two years ago?” are typical questions asked by those undertaking research far from shore. Answering these questions like these, in a timely manner, using systems commonly used on research vessels can be difficult. This study explored the combination of an open-source spatio-temporal DataBase Management System (DBMS) and Keyhole Markup Language (KML), creating a framework for the storage and exploration of real-time spatio-temporal data at sea. The framework supported multiple concurrent users using Virtual Globe browsers. This study created a methodology, which resulted in a functional software tool, MARVIN, using open-source software. Empirical and modelled datasets were used in conjunction with MARVIN, both at sea and in the laboratory. MARVIN was found to be able to provide a simple and intuitive 4D (3D + time) real-time view of spatio-temporal datasets, as they were collected at sea. The key combination of a spatio-temporal DBMS and KML, offered a robust solution for the storage of real-time data, undertaking of Geographical Information System (GIS) operations, and streaming of data to multiple clients, running Virtual Globe browsers such as Google Earth. The techniques implemented also support existing navigation, GIS, and numeric modelling software commonly used on modern research vessels.

In molti campi di ricerca, i ricercatori hanno la necessità di memorizzare, gestire e interrogare dati spazio-temporali. Tali dati sono classici dati alfanumerici arricchiti però con una o più componenti temporali, spaziali e spazio-temporali che, con diversi possibili significati, li localizzano nel tempo e/o nello spazio. Ambiti in cui tali dati spazio-temporali devono essere raccolti e gestiti sono, per esempio, la gestione del territorio o delle risorse naturali, l'epidemiologia, l'archeologia e la geografia. Più in dettaglio, per esempio nelle ricerche epidemiologiche, i dati spazio-temporali possono servire a rappresentare diversi aspetti delle malattie e delle loro caratteristiche, quali per esempio la loro origine, espansione ed evoluzione e i fattori di rischio potenzialmente connessi alle malattie e al loro sviluppo. Le componenti spazio-temporali dei dati possono essere considerate come dei "meta-dati" che possono essere sfruttati per introdurre nuovi tipi di analisi sui dati stessi. La gestione di questi "meta-dati" può avvenire all'interno di diversi framework proposti in letteratura. Uno dei concetti proposti a tal fine è quello delle granularità. In letteratura c'è ampio consenso sul concetto di granularità temporale, di cui esistono framework basati su diversi approcci. D'altro canto, non esiste invece un consenso generale sulla definizione di un framework completo, come quello delle granularità temporali, per le granularità spaziali e spazio-temporali. Questa tesi ha lo scopo di riempire questo vuoto proponendo un framework per le granularità spaziali e, basandosi su questo e su quello già presente in letteratura per le granularità temporali, un framework per le granularità spazio-temporali. I framework proposti vogliono essere completi, per questo, oltre alle definizioni dei concetti di granularità spaziale e spazio-temporale, includono anche la definizione di diversi concetti legati alle granularità, quali per esempio le relazioni e le operazioni tra granularità. Le relazioni permettono di conoscere come granularità diverse sono legate tra loro, costruendone anche una gerarchia. Tali informazioni sono poi utili al fine di conoscere se e come è possibile confrontare dati associati e rappresentati con granularità diverse. Le operazioni permettono invece di creare nuove granularità a partire da altre granularità già definite nel sistema, manipolando o selezionando alcune loro componenti. Basandosi su questi framework, l'obiettivo della tesi si sposta poi sul mostrare come le granularità possano essere utilizzate per arricchire basi di dati spazio-temporali già esistenti al fine di una loro migliore e più ricca gestione e interrogazione. A tal fine, proponiamo qui una base di dati per la gestione dei dati riguardanti le granularità temporali, spaziali e spazio-temporali. Nella base di dati proposta possono essere rappresentate tutte le componenti di una granularità come definito nei framework proposti. La base di dati può poi essere utilizzata per estendere una base di dati spazio-temporale esistente aggiungendo alle tuple di quest'ultima delle referenze alle granularità dove quei dati possono essere localizzati nel tempo e/o nel spazio. Per dimostrare come ciò possa essere fatto, nella tesi introduciamo la base di dati sviluppata ed utilizzata dal Servizio Psichiatrico Territoriale (SPT) di Verona. Tale base di dati memorizza le informazioni su tutti i pazienti venuti in contatto con l'SPT negli ultimi 30 anni e tutte le informazioni sui loro contatti con il servizio stesso (per esempio: chiamate telefoniche, visite a domicilio, ricoveri). Parte di tali informazioni hanno una componente spazio-temporale e possono essere quindi analizzate studiandone trend e pattern nel tempo e nello spazio. Nella tesi quindi estendiamo questa base di dati psichiatrica collegandola a quella proposta per la gestione delle granularità. A questo punto i dati psichiatrici possono essere interrogati anche sulla base di vincoli spazio-temporali basati su granularità. L'interrogazione di dati spazio-temporali associati a granularità richiede l'utilizzo di un linguaggio d'interrogazione che includa, oltre a strutture, operatori e funzioni spazio-temporali per la gestione delle componenti spazio-temporali dei dati, anche costrutti per l'utilizzo delle granularità nelle interrogazioni. Quindi, partendo da un linguaggio d'interrogazione spazio-temporale già presente in letteratura, in questa tesi proponiamo anche un linguaggio d'interrogazione che permetta ad un utente di recuperare dati da una base di dati spazio-temporale anche sulla base di vincoli basati su granularità. Il linguaggio viene introdotto fornendone la sintassi e la semantica. Inoltre per mostrare l'effettivo ruolo delle granularità nell'interrogazione di una base di dati clinica, mostreremo diversi esempi di interrogazioni, scritte con il linguaggio d'interrogazione proposto, sulla base di dati psichiatrica dell'SPT di Verona. Tali interrogazioni spazio-temporali basate su granularità possono essere utili ai ricercatori ai fini di analisi epidemiologiche dei dati psichiatrici.<br>In several research fields, temporal, spatial, and spatio-temporal data have to be managed and queried with several purposes. These data are usually composed by classical data enriched with a temporal and/or a spatial qualification. For instance, in epidemiology spatio-temporal data may represent surveillance data, origins of disease and outbreaks, and risk factors. In order to better exploit the time and spatial dimensions, spatio-temporal data could be managed considering their spatio-temporal dimensions as meta-data useful to retrieve information. One way to manage spatio-temporal dimensions is by using spatio-temporal granularities. This dissertation aims to show how this is possible, in particular for epidemiological spatio-temporal data. For this purpose, in this thesis we propose a framework for the definition of spatio-temporal granularities (i.e., partitions of a spatio-temporal dimension) with the aim to improve the management and querying of spatio-temporal data. The framework includes the theoretical definitions of spatial and spatio-temporal granularities (while for temporal granularities we refer to the framework proposed by Bettini et al.) and all related notions useful for their management, e.g., relationships and operations over granularities. Relationships are useful for relating granularities and then knowing how data associated with different granularities can be compared. Operations allow one to create new granularities from already defined ones, manipulating or selecting their components. We show how granularities can be represented in a database and can be used to enrich an existing spatio-temporal database. For this purpose, we conceptually and logically design a relational database for temporal, spatial, and spatio-temporal granularities. The database stores all data about granularities and their related information we defined in the theoretical framework. This database can be used for enriching other spatio-temporal databases with spatio-temporal granularities. We introduce the spatio-temporal psychiatric case register, developed by the Verona Community-based Psychiatric Service (CPS), for storing and managing information about psychiatric patient, their personal information, and their contacts with the CPS occurred in last 30 years. The case register includes both clinical and statistical information about contacts, that are also temporally and spatially qualified. We show how the case register database can be enriched with spatio-temporal granularities both extending its structure and introducing a spatio-temporal query language dealing with spatio-temporal data and spatio-temporal granularities. Thus, we propose a new spatio-temporal query language, by defining its syntax and semantics, that includes ad-hoc features and constructs for dealing with spatio-temporal granularities. Finally, using the proposed query language, we report several examples of spatio-temporal queries on the psychiatric case register showing the ``usage'' of granularities and their role in spatio-temporal queries useful for epidemiological studies.

碩士<br>國立臺灣大學<br>資訊管理研究所<br>89<br>The knowledge structure, called 2D C+-string, to represent the spatial relations between the objects in an image was proposed by P.W. Huang et al. It allows us to represent spatial knowledge in images. The knowledge structure, called 3D string, to represent the spatial and temporal relations between the objects in a video was proposed by A.L.P. Chen et al. In the 3D string representation, an object is represented by its central point and starting frame number. So, they cannot deal with the overlapping relation in spatial and temporal dimensions and with the information of motions and size changes. In this thesis, we propose a new spatio-temporal knowledge representation called 3D C-string. 3D C-string can overcome the weakness of 3D string. The knowledge structure of 3D C-string, based on the concepts of 2D C+-string, uses the projections of video objects to represent spatial and temporal relations between the objects in a video. Moreover, 3D C-string can keep track of the motions and size changes of the objects in a video. This approach can provide us an easy and efficient way to retrieve, visualize and manipulate video objects in video database systems. The string generation and video reconstruction algorithms for the 3D C-string representation of video objects are also developed. By introducing the concept of the template objects and nearest former objects. The string generated by the string generation algorithm is unique and the symbolic video reconstructed from a given 3D C-string is unique, too. In comparison with the spatial relation inference and similarity retrieval in image database systems, the counterparts in video database systems are a fuzzier concept. Therefore, we extend the idea behind the relation inference and similarity retrieval of images in 2D C+-string to 3D C-string. We also define the similarity measures and propose a similarity retrieval algorithm. Finally, some experiments are performed to show the efficiency and effectiveness of the proposed algorithm.

The goal of this master thesis is to suggest a methodology for a visualization history of changes in cadastral maps. The suggested methodology takes into account a selection of original historical and contemporary data, processing workflow and follow-up visualization using existing open source web technologies. The greatest contribution of this thesis is in the design of the spatio-temporal database, because currently there does not exist workable editor similar to it, which could be used for creating such data. The suggested procedure is based on database updating method of ISKN database utilizing amendment records. However this method is significantly simplified with the use of PostgreSQL/PostGIS geospatial functions. The available literature and other informational sources to the topic are overviewed in the first part of the master thesis. The term "spatio-temporal data" is thoroughly defined and also the ways of integrating temporal features into spatial data, methods of visualization of spatio-temporal data and recent state of their implementations into desktop platforms and web applications are noted. Furthermore historical and current data sources and their usability for the master thesis are described. The full methodology of pre-processing and processing of data and a subsequent visualization using...

博士<br>國立成功大學<br>資訊工程學系碩博士班<br>97<br>Spatio-temporal databases aim at combining the spatial and temporal characteristics of data. Spatio-temporal queries have been used in many applications such as mobile communication systems, traffic control systems, geographical information systems, location-aware advertisement, and multimedia applications. Continuous Range (CR) query and Continuous K-Nearest Neighbor (CKNN) query are two important and widely used spatio-temporal queries.A CR query is to find the moving objects whose Euclidean distances to the moving query object are within a distance at each time instant within a time interval [ts, te]. As for the CKNN query, it can be utilized to retrieve the query object's K-Nearest Neighbors (KNNs) at each time instant within [ts, te]. The context of this dissertation is categorized into two parts according to whether objects are moving in Euclidean space or road networks. In the first part, we investigate how to efficiently process these spatio-temporal queries over moving objects in Euclidean space (that is, the results are determined based on the Euclidean distance between each moving object and the query object). Existing methods for processing spatio-temporal queries, however, assume that each object moves with a fixed velocity (speed and direction). Different from the existing methods, we relieve this assumption by allowing the velocity of each object to be uncertain. This uncertainty on the velocity of object inevitably results in high complexity in processing spatio-temporal queries. We will discuss the complications incurred by this uncertainty and propose several efficient methods to answer the spatio-temporal queries over moving objects with uncertainty. Our performance results demonstrate the effectiveness and the efficiency of the proposed approaches. In the second part of this dissertation, we focus our attention on processing the spatio-temporal queries over moving objects in road networks. As the movements of objects are constrained to a road network, the distance between two objects should be computed based on the connectivity of the road network rather than the two objects' locations. We first highlight the limitations of the existing apporaches for processing the spatio-temporal queries in road networks, and then propose a cost-effective method to overcome these limitations. By using the proposed method, we can determine the result set of spatio-temporal queries under the following three conditions: (1) All objects (including the query object) move continuously in a road network. (2) The distance between two objects is defined as the distance along the shortest path between them in the network. (3) The result set of the query object at each timestamp should be completely determined. Comprehensive experiments are performed to investigate the efficiency of this method.

碩士<br>國立臺灣大學<br>資訊管理研究所<br>91<br>Usually a video consists of a number of frames and each frame may contain several objects. The changes of video objects in spatial and temporal dimension are quite useful to measure two videos. In this thesis, we propose a new method to measure the similarity (dissimilarity) between two videos by spatio-temporal relationships between objects. The new method basically includes two phases. One is to split a video into several intervals of video and make use of the finding maximal similar object-set algorithm to compute the maximal similar object-sets as the similarity norm between any two intervals. The other is to utilize the maximal similar object-sets between intervals obtained from the first phase to compute maximal similar object-sets between videos in the dynamic programming approach. We propose continuous and discontinuous intervals matching algorithm for this part. Some experiments are performed to show the efficiency and effectiveness of our proposed algorithm.

博士<br>國立中山大學<br>資訊工程學系研究所<br>99<br>With the large number of spatial queries for spatial data objects changing with time in many applications, e.g., the location based services and geographic information systems, spatio-temporal databases have been developed to manipulate them in spatial or temporal databases. We focus on queries for stationary and moving objects in the spatial database in the present. However, there is no total ordering for the large volume and complicated objects which may change their geometries with time. A spatial access method based on the spatial index structure attempts to preserve the spatial proximity as much as possible. Then, the number of disk access which takes the response time is reduced during the query processing. Therefore, in this dissertation, based on the NA-tree, first, we propose the NA-tree join method over the stationary objects. Our NA-tree join simply uses the correlation table to directly obtain candidate leaf nodes based on two NA-trees which have non-empty overlaps. Moreover, our NA-tree join accesses objects once from those candidate leaf nodes and returns pairs of objects which have non-empty overlaps. Second, we propose the NABP method for the continuous range queries over the moving objects. Our NABP method uses the bit-patterns of regions in the NA-tree to check the relation between the range queries and moving objects. Our NABP method searches only one path in the NA-tree for the range query, instead of more than one path in the R*-tree-based method which has the overlapping problem. When the number of range queries increases with time, our NABP method incrementally updates the affected range queries by bit-patterns checking, instead of rebuilding the index like the cell-based method. From the experimental results, we have shown that our NABP method needs less time than the cell-based method for range queries update and less time than the R*-tree-based method for moving objects update. Based on the Hilbert curve with the good clustering property, we propose the ANHC method to answer the all-nearest-neighbors query by our ONHC method. Our ONHC method is used to answer the one-nearest-neighbor query over the stationary objects. We generate direction sequences to store the orientations of the query block in the Hilbert curve of different orders. By using quaternary numbers and direction sequences of the query block, we obtain the relative locations of the neighboring blocks and compute their quaternary numbers. Then, we directly access the neighboring blocks by their sequence numbers which is the transformation of the quaternary numbers from base four to ten. The nearest neighbor can be obtained by distance comparisons in these blocks. From the experimental results, we have shown that our ONHC and ANHC methods need less time than CCSF method for the one-nearest-neighbor query and the method based on R*-trees for the all-nearest-neighbors query, respectively.

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.

Dissertação de mestrado integrado em Engenharia de Comunicações<br>A grande evolução tecnológica tanto dos Sistemas de Informação Geográfica (SIG) bem como das tecnologias de localização (GPS, WI-FI, RFID) contribuíram para um significativo aumento da recolha de dados espaciais. Devido a esta proliferação e às grandes quantidades de dados que são recolhidos, são necessárias bases de dados e mecanismos apropriados para o seu armazenamento e sua respectiva análise. No passado, o desenho de sistemas de informação para objectos móveis basearam-se muitas vezes em abordagens (aplicações) restritas a tecnologias de localização específicas, levando a um vasto leque de modelos de dados, modelos de base de dados e respectivas funcionalidades. Para superar esta proliferação de modelos, este projecto propõe um sistema de informação espaço-temporal independente do domínio de aplicação, e com o intuito de se abstrair da tecnologia de posicionamento utilizada para a recolha de dados. Este sistema de informação espaço-temporal visa o desenvolvimento de um sistema de armazenamento, análise e visualização de dados sobre objectos móveis capazes de representar e armazenar dados com características espaciais e de realizar análises sobre os mesmos. Este sistema é intitulado STAR e integra três componentes principais, as bases de dados espaçotemporais, os SIG e os dados espaço-temporais. A base de dados espaço-temporal desenhada permite o armazenamento dos dados espaço-temporais bem como o armazenamento da geometria do espaço no qual ocorre o movimento. Esta geometria é representada por pontos, linhas e/ou polígonos. Os SIG auxiliam os processos de análise e visualizações de dados. Os dados espaço-temporais são intitulados neste projecto de objectos móveis, podendo o movimento dos mesmos ser analisado no STAR. Os resultados alcançados são promissores na demonstração de como o sistema é capaz de armazenar dados de posicionamento com formatos diferentes, e na aplicação de análises, visualizações e representações sobre os mesmos.<br>The huge technological evolution of both the Geographic Information Systems (GIS) as well as location technologies (GPS, Wi-Fi, RFID) contributes to a large increase in spatial data collection. Because of this proliferation and to the large amounts of data that are collected, databases and appropriate mechanisms for their storage and their analysis are necessary. In the past, the design of information systems for moving objects was often based on approaches (applications) restricted to specific location technologies, leading to a wide range of data models, database models and functionalities. To overcome this proliferation of models, this project proposes a spatio-temporal information system that is independent of the application domain and that abstract the positioning technology used for data collection. This spatio-temporal information system aims the development of a storage system with data analysis and visualization mechanism for moving objects that can represent and store data with spatial characteristics and perform spatial analysis on them. This system is named STAR and incorporates three main components, spatio-temporal databases, GIS and spatio-temporal data. The designed spatio-temporal database enables the storage of the spatio-temporal data and the geometry of the space in which the movement occurs. This geometry is represented by points, lines and/or polygons. The GIS help the processes of analysis and visualization of data. The spatio-temporal data in this project are entitled to moving objects, their movement can be analysed in STAR. The results obtained so far are promising in demonstrating how the system is capable of storing positioning data with different formats, and in applying analysis, visualizations and different representations of the analysed data.