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.

Using visual spatial search interface for WWW applications

Most Internet search engines are keyword-based. They are not efficient for the queries where geographical location is important, such as finding hotels within an area or close to a place of interest. A natural interface for spatial searching is a map, which can be used not only to display locations of search results but also to assist forming search conditions. A map-based search engine requires a well-designed visual interface that is intuitive to use yet flexible and expressive enough to support various types of spatial queries as well as aspatial queries. Similar to hyperlinks for text and images in an HTML page, spatial objects in a map should support hyperlinks. Such an interface needs to be scalable with the size of the geographical regions and the number of websites it covers. In spite of handling typically a very large amount of spatial data, a map-based search interface should meet the expectation of fast response time for interactive applications. In this paper we discuss general requirements and the design for a new map-based web search interface, focusing on integration with the WWW and visual spatial query interface. A number of current and future research issues are discussed, and a prototype for the University of Queensland is presented. (C) 2001 Published by Elsevier Science Ltd.

Remotely sensed data for ecosystem analyses: Combining hierarchy and scene models

Remotely sensed data have been used extensively for environmental monitoring and modeling at a number of spatial scales; however, a limited range of satellite imaging systems often. constrained the scales of these analyses. A wider variety of data sets is now available, allowing image data to be selected to match the scale of environmental structure(s) or process(es) being examined. A framework is presented for use by environmental scientists and managers, enabling their spatial data collection needs to be linked to a suitable form of remotely sensed data. A six-step approach is used, combining image spatial analysis and scaling tools, within the context of hierarchy theory. The main steps involved are: (1) identification of information requirements for the monitoring or management problem; (2) development of ideal image dimensions (scene model), (3) exploratory analysis of existing remotely sensed data using scaling techniques, (4) selection and evaluation of suitable remotely sensed data based on the scene model, (5) selection of suitable spatial analytic techniques to meet information requirements, and (6) cost-benefit analysis. Results from a case study show that the framework provided an objective mechanism to identify relevant aspects of the monitoring problem and environmental characteristics for selecting remotely sensed data and analysis techniques.

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.

Semantic caching for multiresolution spatial query processing in mobile environments

Spatial data are particularly useful in mobile environments. However, due to the low bandwidth of most wireless networks, developing large spatial database applications becomes a challenging process. In this paper, we provide the first attempt to combine two important techniques, multiresolution spatial data structure and semantic caching, towards efficient spatial query processing in mobile environments. Based on the study of the characteristics of multiresolution spatial data (MSD) and multiresolution spatial query, we propose a new semantic caching model called Multiresolution Semantic Caching (MSC) for caching MSD in mobile environments. MSC enriches the traditional three-category query processing in semantic cache to five categories, thus improving the performance in three ways: 1) a reduction in the amount and complexity of the remainder queries; 2) the redundant transmission of spatial data already residing in a cache is avoided; 3) a provision for satisfactory answers before 100% query results have been transmitted to the client side. Our extensive experiments on a very large and complex real spatial database show that MSC outperforms the traditional semantic caching models significantly

RSA-Grid: A grid computing based framework for power system reliability and security analysis

Grid computing is an emerging technology for providing the high performance computing capability and collaboration mechanism for solving the collaborated and complex problems while using the existing resources. In this paper, a grid computing based framework is proposed for the probabilistic based power system reliability and security analysis. The suggested name of this computing grid is Reliability and Security Grid (RSA-Grid). Then the architecture of this grid is presented. A prototype system has been built for further development of grid-based services for power systems reliability and security assessment based on probabilistic techniques, which require high performance computing and large amount of memory. Preliminary results based on prototype of this grid show that RSA-Grid can provide the comprehensive assessment results for real power systems efficiently and economically.

Efficiently computing weighted proximity relationships in spatial databases

Spatial data mining recently emerges from a number of real applications, such as real-estate marketing, urban planning, weather forecasting, medical image analysis, road traffic accident analysis, etc. It demands for efficient solutions for many new, expensive, and complicated problems. In this paper, we investigate the problem of evaluating the top k distinguished “features” for a “cluster” based on weighted proximity relationships between the cluster and features. We measure proximity in an average fashion to address possible nonuniform data distribution in a cluster. Combining a standard multi-step paradigm with new lower and upper proximity bounds, we presented an efficient algorithm to solve the problem. The algorithm is implemented in several different modes. Our experiment results not only give a comparison among them but also illustrate the efficiency of the algorithm.

Asymmetric page split generalized index search trees for formal concept analysis

