abstract: In today's world, unprecedented amounts of data of individual mobile objects have become more available due to advances in location aware technologies and services. Studying the spatio-temporal patterns, processes, and behavior of mobile objects is an important issue for extracting useful information and knowledge about mobile phenomena. Potential applications across a wide range of fields include urban and transportation planning, Location-Based Services, and logistics. This research is designed to contribute to the existing state-of-the-art in tracking and modeling mobile objects, specifically targeting three challenges in investigating spatio-temporal patterns and processes; 1) a lack of space-time analysis tools; 2) a lack of studies about empirical data analysis and context awareness of mobile objects; and 3) a lack of studies about how to evaluate and test agent-based models of complex mobile phenomena. Three studies are proposed to investigate these challenges; the first study develops an integrated data analysis toolkit for exploration of spatio-temporal patterns and processes of mobile objects; the second study investigates two movement behaviors, 1) theoretical random walks and 2) human movements in urban space collected by GPS; and, the third study contributes to the research challenge of evaluating the form and fit of Agent-Based Models of human movement in urban space. The main contribution of this work is the conceptualization and implementation of a Geographic Knowledge Discovery approach for extracting high-level knowledge from low-level datasets about mobile objects. This allows better understanding of space-time patterns and processes of mobile objects by revealing their complex movement behaviors, interactions, and collective behaviors. In detail, this research proposes a novel analytical framework that integrates time geography, trajectory data mining, and 3D volume visualization. In addition, a toolkit that utilizes the framework is developed and used for investigating theoretical and empirical datasets about mobile objects. The results showed that the framework and the toolkit demonstrate a great capability to identify and visualize clusters of various movement behaviors in space and time. / Dissertation/Thesis / Ph.D. Geography 2011

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

Les relations spatiales entre les différentes régions dans une image sont utiles pour la compréhension et l'interprétation de la scène représentée. L'analyse Spatio-temporelle d'une scène implique l'intégration du temps dans des relations spatiales entre les objets en mouvement. Les relations spatio-temporelles sont définies dans un intervalle de temps utilisant la géométrie 3D ou l'extension de la géométrie 2D à la dimension temporelle. La modélisation des relations spatiales dynamiques prend en compte la position relative des objets et leurs relations directionnelles, ceci implique les relations topologiques, directionnelles et de distance. Ces relations sont étendues au domaine temporel. Dans notre travail, on décrit une méthode de combinaison d’information topologique et directionnelle où les relations d'Allen floues 1D sont appliquées au domaine spatial. La méthode proposée intègre le flou au niveau des relations. La méthode très gourmande initialement en temps de calcul en raison de l’approximation des objets ainsi qu'à l'algorithme de fuzzification des segments des sections longitudinales est améliorée en utilisant une approximation polygonale adaptée sur les objets considérés. L'algorithme du fuzzification des segments d'une section longitudinale inclut des opérateurs d'agrégation floue. Dans la méthode proposée, Les relations topologiques 2Dsont représentées par un histogramme. Les relations floues n'étant pas exhaustives, un algorithme de défuzzification des relations spatiales a été proposé pour réaliser un ensemble JEPD de relations spatiales. Cet ensemble de relations spatiales est représenté par un graphe de voisinage où chaque nœud du graphe représente la relation topologique et directionnelle. Cette méthode définit des relations spatio-temporelles en utilisant le modèle de données Espace-Temps. Un ensemble de relations spatio-temporelles est également fourni à l'aide de la stabilité topologique. Afin de valider le modèle, nous avons développé des applications fondées sur le raisonnement spatio-temporel proposé. Celui-ci a permit la création de tables de composition pour les relations spatiales topologiques structurées en sous-tables. Les entités de ces sous-tables sont liées les unes aux autres par des relations spatiales. Dans une seconde application, nous avons proposé une méthode de prédiction des évènements entre objets en mouvement fondée sur le même raisonnement spatio-temporel. Les objets en mouvement changeant de position à chaque instant, la prédiction de la nouvelle position spatiale d'un objet tient compte des états de relations spatiales calculées précédemment. / Spatial relations between different image regions are helpful in image understanding, interpretation and computer vision applications. Spatio-temporal analysis involves the integration of spatial relations changing over time between moving objects of a dynamic scene. Spatio-temporal relations are defined for a selected time interval using 3D geometry or extension of 2D object geometry to the time dimension with sequence occurrence of primitive events for each snapshot. Modeling dynamic spatial relations takes into account the relative object position and their directional relations; this involves the topological, directional and distance relations and their logical extension to the temporal domain. In this thesis, a method for combining topological and directional relations information is discussed where 1D temporal fuzzy Allen relations are applied in spatial domain. Initially, the method has a high computational cost. This computing cost is due to the object approximation and the fuzzification algorithm of segments. The computing time has been using polygonal object approximation. Fuzzification algorithm is replaced with fuzzy aggregation operators for segments of a longitudinal section. In this method, two dimensional topological relations are represented in a histogram. The representation method for two dimensional spatial relations has been changed. These fuzzy relations are not Jointly Exhaustive and Pairwise Disjoint (JEPD). An algorithm for defuzzification of spatial relations is proposed to realize JEPD set of spatial relations, these JEPD spatial relations are represented in a neighborhood graph. In this neighborhood graph, each node represents the topological and directional relation. This method is further extended for defining spatio-temporal relations using space and time data model, a set of spatio-temporal relations are also elaborated using the stability property in topology. In an application, a method for spatio-temporal reasoning based on this new model is developed. Spatio-temporal reasoning consists of developing the composition tables for spatial relations. Composition table for topological relations are rearranged into sub-tables. Entities in these sub-tables are related to each other and mathematical rules are defined for composition of spatial relations which elaborate the relation between entities of sub-tables. In another application, we propose a method for motion event predictions between moving objects. It is a similar process to the spatio-temporal reasoning. Dynamic objects occupy different places at different time points, these objects have multiple choices for subsequent positions and a unique history. Prediction about motion events take into account the history of a moving object and predict about the semantics of a motion event.

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.

