bluuebunny/crossref_metadata_2025 huggingface dataset:
DFT STUDY ON THE MECHANISM OF DNA DAMAGE CAUSED BY THE ISOMERIZATION OF DNA PURINE BASE
Authors: LIN XIANJIE , WANG QIANG , WU JIAN , LIU CHENGBU
Published: September 2008

The mechanism of DNA damage caused by the isomerization of purine base is studied with density functional theory calculations at the B3LYP/6-311+G(d,p) level. The transition states of all the isomerizations are obtained, and the intrinsic reaction coordinate (IRC) analyses are performed to identify these transition states further. The isomerizations of purine bases can be classified into two types. The first is the hydrogen transfer between atoms, whose transition state includes a four-member ring. The second is the bond N–H rotation about the double bond N=C , and the plane CNH is perpendicular to the molecular plane in its transition state. The hydrogen transfer has higher reaction potential barrier, larger tunnel effect, and smaller equilibrium constant and rate constant than that of the N–H rotation. Effects of the hydration are considered in the framework of the polarizable continuum model (PCM) in SCRF method at the B3LYP/6-311+G(d,p) level. The isomerizations which result in the configuration changes of purine base and bring directly the DNA damage are endothermic and thermodynamic nonspontaneous processes. The probability of DNA damage caused by the guanine isomerization is larger than that by adenine.
DESIGN OF HYBRID INHIBITORS TO HIV-1 PROTEASE
Authors: ZHANG DA W. , HUANG PHILIP LIN , LEE-HUANG SYLVIA , ZHANG JOHN Z. H.
Published: September 2008

A series of HIV-1 protease (PR) inhibitors are designed to increase the binding affinity with PR subsites based on the quantum analysis of the contributions of molecular fragments in six FDA-approved PR drugs to the total binding interaction. The binding free energies were estimated by modified linear interaction energy approach [Zoete H, Michielin O, Karplus M, J Comput Aided Mol Des17:861, 2003], in which the binding free energy is written as a linear combination of the electrostatic interaction energy between PR and the ligand, Eelec, the van der Waals interaction energy between PR and the ligand, E vdW , and the difference of the solvation free energies of the complex, the receptor and the isolated ligand, ΔG solv . The parameters of these energy terms were fitted for a training set of 14 HIV-1 protease–inhibitor complexes of known 3D structure with a correlation coefficient of 0.91 and an unsigned mean error of 0.83 kcal/mol.
STRUCTURE AND PROPERTIES OF PERFLUOROALKYLATED PHTHALOCYANINES: A THEORETICAL STUDY
Authors: LIAO MENG-SHENG , WATTS JOHN D. , GORUN SERGIU M. , SCHEINER STEVE , HUANG MING-JU
Published: September 2008

Density functional theory (DFT) calculations are performed on a series of peripherally substituted free-base and fluorinated zinc phthalocyanines, namely F n Pc M (M = 2 H , Zn ; n = 16, 32, 48, 64). F 16 Pc M, F 32 Pc M, and F 48 Pc M all prefer a planar skeletal structure of the metallomacrocycle core. In the case of F 64 Pc , F 64 PcZn remains planar but F 64 PcH 2 is domed. The occurrence of a dome distortion appears to be related, at least in part, to the orientation of the isopropyl - C 3 F 7 substituents as well as to the intermolecular (packing) interactions. The trends in the calculated results of the Pc 2-– M 2+ binding energy, polarizabilities, and electron excitation energies in H 16 Pc M, F 16 Pc M, and F 64 Pc M are in agreement with the experimental observations, as are the geometrical features. It is further confirmed that the simpler F 32 Pc M or F 48 Pc M mimic the basic electronic properties of F64 Pc M .
STRUCTURE AND STABILITY OF MONOCYCLIC $({\rm CH})_{4-n} ({\rm BL})_{n}^{2-}$(L = CO, N2, CS) DIANIONS AND THEIR DILITHIUM COMPLEXES
Authors: WU HAI-SHUN , QIN XIAO-FANG , JIAO HAIJUN
Published: September 2008

Structure and stability of monocyclic [Formula: see text] dianions ( L = CO , N 2, CS ) with 6π-electrons, which are isolobal with cyclobutadiene dianion [Formula: see text], have been investigated at the B3LYP and CCSD(T) levels of theory. ( CH )3( BL )2- have non-planar singlet ground states. [Formula: see text] have planar singlet ground states, while [Formula: see text] isomers have folded four-membered central rings. Both [Formula: see text] and [Formula: see text] have planar ground states, the ground state of [Formula: see text] has a six-membered ring with two bridging and one terminal CS. Both [Formula: see text] and [Formula: see text] have reduced aromaticity compared to [Formula: see text] as indicated by the less negative nucleus independent chemical shifts (NICS) values. The mono-, di- and trisubstituted ( CH )3( BL )2-, [Formula: see text], and [Formula: see text] also have reduced aromaticity, while the 1,3-substituted [Formula: see text] have positive NICS values due to the localization of the negative charge at the ring carbon centers. In addition, the electrostatic stabilization of Li + in favor of the singlet or triplet states depends on the nature of their structures.
AN ACCURATE QUANTUM DYNAMICS STUDY OF THE N+OH REACTION
Authors: GE MEI-HUA , CHU TIAN-SHU , HAN KE-LI
Published: September 2008

