Summarizing level-two topological relations in large spatial datasets

Summarizing topological relations is fundamental to many spatial applications including spatial query optimization. In this article, we present several novel techniques to effectively construct cell density based spatial histograms for range (window) summarizations restricted to the four most important level-two topological relations: contains, contained, overlap, and disjoint. We first present a novel framework to construct a multiscale Euler histogram in 2D space with the guarantee of the exact summarization results for aligned windows in constant time. To minimize the storage space in such a multiscale Euler histogram, an approximate algorithm with the approximate ratio 19/12 is presented, while the problem is shown NP-hard generally. To conform to a limited storage space where a multiscale histogram may be allowed to have only k Euler histograms, an effective algorithm is presented to construct multiscale histograms to achieve high accuracy in approximately summarizing aligned windows. Then, we present a new approximate algorithm to query an Euler histogram that cannot guarantee the exact answers; it runs in constant time. We also investigate the problem of nonaligned windows and the problem of effectively partitioning the data space to support nonaligned window queries. Finally, we extend our techniques to 3D space. Our extensive experiments against both synthetic and real world datasets demonstrate that the approximate multiscale histogram techniques may improve the accuracy of the existing techniques by several orders of magnitude while retaining the cost efficiency, and the exact multiscale histogram technique requires only a storage space linearly proportional to the number of cells for many popular real datasets.

Multiscale histograms: Summarizing topological relations in large spatial datasets

Summarizing topological relations is fundamental to many spatial applications including spatial query optimization. In this paper, we present several novel techniques to eectively construct cell density based spatial histograms for range (window) summarizations restricted to the four most important topological relations: contains, contained, overlap, and disjoint. We rst present a novel framework to construct a multiscale histogram composed of multiple Euler histograms with the guarantee of the exact summarization results for aligned windows in constant time. Then we present an approximate algorithm, with the approximate ratio 19/12, to minimize the storage spaces of such multiscale Euler histograms, although the problem is generally NP-hard. To conform to a limited storage space where only k Euler histograms are allowed, an effective algorithm is presented to construct multiscale histograms to achieve high accuracy. Finally, we present a new approximate algorithm to query an Euler histogram that cannot guarantee the exact answers; it runs in constant time. Our extensive experiments against both synthetic and real world datasets demonstrated that the approximate mul- tiscale histogram techniques may improve the accuracy of the existing techniques by several orders of magnitude while retaining the cost effciency, and the exact multiscale histogram technique requires only a storage space linearly proportional to the number of cells for the real datasets.

Collaborative decision-making processes for maintaining biodiversity: Two Australian case studies

There have been many models developed by scientists to assist decision-makers in making socio-economic and environmental decisions. It is now recognised that there is a shift in the dominant paradigm to making decisions with stakeholders, rather than making decisions for stakeholders. Our paper investigates two case studies where group model building has been undertaken for maintaining biodiversity in Australia. The first case study focuses on preservation and management of green spaces and biodiversity in metropolitan Melbourne under the umbrella of the Melbourne 2030 planning strategy. A geographical information system is used to collate a number of spatial datasets encompassing a range of cultural and natural assets data layers including: existing open spaces, waterways, threatened fauna and flora, ecological vegetation covers, registered cultural heritage sites, and existing land parcel zoning. Group model building is incorporated into the study through eliciting weightings and ratings of importance for each datasets from urban planners to formulate different urban green system scenarios. The second case study focuses on modelling ecoregions from spatial datasets for the state of Queensland. The modelling combines collaborative expert knowledge and a vast amount of environmental data to build biogeographical classifications of regions. An information elicitation process is used to capture expert knowledge of ecoregions as geographical descriptions, and to transform this into prior probability distributions that characterise regions in terms of environmental variables. This prior information is combined with measured data on the environmental variables within a Bayesian modelling technique to produce the final classified regions. We describe how linked views between descriptive information, mapping and statistical plots are used to decide upon representative regions that satisfy a number of criteria for biodiversity and conservation. This paper discusses the advantages and problems encountered when undertaking group model building. Future research will extend the group model building approach to include interested individuals and community groups.

A strategy to fill gaps in soil survey over large spatial extents: an example from the Murray-Darling basin of Australia

We re-mapped the soils of the Murray-Darling Basin (MDB) in 1995-1998 with a minimum of new fieldwork, making the most out of existing data. We collated existing digital soil maps and used inductive spatial modelling to predict soil types from those maps combined with environmental predictor variables. Lithology, Landsat Multi Spectral Scanner (Landsat MSS), the 9-s digital elevation model (DEM) of Australia and derived terrain attributes, all gridded to 250-m pixels, were the predictor variables. Because the basin-wide datasets were very large data mining software was used for modelling. Rule induction by data mining was also used to define the spatial domain of extrapolation for the extension of soil-landscape models from existing soil maps. Procedures to estimate the uncertainty associated with the predictions and quality of information for the new soil-landforms map of the MDB are described. (C) 2002 Elsevier Science B.V. All rights reserved.