A variety of research exists for the processing of continuous queries in large, mobile environments. Each method tries, in its own way, to address the computational bottleneck of constantly processing so many queries. For this research, we present a two-pronged approach at addressing this problem. Firstly, we introduce an efficient and scalable system for monitoring traditional, continuous queries by leveraging the parallel processing capability of the Graphics Processing Unit. We examine a naive CPU-based solution for continuous range-monitoring queries, and we then extend this system using the GPU. Additionally, with mobile communication devices becoming commodity, location-based services will become ubiquitous. To cope with the very high intensity of location-based queries, we propose a view oriented approach of the location database, thereby reducing computation costs by exploiting computation sharing amongst queries requiring the same view. Our studies show that by exploiting the parallel processing power of the GPU, we are able to significantly scale the number of mobile objects, while maintaining an acceptable level of performance. Our second approach was to view this research problem as one belonging to the domain of data streams. Several works have convincingly argued that the two research fields of spatiotemporal data streams and the management of moving objects can naturally come together. [IlMI10, ChFr03, MoXA04] For example, the output of a GPS receiver, monitoring the position of a mobile object, is viewed as a data stream of location updates. This data stream of location updates, along with those from the plausibly many other mobile objects, is received at a centralized server, which processes the streams upon arrival, effectively updating the answers to the currently active queries in real time. iv For this second approach, we present GEDS, a scalable, Graphics Processing Unit (GPU)-based framework for the evaluation of continuous spatio-temporal queries over spatiotemporal data streams. Specifically, GEDS employs the computation sharing and parallel processing paradigms to deliver scalability in the evaluation of continuous, spatio-temporal range queries and continuous, spatio-temporal kNN queries. The GEDS framework utilizes the parallel processing capability of the GPU, a stream processor by trade, to handle the computation required in this application. Experimental evaluation shows promising performance and shows the scalability and efficacy of GEDS in spatio-temporal data streaming environments. Additional performance studies demonstrate that, even in light of the costs associated with memory transfers, the parallel processing power provided by GEDS clearly counters and outweighs any associated costs. Finally, in an effort to move beyond the analysis of specific algorithms over the GEDS framework, we take a broader approach in our analysis of GPU computing. What algorithms are appropriate for the GPU? What types of applications can benefit from the parallel and stream processing power of the GPU? And can we identify a class of algorithms that are best suited for GPU computing? To answer these questions, we develop an abstract performance model, detailing the relationship between the CPU and the GPU. From this model, we are able to extrapolate a list of attributes common to successful GPU-based applications, thereby providing insight into which algorithms and applications are best suited for the GPU and also providing an estimated theoretical speedup for said GPU-based applications