Using time-dependent quantum wave packet method, the total reaction probabilities and thermal rate constants (TRC) are calculated for the exoergic reaction N+OH on the 3A″ potential energy surface (Guadagnini R, Schatz GC, Walch SP, J Chem Phys102:774, 1995) under both coupled-state or centrifugal sudden (CS) approximation and Coriolis-coupled or close-coupling (CC) approach. As a result, the difference between CS and CC total reaction probabilities gets more prominent when the value of total angular momentum J increases. As for TRC, the calculated results are in excellent agreement with earlier experimental measurements.
QUANTUM PARAMETRIC RESONANCE: ANALYTICAL STUDIES
Authors: SHAO JIUSHU
Published: September 2008

The quantum version of parametric resonance of the harmonic oscillator is studied in terms of Feynman's propagator method and a discrete map. The eigenfunctions and eigenvalues of the Floquet operator are derived explicitly. The solutions follow the general laws: In the regions of parametric resonance the spectrum of the Floquet operator becomes continuous, while it is pointlike in the stable regimes. The Gaussian wave packet undergoes spreading exponentially and linearly in the two regimes, respectively.
THEORETICAL STUDY OF NITROGEN MONOXIDE ADSORPTION ON RHODIUM CLUSTERS AT DIFFERENT SITES
Authors: CHEN JIAN , TAN KAI , LIN MENG-HAI
Published: September 2008

The adsorption of nitrogen monoxide NO with charged and neutral [Formula: see text] clusters at atop, bridge, and threefold hollow sites had been investigated by density functional theory calculations. The results showed that rhodium clusters had strong orbital interactions with NO and formed the complex [ RhnNO ]-/0/+. The stretching vibrational frequencies of the N–O bonds changed with the different adsorption sites and clusters sizes. The interactions between rhodium clusters and NO molecular could be described through the donation and back-donation of their frontier orbitals. The more back donation from Rh to NO , the weaker the N–O bonds, exhibiting that the lengthening of the N–O bond length and the lowering of its vibrational frequency. In general, the donation and back-donation interactions followed the tendencies: anionic > neutral > cationic, big size > small size, threefold hollow site > bridge site > atop site.
MOLECULAR DYNAMICS STUDIES OF CRAMBIN AND BPTI IN TERMS OF ABEEM/MM METHOD
Authors: YANG ZHONG-ZHI , GUAN QING-MEI , ZHAO DONG-XIA
Published: September 2008

Recently, the ABEEM/MM method (atom-bond electronegativity equalization method fused into molecular mechanics) has successfully been applied to study polypeptide conformations. In order to further test the reliability of this method as well as the transferability of the parameters (including ABEEM and force field parameters), molecular dynamics simulation studies on Crambin and BPTI (298 K, in vacuo) have been performed in terms of ABEEM/MM fluctuating charge force field. Some of their structural properties were obtained, and relative to the X-ray structures, the root-mean-square deviations (RMSD) of bond lengths, bond angles and key dihedral angles, and the coordinate RMSDs of atoms were calculated. The ABEEM/MM results are fairly consistent with those from X-ray experiment.
HYDRATION FREE ENERGY AND ABSORPTION SPECTRUM OF AN EXTRA ELECTRON IN WATER BY QUANTUM-CONTINUUM MODEL
Authors: WANG XING-JIAN , ZHU QUAN , LI XIANG-YUAN
Published: September 2008

In this paper, the hydration energy of electron and absorption spectrum at room temperature have been estimated by quantum-continuum model. Taking a number of negatively charged water clusters as the quantum part, the hydration energy is calculated at high levels associated with IPCM and IEFPCM. The optical absorption spectrum is calculated by TDDFT with different basis sets. The vertical detachment energy and cluster reorganization energy in gas phase are also investigated. The results have been discussed by comparing with the experimental observations.
POLARIZABILITY AND SHIELDING OF COAXIAL HYBRID DOUBLE-WALLED NANOTUBES: A FIRST-PRINCIPLES STUDY
Authors: LI NUANXIANG , LI QUNXIANG , SU HAIBIN , SHI Q. W. , YANG JINLONG
Published: September 2008

First-principles studies on electronic structures, transverse polarizability, and shielding of two coaxial hybrid double-walled nanotubes consisting of carbon nanotube (CNT) and boron nitride nanotube (BNNT), namely CNT@BNNT and BNNT@CNT, are conducted. The interaction between inner and outer tubes is considerably weak. The polarizability of single-walled CNT is larger than that of single-walled BNNT due to the different electronic properties. In BNNT@CNT, the outer CNT with delocalized π-electrons character demonstrates a nearly complete shielding with the order of 90% of the inner BNNT from the transverse external electric field, while the outer BNNT has a relative small shielding of about 40% for the inner CNT in CNT@BNNT system. Moreover, the shielding of the outer tube can be appreciably enhanced by increasing the intertube separation.
REDUCED MULTIREFERENCE COUPLED-CLUSTER METHOD AND ITS APPLICATION TO THE PYRIDYNE DIRADICALS
Authors: LI XIANGZHU , PALDUS JOSEF
Published: September 2008

