Secondary attribute retrieval using tree data structures

Several techniques are known for searching an ordered collection of data. The techniques and analyses of retrieval methods based on primary attributes are straightforward. Retrieval using secondary attributes depends on several factors. For secondary attribute retrieval, the linear structures—inverted lists, multilists, doubly linked lists—and the recently proposed nonlinear tree structures—multiple attribute tree (MAT), K-d tree (kdT)—have their individual merits. It is shown in this paper that, of the two tree structures, MAT possesses several features of a systematic data structure for external file organisation which make it superior to kdT. Analytic estimates for the complexity of node searchers, in MAT and kdT for several types of queries, are developed and compared.

A comparative study of multiple attribute tree and inverted file structures for large bibliographic files

A variety of data structures such as inverted file, multi-lists, quad tree, k-d tree, range tree, polygon tree, quintary tree, multidimensional tries, segment tree, doubly chained tree, the grid file, d-fold tree. super B-tree, Multiple Attribute Tree (MAT), etc. have been studied for multidimensional searching and related problems. Physical data base organization, which is an important application of multidimensional searching, is traditionally and mostly handled by employing inverted file. This study proposes MAT data structure for bibliographic file systems, by illustrating the superiority of MAT data structure over inverted file. Both the methods are compared in terms of preprocessing, storage and query costs. Worst-case complexity analysis of both the methods, for a partial match query, is carried out in two cases: (a) when directory resides in main memory, (b) when directory resides in secondary memory. In both cases, MAT data structure is shown to be more efficient than the inverted file method. Arguments are given to illustrate the superiority of MAT data structure in an average case also. An efficient adaptation of MAT data structure, that exploits the special features of MAT structure and bibliographic files, is proposed for bibliographic file systems. In this adaptation, suitable techniques for fixing and ranking of the attributes for MAT data structure are proposed. Conclusions and proposals for future research are presented.

Bayesian and Decision Tree Approaches for Pattern Recognition Including Feature Measurement Costs

The minimum cost classifier when general cost functionsare associated with the tasks of feature measurement and classification is formulated as a decision graph which does not reject class labels at intermediate stages. Noting its complexities, a heuristic procedure to simplify this scheme to a binary decision tree is presented. The optimizationof the binary tree in this context is carried out using ynamicprogramming. This technique is applied to the voiced-unvoiced-silence classification in speech processing.

Tree-ring based hydroclimate reconstruction over northern Vietnam from Fokienia hodginsii: eighteenth century mega-drought and tropical Pacific influence

We present here the first statistically calibrated and verified tree-ring reconstruction of climate from continental Southeast Asia.The reconstructed variable is March-May (MAM) Palmer Drought Severity Index (PDSI) based on ring widths from 22 trees (42 radial cores) of rare and long-lived conifer, Fokienia hodginsii (Po Mu as locally called) from northern Vietnam. This is the first published tree ring chronology from Vietnam as well as the first for this species. Spanning 535 years, this is the longest cross-dated tree-ring series yet produced from continental Southeast Asia. Response analysis revealed that the annual growth of Fokienia at this site was mostly governed by soil moisture in the pre-monsoon season. The reconstruction passed the calibration-verification tests commonly used in dendroclimatology, and revealed two prominent periods of drought in the mid-eighteenth and late-nineteenth enturies. The former lasted nearly 30 years and was concurrent with a similar drought over northwestern Thailand inferred from teak rings, suggesting a ``mega-drought'' extending across Indochina in the eighteenth century. Both of our reconstructed droughts are consistent with the periods of warm sea surface temperature (SST)anomalies in the tropical Pacific. Spatial correlation analyses with global SST indicated that ENSO-like anomalies might play a role in modulating droughts over the region, with El Nio (warm) phases resulting in reduced rainfall. However, significant correlation was also seen with SST over the Indian Ocean and the north Pacific,suggesting that ENSO is not the only factor affecting the climate of the area. Spectral analyses revealed significant peaks in the range of 53.9-78.8 years as well as in the ENSO-variability range of 2.0 to 3.2 years.

An (O)over-tilde(mn) Gomory-Hu Tree Construction Algorithm for Unweighted Graphs

