ALBERT

Description:    When users need to find something on the Web that is related to a place, chances are place names will be submitted along with some other keywords to a search engine. However, automatic recognition of geographic characteristics embedded in Web documents, which would allow for a better connection between documents and places, remains a difficult task. We propose an ontology-driven approach to facilitate the process of recognizing, extracting, and geocoding partial or complete references to places embedded in text. Our approach combines an extraction ontology with urban gazetteers and geocoding techniques. This ontology, called OnLocus, is used to guide the discovery of geospatial evidence from the contents of Web pages. We show that addresses and positioning expressions, along with fragments such as postal codes or telephone area codes, provide satisfactory support for local search applications, since they are able to determine approximations to the physical location of services and activities named within Web pages. Our experiments show the feasibility of performing automated address extraction and geocoding to identify locations associated to Web pages. Combining location identifiers with basic addresses improved the precision of extractions and reduced the number of false positive results. Content Type Journal Article Pages 609-631 DOI 10.1007/s10707-010-0118-z Authors Karla A. V. Borges, PRODABEL-Empresa de Informática e Informação do Município de Belo Horizonte, Av. Pres. Carlos Luz, 1275, 31230-000 Belo Horizonte, MG, Brazil Clodoveu A. Davis, Departamento de Ciência da Computação, Universidade Federal de Minas Gerais, Av. Pres. Antônio Carlos, 6627, 31270-010 Belo Horizonte, MG, Brazil Alberto H. F. Laender, Departamento de Ciência da Computação, Universidade Federal de Minas Gerais, Av. Pres. Antônio Carlos, 6627, 31270-010 Belo Horizonte, MG, Brazil Claudia Bauzer Medeiros, Instituto de Informática, Universidade de Campinas, Av. Albert Einstein,1251, 13083-970 Campinas, SP, Brazil Journal GeoInformatica Online ISSN 1573-7624 Print ISSN 1384-6175 Journal Volume Volume 15 Journal Issue Volume 15, Number 4

Description:    With the exponential growth of moving objects data to the Gigabyte range, it has become critical to develop effective techniques for indexing, updating, and querying these massive data sets. To meet the high update rate as well as low query response time requirements of moving object applications, this paper takes a novel approach in moving object indexing. In our approach, we do not require a sophisticated index structure that needs to be adjusted for each incoming update. Rather, we construct conceptually simple short-lived index images that we only keep for a very short period of time (sub-seconds) in main memory. As a consequence, the resulting technique MOVIES supports at the same time high query rates and high update rates, trading this property for query result staleness. Moreover, MOVIES is the first main memory method supporting time-parameterized predictive queries. To support this feature, we present two algorithms: non-predictive MOVIES and predictive MOVIES . We obtain the surprising result that a predictive indexing approach—considered state-of-the-art in an external-memory scenario—does not scale well in a main memory environment. In fact, our results show that MOVIES outperforms state-of-the-art moving object indexes such as a main-memory adapted B x -tree by orders of magnitude w.r.t. update rates and query rates. In our experimental evaluation, we index the complete road network of Germany consisting of 40,000,000 road segments and 38,000,000 nodes. We scale our workload up to 100,000,000 moving objects, 58,000,000 updates per second and 10,000 queries per second, a scenario at a scale unmatched by any previous work. Content Type Journal Article Pages 727-767 DOI 10.1007/s10707-011-0122-y Authors Jens Dittrich, Information Systems Group, Saarland University, Saarbrücken, Germany Lukas Blunschi, Systems Group, ETH Zurich, Zürich, Switzerland Marcos Antonio Vaz Salles, Department of Computer Science, Cornell University, Ithaca, NY, USA Journal GeoInformatica Online ISSN 1573-7624 Print ISSN 1384-6175 Journal Volume Volume 15 Journal Issue Volume 15, Number 4