The reduced multireference (RMR) coupled-cluster (CC) method with singles and doubles (RMR CCSD) that employs a modest-size MR CISD wave function as an external source for the most important (primary) triples and quadruples in order to account for the nondynamic correlation effects in the presence of quasidegeneracy, and which is further perturbatively corrected for the remaining (secondary) triples, RMR CCSD(T), is employed to compute the molecular geometry and the energy of the lowest-lying singlet and triplet states, as well as the corresponding singlet–triplet splitting, for all possible isomers of the m, n-pyridyne diradicals. A comparison is made with earlier results that were obtained by other authors, and the role of the multireference effects for both the geometry and the spin multiplicity of the lowest state, as described by the RMR-type methods, is demonstrated on the example of 2,6- and 3,5-pyridynes.
A THEORETICAL STUDY ON DUAL FLUORESCENCE OF 4-DIMETHYLAMINOPYRIDINE BY POLARIZABLE CONTINUUM MODEL
Authors: LI JUAN-QIN , LI XIANG-YUAN , WANG FENG
Published: September 2008

Dual fluorescence spectra of 4-dimethylaminopyridine (DMAP) is investigated using time-dependent density functional theory and complete active space self-consistent field methods. Electronic absorption and emission spectra of DMAP have been investigated in three solvents, that is, cyclohexane, chloroform, and acetonitrile. The present study reveals that the dual fluorescence phenomena of DMAP appear in the cases of acetonitrile and chloroform, but not in cyclohexane. The electronic structures of the ground state and the intramolecular charge transfer states are, therefore, studied in order to reveal the insight of dual fluorescence. Our theoretical results suggest that the twisting of dimethylamino moiety in DMAP is necessary for the intramolecular charge transfer. The mechanism of the dual fluorescence of DMAP is discussed based on the twisted intramolecular charge transfer model and the dual fluorescence phenomenon is explained theoretically.
DENSITY MATRIX ANALYSIS AND SIMULATION OF ELECTRON DYNAMICS IN MULTIPLE-BRIDGED DONOR/ACCEPTOR MOLECULES UNDER DISSIPATIVE ENVIRONMENTS
Authors: ZHAO YI
Published: September 2008

Feynman and Vernon path integral approach is adopted to investigate electron transfer dynamics in donor–bridge–acceptor molecules under dissipative environments. Especially, we focus on the solvent effect on the superexchange process of electron transfer. The results reveal that at high enough bridge energies or low enough temperature, electron can transfer with a superexchange mechanism no matter whether solvent is incorporated or not. However, the superexchange changes from coherent to incoherent limits when the dissipative strength increases, and electron transfer rates are much dependent on the dissipative strength.
The carbon and oxygen stable isotopic composition of cultured benthic foraminifera
Authors: McCorkle Daniel C. , Bernhard Joan M. , Hintz Christopher J. , Blanks Jessica K. , Chandler G. Thomas , Shaw Timothy J.
Published: September 2008

Laboratory cultures of several species of benthic foraminifera were grown under controlled physical and chemical conditions during months-long experiments carried out at the University of South Carolina in 2001 and 2002. A dozen experimental culture chambers contained a
c
. 1–3 mm layer of trace-metal free silica substrate, and were continuously flushed with water from a large (1600 L) seawater reservoir with known, constant temperature and composition (δ
18
O(water), carbonate system chemistry, and trace element concentrations). Each year, in most of the culture chambers, one or more species reproduced, producing hundreds of juveniles which grew into size classes ranging from 100 to 500 microns.
Bulimina aculeata
was the most successful species in the 2001 cultures, and both
B. aculeata
and
Rosalina vilardeboana
were abundant in 2002.

We determined the shell C and O isotopic composition of the cultured foraminifera, and compared these isotopic values with the water chemistry of the culture chambers, and also with the shell chemistry of field specimens collected from sites on the North Carolina and South Carolina (USA) continental margin. The cultured foraminifera showed substantial offsets from the δ
13
C of system water dissolved inorganic carbon (−0.5 to −2.5‰, depending on species) and smaller offsets (0 to −0.5‰) from the predicted δ
18
O of calcite in equilibrium with the culture system water at the growth temperature. These offsets reflect at least three factors: species-dependent vital effects; ontogenetic variations in shell chemistry; and the aqueous carbonate chemistry ([CO
3
−
] or pH) of the experimental system.
Seasonal dynamics of coastal water masses in a Scottish fjord and their potential influence on benthic foraminiferal shell geochemistry
Authors: Cage Alix G. , Austin William E. N.
Published: September 2008