We present a fast algorithm for computing a Gomory-Hu tree or cut tree for an unweighted undirected graph G = (V, E). The expected running time of our algorithm is (O) over tilde (mc) where vertical bar E vertical bar = m and c is the maximum u-v edge connectivity, where u, v is an element of V. When the input graph is also simple (i.e., it has no parallel edges), then the u-v edge connectivity for each pair of vertices u and v is at most n - 1; so the expected run-ning time of our algorithm for simple unweighted graphs is (O) over tilde (mn). All the algorithms currently known for constructing a Gomory-Hu tree [8, 9] use n - 1 minimum s-t cut (i.e., max flow) subroutines. This in conjunction with the current fastest (O) over tilde (n(20/9)) max flow algorithm due to Karger and Levine[11] yields the current best running time of (O) over tilde (n(20/9)n) for Gomory-Hu tree construction on simple unweighted graphs with m edges and n vertices. Thus we present the first (O) over tilde (mn) algorithm for constructing a Gomory-Hu tree for simple unweighted graphs. We do not use a max flow subroutine here; we present an efficient tree packing algorithm for computing Steiner edge connectivity and use this algorithm as our main subroutine. The advantage in using a tree packing algorithm for constructing a Gomory-Hu tree is that the work done in computing a minimum Steiner cut for a Steiner set S subset of V can be reused for computing a minimum Steiner cut for certain Steiner sets S' subset of S.

Effect of rodents on seed fate of five hornbill-dispersed tree species in a tropical forest in north-east India

Hornbills are important dispersers of a wide range of tree species. Many of these species bear fruits with large, lipid-rich seeds that could attract terrestrial rodents. Rodents have multiple effects on seed fates, many of which remain poorly understood in the Palaeotropics. The role of terrestrial rodents was investigated by tracking seed fate of five horn bill-dispersed tree species in a tropical forest in north-cast India. Seeds were marked inside and outside of exclosures below 6-12 parent fruiting trees (undispersed seed rain) and six hornbill nest trees (a post-dispersal site). Rodent visitors and seed removal ere monitored using camera traps. Our findings suggest that several rodent species. especially two species of porcupine were major on-site seed predators. Scatter-hoarding was rare (1.4%). Seeds at hornbill nest trees had lower survival compared with parent fruiting trees, indicating that clumped dispersal by hornbills may not necessarily improve seed survival. Seed survival in the presence and absence of rodents varied with tree species. Some species (e.g. Polyalthia simiarum) showed no difference, others (e.g. Dysoxylum binectariferum) experienced up to a 64%. decrease in survival in the presence of rodents. The differing magnitude of seed predation by rodents can have significant consequences at the seed establishment stage.

Optical, radiative, and source characteristics of aerosols at Minicoy, a remote island in the southern Arabian Sea

Extensive measurements of aerosol radiative and microphysical properties were made at an island location, Minicoy (8.3 degrees N, 73.04 degrees E) in the southern Arabian Sea. A large variability in aerosol characteristics associated with changes in air mass and precipitation characteristics was observed. Six distinct transport pathways were identified on the basis of cluster analysis. The Indo-Gangetic Plain, along with the northern Arabian Sea and west Asia (NWA), was identified to be the region having the highest potential for aerosol mass loading at the island. This estimate is based on the concentration weighted trajectory as well as cluster analysis. Dust transport from the NWA region was found to make a substantial contribution to the supermicron mass fraction. The black carbon mass mixing ratios observed were the lowest compared to previous measurements over this region. Consequently, the atmospheric radiative forcing efficiency was low and was in the range 10-28 W m(-2).

Formation of a novel surface structure encoded by Salmonella Pathogenicity Island 2.

The type III secretion system (T3SS) encoded by Salmonella Pathogenicity Island 2 (SPI2) is essential for virulence and intracellular proliferation of Salmonella enterica. We have previously identified SPI2-encoded proteins that are secreted and function as a translocon for the injection of effector proteins. Here, we describe the formation of a novel SPI2-dependent appendage structure in vitro as well as on the surface of bacteria that reside inside a vacuole of infected host cells. In contrast to the T3SS of other pathogens, the translocon encoded by SPI2 is only present singly or in few copies at one pole of the bacterial cell. Under in vitro conditions, appendages are composed of a filamentous needle-like structure with a diameter of 10 nm that was sheathed with secreted protein. The formation of the appendage in vitro is dependent on acidic media conditions. We analyzed SPI2-encoded appendages in infected cells and observed that acidic vacuolar pH was not required for induction of SPI2 gene expression, but was essential for the assembly of these structures and their function as translocon for delivery of effector proteins.

