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.

Local edge detectors: A substrate for fine spatial vision at low temporal frequencies in rabbit retina

Visual acuity is limited by the size and density of the smallest retinal ganglion cells, which correspond to the midget ganglion cells in primate retina and the beta- ganglion cells in cat retina, both of which have concentric receptive fields that respond at either light- On or light- Off. In contrast, the smallest ganglion cells in the rabbit retina are the local edge detectors ( LEDs), which respond to spot illumination at both light- On and light- Off. However, the LEDs do not predominate in the rabbit retina and the question arises, what role do they play in fine spatial vision? We studied the morphology and physiology of LEDs in the isolated rabbit retina and examined how their response properties are shaped by the excitatory and inhibitory inputs. Although the LEDs comprise only similar to 15% of the ganglion cells, neighboring LEDs are separated by 30 - 40 mu m on the visual streak, which is sufficient to account for the grating acuity of the rabbit. The spatial and temporal receptive- field properties of LEDs are generated by distinct inhibitory mechanisms. The strong inhibitory surround acts presynaptically to suppress both the excitation and the inhibition elicited by center stimulation. The temporal properties, characterized by sluggish onset, sustained firing, and low bandwidth, are mediated by the temporal properties of the bipolar cells and by postsynaptic interactions between the excitatory and inhibitory inputs. We propose that the LEDs signal fine spatial detail during visual fixation, when high temporal frequencies are minimal.

Advanced computing for systems biology

Systems biology is based on computational modelling and simulation of large networks of interacting components. Models may be intended to capture processes, mechanisms, components and interactions at different levels of fidelity. Input data are often large and geographically disperse, and may require the computation to be moved to the data, not vice versa. In addition, complex system-level problems require collaboration across institutions and disciplines. Grid computing can offer robust, scaleable solutions for distributed data, compute and expertise. We illustrate some of the range of computational and data requirements in systems biology with three case studies: one requiring large computation but small data (orthologue mapping in comparative genomics), a second involving complex terabyte data (the Visible Cell project) and a third that is both computationally and data-intensive (simulations at multiple temporal and spatial scales). Authentication, authorisation and audit systems are currently not well scalable and may present bottlenecks for distributed collaboration particularly where outcomes may be commercialised. Challenges remain in providing lightweight standards to facilitate the penetration of robust, scalable grid-type computing into diverse user communities to meet the evolving demands of systems biology.

Spatial indexing for scalability in FCA

The paper provides evidence that spatial indexing structures offer faster resolution of Formal Concept Analysis queries than B-Tree/Hash methods. We show that many Formal Concept Analysis operations, computing the contingent and extent sizes as well as listing the matching objects, enjoy improved performance with the use of spatial indexing structures such as the RD-Tree. Speed improvements can vary up to eighty times faster depending on the data and query. The motivation for our study is the application of Formal Concept Analysis to Semantic File Systems. In such applications millions of formal objects must be dealt with. It has been found that spatial indexing also provides an effective indexing technique for more general purpose applications requiring scalability in Formal Concept Analysis systems. The coverage and benchmarking are presented with general applications in mind.

The spatial pattern of child growth in Papua New Guinea

Child growth in PNG shows strong regional differences, with highlands children being generally shorter but stockier than those from lowland areas. Differences in diet, socioeconomic status and local subsistence agriculture were found to be important predictors of child growth. All variables indicating higher socioeconomic status were correlated with better growth, as was a high consumption of imported and local high quality foods such as cereals, legumes, tinned fish or meat and fresh fish. Differences in subsistence explained between 25% and 50% of the geographical variation in growth. Child growth was better in systems based on cassava and sweet potato, and worse in those where banana, sago and taro are staples. The cultivation of all major cash crops and sales of fish and food crops improved child growth. Birth weights show similar patterns to those observed in child growth. The implications of these findings for possible interventions are discussed.

On aggregation issues in spatial data management

Large amounts of information can be overwhelming and costly to process, especially when transmitting data over a network. A typical modern Geographical Information System (GIS) brings all types of data together based on the geographic component of the data and provides simple point-and-click query capabilities as well as complex analysis tools. Querying a Geographical Information System, however, can be prohibitively expensive due to the large amounts of data which may need to be processed. Since the use of GIS technology has grown dramatically in the past few years, there is now a need more than ever, to provide users with the fastest and least expensive query capabilities, especially since an approximated 80 % of data stored in corporate databases has a geographical component. However, not every application requires the same, high quality data for its processing. In this paper we address the issues of reducing the cost and response time of GIS queries by preaggregating data by compromising the data accuracy and precision. We present computational issues in generation of multi-level resolutions of spatial data and show that the problem of finding the best approximation for the given region and a real value function on this region, under a predictable error, in general is "NP-complete.