Pronounced seasonal heating of middle and high latitude shelf seas results in large temporal changes in seawater temperature that have the potential to be recorded by benthic foraminifera. Predicted oxygen isotope composition for calcite precipitating in equilibrium conditions with seawater suggest that pronounced ‘seasonal isotope effects’ may be encountered in the growth history of benthic foraminifera. Such ‘seasonal’ effects can be difficult to distinguish from so-called ‘vital effects’, where shell and equilibrium calcite values are offset by a constant difference in oxygen isotope values. Preliminary findings suggest that benthic foraminifera may have more than one phase of growth, for example
Ammonia becarii
calcifies in spring and late summer, potentially introducing apparent intra-annual and inter-annual temperature variations of >1°C into palaeoclimatic reconstructions when mixed-season populations are sampled. We highlight the need to select species-specific palaeotemperature equations to establish reliable isotopic disequilibria and illustrate the importance of understanding the ‘seasonal isotope effect’ when considering disequilibrium effects in foraminifera which have grown in seasonally-changing environments.
Isotopic variability in the intertidal acorn barnacle
Semibalanus balanoides
: a potentially novel sea-level proxy indicator
Authors: Craven K. F. , Bird M. I. , Austin W. E. N. , Wynn J.
Published: September 2008

We report variations in the δ
13
C and δ
18
O values of barnacle skeletal carbonate as well as the δ
13
C and δ
15
N value of tissue from specimens of the acorn barnacle
S. balanoides
, as a function of elevation within its living range on the Isle of May, Scotland. Individuals were sampled over a 3.50 m range at 0.25 m intervals (1.00–4.50 m above ordnance datum). Carbonate δ
18
O values (2.44±0.13‰ [1σ], n=45) and tissue δ
15
N values (8.17±0.42‰, n=15) do not vary systematically with elevation. The δ
13
C value of shell carbonate increases with elevation by
c.
1‰ (total range: −0.77‰ to +0.63‰), but the variability between samples at the same elevation suggests that this relationship will be of limited use in constraining palaeo-elevation. By contrast, tissue δ
13
C values show systematic variation with elevation, increasing by
c
. 8‰ (total range: −19.36‰ to −8.77‰) with increasing elevation.

These results suggest that there is potential to use the tissue δ
13
C values to determine the elevation of a Fixed Biological Indicator (FBI) such as
S. balanoides
within its living range. If this is also true of the organic matrix of the carbonate skeleton, and if this organic matrix is preserved in Holocene FBIs, then the potential exists to use carbon isotopes to more precisely constrain the palaeo-elevation of FBIs within their living range and hence palaeo sea-level. The small range of carbonate δ
18
O values suggests that oxygen isotopes in FBIs can be used to constrain water δ
18
O values if an independent estimate of temperature is available, or temperature if an independent estimate of salinity is available.
Biogeochemical controls on palaeoceanographic environmental proxies: a review
Authors: James Rachael H. , Austin William E. N.
Published: September 2008

Scientific observations of our oceans and climate go back no more than a couple of hundred years. Most of our information about the evolution of Earth's ocean-climate system relies instead on proxies – primarily measurements of sediment components that respond to changes in environmental parameters. This paper provides an overview of some of the most important biological and geochemical proxies and outlines their contribution to our understanding of the ocean-climate system. We also discuss some of the challenges that need to be overcome to obtain accurate records. These include: better understanding of the controls on the mechanisms of biomineralization; the impacts of post-depositional dissolution and diagenesis on primary proxy relationships; proxy validation; and analytical considerations.
Some fundamental features of biomineralization
Authors: Williams R. J. P.
Published: September 2008

This contribution summarizes the considerations that are of major importance in inorganic mineral formation before we look at specific biological minerals. Some factors which have to be taken into account (other than those that are well-known from inorganic (abiological) precipitations) are: the nature of the biological organic matrix; the restricted volume, outside or inside the cytoplasm, which can cause differences in impurity content (Mg); crystal morphology; and isotopic fractionation. Cases such as those of corals, foraminifera and coccoliths are taken as examples.
Fine-scale growth patterns in coral skeletons: biochemical control over crystallization of aragonite fibres and assessment of early diagenesis
Authors: Cuif J. P. , Dauphin Y. , Meibom A. , Rollion-Bard C. , Salomé M. , Susini J. , Williams C. T.
Published: September 2008

Recent works have paved the way for an understanding of the scale at which environmental signals might be recorded in coral skeletons. In this paper, the resulting structural and chemical insights are exemplified by a
Goniastrea
corallite. The bulk of the coral skeleton consists of fibrous aragonite, which in turn is constructed by sequential growth of micrometre thick layers, oriented parallel to the local growth direction. These growth layers consist of nanograins (50–100 nm) of aragonite that appear to be crystallized in close association with a matrix, conceivably proteoglycans, which seem to coat individual nanograins. These observations contradict the traditional notion that coral fibre consists of ‘a single crystal of orthorhombic aragonite’.

Additionally, the ultrastructural observations provide us with criteria to assess early diagenetic effects. Some Lower Norian corals from South Anatolia (Turkey) display extremely well-preserved mineralogy and structures. They have also preserved the organic components of their skeletons from which it has been demonstrated, through a study of the Nitrogen isotopic composition, that photosynthesis was involved in the metabolism of these early Scleractinia. But even in these remarkably preserved corals, we find evidence for diagenetic changes at the nanometre scale, concerning both the amount of organic matrices and the appearance of the aragonitic nano-granular units. Such micro-structural observations call for caution when interpreting isotopic effects in the fossil coral record.
Modern deep-sea benthic foraminifera: a brief review of their morphology-based biodiversity and trophic diversity
Authors: Gooday A. J. , Nomaki H. , Kitazato H.
Published: September 2008

