Decentralized load balancing for highly irregular search problems

In this paper, we present a distributed computing framework for problems characterized by a highly irregular search tree, whereby no reliable workload prediction is available. The framework is based on a peer-to-peer computing environment and dynamic load balancing. The system allows for dynamic resource aggregation, does not depend on any specific meta-computing middleware and is suitable for large-scale, multi-domain, heterogeneous environments, such as computational Grids. Dynamic load balancing policies based on global statistics are known to provide optimal load balancing performance, while randomized techniques provide high scalability. The proposed method combines both advantages and adopts distributed job-pools and a randomized polling technique. The framework has been successfully adopted in a parallel search algorithm for subgraph mining and evaluated on a molecular compounds dataset. The parallel application has shown good calability and close-to linear speedup in a distributed network of workstations.

Processing of regular and irregular past tense morphology in highly proficient second language learners of English: a self-paced reading study

Dual-system models suggest that English past tense morphology involves two processing routes: rule application for regular verbs and memory retrieval for irregular verbs (Pinker, 1999). In second language (L2) processing research, Ullman (2001a) suggested that both verb types are retrieved from memory, but more recently Clahsen and Felser (2006) and Ullman (2004) argued that past tense rule application can be automatised with experience by L2 learners. To address this controversy, we tested highly proficient Greek-English learners with naturalistic or classroom L2 exposure compared to native English speakers in a self-paced reading task involving past tense forms embedded in plausible sentences. Our results suggest that, irrespective to the type of exposure, proficient L2 learners of extended L2 exposure apply rule-based processing.

Lesions impairing regular versus irregular past tense production

We investigated selective impairments in the production of regular and irregular past tense by examining language performance and lesion sites in a sample of twelve stroke patients. A disadvantage in regular past tense production was observed in six patients when phonological complexity was greater for regular than irregular verbs, and in three patients when phonological complexity was closely matched across regularity. These deficits were not consistently related to grammatical difficulties or phonological errors but were consistently related to lesion site. All six patients with a regular past tense disadvantage had damage to the left ventral pars opercularis (in the inferior frontal cortex), an area associated with articulatory sequencing in prior functional imaging studies. In addition, those that maintained a disadvantage for regular verbs when phonological complexity was controlled had damage to the left ventral supramarginal gyrus (in the inferior parietal lobe), an area associated with phonological short-term memory. When these frontal and parietal regions were spared in patients who had damage to subcortical (n = 2) or posterior temporo-parietal regions (n = 3), past tense production was relatively unimpaired for both regular and irregular forms. The remaining (12th) patient was impaired in producing regular past tense but was significantly less accurate when producing irregular past tense. This patient had frontal, parietal, subcortical and posterior temporo-parietal damage, but was distinguished from the other patients by damage to the left anterior temporal cortex, an area associated with semantic processing. We consider how our lesion site and behavioral observations have implications for theoretical accounts of past tense production.

The effect of doubled CO2 and model basic state biases on the monsoon-ENSO system. II: Changing ENSO regimes

Integrations of a fully-coupled climate model with and without flux adjustments in the equatorial oceans are performed under 2×CO2 conditions to explore in more detail the impact of increased greenhouse gas forcing on the monsoon-ENSO system. When flux adjustments are used to correct some systematic model biases, ENSO behaviour in the modelled future climate features distinct irregular and periodic (biennial) regimes. Comparison with the observed record yields some consistency with ENSO modes primarily based on air-sea interaction and those dependent on basinwide ocean wave dynamics. Simple theory is also used to draw analogies between the regimes and irregular (stochastically forced) and self-excited oscillations respectively. Periodic behaviour is also found in the Asian-Australian monsoon system, part of an overall biennial tendency of the model under these conditions related to strong monsoon forcing and increased coupling between the Indian and Pacific Oceans. The tropospheric biennial oscillation (TBO) thus serves as a useful descriptor for the coupled monsoon-ENSO system in this case. The presence of obvious regime changes in the monsoon-ENSO system on interdecadal timescales, when using flux adjustments, suggests there may be greater uncertainty in projections of future climate, although further modelling studies are required to confirm the realism and cause of such changes.

A groove-ploughing theory for the production of mega-scale glacial lineations, and implications for ice-stream mechanics