Description:    This paper presents a novel approach to express and evaluate the complex class of queries in moving object databases called spatiotemporal pattern queries (STP queries). That is, one can specify temporal order constraints on the fulfillment of several predicates. This is in contrast to a standard spatiotemporal query that is composed of a single predicate. We propose a language design for spatiotemporal pattern queries in the context of spatiotemporal DBMSs. The design builds on the well established concept of lifted predicates . Hence, unlike previous approaches, patterns are neither restricted to specific sets of predicates, nor to specific moving object types. The proposed language can express arbitrarily complex patterns that involve various types of spatiotemporal operations such as range, metric, topological, set operations, aggregations, distance, direction, and boolean operations. This work covers the language integration in SQL, the evaluation of the queries, and the integration with the query optimizer. We also propose a simple language for defining the temporal constraints. The approach allows for queries that were never available. We provide a complete implementation in C+ + and Prolog in the context of the S econdo platform. The implementation is made publicly available online as a S econdo Plugin, which also includes automatic scripts for repeating the experiments in this paper. Content Type Journal Article Pages 497-540 DOI 10.1007/s10707-010-0114-3 Authors Mahmoud Attia Sakr, Database Systems for New Applications, FernUniversität in Hagen, 58084 Hagen, Germany Ralf Hartmut Güting, Database Systems for New Applications, FernUniversität in Hagen, 58084 Hagen, Germany Journal GeoInformatica Online ISSN 1573-7624 Print ISSN 1384-6175 Journal Volume Volume 15 Journal Issue Volume 15, Number 3

Description:    Supervised learning methods such as Maximum Likelihood (ML) are often used in land cover (thematic) classification of remote sensing imagery. ML classifier relies exclusively on spectral characteristics of thematic classes whose statistical distributions (class conditional probability densities) are often overlapping. The spectral response distributions of thematic classes are dependent on many factors including elevation, soil types, and ecological zones. A second problem with statistical classifiers is the requirement of the large number of accurate training samples (10 to 30 × | dimensions |), which are often costly and time consuming to acquire over large geographic regions. With the increasing availability of geospatial databases, it is possible to exploit the knowledge derived from these ancillary datasets to improve classification accuracies even when the class distributions are highly overlapping. Likewise newer semi-supervised techniques can be adopted to improve the parameter estimates of the statistical model by utilizing a large number of easily available unlabeled training samples. Unfortunately, there is no convenient multivariate statistical model that can be employed for multisource geospatial databases. In this paper we present a hybrid semi-supervised learning algorithm that effectively exploits freely available unlabeled training samples from multispectral remote sensing images and also incorporates ancillary geospatial databases. We have conducted several experiments on Landsat satellite image datasets, and our new hybrid approach shows over 24% to 36% improvement in overall classification accuracy over conventional classification schemes. Content Type Journal Article Pages 29-47 DOI 10.1007/s10707-010-0113-4 Authors Ranga Raju Vatsavai, Computational Sciences and Engineering Division, Oak Ridge National Laboratory, Oak Ridge, TN 37831, USA Budhendra Bhaduri, Computational Sciences and Engineering Division, Oak Ridge National Laboratory, Oak Ridge, TN 37831, USA Journal GeoInformatica Online ISSN 1573-7624 Print ISSN 1384-6175 Journal Volume Volume 15 Journal Issue Volume 15, Number 1

Description:    Statistical models for areal data are primarily used for smoothing maps revealing spatial trends. Subsequent interest often resides in the formal identification of ‘boundaries’ on the map. Here boundaries refer to ‘difference boundaries’, representing significant differences between adjacent regions. Recently, Lu and Carlin (Geogr Anal 37:265–285, 2005 ) discussed a Bayesian framework to carry out edge detection employing a spatial hierarchical model that is estimated using Markov chain Monte Carlo (MCMC) methods. Here we offer an alternative that avoids MCMC and is easier to implement. Our approach resembles a model comparison problem where the models correspond to different underlying edge configurations across which we wish to smooth (or not). We incorporate these edge configurations in spatially autoregressive models and demonstrate how the Bayesian Information Criteria (BIC) can be used to detect difference boundaries in the map. We illustrate our methods with a Minnesota Pneumonia and Influenza Hospitalization dataset to elicit boundaries detected from the different models. Content Type Journal Article Pages 435-454 DOI 10.1007/s10707-010-0109-0 Authors Pei Li, Division of Biostatistics, School of Public Health, University of Minnesota, Mayo Mail Code 303, Minneapolis, MN 55455–0392, USA Sudipto Banerjee, Division of Biostatistics, School of Public Health, University of Minnesota, Mayo Mail Code 303, Minneapolis, MN 55455–0392, USA Alexander M. McBean, Division of Biostatistics, School of Public Health, University of Minnesota, Mayo Mail Code 303, Minneapolis, MN 55455–0392, USA Journal GeoInformatica Online ISSN 1573-7624 Print ISSN 1384-6175 Journal Volume Volume 15 Journal Issue Volume 15, Number 3