Most fossil deep-sea foraminifera are multichambered and have relatively robust, calcareous or agglutinated shells. Modern assemblages, on the other hand, include many fragile monothalamous (single-chambered) forms and komokiaceans (a superfamily of protist currently placed within the foraminifera) with soft test walls. These groups are poorly known and most of the hundreds of morphospecies recognized in deep-sea samples are undescribed. The relative abundance of robust and fragile taxa varies with water depth and food supply. Calcareous and other hard-shelled species tend to predominate in relatively eutrophic areas, particularly on continental margins, but decrease as a proportion of the ‘entire’ live fauna (i.e. including soft-shelled species) with increasing water depth, even above the CCD (carbonate compensation depth). Most of the species on which the foraminiferal proxies used in palaeoceanography are based live in these bathyal regions. At abyssal depths, and particularly below the CCD, faunas are largely agglutinated and dominated by monothalamous forms. These assemblages have a much lower fossilization potential than those found on continental margins. In addition to carbonate dissolution, these patterns probably reflect adaptations to increasingly oligotrophic conditions on the ocean floor with increasing depth and distance from land. Bathyal species include herbivores and opportunistic deposit feeders (omnivores) that consume labile organic material, in addition to deep-infaunal deposit feeders, and must contribute significantly to carbon cycling. Many abyssal monothalamous foraminifera, in constrast, accumulate stercomata (waste pellets composed of fine sediment particles) and probably ingest sediment, associated bacteria and more refractory organic matter. Some monothalamous species without stercomata may be bacteriovores. Although they probably process organic carbon at a slower rate than calcareous species, the shear abundance of monothalamous taxa at abyssal depths suggests that they are important in carbon cycling on a global scale. The loss of a substantial proportion of foraminiferal biomass and biodiversity from the fossil record should be considered when using foraminifera to reconstruct palaeoproductivity, for example, by using the Benthic Foraminiferal Accummulation Rate (BFAR). Different dietary preferences among calcareous species have implications for the stable carbon isotope signal preserved in their shells.
On the use of benthic foraminiferal δ
13
C in palaeoceanography: constraints from primary proxy relationships
Authors: Mackensen Andreas
Published: September 2008

Recent findings are reviewed from observations in the field on the generation of the δ
13
C signal in shells of live (Rose Bengal stained) benthic foraminifera, and end up with implications for the interpretation of fossil signatures. The δ
13
C values of calcite tests of preferentially epifaunal foraminifera principally reflect the δ
13
C of dissolved inorganic carbon (DIC) of ambient seawater, whereas infaunal species record a porewater signal, both with an offset from equilibrium calcite. Species occupying the deepest average living depth in the sediment usually exhibit lowest δ
13
C test values, but δ
13
C values of conspecific specimens at a single site do not decrease with increasing subbottom depth and decreasing porewater δ
13
C
DIC
. Organic carbon fluxes to the sediment surface are generally reflected by infaunal species such that lowered δ
13
C values coincide with high fluxes, but even strictly epifaunal species may reflect seasonally pulsed phytodetritus supply by depleted test δ
13
C. In high-productivity environments, however, where dissolved oxygen and sedimentary carbonate contents are low, benthic foraminiferal tests show
13
C enrichment probably due to carbonate-ion undersaturation. Ontogenetic increase in δ
13
C values of certain infaunal species suggests a slow-down of metabolic rates during test growth and decreasing fractionation with age. At sites of active methane discharge δ
13
C values of infaunal species reflect low pore water δ
13
C
DIC
values, documenting active methane release in the sediment, whereas lowered δ
13
C values of strictly epifaunal species are most probably the result of incorporation of
13
C depleted methanotrophic biomass.
Reasoning with recursive loops under the PLP framework
Authors: Shen Yi-Dong
Published: September 2008

Recursive loops in a logic program present a challenging problem to the PLP (Probabilistic Logic Programming) framework. On the one hand, they loop forever so that the PLP backward-chaining inferences would never stop. On the other hand, they may generate cyclic influences, which are disallowed in Bayesian networks. Therefore, in existing PLP approaches, logic programs with recursive loops are considered to be problematic and thus are excluded. In this article, we propose a novel solution to this problem by making use of recursive loops to build a stationary dynamic Bayesian network. We introduce a new PLP formalism, called a
Bayesian knowledge base
. It allows recursive loops and contains logic clauses of the form
A
← A
1
,…,

A
l

,
true
,
Context
,
Types
, which naturally formulate the knowledge that the

A
i

s have direct influences on
A
in the context
Context
under the type constraints
Types
. We use the well-founded model of a logic program to define the direct influence relation and apply SLG-resolution to compute the space of random variables together with their parental connections. This establishes a clear declarative semantics for a Bayesian knowledge base. We view a logic program with recursive loops as a special temporal model, where backward-chaining cycles of the form
A
← …
A
← … are interpreted as feedbacks. This extends existing PLP approaches, which mainly aim at (nontemporal) relational models.
Flat and one-variable clauses
Authors: Seidl Helmut , Verma Kumar Neeraj
Published: September 2008