Functional transfer of Salmonella pathogenicity island 2 to Salmonella bongori and Escherichia coli.

The type III secretion system (T3SS) encoded by the Salmonella pathogenicity island 2 (SPI2) has a central role in systemic infections by Salmonella enterica and for the intracellular phenotype. Intracellular S. enterica uses the SPI2-encoded T3SS to translocate a set of effector proteins into the host cell, which modify host cell functions, enabling intracellular survival and replication of the bacteria. We sought to determine whether specific functions of the SPI2-encoded T3SS can be transferred to heterologous hosts Salmonella bongori and Escherichia coli Mutaflor, species that lack the SPI2 locus and loci encoding effector proteins. The SPI2 virulence locus was cloned and functionally expressed in S. bongori and E. coli. Here, we demonstrate that S. bongori harboring the SPI2 locus is capable of secretion of SPI2 substrate proteins under culture conditions, as well as of translocation of effector proteins under intracellular conditions. An SPI2-mediated cellular phenotype was induced by S. bongori harboring the SPI2 if the sifA locus was cotransferred. An interference with the host cell microtubule cytoskeleton, a novel SPI2-dependent phenotype, was observed in epithelial cells infected with S. bongori harboring SPI2 without additional effector genes. S. bongori harboring SPI2 showed increased intracellular persistence in a cell culture model, but SPI2 transfer was not sufficient to confer to S. bongori systemic pathogenicity in a murine model. Transfer of SPI2 to heterologous hosts offers a new tool for the study of SPI2 functions and the phenotypes of individual effectors.

Salmonella pathogenicity island 2 mediates protection of intracellular Salmonella from reactive nitrogen intermediates.

Salmonella typhimurium causes an invasive disease in mice that has similarities to human typhoid. A type III protein secretion system encoded by Salmonella pathogenicity island 2 (SPI2) is essential for virulence in mice, as well as survival and multiplication within macrophages. Reactive nitrogen intermediates (RNI) synthesized by inducible nitric oxide synthase (iNOS) are involved in the control of intracellular pathogens, including S. typhimurium. We studied the effect of Salmonella infection on iNOS activity in macrophages. Immunofluorescence microscopy demonstrated efficient colocalization of iNOS with bacteria deficient in SPI2 but not wild-type Salmonella, and suggests that the SPI2 system interferes with the localization of iNOS and Salmonella. Furthermore, localization of nitrotyrosine residues in the proximity was observed for SPI2 mutant strains but not wild-type Salmonella, indicating that peroxynitrite, a potent antimicrobial compound, is excluded from Salmonella-containing vacuoles by action of SPI2. Altered colocalization of iNOS with intracellular Salmonella required the function of the SPI2-encoded type III secretion system, but not of an individual "Salmonella translocated effector." Inhibition of iNOS increased intracellular proliferation of SPI2 mutant bacteria and, to a lesser extent, of wild-type Salmonella. The defect in systemic infection of a SPI2 mutant strain was partially restored in iNOS(-/-) mice. In addition to various strategies to detoxify RNI or repair damage due to RNI, avoidance of colocalization with RNI is important in adaptation of a pathogen to an intracellular life style.

Mechanical response of the tympanal membranes of the tree cricket Oecanthus henryi

Crickets have two tympanal membranes on the tibiae of each foreleg. Among several field cricket species of the genus Gryllus (Gryllinae), the posterior tympanal membrane (PTM) is significantly larger than the anterior membrane (ATM). Laser Doppler vibrometric measurements have shown that the smaller ATM does not respond as much as the PTM to sound. Hence the PTM has been suggested to be the principal tympanal acoustic input to the auditory organ. In tree crickets (Oecanthinae), the ATM is slightly larger than the PTM. Both membranes are structurally complex, presenting a series of transverse folds on their surface, which are more pronounced on the ATM than on the PTM. The mechanical response of both membranes to acoustic stimulation was investigated using microscanning laser Doppler vibrometry. Only a small portion of the membrane surface deflects in response to sound. Both membranes exhibit similar frequency responses, and move out of phase with each other, producing compressions and rarefactions of the tracheal volume backing the tympanum. Therefore, unlike field crickets, tree crickets may have four instead of two functional tympanal membranes. This is interesting in the context of the outstanding question of the role of spiracular inputs in the auditory system of tree crickets.