This thesis aims to seek interesting patterns from massive amounts of Flickr data in Sweden with pro- posed new clustering strategies. The aim can be further divided into three objectives. The first one is to acquire large amount of timestamped geolocation data from Flickr servers. The second objective is to develop effective and efficient methods to process the data. More specifically, the methods to be developed are bifold, namely, the preprocessing method to solve the “Big Data” issue encountered in the study and the new clustering method to extract spatio-temporal patterns from data. The third one is to analyze the extracted patterns with scaling analysis techniques in order to interpret human social activities underlying the Flickr Data within the urban envrionment of Sweden. During the study, the three objectives were achieved sequentially. The data employed for this study was vector points downloaded through Flickr Application Programming Interface (API). After data ac- quisition, preprocessing was performed on the raw data. The whole dataset was firstly separated by year based on the temporal information. Then data of each year was accumulated with its former year(s) so that the evovling process can be explored. After that, large datasets were splitted into small pieces and each piece was clipped, georeferenced, and rectified respectively. Then the pieces were merged together for clustering. With respect to clustering, the strategy was developed based on the Delaunay Triangula- tion (DT) and head/tail break rule. After that, the generated clusters were analyzed with scaling analysis techniques and spatio-temporal patterns were interpreted from the analysis results. It has been found that the spatial pattern of the human social activities in the urban environment of Sweden generally follows the power-law distribution and the cities defined by human social activities are evolving as time goes by. To conclude, the contributions of this research are threefold and fulfill the objectives of this study, respectively. Firstly, large amount of Flickr data is acquired and collated as a contribution to other aca- demic researches related to Flickr. Secondly, the clustering strategy based on the DT and head/tail break rule is proposed for spatio-temporal pattern seeking. Thirdly, the evolving of the cities in terms of human activities in Sweden is detected from the perspective of scaling. Future work is expected in major two aspects, namely, data and data processing. For the data aspect, the downloaded Flickr data is expected to be employed by other studies, especially those closely related to human social activities within urban environment. For the processing aspect, new algorithms are expected to either accelerate the processing process or better fit machines with super computing capacities.

Doctor of Philosophy / Department of Statistics / Juan Du / Spatio-temporal and/or multivariate dependence naturally occur in datasets obtained in various disciplines; such as atmospheric sciences, meteorology, engineering and agriculture. There is a great deal of need to effectively model the complex dependence and correlated structure exhibited in these datasets. For this purpose, this dissertation studies methods and application of the spatio-temporal modeling and multivariate computation. First, a collection of spatio-temporal functions is proposed to model spatio-temporal processes which are continuous in space and discrete over time. Theoretically, we derived the necessary and sufficient conditions to ensure the model validity. On the other hand, the possibility of taking the advantage of well-established time series and spatial statistics tools makes it relatively easy to identify and fit the proposed model in practice. The spatio-temporal models with some ARMA discrete temporal margin are fitted to Kansas precipitation and Irish wind datasets for estimation or prediction, and compared with some general existing parametric models in terms of likelihood and mean squared prediction error. Second, to deal with the immense computational burden of statistical inference for multi- ple attributes recorded at a large number of locations, we develop Wendland-type compactly supported covariance matrix function models and propose multivariate covariance tapering technique with those functions for computation reduction. Simulation studies and US tem- perature data are used to illustrate applications of the proposed multivariate tapering and computational gain in spatial cokriging. Finally, to study the impact of weather change on corn yield in Kansas, we develop a spatial functional linear regression model accounting for the fact that weather data were recorded daily or hourly as opposed to the yearly crop yield data and the underlying spatial autocorrelation. The parameter function is estimated under the functional data analysis framework and its characteristics are investigated to show the influential factor and critical period of weather change dictating crop yield during the growing season.