Cryptographic protocols with single blind copying were defined and modeled by Comon and Cortier using the new class C of first-order clauses. They showed its satisfiability problem to be in 3-DEXPTIME. We improve this result by showing that satisfiability for this class is NEXPTIME-complete, using new resolution techniques. We show satisfiability to be DEXPTIME-complete if clauses are Horn, which is what is required for modeling cryptographic protocols. While translation to Horn clauses only gives a DEXPTIME upper bound for the secrecy problem for these protocols, we further show that this secrecy problem is actually DEXPTIME-complete.
Probabilistic top-
k
and ranking-aggregate queries
Authors: Soliman Mohamed A. , Ilyas Ihab F. , Chang Kevin Chen--Chuan
Published: September 2008

Ranking and aggregation queries are widely used in data exploration, data analysis, and decision-making scenarios. While most of the currently proposed ranking and aggregation techniques focus on deterministic data, several emerging applications involve data that is unclean or uncertain. Ranking and aggregating uncertain (probabilistic) data raises new challenges in query semantics and processing, making conventional methods inapplicable. Furthermore, uncertainty imposes probability as a new ranking dimension that does not exist in the traditional settings.

In this article we introduce new probabilistic formulations for top-
k
and ranking-aggregate queries in probabilistic databases. Our formulations are based on marriage of traditional top-
k
semantics with possible worlds semantics. In the light of these formulations, we construct a generic processing framework supporting both query types, and leveraging existing query processing and indexing capabilities in current RDBMSs. The framework encapsulates a state space model and efficient search algorithms to compute query answers. Our proposed techniques minimize the number of accessed tuples and the size of materialized search space to compute query answers. Our experimental study shows the efficiency of our techniques under different data distributions with orders of magnitude improvement over naïve methods.
Sketches for size of join estimation
Authors: Rusu Florin , Dobra Alin
Published: September 2008

Sketching techniques provide approximate answers to aggregate queries both for data-streaming and distributed computation. Small space summaries that have linearity properties are required for both types of applications. The prevalent method for analyzing sketches uses moment analysis and distribution-independent bounds based on moments. This method produces clean, easy to interpret, theoretical bounds that are especially useful for deriving asymptotic results. However, the theoretical bounds obscure fine details of the behavior of various sketches and they are mostly not indicative of which type of sketches should be used in practice. Moreover, no significant empirical comparison between various sketching techniques has been published, which makes the choice even harder. In this article we take a close look at the sketching techniques proposed in the literature from a statistical point of view with the goal of determining properties that indicate the actual behavior and producing tighter confidence bounds. Interestingly, the statistical analysis reveals that two of the techniques, Fast-AGMS and Count-Min, provide results that are in some cases orders of magnitude better than the corresponding theoretical predictions. We conduct an extensive empirical study that compares the different sketching techniques in order to corroborate the statistical analysis with the conclusions we draw from it. The study indicates the expected performance of various sketches, which is crucial if the techniques are to be used by practitioners. The overall conclusion of the study is that Fast-AGMS sketches are, for the full spectrum of problems, either the best, or close to the best, sketching technique. We apply the insights obtained from the statistical study and the experimental results to design effective algorithms for sketching interval data. We show how the two basic methods for sketching interval data, DMAP and fast range-summation, can be improved significantly with respect to the update time without a significant loss in accuracy. The gain in update time can be as large as two orders of magnitude, thus making the improved methods practical. The empirical study suggests that DMAP is preferable when update time is the critical requirement and fast range-summation is desirable for better accuracy.
Confidence bounds for sampling-based group by estimates
Authors: Xu Fei , Jermaine Christopher , Dobra Alin
Published: September 2008

Sampling is now a very important data management tool, to such an extent that an interface for database sampling is included in the latest SQL standard. In this article we reconsider in depth what at first may seem like a very simple problem—computing the error of a sampling-based guess for the answer to a GROUP BY query over a multitable join. The difficulty when sampling for the answer to such a query is that the same sample will be used to guess the result of the query for each group, which induces correlations among the estimates. Thus, from a statistical point-of-view it is very problematic and even dangerous to use traditional methods such as confidence intervals for communicating estimate accuracy to the user. We explore ways to address this problem, and pay particular attention to the computational aspects of computing “safe” confidence intervals.
Hierarchical synopses with optimal error guarantees
Authors: Karras Panagiotis , Mamoulis Nikos
Published: September 2008