Description:    In recent years, applications aimed at exploring and analyzing spatial data have emerged, powered by the increasing need of software that integrates Geographic Information Systems (GIS) and On-Line Analytical Processing (OLAP). These applications have been called SOLAP (Spatial OLAP). In previous work, the authors have introduced Piet, a system based on a formal data model that integrates in a single framework GIS, OLAP (On-Line Analytical Processing), and Moving Object data. Real-world problems are inherently spatio-temporal. Thus, in this paper we present a data model that extends Piet, allowing tracking the history of spatial data in the GIS layers. We present a formal study of the two typical ways of introducing time into Piet: timestamping the thematic layers in the GIS, and timestamping the spatial objects in each layer. We denote these strategies snapshot-based and timestamp-based representations, respectively, following well-known terminology borrowed from temporal databases. We present and discuss the formal model for both alternatives. Based on the timestamp-based representation, we introduce a formal First-Order spatio-temporal query language, which we denote able to express spatio-temporal queries over GIS, OLAP, and trajectory data. Finally, we discuss implementation issues, the update operators that must be supported by the model, and sketch a temporal extension to Piet-QL, the SQL-like query language that supports Piet. Content Type Journal Article Pages 455-496 DOI 10.1007/s10707-010-0110-7 Authors Leticia Gómez, Instituto Tecnológico de Buenos Aires, Av. Madero 399, Buenos Aires, Argentina Bart Kuijpers, Hasselt University and Transnational University of Limburg, Gebouw D, 3590 Diepenbeek, Belgium Alejandro Vaisman, Universidad de Buenos Aires, Ciudad Universitaria, Pabellon I, Buenos Aires, 1428 Argentina Journal GeoInformatica Online ISSN 1573-7624 Print ISSN 1384-6175 Journal Volume Volume 15 Journal Issue Volume 15, Number 3

Description:    Sensor networks have increased the amount and variety of temporal data available, requiring the definition of new techniques for data mining. Related research typically addresses the problems of indexing, clustering, classification, summarization, and anomaly detection. There is a wide range of techniques to describe and compare time series, but they focus on series’ values. This paper concentrates on a new aspect—that of describing oscillation patterns. It presents a technique for time series similarity search, and multiple temporal scales, defining a descriptor that uses the angular coefficients from a linear segmentation of the curve that represents the evolution of the analyzed series. This technique is generalized to handle co-evolution, in which several phenomena vary at the same time. Preliminary experiments with real datasets showed that our approach correctly characterizes the oscillation of single time series, for multiple time scales, and is able to compute the similarity among sets of co-evolving series. Content Type Journal Article Pages 75-109 DOI 10.1007/s10707-010-0112-5 Authors Leonardo E. Mariote, Institute of Computing, University of Campinas—CP6176, Campinas, São Paulo 13084-851, Brazil Claudia Bauzer Medeiros, Institute of Computing, University of Campinas—CP6176, Campinas, São Paulo 13084-851, Brazil Ricardo da Silva Torres, Institute of Computing, University of Campinas—CP6176, Campinas, São Paulo 13084-851, Brazil Lucas M. Bueno, Institute of Computing, University of Campinas—CP6176, Campinas, São Paulo 13084-851, Brazil Journal GeoInformatica Online ISSN 1573-7624 Print ISSN 1384-6175 Journal Volume Volume 15 Journal Issue Volume 15, Number 1

Description:    Time geography uses space–time volumes to represent the possible locations of a mobile agent over time in a x – y – t space. A volume is a qualitative representation of the fact that the agent is at a particular time t i inside of the volume’s base at t i . Space–time volumes enable qualitative analysis such as potential encounters between agents. In this paper the qualitative statements of time geography will be quantified. For this purpose an agent’s possible locations are modeled from a stochastic perspective. It is shown that probability is not equally distributed in a space–time volume, i.e., a quantitative analysis cannot be based simply on proportions of intersections. The actual probability distribution depends on the degree of a priori knowledge about the agent’s behavior. This paper starts with the standard assumption of time geography (no further knowledge), and develops the appropriate probability distribution by three equivalent approaches. With such a model any analysis of the location of an agent, or relations between the locations of two agents, can be improved in expressiveness as well as accuracy. Content Type Journal Article Pages 417-434 DOI 10.1007/s10707-010-0108-1 Authors Stephan Winter, Department of Geomatics, The University of Melbourne, Victoria, 3010 Australia Zhang-Cai Yin, School of Resources and Environmental Engineering, Wuhan University of Technology, Wuhan, Hubei, China Journal GeoInformatica Online ISSN 1573-7624 Print ISSN 1384-6175 Journal Volume Volume 15 Journal Issue Volume 15, Number 3