A scaleless data model for direct and progressive spatial query processing

A progressive spatial query retrieves spatial data based on previous queries (e.g., to fetch data in a more restricted area with higher resolution). A direct query, on the other side, is defined as an isolated window query. A multi-resolution spatial database system should support both progressive queries and traditional direct queries. It is conceptually challenging to support both types of query at the same time, as direct queries favour location-based data clustering, whereas progressive queries require fragmented data clustered by resolutions. Two new scaleless data structures are proposed in this paper. Experimental results using both synthetic and real world datasets demonstrate that the query processing time based on the new multiresolution approaches is comparable and often better than multi-representation data structures for both types of queries.

Spatial, temporal, and human dimensions of air pollution in Brisbane

Arriving in Brisbane some six years ago, I could not help being impressed by what may be prosaically described as its atmospheric amenity resources. Perhaps this in part was due to my recent experiences in major urban centres in North America, but since that time, that sparkling quality and the blue skies seem to have progressively diminished. Unfortunately, there is also objective evidence available to suggest that this apparent deterioration is not merely the result of habituation of the senses. Air pollution data for the city show trends of increasing concentrations of those very substances that have destroyed the attractiveness of major population centres elsewhere, with climates initially as salubrious. Indeed, present figures indicate that photochemical smog in unacceptably high concentrations is rapidly becoming endemic also over Brisbane. These regrettable developments should come as no surprise. The society at large has not been inclined to respond purposefully to warnings of impending environmental problems, despite the experiences and publicity from overseas and even from other cities within Australia. Nor, up to the present, have certain politicians and government officials displayed stances beyond those necessary for the maintenance of a decorum of concern. At this stage, there still exists the possibility for meaningful government action without the embarrassment of losing political favour with the electorate. To the contrary, there is every chance that such action may be turned to advantage with increased public enlightenment. It would be more than a pity to miss perhaps the final remaining opportunity: Queensland is one of the few remaining places in the world with sufficient resources to permit both rational development and high environmental quality. The choice appears to be one of making a relatively minor investment now for a large financial and social gain the near future, or, permitting Brisbane to degenerate gradually into just another stagnated Los Angeles or Sydney. The present monograph attempts to introduce the problem by reviewing the available research on air quality in the Brisbane area. It also tries to elucidate some seemingly obvious, but so far unapplied management approaches. By necessity, such a broad treatment needs to make inroads into extensive ranges of subject areas, including political and legal practices to public perceptions, scientific measurement and statistical analysis to dynamics of air flow. Clearly, it does not pretend to be definitive in any of these fields, but it does try to emphasize those adjustable facets of the human use system of natural resources, too often neglected in favour of air pollution control technology. The crossing of disciplinary boundaries, however, needs no apology: air quality problems are ubiquitous, touching upon space, time and human interaction.

Verbs as Spatial Deixis markers in Jingulu

Contrary to the common pattern of spatial terms being metaphorically extended to location in time, the Australian language Jingulu shows an unusual extension of temporal markers to indicate location in space. Light verbs, which typically encode tense, aspect, mood and associated motion, are occasionally found on nouns to indicate the relative location of the referent with respect to the speaker. It is hypothesised that this pattern resulted from the reduction of verbal clauses used as relative modifiers to the nouns in question.

Spatial Technologies: What use are they to managers of environmental lands?

This paper reviews the potential use of three types of spatial technology to land managers, namely satellite imagery, satellite positioning systems and supporting computer software. Developments in remote sensing and the relative advantages of multispectral and hyperspectral images are discussed. The main challenge to the wider use of remote sensing as a land management tool is seen as uncertainty whether apparent relationships between biophysical variables and spectral reflectance are direct and causal, or artefacts of particular images. Developments in satellite positioning systems are presented in the context of land managers’ need for position estimates in situations where absolute precision may or may not be required. The role of computer software in supporting developments in spatial technology is described. Spatial technologies are seen as having matured beyond empirical applications to the stage where they are useful and reliable land management tools. In addition, computer software has become more user-friendly and this has facilitated data collection and manipulation by semi-expert as well as specialist staff.

A GIS Based Assessment of Land Suitable for Growing Hoop Pine in the Atherton, Eacham and Herberton Shires of North Queensland

The area of private land suitable and available for growing hoop pine (Araucaria cunninghamii) on the Atherton Tablelands in North Queensland was modelled using a geographic information system (GIS). In Atherton, Eacham and Herberton shires, approximately 64,700 ha of privately owned land were identified as having a mean annual rainfall and soil type similar to Forestry Plantations Queensland (FPQ) hoop pine growth plots with an approximate growth rate of 20 m3 per annum. Land with slope of over 25° and land covered with native vegetation were excluded in the estimation. If land which is currently used for high-value agriculture is also excluded, the net area of land potentially suitable and available for expansion of hoop pine plantations is approximately 22,900 ha. Expert silvicultural advice emphasized the role of site preparation and weed control in affecting the long-term growth rate of hoop pine. Hence, sites with less than optimal fertility and rainfall may be considered as being potentially suitable for growing hoop pine at a lower growth rate. The datasets had been prepared at various scales and differing precision for their description of land attributes. Therefore, the results of this investigation have limited applicability for planning at the individual farm level but are useful at the regional level to target areas for plantation expansion.