Hierarchical synopsis structures offer a viable alternative in terms of efficiency and flexibility in relation to traditional summarization techniques such as histograms. Previous research on such structures has mostly focused on a single model, based on the Haar wavelet decomposition. In previous work, we have introduced a more refined, wavelet-inspired hierarchical index structure for synopsis construction: the Haar
+
tree. The chief advantages of this structure are twofold. First, it achieves higher synopsis quality at the task of summarizing data sets with sharp discontinuities than state-of-the-art histogram and Haar wavelet techniques. Second, thanks to its search space delimitation capacity, Haar
+
synopsis construction operates in time
linear
in the size of the data set for
any
monotonic distributive error metric. Contemporaneous research has introduced another hierarchical synopsis structure, the compact hierarchical histogram (CHH). In this article, we elaborate on both these structures. First, we formally prove that the CHH, in its default binary-hierarchy form, is a simplified variant of a Haar
+
tree. We then focus on the summarization problem, with both these hierarchical synopsis structures, in which an error guarantee expressed by a
maximum-error
metric is required. We show that this problem is most efficiently solved through its dual, space-minimization counterpart, which can also achieve
optimal quality
. In this case, there is a benefit to be gained by specializing the algorithm for each structure; hence, our algorithm for optimal-quality maximum-error CHH requires
low polynomial
time; on the other hand, optimal-quality Haar
+
synopses for maximum-error metrics are constructed in exponential time; hence, we also develop a low-polynomial-time approximation scheme for the maximum-error Haar
+
case. Furthermore, we extend our approach for both general-error and maximum-error Haar
+
synopses to arbitrary dimensionality. In our experimental study, (i) we confirm the theoretically expected superiority of Haar
+
synopses over Haar wavelet methods in both construction time and achieved quality for representative error metrics; (ii) we demonstrate that Haar
+
synopses are also constructed faster than optimal plain histograms, and, moreover, achieve higher synopsis quality with highly discontinuous data sets; such an advantage of a hierarchical synopsis structure over a histogram had been intuitively expressed, but never experimentally verified; and (iii) we show that Haar
+
synopsis quality supersedes that of a CHH.
Defending wireless sensor networks from radio interference through channel adaptation
Authors: Xu Wenyuan , Trappe Wade , Zhang Yanyong
Published: September 2008

Radio interference, whether intentional or otherwise, represents a serious threat to assuring the availability of sensor network services. As such, techniques that enhance the reliability of sensor communications in the presence of radio interference are critical. In this article, we propose to cope with this threat through a technique called channel surfing, whereby the sensor nodes in the network adapt their channel assignments to restore network connectivity in the presence of interference. We explore two different approaches to channel surfing: coordinated channel switching, in which the entire sensor network adjusts its channel; and spectral multiplexing, in which nodes in a jammed region switch channels and nodes on the boundary of a jammed region act as radio relays between different spectral zones. For coordinated channel switching, we examine an autonomous strategy where each node detects the loss of its neighbors in order to initiate channel switching. To cope with latency issues in the autonomous strategy, we propose a broadcast-assisted channel switching strategy to more rapidly coordinate channel switching. For spectral multiplexing, we have devised both synchronous and asynchronous strategies to facilitate the scheduling of nodes in order to improve network fidelity when sensor nodes operate on multiple channels. In designing these algorithms, we have taken a system-oriented approach that has focused on exploring actual implementation issues under realistic network settings. We have implemented these proposed methods on a testbed of 30 Mica2 sensor nodes, and the experimental results show that channel surfing, in its various forms, is an effective technique for repairing network connectivity in the presence of radio interference, while not introducing significant performance-overhead.
Activity recognition via user-trace segmentation
Authors: Yin Jie , Yang Qiang , Shen Dou , Li Ze-Nian
Published: September 2008

A major issue of activity recognition in sensor networks is automatically recognizing a user's high-level goals accurately from low-level sensor data. Traditionally, solutions to this problem involve the use of a location-based sensor model that predicts the physical locations of a user from the sensor data. This sensor model is often trained offline, incurring a large amount of calibration effort. In this article, we address the problem using a goal-based segmentation approach, in which we automatically segment the low-level user traces that are obtained cheaply by collecting the signal sequences as a user moves in wireless environments. From the traces we discover primitive signal segments that can be used for building a probabilistic activity model to recognize goals directly. A major advantage of our algorithm is that it can reduce a significant amount of human effort in calibrating the sensor data while still achieving comparable recognition accuracy. We present our theoretical framework for activity recognition, and demonstrate the effectiveness of our new approach using the data collected in an indoor wireless environment.
Optimally balancing energy consumption versus latency in sensor network routing
Authors: Lai Wei , Paschalidis Ioannis C.
Published: September 2008

We consider wireless sensor networks with nodes switching ON (awake) and OFF (sleeping) to preserve energy, and transmitting data over channels with varying quality. The objective is to determine the best path from each node to a single gateway. The performance metrics we are interested in are: the expected energy consumption, and the probability that the latency exceeds a certain threshold. Under Markovian assumptions on the sleeping schedules and the channel conditions, we obtain the expected energy consumption of transmitting a packet on any path to the gateway. We also provide an upper (Chernoff) bound and a tight large deviations asymptotic for the latency probability on each path. To capture the trade-off between energy consumption and latency probability, we formulate the problem of choosing a path to minimize a weighted sum of the expected energy consumption and the exponent of the latency probability. We provide two algorithms to solve this problem: a centralized stochastic global optimization algorithm, and a distributed algorithm based on simulated annealing. The proposed methodology can also optimize over the fraction of time that sensor nodes remain ON (duty cycle).
MAX
Authors: Yap Kok-KIONG , Srinivasan Vikram , Motani Mehul
Published: September 2008