Master of Science / Department of Electrical and Computer Engineering / William H. Hsu / Caterina M. Scoglio / Early detection of livestock diseases and development of cost optimal mitigation strategies are becoming a global necessity. Foot and Mouth Disease (FMD) is considered one of the most serious livestock diseases owing to its high rate of transmission and extreme economic consequences. Thus, it is imperative to improve parameterized mathematical models for predictive and preventive purposes. In this work, a meta-population based stochastic model is implemented to assess the FMD infection dynamics and to curb economic losses in countries with underdeveloped livestock disease surveillance databases. Our model predicts the spatio-temporal evolution of FMD over a weighted contact network where the weights are characterized by the effect of wind and movement of animals and humans. FMD incidence data from countries such as Turkey, Iran and Thailand are used to calibrate and validate our model, and the predictive performance of our model is compared with that of baseline models as well. Additionally, learning-based prediction models can be utilized to detect the time of onset of an epidemic outbreak. Such models are computationally simple and they may be trained to predict infection in the absence of background data representing the dynamics of disease transmission, which is otherwise necessary for predictions using spatio-temporal models. Thus, we comparatively study the predictive performance of our spatio-temporal against neural networks and autoregressive models. Also, Bayesian networks combined with Monte-Carlo simulations are used to determine the gold standard by approximation. Next, cost-effective mitigation strategies are simulated using the theoretical concept of infection network fragmentation. Based on the theoretical reduction in the total number of infected animals, several simulative mitigation strategies are proposed and their cost-effectiveness measures specified by the percentage reduction in the total number of infected animals per million US dollars, are also analyzed. We infer that the cost-effectiveness measures of mitigation strategies implemented using our spatio-temporal predictive model have a narrower range and higher granularity than those for mitigation strategies formulated using learning-based prediction models. Finally, we coin optimal mitigation strategies using Fuzzy Dominance Genetic Algorithms (FDGA). We use the concept of hierarchical fuzzy dominance to minimize the total number of infected animals, the direct cost incurred due to the implementation of mitigation strategies, the number of animals culled, and the number of animals vaccinated to mitigate an epidemic. This method has the potential to aid in economic policy development for countries that have lost their FMD-free status.

A fundamental question on visual system in neuroscience is how the visual stimuli are functionally related to neural responses. This relationship is often explained by the notion of receptive fields, an approximated linear or quasi-linear filter that encodes the high dimensional visual stimuli into neural spikes. Traditional methods for estimating the filter do not efficiently exploit prior information about the structure of neural receptive fields. Here, we propose several approaches to design the prior distribution over the filter, considering the neurophysiological fact that receptive fields tend to be localized both in space-time and spatio-temporal frequency domain. To automatically regularize the estimation of neural receptive fields, we use the evidence optimization technique, a MAP (maximum a posteriori) estimation under a prior distribution whose parameters are set by maximizing the marginal likelihood. Simulation results show that the proposed methods can estimate the receptive field using datasets that are tens to hundreds of times smaller than those required by traditional methods. / text

We propose using statistical regular pavings (SRPs) as an efficient and adaptive statistical data structure for processing massive, multi-dimensional data. A regular paving (RP) is an ordered binary tree that recursively bisects a box in $\Rz^{d}$ along the first widest side. An SRP is extended from an RP by allowing mutable caches of recursively computable statistics of the data. In this study we use SRPs for two major applications: estimating histogram densities and summarising large spatio-temporal datasets. The SRP histograms produced are $L_1$-consistent density estimators driven by a randomised priority queue that adaptively grows the SRP tree, and formalised as a Markov chain over the space of SRPs. A way to select an estimate is to run a Markov chain over the space of SRP trees, also initialised by the randomised priority queue, but here the SRP tree either shrinks or grows adaptively through pruning or splitting operations. The stationary distribution of the Markov chain is then the posterior distribution over the space of all possible histograms. We then take advantage of the recursive nature of SRPs to make computationally efficient arithmetic averages, and take the average of the states sampled from the stationary distribution to obtain the posterior mean histogram estimate. We also show that SRPs are capable of summarizing large datasets by working with a dataset containing high frequency aircraft position information. Recursively computable statistics can be stored for variable-sized regions of airspace. The regions themselves can be created automatically to reflect the varying density of aircraft observations, dedicating more computational resources and providing more detailed information in areas with more air traffic. In particular, SRPs are able to very quickly aggregate or separate data with different characteristics so that data describing individual aircraft or collected using different technologies (reflecting different levels of precision) can be stored separately and yet also very quickly combined using standard arithmetic operations.