Short-term spatial diffusion in sigma o+ o- optical molasses

We have measured the spatial diffusion of atoms in a three-dimensional sigma(+)-sigma(-) optical molasses over twenty milliseconds timescale, starting from the initial interaction of the atoms with the molasses. We find that the diffusion constants agree well with a linear model for these short time scales and also compare favourably to other studies of diffusion made over longer time scales. These measurements enable us to quantify the detection method known as freezing molasses. We discuss this method, for detecting and measuring the momentum distribution of cold atoms, which relies on the slow diffusion of atoms in optical molasses to produce a freeze-frame of the spatial distribution of the atoms. This method enables a longer interrogation interval, providing a greatly increased signal-to-noise ratio. (C) 1998 Elsevier Science B.V.

Data partitioning for parallel spatial join processing

The cost of spatial join processing can be very high because of the large sizes of spatial objects and the computation-intensive spatial operations. While parallel processing seems a natural solution to this problem, it is not clear how spatial data can be partitioned for this purpose. Various spatial data partitioning methods are examined in this paper. A framework combining the data-partitioning techniques used by most parallel join algorithms in relational databases and the filter-and-refine strategy for spatial operation processing is proposed for parallel spatial join processing. Object duplication caused by multi-assignment in spatial data partitioning can result in extra CPU cost as well as extra communication cost. We find that the key to overcome this problem is to preserve spatial locality in task decomposition. We show in this paper that a near-optimal speedup can be achieved for parallel spatial join processing using our new algorithms.

The spatial and temporal distribution of koala faecal pellets

Faecal pellets were collected under trees used by free-ranging koalas in south-western, central and southeastern Queensland to determine the spatial and temporal distribution of pellets with respect to the activity of koalas. Deposition of faecal pellets by koalas was analysed according to the time of day at which the tree was occupied. For free-ranging koalas, 47% of daily faecal pellet output was recovered using a collection mat of 8 x 8 m placed under a day-roost tree. The best predictor of pellet production was the presence of a koala in a tree between 1800 hours and midnight. For other periods, there was no relationship between period of tree occupancy and faecal pellet recovery. There was a significant relationship between the average length of tree occupancy and the time of day that a koala entered a tree.

X-ray computed tomography to quantify tree rooting spatial distributions

Poor root development due to constraining soil conditions could be an important factor influencing health of urban trees. Therefore, there is a need for efficient techniques to analyze the spatial distribution of tree roots. An analytical procedure for describing tree rooting patterns from X-ray computed tomography (CT) data is described and illustrated. Large irregularly shaped specimens of undisturbed sandy soil were sampled from Various positions around the base of trees using field impregnation with epoxy resin, to stabilize the cohesionless soil. Cores approximately 200 mm in diameter by 500 mm in height were extracted from these specimens. These large core samples were scanned with a medical X-ray CT device, and contiguous images of soil slices (2 mm thick) were thus produced. X-ray CT images are regarded as regularly-spaced sections through the soil although they are not actual 2D sections but matrices of voxels similar to 0.5 mm x 0.5 mm x 2 mm. The images were used to generate the equivalent of horizontal root contact maps from which three-dimensional objects, assumed to be roots, were reconstructed. The resulting connected objects were used to derive indices of the spatial organization of roots, namely: root length distribution, root length density, root growth angle distribution, root spatial distribution, and branching intensity. The successive steps of the method, from sampling to generation of indices of tree root organization, are illustrated through a case study examining rooting patterns of valuable urban trees. (C) 1999 Elsevier Science B.V. All rights reserved.

Differentiation of soil properties related to the spatial association of wheat roots and soil macropores

Under certain soil conditions, e.g. hardsetting clay B-horizons of South-Eastern Australia, wheat plants do not perform as well as would be expected given measurements of bulk soil attributes. In such soils, measurement indicates that a large proportion (80%) of roots are preferentially located in the soil within 1 mm of macropores. This paper addresses the question of whether there are biological and soil chemical effects concomitant with this observed spatial relationship. The properties of soil manually dissected from the 1-3 mm wide region surrounding macropores, the macropore sheath, were compared to those that are measured in a conventional manner on the bulk soil. Field specimens of two different soil materials were dissected to examine biological differentiation. To ascertain whether the macropore sheath soil differs from rhizosphere soil, wheat was grown in structured and repacked cores under laboratory conditions. The macropore sheath soil contained more microbial biomass per unit mass than both the bulk soil and the rhizosphere. The bacterial population in the macropore sheath was able to utilise a wider range of carbon substrates and to a greater extent than the bacterial population in the corresponding bulk soil. These differences between the macropore sheath and bulk soil were almost non-existent in the repacked cores. Evidence for larger numbers of propagules of the broad host range fungus Pythium in the macropore sheath soil were also obtained.