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.

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.

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.

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.

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.

Ross River virus disease clusters and spatial relationship with mosquito biting exposure in Redland Shire, southern Queensland, Australia

The spatial heterogeneity in the risk of Ross River virus (family Togaviridae, genus Alphavirus, RRV) disease, the most common mosquito-borne disease in Australia, was examined in Redland Shire in southern Queensland, Australia. Disease cases, complaints from residents of intense mosquito biting exposure, and human population data were mapped using a geographic information system. Surface maps of RRV disease age-sex standardized morbidity ratios and mosquito biting complaint morbidity ratios were created. To determine whether there was significant spatial variation in disease and complaint patterns, a spatial scan analysis method was used to test whether the number of cases and complaints was distributed according to underlying population at risk. Several noncontiguous areas in proximity to productive saline water habitats of Aedes vigilax (Skuse), a recognized vector of RRV, had higher than expected numbers of RRV disease cases and complaints. Disease rates in human populations in areas which had high numbers of adult Ae. vigilax in carbon dioxide- and octenol-baited light traps were up to 2.9 times those in areas that rarely had high numbers of mosquitoes. It was estimated that targeted control of adult Ae. vigilax in these high-risk areas could potentially reduce the RRV disease incidence by an average of 13.6%. Spatial correlation was found between RRV disease risk and complaints from residents of mosquito biting. Based on historical patterns of RRV transmission throughout Redland Shire and estimated future human population growth in areas with higher than average RRV disease incidence, it was estimated that RRV incidence rates will increase by 8% between 2001 and 2021. The use of arbitrary administrative areas that ranged in size from 4.6 to 318.3 km2, has the potential to mask any small scale heterogeneity in disease patterns. With the availability of georeferenced data sets and high-resolution imagery, it is becoming more feasible to undertake spatial analyses at relatively small scales.

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.

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.

Exploring sequential data: Commentary on Bowers, Jentsch, Salas, and Braun (1998)

In an investigation intended to determine training needs of night crews, Bowers et al. (1998, this issue) report two studies showing that the patterning of communication is a better discriminator of good and poor crews than is the content of communication. Bowers et al. characterize their studies as intended to generate hypotheses for training needs and draw connections with Exploratory Sequential Data Analysis (ESDA). Although applauding the intentions of Bowers ct al., we point out some concerns with their characterization and implementation of ESDA. Our principal concern is that the Bowers et al. exploration of the data does not convincingly lead them back to a better fundamental understanding of the original phenomena they are investigating.