Mega-scale glacial lineations (MSGLs) are longitudinally aligned corrugations (ridge-groove structures 6-100 km long) in sediment produced subglacially. They are indicators of fast flow and a common signature of ice-stream beds. We develop a qualitative theory that accounts for their formation, and use numerical modelling, and observations of ice-stream beds to provide supporting evidence. Ice in contact with a rough (scale of 10-10(3) m) bedrock surface will mimic the form of the bed. Because of flow acceleration and convergence in ice-stream onset zones, the ice-base roughness elements experience transverse strain, transforming them from irregular bumps into longitudinally aligned keels of ice protruding downwards. Where such keels slide across a soft sedimentary bed, they plough through the sediments, carving elongate grooves, and deforming material up into intervening ridges. This explains MSGLs and has important implications for ice-stream mechanics. Groove ploughing provides the means to acquire new lubricating sediment and to transport large volumes of it downstream. Keels may provide basal drag in the force budget of ice streams, thereby playing a role in flow regulation and stability We speculate that groove ploughing permits significant ice-stream widening, thus facilitating high-magnitude ice discharge.

Spatangoid-produced ichnofabrics (Bateig Limestone, Miocene, Spain) and the preservation of spatangoid trace fossils

A spatangoid-produced ichnofabric is described from the Miocene Bateig Limestone, SE Spain. This ichnofabric is characterized by the dominant presence of large meniscate burrows (Bichordites) produced by irregular echinoids. This constitutes an unusual mode of occurrence for spatangoid bioturbation, as their traces are most typically preserved in bases and tops of sandstone event beds. In fact, despite their important role as burrowers in modern settings (that can be extended back to the Early Cretaceous based on their body fossil record), spatangoid trace fossils (Scolicia and Bichordites) are comparatively rare. Several factors play an important role in their preservation: mechanism of burrowing, sediment characteristics, early diagenesis and presence/absence of deep-tier burrowers. Spatangoid-produced ichnofabrics, such as those from the Bateig Limestone, characterize depositional settings with intermittent deposition of event beds where there is an absence of deeper-tier bioturbation. (C) 2008 Elsevier B.V. All rights reserved

Wiggle-match dating of tree-ring sequences

Given the non-monotonic form of the radiocarbon calibration curve, the precision of single C-14 dates on the calendar timescale will always be limited. One way around this limitation is through comparison of time-series, which should exhibit the same irregular patterning as the calibration curve. This approach can be employed most directly in the case of wood samples with many years growth present (but not able to be dated by dendrochronology), where the tree-ring series of unknown date can be compared against the similarly constructed C-14 calibration curve built from known-age wood. This process of curve-fitting has come to be called "wiggle-matching." In this paper, we look at the requirements for getting good precision by this method: sequence length, sampling frequency, and measurement precision. We also look at 3 case studies: one a piece of wood which has been independently dendrochronologically dated, and two others of unknown age relating to archaeological activity at Silchester, UK (Roman) and Miletos, Anatolia (relating to the volcanic eruption at Thera).

Trace fossils and pseudofossils from the Wealden strata (non-marine Lower Cretaceous) of southern England

The trace fossils of the Wealden (non-marine Lower Cretaceous) of southern England are described. Sixteen invertebrate ichnotaxa include Agrichnium fimbriatus, Beaconites antarcticus, B. barretti, Cochlichnus anguineus, Diplichnites triassicus, Diplocraterion parallelum, Lockeia siliquaria, L. serialis, Monocraterion cf. tentaculum, Palaeophycus striatus, P. tubularis, Planolites montanus, Protovirgularia rugosa, Rhizocorallium isp., Scoyenia cf. gracilis, Unisulcus minutus, insect and root traces. Tetrapod tracks and trackways include tridactyl Iguanodontipus burreyi and other ornithopods, theropod, and tetradactyl sauropod (or possibly ankylosaur), together with extensive dinosaur tramplings. Coprolites are referred to two broad types: spiral, with or without included fish scales (attributable to sharks), and elongate and irregular (possibly produced by reptiles). A skinprint and two types of pseudofossil are also included. Five environmental associations are recognised: (1) lacustrine/lagoonal; (2) brackish incursions (flooding events) into the lacustrine/lagoonal environment; (3) a marginal lacustrine association with fluvial input; (4) a fluvial (lacustrine delta) association; (5) floodplain sediments (seasonal wetlands). These associations are assigned to the fluvial-lacustrine Scoyenia Ichnofacies and the incursions to Glossifungites lchnofacies. (c) 2005 Elsevier Ltd. All rights reserved.