Formal Concept Analysis is an unsupervised machine learning technique that has successfully been applied to document organisation by considering documents as objects and keywords as attributes. The basic algorithms of Formal Concept Analysis then allow an intelligent information retrieval system to cluster documents according to keyword views. This paper investigates the scalability of this idea. In particular we present the results of applying spatial data structures to large datasets in formal concept analysis. Our experiments are motivated by the application of the Formal Concept Analysis idea of a virtual filesystem [11,17,15]. In particular the libferris [1] Semantic File System. This paper presents customizations to an RD-Tree Generalized Index Search Tree based index structure to better support the application of Formal Concept Analysis to large data sources.

Dynamic multi-resolution spatial object derivation for mobile and WWW applications

Online geographic information systems provide the means to extract a subset of desired spatial information from a larger remote repository. Data retrieved representing real-world geographic phenomena are then manipulated to suit the specific needs of an end-user. Often this extraction requires the derivation of representations of objects specific to a particular resolution or scale from a single original stored version. Currently standard spatial data handling techniques cannot support the multi-resolution representation of such features in a database. In this paper a methodology to store and retrieve versions of spatial objects at, different resolutions with respect to scale using standard database primitives and SQL is presented. The technique involves heavy fragmentation of spatial features that allows dynamic simplification into scale-specific object representations customised to the display resolution of the end-user's device. Experimental results comparing the new approach to traditional R-Tree indexing and external object simplification reveal the former performs notably better for mobile and WWW applications where client-side resources are limited and retrieved data loads are kept relatively small.

An internet GIS and spatial model to benchmark local government socio-economic performance

This paper develops an Internet geographical information system (GIS) and spatial model application that provides socio-economic information and exploratory spatial data analysis for local government authorities (LGAs) in Queensland, Australia. The application aims to improve the means by which large quantities of data may be analysed, manipulated and displayed in order to highlight trends and patterns as well as provide performance benchmarking that is readily understandable and easily accessible for decision-makers. Measures of attribute similarity and spatial proximity are combined in a clustering model with a spatial autocorrelation index for exploratory spatial data analysis to support the identification of spatial patterns of change. Analysis of socio-economic changes in Queensland is presented. The results demonstrate the usefulness and potential appeal of the Internet GIS applications as a tool to inform the process of regional analysis, planning and policy.

Fine-scale spatial genetic correlation analyses reveal strong female philopatry within a brush-tailed rock-wallaby colony in southeast Queensland

We combine spatial data on home ranges of individuals and microsatellite markers to examine patterns of fine-scale spatial genetic structure and dispersal within a brush-tailed rock-wallaby (Petrogale penicillata) colony at Hurdle Creek Valley, Queensland. Brush-tailed rock-wallabies were once abundant and widespread throughout the rocky terrain of southeastern Australia; however, populations are nearly extinct in the south of their range and in decline elsewhere. We use pairwise relatedness measures and a recent multilocus spatial autocorrelation analysis to test the hypotheses that in this species, within-colony dispersal is male-biased and that female philopatry results in spatial clusters of related females within the colony. We provide clear evidence for strong female philopatry and male-biased dispersal within this rock-wallaby colony. There was a strong, significant negative correlation between pairwise relatedness and geographical distance of individual females along only 800 m of cliff line. Spatial genetic autocorrelation analyses showed significant positive correlation for females in close proximity to each other and revealed a genetic neighbourhood size of only 600 m for females. Our study is the first to report on the fine-scale spatial genetic structure within a rock-wallaby colony and we provide the first robust evidence for strong female philopatry and spatial clustering of related females within this taxon. We discuss the ecological and conservation implications of our findings for rock-wallabies, as well as the importance of fine-scale spatial genetic patterns in studies of dispersal behaviour.

Community-based interventions for the prevention of burns and scalds in children