Advanced receivers for next generation wireless communication systems

Despite extensive progress on the theoretical aspects of spectral efficient communication systems, hardware impairments, such as phase noise, are the key bottlenecks in next generation wireless communication systems. The presence of non-ideal oscillators at the transceiver introduces time varying phase noise and degrades the performance of the communication system. Significant research literature focuses on joint synchronization and decoding based on joint posterior distribution, which incorporate both the channel and code graph. These joint synchronization and decoding approaches operate on well designed sum-product algorithms, which involves calculating probabilistic messages iteratively passed between the channel statistical information and decoding information. Channel statistical information, generally entails a high computational complexity because its probabilistic model may involve continuous random variables. The detailed knowledge about the channel statistics for these algorithms make them an inadequate choice for real world applications due to power and computational limitations. In this thesis, novel phase estimation strategies are proposed, in which soft decision-directed iterative receivers for a separate A Posteriori Probability (APP)-based synchronization and decoding are proposed. These algorithms do not require any a priori statistical characterization of the phase noise process. The proposed approach relies on a Maximum A Posteriori (MAP)-based algorithm to perform phase noise estimation and does not depend on the considered modulation/coding scheme as it only exploits the APPs of the transmitted symbols. Different variants of APP-based phase estimation are considered. The proposed algorithm has significantly lower computational complexity with respect to joint synchronization/decoding approaches at the cost of slight performance degradation. With the aim to improve the robustness of the iterative receiver, we derive a new system model for an oversampled (more than one sample per symbol interval) phase noise channel. We extend the separate APP-based synchronization and decoding algorithm to a multi-sample receiver, which exploits the received information from the channel by exchanging the information in an iterative fashion to achieve robust convergence. Two algorithms based on sliding block-wise processing with soft ISI cancellation and detection are proposed, based on the use of reliable information from the channel decoder. Dually polarized systems provide a cost-and spatial-effective solution to increase spectral efficiency and are competitive candidates for next generation wireless communication systems. A novel soft decision-directed iterative receiver, for separate APP-based synchronization and decoding, is proposed. This algorithm relies on an Minimum Mean Square Error (MMSE)-based cancellation of the cross polarization interference (XPI) followed by phase estimation on the polarization of interest. This iterative receiver structure is motivated from Master/Slave Phase Estimation (M/S-PE), where M-PE corresponds to the polarization of interest. The operational principle of a M/S-PE block is to improve the phase tracking performance of both polarization branches: more precisely, the M-PE block tracks the co-polar phase and the S-PE block reduces the residual phase error on the cross-polar branch. Two variants of MMSE-based phase estimation are considered; BW and PLP.

Stimuli of varying spatial scale induce gamma activity with distinct temporal characteristics in human visual cortex

Gamma activity to stationary grating stimuli was studied non-invasively using MEG recordings in humans. Using a spatial filtering technique, we localized gamma activity to primary visual cortex. We tested the hypothesis that spatial frequency properties of visual stimuli may be related to the temporal frequency characteristics of the associated cortical responses. We devised a method to assess temporal frequency differences between stimulus-related responses that typically exhibit complex spectral shapes. We applied this methodology to either single-trial (induced) or time-averaged (evoked) responses in four frequency ranges (0-40, 20-60, 40-80 and 60-100 Hz) and two time windows (either the entire duration of stimulus presentation or the first second following stimulus onset). Our results suggest that stimuli of varying spatial frequency induce responses that exhibit significantly different temporal frequency characteristics. These effects were particularly accentuated for induced responses in the classical gamma frequency band (20-60 Hz) analyzed over the entire duration of stimulus presentation. Strikingly, examining the first second of the responses following stimulus onset resulted in significant loss in stimulus specificity, suggesting that late signal components contain functionally relevant information. These findings advocate a functional role of gamma activity in sensory representation. We suggest that stimulus specific frequency characteristics of MEG signals can be mapped to processes of neuronal synchronization within the framework of coupled dynamical systems.