We propose MAX, a system that facilitates human-centric search of the physical world. Instead of organizing objects a priori, it allows humans to search for and locate them as needed. Designed for the following objectives: (i) human-centric operation, (ii) privacy, and (iii) efficient searching of any tagged object, MAX provides location information in a form natural to humans, that is, with reference to identifiable landmarks (such as, “on the dining table”) rather than precise coordinates. In the system, all physical objects—from documents to clothing—can be tagged, users then locate objects using an intuitive search interface. To make searching efficient, MAX adopts a hierarchical architecture consisting of tags (bound to objects), substations (bound to landmarks), and base-stations (bound to localities). Tags can be marked as either public or private, with private tags searchable only by the owner. MAX also provides for privacy of physical spaces. It requires minimal initial configuration, and is robust to reconfiguration of the physical space. We also present a methodology to design energy-optimal and delay-optimal query protocols for a variety of device choices, this optimizes system performance, and affords insight into the appropriate actions for various scenarios. We have implemented a simple prototype of MAX, demonstrating the feasibility of the system for human-centric search over several locations across a wide area. We contend that a MAX-like search system will enable sharing (e.g., books on a college campus) and trading (e.g., buying and selling used books) of physical resources, and will be the engine for a host of new applications.
A capability calculus for concurrency and determinism
Authors: Terauchi Tachio , Aiken Alex
Published: September 2008

This article presents a static system for checking determinism (technically, partial confluence) of communicating concurrent processes. Our approach automatically detects partial confluence in programs communicating via a mix of different kinds of communication methods: rendezvous channels, buffered channels, broadcast channels, and reference cells. Our system reduces the partial confluence checking problem in polynomial time (in the size of the program) to the problem of solving a system of rational linear inequalities, and is thus efficient.
Performance scalability of decoupled software pipelining
Authors: Rangan Ram , Vachharajani Neil , Ottoni Guilherme , August David I.
Published: September 2008

Any successful solution to using multicore processors to scale general-purpose program performance will have to contend with rising intercore communication costs while exposing coarse-grained parallelism. Recently proposed pipelined multithreading (PMT) techniques have been demonstrated to have general-purpose applicability and are also able to effectively tolerate inter-core latencies through pipelined interthread communication. These desirable properties make PMT techniques strong candidates for program parallelization on current and future multicore processors and understanding their performance characteristics is critical to their deployment. To that end, this paper evaluates the performance scalability of a general-purpose PMT technique called decoupled software pipelining (DSWP) and presents a thorough analysis of the communication bottlenecks that must be overcome for optimal DSWP scalability.
Distilling the essence of proprietary workloads into miniature benchmarks
Authors: Joshi Ajay , Eeckhout Lieven , Bell Robert H. , John Lizy K.
Published: September 2008

Benchmarks set standards for innovation in computer architecture research and industry product development. Consequently, it is of paramount importance that these workloads are representative of real-world applications. However, composing such representative workloads poses practical challenges to application analysis teams and benchmark developers (1) real-world workloads are intellectual property and vendors hesitate to share these proprietary applications; and (2) porting and reducing these applications to benchmarks that can be simulated in a tractable amount of time is a nontrivial task. In this paper, we address this problem by proposing a technique that automatically distills key inherent behavioral attributes of a proprietary workload and captures them into a miniature synthetic benchmark clone. The advantage of the benchmark clone is that it hides the functional meaning of the code but exhibits similar performance characteristics as the target application. Moreover, the dynamic instruction count of the synthetic benchmark clone is substantially shorter than the proprietary application, greatly reducing overall simulation time for SPEC CPU, the simulation time reduction is over five orders of magnitude compared to entire benchmark execution. Using a set of benchmarks representative of general-purpose, scientific, and embedded applications, we demonstrate that the power and performance characteristics of the synthetic benchmark clone correlate well with those of the original application across a wide range of microarchitecture configurations.
Facts through fiction
Authors: Westman Hans
Published: September 2008

Welcome to the 2008 SIGGRAPH conference and to the August e-quarterly issue of "Computer Graphics".

I am excited about the submissions in regards to both the breadth in content as well as the geographic location of the contributors, which is an indicator of how truly global the SIGGRAPH organization is.

Murat Kurt and Muhammed Gökhan Cinsdikici at the International Computer Institute, Ege University, Turkey have written a paper on "bidirectional reflectance distribution functions" (BRDFs) and approaches to solving memory and measurement noise problems. Jonathan Amakawa, Instructor at The Art Institute of Pittsburgh, delves into preserving facts through fiction by researching the use of video game technology to archive Japanese culture as illustrated in his article "Exploring the World of 16th Century Japanese Castles and Samurai in Real-time 3D".

VisFiles brings us another interesting article by way of Norway and Austria, this time about illustrative visualization, discussing digital and traditional techniques and technologies.

Canadian Neil Schneider takes up the subject of popularizing 3D Stereoscopics in the "Members at work" section and has submitted a two part interview with the world renowned Dr. Robert Cailliau, Co-Developer of the WWW.

Following the first Antics article written by founder Philip Swinstead, Brad Kolacinski has submitted the second in a series of three entitled "If You Animate It, They will Come", which presents examples of how 3D is being used in the classroom.

Last but not least, don't forget to read the "calls for participation" by Rick Barry for the SIGGRAPH 2008 SpaceTime, Second Life Exhibition and by Anna Ursyn for The History of Computer Graphics and Digital Art Project.