Relationship between annual rainfall and tree mortality in a tropical dry forest: Results of a 19-year study at Mudumalai, southern India

Variability in rainfall is known to be a major influence on the dynamics of tropical forests, especially rates and patterns of tree mortality. In tropical dry forests a number of contributing factors to tree mortality, including dry season fire and herbivory by large herbivorous mammals, could be related to rainfall patterns, while loss of water potential in trees during the dry season or a wet season drought could also result in enhanced rates of death. While tree mortality as influenced by severe drought has been examined in tropical wet forests there is insufficient understanding of this process in tropical dry forests. We examined these causal factors in relation to inter-annual differences in rainfall in causing tree mortality within a 50-ha Forest Dynamics Plot located in the tropical dry deciduous forests of Mudumalai, southern India, that has been monitored annually since 1988. Over a 19-year period (1988-2007) mean annual mortality rate of all stems >1 cm dbh was 6.9 +/- 4.6% (range = 1.5-17.5%); mortality rates broadly declined from the smaller to the larger size classes with the rates in stems >30 cm dbh being among the lowest recorded in tropical forest globally. Fire was the main agent of mortality in stems 1-5 cm dbh, elephant-herbivory in stems 5-10 cm dbh, and other natural causes in stems > 10 cm dbh. Elephant-related mortality did not show any relationship to rainfall. On the other hand, fire-related mortality was significantly negatively correlated to quantity of rainfall during the preceding year. Mortality due to other causes in the larger stem sizes was significantly negatively correlated to rainfall with a 2-3-year lag, suggesting that water deficit from mild or prolonged drought enhanced the risk of death but only with a time lag that was greater than similar lags in tree mortality observed in other forest types. In this respect, tropical dry forests growing in regions of high rainfall variability may have evolved greater resistance to rainfall deficit as compared to tropical moist or temperate forests but are still vulnerable to drought-related mortality.

Shrewd alliances: mixed foraging associations between treeshrews,greater racket-tailed drongos and sparrowhawks on Great Nicobar Island, India

Mixed-species foraging associations may form to enhance feeding success or to avoid predators. We report the costs and consequences of an unusual foraging association between an endemic foliage gleaning tupaid (Nicobar treeshrew Tupaia nicobarica) and two species of birds; one an insectivorous commensal (greater racket-tailed drongo Dicrurus paradiseus) and the other a diurnal raptor and potential predator (Accipiter sp.). In an alliance driven, and perhaps engineered, by drongos, these species formed cohesive groups with predictable relationships. Treeshrew breeding pairs were found more frequently than solitary individuals with sparrowhawks and were more likely to tolerate sparrowhawks in the presence of drongos. Treeshrews maintained greater distances from sparrowhawks than drongos, and permitted the raptors to come closer when drongos were present. Treeshrew foraging rates declined in the presence of drongos; however, the latter may provide them predator avoidance benefits. The choice of the raptor to join the association is intriguing; particular environmental resource states may drive the evolution of such behavioural strategies. Although foraging benefits seem to be the primary driver of this association, predator avoidance also influences interactions, suggesting that strategies driving the formation of flocks may be complex and context dependent with varying benefits for different actors.

An efficient reduction algorithm for computation of interconnect delay variability for statistical timing analysis in clock tree planning

In this paper, we propose a novel and efficient algorithm for modelling sub-65 nm clock interconnect-networks in the presence of process variation. We develop a method for delay analysis of interconnects considering the impact of Gaussian metal process variations. The resistance and capacitance of a distributed RC line are expressed as correlated Gaussian random variables which are then used to compute the standard deviation of delay Probability Distribution Function (PDF) at all nodes in the interconnect network. Main objective is to find delay PDF at a cheaper cost. Convergence of this approach is in probability distribution but not in mean of delay. We validate our approach against SPICE based Monte Carlo simulations while the current method entails significantly lower computational cost.