Description:    In modern geographic information systems, route search represents an important class of queries. In route search related applications, users may want to define a number of traveling rules (traveling preferences) when they plan their trips. However, these traveling rules are not considered in most existing techniques. In this paper, we propose a novel spatial query type, the multi-rule partial sequenced route (MRPSR) query, which enables efficient trip planning with user defined traveling rules. The MRPSR query provides a unified framework that subsumes the well-known trip planning query (TPQ) and the optimal sequenced route (OSR) query. The difficulty in answering MRPSR queries lies in how to integrate multiple choices of points-of-interest (POI) with traveling rules when searching for satisfying routes. We prove that MRPSR query is NP -hard and then provide three algorithms by mapping traveling rules to an activity on vertex network. Afterwards, we extend all the proposed algorithms to road networks. By utilizing both real and synthetic POI datasets, we investigate the performance of our algorithms. The results of extensive simulations show that our algorithms are able to answer MRPSR queries effectively and efficiently with underlying road networks. Compared to the Light Optimal Route Discoverer (LORD) based brute-force solution, the response time of our algorithms is significantly reduced while the distances of the computed routes are only slightly longer than the shortest route. Content Type Journal Article Pages 541-569 DOI 10.1007/s10707-010-0115-2 Authors Haiquan Chen, Department of Computer Science and Software Engineering, Auburn University, Auburn, AL 36849, USA Wei-Shinn Ku, Department of Computer Science and Software Engineering, Auburn University, Auburn, AL 36849, USA Min-Te Sun, Department of Computer Science and Information Engineering, National Central University, Taoyuan, 320 Taiwan Roger Zimmermann, Department of Computer Science, National University of Singapore, Singapore, 117590 Singapore Journal GeoInformatica Online ISSN 1573-7624 Print ISSN 1384-6175 Journal Volume Volume 15 Journal Issue Volume 15, Number 3

Description:    The motivation for regional association rule mining and scoping is driven by the facts that global statistics seldom provide useful insight and that most relationships in spatial datasets are geographically regional, rather than global. Furthermore, when using traditional association rule mining, regional patterns frequently fail to be discovered due to insufficient global confidence and/or support. In this paper, we systematically study this problem and address the unique challenges of regional association mining and scoping: (1) region discovery: how to identify interesting regions from which novel and useful regional association rules can be extracted; (2) regional association rule scoping: how to determine the scope of regional association rules. We investigate the duality between regional association rules and regions where the associations are valid: interesting regions are identified to seek novel regional patterns, and a regional pattern has a scope of a set of regions in which the pattern is valid. In particular, we present a reward-based region discovery framework that employs a divisive grid-based supervised clustering for region discovery. We evaluate our approach in a real-world case study to identify spatial risk patterns from arsenic in the Texas water supply. Our experimental results confirm and validate research results in the study of arsenic contamination, and our work leads to the discovery of novel findings to be further explored by domain scientists. Content Type Journal Article Pages 1-28 DOI 10.1007/s10707-010-0111-6 Authors Wei Ding, Department of Computer Science, University of Massachusetts-Boston, Boston, MA 02125-3393, USA Christoph F. Eick, Department of Computer Science, University of Houston, Houston, TX 77004, USA Xiaojing Yuan, Engineering Technology Department, University of Houston, Houston, TX 77004, USA Jing Wang, Department of Computer Science, University of Houston, Houston, TX 77004, USA Jean-Philippe Nicot, Bureau of Economic Geology, John A. & Katherine G. Jackson School of Geosciences, The University of Texas at Austin, Austin, TX USA Journal GeoInformatica Online ISSN 1573-7624 Print ISSN 1384-6175 Journal Volume Volume 15 Journal Issue Volume 15, Number 1