Hiatal surfaces from the Miocene Globigerina Limestone Formation of Malta: Biostratigraphy, sedimentology, trace fossils and early diagenesis

The Miocene Globigerina Limestone of the Maltese islands contains widespread omission surfaces with very different characteristics and origins. The terminal Lower Globigerina Limestone hardground (TLGLHg) formed during a period of falling sea level. Coccolith assemblages suggest shallowness. Sedimentary structures and trace fossil assemblages, indicate increasing frequency of storm events and erosional episodes, towards the surface. Calcite cementation which took place around Thalassinoides burrows and formed irregular nodules was followed by dissolution of aragonite. It is suggested that lithification was linked to microbial reactions involving organic matter. In contrast two later surfaces, the terminal Middle Globigerina Limestone omissionground (TMGLOg), which marks the Lower to Middle Miocene boundary, and the Fomm-ir-Rih local hardground (FiRLHg) both contain early diagenetic dolomite. Lithification took place in two phases. The dolomite is interpreted to have formed beneath the sea floor: it was subsequently exhumed and partially corroded as the precipitation of calcitic and phosphatic cements took place around burrows open to the circulation of sea water. (C) 2008 Elsevier B.V. All rights reserved.

Production of tense marking in successive bilingual children: when do they converge with their monolingual peers?

Children with English as a second language (L2) with exposure of 18 months or less exhibit similar difficulties to children with Specific Language Impairment in tense marking, a marker of language impairment for English. This paper examines whether L2 children with longer exposure converge with their monolingual peers in the production of tense marking. 38 Turkish-English L2 children with a mean age of 7;8 and 33 monolingual age-matched controls completed the screening test of the Test of Early Grammatical Impairment (TEGI). The L2 children as a group were as accurate as the controls in the production of -ed, but performed significantly lower than the controls in the production of third person –s. Age and YoE affected the children’s performance. The highest age-expected performance on the TEGI was attested in eight and nine year-old children who had 4-6 YoE. L1 and L2 children performed better in regular compared to irregular verbs, but L2 children overregularized more than L1 children and were less sensitive to the phonological properties of verbs. The results show that tense marking and the screening test of the TEGI may be promising for differential diagnosis in eight and nine year-old L2 children with at least four YoE.

Dynamic load balancing for the distributed mining of molecular structures

In molecular biology, it is often desirable to find common properties in large numbers of drug candidates. One family of methods stems from the data mining community, where algorithms to find frequent graphs have received increasing attention over the past years. However, the computational complexity of the underlying problem and the large amount of data to be explored essentially render sequential algorithms useless. In this paper, we present a distributed approach to the frequent subgraph mining problem to discover interesting patterns in molecular compounds. This problem is characterized by a highly irregular search tree, whereby no reliable workload prediction is available. We describe the three main aspects of the proposed distributed algorithm, namely, a dynamic partitioning of the search space, a distribution process based on a peer-to-peer communication framework, and a novel receiverinitiated load balancing algorithm. The effectiveness of the distributed method has been evaluated on the well-known National Cancer Institute’s HIV-screening data set, where we were able to show close-to linear speedup in a network of workstations. The proposed approach also allows for dynamic resource aggregation in a non dedicated computational environment. These features make it suitable for large-scale, multi-domain, heterogeneous environments, such as computational grids.

A customizable multi-agent system for distributed data mining

We present a general Multi-Agent System framework for distributed data mining based on a Peer-to-Peer model. Agent protocols are implemented through message-based asynchronous communication. The framework adopts a dynamic load balancing policy that is particularly suitable for irregular search algorithms. A modular design allows a separation of the general-purpose system protocols and software components from the specific data mining algorithm. The experimental evaluation has been carried out on a parallel frequent subgraph mining algorithm, which has shown good scalability performances.