Background Burns and scalds are a significant cause of morbidity and mortality in children. Successful counter-measures to prevent burn and scald-related injury have been identified. However, evidence indicating the successful roll-out of these counter-measures into the wider community is lacking. Community-based interventions in the form of multi-strategy, multi-focused programmes are hypothesised to result in a reduction in population-wide injury rates. This review tests this hypothesis with regards to burn and scald injury in children. Objectives To assess the effects of community-based interventions, defined as coordinated, multi-strategy initiatives, for reducing burns and scalds in children aged 14 years and under. Search strategy We searched the Cochrane Injuries Group's specialised register, CENTRAL, MEDLINE, EMBASE, CINAHL, PsycINFO, National Research Register and the Web of Knowledge. We also handsearched selected journals and checked the reference lists of selected publications. The searches were last updated in May 2007. Selection criteria Included studies were those that reported changes in medically attended burn and scald-related injury rates in a paediatric population (aged 14 years and under), following the implementation of a controlled community-based intervention. Data collection and analysis Two authors independently assess studies for eligibility and extracted data. Due to heterogeneity between the included studies, a pooled analysis was not appropriate. Main results Of 39 identified studies, four met the criteria for inclusion. Two of the included studies reported a significant decrease in paediatric burn and scald injury in the intervention compared with the control communities. The failure of the other two studies to show a positive result may have been due to limited time-frame for the intervention and/or failure to adequately implement the counter-measures in the communities. Authors' conclusions There are a very limited number of research studies allowing conclusions to be drawn about the effectiveness of community-based injury prevention programmes to prevent burns and scalds in children. There is a pressing need to evaluate high-quality community-based intervention programmes based on efficacious counter-measures to reduce burns and scalds in children. It is important that a framework for considering the problem of burns and scalds in children from a prevention perspective be articulated, and that an evidence-based suite of interventions be combined to create programme guidelines suitable for implementation in communities throughout the world.

A broad-scale analysis of links between coastal fisheries production and mangrove extent: A case-study for northeastern Australia

The paradigm that mangroves are critical for sustaining production in coastal fisheries is widely accepted, but empirical evidence has been tenuous. This study showed that links between mangrove extent and coastal fisheries production could be detected for some species at a broad regional scale (1000s of kilometres) on the east coast of Queensland, Australia. The relationships between catch-per-unit-effort for different commercially caught species in four fisheries (trawl, line, net and pot fisheries) and mangrove characteristics, estimated from Landsat images were examined using multiple regression analyses. The species were categorised into three groups based on information on their life history characteristics, namely mangrove-related species (banana prawns Penaeus merguiensis, mud crabs Scylla serrata and barramundi Lates calcarifer), estuarine species (tiger prawns Penaeus esculentus and Penaeus semisulcatus, blue swimmer crabs Portunus pelagicus and blue threadfin Eleutheronema tetradactylum) and offshore species (coral trout Plectropomus spp.). For the mangrove-related species, mangrove characteristics such as area and perimeter accounted for most of the variation in the model; for the non-mangrove estuarine species, latitude was the dominant parameter but some mangrove characteristics (e.g. mangrove perimeter) also made significant contributions to the models. In contrast, for the offshore species, latitude was the dominant variable, with no contribution from mangrove characteristics. This study also identified that finer scale spatial data for the fisheries, to enable catch information to be attributed to a particular catchment, would help to improve our understanding of relationships between mangroves and fisheries production. (C) 2005 Elsevier B.V. All rights reserved.

Temporal and spatial transcriptional programs in murine kidney development

We have performed a systematic temporal and spatial expression profiling of the developing mouse kidney using Compugen long-oligonucleotide microarrays. The activity of 18,000 genes was monitored at 24-h intervals from 10.5-day-postcoitum (dpc) metanephric mesenchyme (MM) through to neonatal kidney, and a cohort of 3,600 dynamically expressed genes was identified. Early metanephric development was further surveyed by directly comparing RNA from 10.5 vs. 11.5 vs. 13.5dpc kidneys. These data showed high concordance with the previously published dynamic profile of rat kidney development (Stuart RO, Bush KT, and Nigam SK. Proc Natl Acad Sci USA 98: 5649-5654, 2001) and our own temporal data. Cluster analyses were used to identify gene ontological terms, functional annotations, and pathways associated with temporal expression profiles. Genetic network analysis was also used to identify biological networks that have maximal transcriptional activity during early metanephric development, highlighting the involvement of proliferation and differentiation. Differential gene expression was validated using whole mount and section in situ hybridization of staged embryonic kidneys. Two spatial profiling experiments were also undertaken. MM (10.5dpc) was compared with adjacent intermediate mesenchyme to further define metanephric commitment. To define the genes involved in branching and in the induction of nephrogenesis, expression profiling was performed on ureteric bud (GFP+) FACS sorted from HoxB7-GFP transgenic mice at 15.5dpc vs. the GFP- mesenchymal derivatives. Comparisons between temporal and spatial data enhanced the ability to predict function for genes and networks. This study provides the most comprehensive temporal and spatial survey of kidney development to date, and the compilation of these transcriptional surveys provides important insights into metanephric development that can now be functionally tested.

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.