bluuebunny/crossref_metadata_2025 huggingface dataset:
The Impact of Trade Liberalization on Enterprises in Small Backward Economies: the Case of Chad and Gabon
Authors: Navaretti Giorgio Barba , Faini Riccardo , Gauthier Bernard
Published: July 2006

This paper examines the impact of trade and fiscal reforms and of the 1994 devaluation of the CFA franc on enterprise development in Chad and Gabon. These reforms provide a natural experiment to assess the impact of trade liberalization in countries with a small and backward manufacturing sector. The empirical analysis is based on a new panel data base covering virtually the whole population of manufacturing firms in Chad and Gabon, and containing data spanning from the year before to two years after the reforms. The paper finds that although firms’ response to changing incentives was non‐negligible, with a shift of output from nontradable to tradable and an increase in productivity, the reform process was unable to generate a virtuous and self‐sustained circle, where export expansion brings a generalized productivity increase which in turn feeds on further export growth.
Aspects of statistical consulting not taught by academia
Authors: Kenett R. , Thyregod P.
Published: July 2006

Education in statistics is preparing for statistical analysis but not necessarily for statistical consulting. The objective of this paper is to explore the phases that precede and follow statistical analysis. Specifically these include: problem elicitation, data collection and, following statistical data analysis, formulation of findings, and presentation of findings, and recommendations. Some insights derived from a literature review and real‐life case studies are provided. Areas for joint research by statisticians and cognitive scientists are outlined.
Statistical process adjustment: a brief retrospective, current status, and some opportunities for further work
Authors: Del Castillo E.
Published: July 2006

Industrial statisticians frequently face problems in their practice where adjustment of a manufacturing process is necessary. In this paper, a view of the origins and recent work in the area of statistical process adjustment (SPA) is provided. A discussion of some topics open for further research is also given including new problems in semiconductor manufacturing process control. The goal of the paper is to help display the SPA field as a research area with its own identity and content, and promote further interest in its development and application in the industry.
Self‐adapting control charts
Authors: Albers Willem , Kallenberg Wilbert C. M.
Published: July 2006

When the distributional form of the observations differs from normality, standard control charts are often prone to serious errors. Such model errors can be avoided by using (modified) nonparametric control charts. Unfortunately, these control charts suffer from large stochastic errors caused by estimation. In between these two types are the so‐called parametric control charts. All three of them, as well as a combined chart, which chooses one of the three control charts according to the appropriate model assumption on the underlying distribution are discussed in this paper. The data indicate which of the three control charts to select. Readymade formulas for the several control charts are presented accompanied by an application on real data. Apart from bias removal, criteria based on exceedance probability and semi‐variance are investigated.
Non‐SCN5A Related Brugada Syndromes: Verification of Normal Splicing and Trafficking of SCN5A Without Exonic Mutations
Authors: Nakano Yukiko , Tashiro Satoshi , Kinoshita Eiji , Kinoshita–Kikuta Emiko , Takenaka Sou , Miyoshi Miwa , Ogi Hiroshi , Sakoda Eiichiro , Oda Noboru , Suenari Kazuyoshi , Tonouchi Yukiji , Okimoto Tomokazu , Hirai Yukoh , Miura Fumiharu , Yamaoka Kazuko , Koike Tohru , Chayama Kazuaki
Published: July 2006

Recently, it has been reported that under 20% of Brugada syndrome cases are linked to SCN5A mutations. The purpose of this study was to clarify whether abnormalities other than exonic mutations, such as splicing disorders, decreased mRNA expression levels, or membrane transport abnormalities of SCN5A, play a role in the pathogenesis of Brugada syndrome.

We analyzed all SCN5A exons and splice sites using genomic DNA from 23 Brugada syndrome patients. We also analyzed the mRNA obtained from RV cardiomyocytes using real time PCR and sequencing, to study the expression levels and splicing patterns of SCN5A. The localization of SCN5A was examined by immunofluorescence analysis.

A de novo heterozygous G to A transversion in a 5′ splice junction of the intron between exons 21 and 22 was detected in 1 patient. In the mRNA analysis of Brugada syndrome patients without a mutation of SCN5A no splicing abnormalities were detected, and the SCN5A mRNA levels were similar to those of normal controls. Immunofluorescence analyses revealed that SCN5A is located on the surface membrane not only in the RV cardiomyocytes of normal controls but also in those with Brugada syndrome.

We can confirm that some Brugada syndrome patients without exonic mutations in SCN5A had no other SCN5A abnormalities, including any involving the location of the SCN5A protein. These results suggest the involvement of other proteins in the pathogenesis in Brugada syndrome.
COPPER AND BRONZE DURING THE ENEOLITHIC AND EARLY BRONZE AGE: A METALLOGRAPHIC EXAMINATION OF AXES FROM THE NORTHALPINE REGION*
Authors: KIENLIN T. L. , BISCHOFF E. , OPIELKA H.
Published: July 2006

This paper presents the results of a metallographic examination of Eneolithic and Early Bronze Age axes from the Northalpine region of central Europe. During this period, different types of copper were in use: arsenical copper, Fahlerz copper and tin bronze. We examine if and to what extent the different properties of the metals used were known to prehistoric metalworkers and actively manipulated in the production of the axes. The development of methods of casting and smithing is discussed. Both aspects contribute to our understanding of the nature of prehistoric technological change. During the Early Bronze Age of the Northalpine region, different traditions of early metallurgy can be identified, which differ in their use of Fahlerz copper, their attitude towards tin alloying and the use made of tin bronze in the production of the axes. These traditions can only be adequately described by reference to both composition—that is, access to different types of copper as well as tin—and knowledge of the production techniques provided by metallographic data.
Standardization of Alcohol Calculations in Research
Authors: Brick John
Published: July 2006

Background: Nonstandardized reporting of alcohol consumption, definitions of what constitutes a standard drink, and incomplete dosing or estimates of intoxication are common problems in many areas of alcohol research. To enhance communication among scientists and to make interpretation of results more accurate and meaningful, researchers need to apply systematically current scientific principles in calculating drinks, doses, and alcohol concentrations. Basic formulas are compiled and explained to assist alcohol researchers and standardize the reporting and interpretation of alcohol data.

Methods: Basic alcohol calculations are reviewed, and 20 mathematical calculations in alcohol pharmacokinetics and pharmacology are derived. Examples of how each calculation works are presented.

Results: The formulas presented enable researchers to calculate accurately and systematically the amount of alcohol in any beverage and estimate the blood alcohol concentration in a range of subjects with individual characteristics and drinking patterns.

Conclusions: Accurate estimates of alcohol use and intoxication are important in many areas of research. Applying standards to the way alcohol is measured and interpreted enables better communication, more accurate analyses, and, in some cases, may impact the interpretation of results. Regardless of the field of study, alcohol researchers are encouraged to and can apply uniform standards in measuring alcohol consumption and estimating the effects of alcohol using the scientific methodologies described.
Neuroadaptations of Cdk5 in Cholinergic Interneurons of the Nucleus Accumbens and Prefrontal Cortex of Inbred Alcohol‐preferring Rats Following Voluntary Alcohol Drinking
Authors: Camp Marguerite Charlotte , Mayfield Roy Dayne , McCracken Mandy , McCracken Lindsay , Alcantara Adriana Angelica
Published: July 2006

Background: Neurobiological studies have identified brain areas and related molecular mechanisms involved in alcohol abuse and dependence. Specific cell types in these brain areas and their role in alcohol‐related behaviors, however, have not yet been identified. This study examined the involvement of cholinergic cells in inbred alcohol‐preferring rats following 1 month of alcohol drinking. Cyclin‐dependent kinase 5 (Cdk5) immunoreactivity (IR), a marker of neuronal plasticity, was examined in cholinergic neurons of the nucleus accumbens (NuAcc) and prefrontal cortex (PFC) and other brain areas implicated in alcohol drinking, using dual immunocytochemical (ICC) procedures. Single Cdk5 IR was also examined in several brain areas implicated in alcohol drinking.

Methods: The experimental group self‐administered alcohol using a 2‐bottle‐choice test paradigm with unlimited access to 10% (v/v) alcohol and water for 23 h/d for 1 month. An average of 6 g/kg alcohol was consumed daily. Control animals received identical treatment, except that both bottles contained water. Rats were perfused and brain sections were processed for ICC procedures.

Results: Alcohol drinking resulted in a 51% increase in Cdk5 IR cholinergic interneurons in the shell NuAcc, while in the PFC there was a 51% decrease in the percent of Cdk5 IR cholinergic interneurons in the infralimbic region and a 46% decrease in Cdk5 IR cholinergic interneurons in the prelimbic region. Additionally, single Cdk5 IR revealed a 42% increase in the central nucleus of the amygdala (CNA).

Conclusions: This study identified Cdk5 neuroadaptation in cholinergic interneurons of the NuAcc and PFC and in other neurons of the CNA following 1 month of alcohol drinking. These findings contribute to our understanding of the cellular and molecular basis of alcohol drinking and toward the development of improved region and cell‐specific pharmacotherapeutic and behavioral treatment programs for alcohol abuse and alcoholism.
Is the Strength of Implicit Alcohol Associations Correlated with Alcohol‐induced Heart‐rate Acceleration?
Authors: Van Den Wildenberg Esther , Beckers Margreet , Van Lambaart Femke , Conrod Patricia J. , Wiers Reinout W.
Published: July 2006

Background: Heart rate (HR) acceleration during the ascending limb of the blood alcohol curve has proven to be a reliable measure of the sensitivity to the activating effects of alcohol. In this study, we investigated the correlation between an ethanol‐induced cardiac change and the strength of implicit alcohol‐related arousal and approach associations and attentional bias for alcohol‐related stimuli in heavy drinkers. These 3 types of implicit alcohol‐related cognitions have been proposed to reflect the strength of incentive sensitization that is experienced after repeated alcohol use.

Methods: Forty‐eight heavy drinking men performed a modified version of the Implicit Association Test (IAT) to measure their implicit alcohol arousal and approach–avoidance associations. A modified version of the emotional Stroop was used to measure attentional bias for alcohol‐related stimuli (blocked and unblocked). Next, a high dose of alcohol (1.0 mL/kg body weight 95% USP alcohol) was administered in a short period of time. Resting baseline HR, blood alcohol concentrations, mood, and craving for alcohol were assessed before alcohol administration and for 2 hours post–alcohol consumption.

Results: Contrary to our hypothesis, a negative association was found between implicit arousal associations and alcohol‐induced HR change. This indicates that strong arousal associations were correlated with a decrease in alcohol‐induced HR. Approach associations and attentional bias were not correlated with alcohol‐induced HR change, but both were correlated positively with each other.

Conclusions: Alcohol‐arousal associations and other implicit cognitions (attentional bias, approach associations) are not positively related to individual differences in the sensitivity to alcohol's activating effects, at least not in the present sample consisting primarily of family history‐negative heavy drinkers.
Comparison of hard tissue density changes around implants assessed in digitized conventional radiographs and subtraction images
Authors: Bittar‐Cortez Juliana Araujo , Passeri Luis Augusto , Bóscolo Frab Norberto , Haiter‐Neto Francisco
Published: July 2006

Objectives: The aim of this in vivo study was to compare peri‐implant bone density assessed by the mean gray value of the histogram in digitized conventional radiographs and two digital subtraction images (DSI) methods: linear and logarithmic.

Material and methods: Thirty‐four patients were monitored by standardized periapical radiographs 1 week after surgery and 4 months later. The radiographs were digitized and manipulated by means of EMAGO® software. Linear and logarithmic DSI were obtained, and a filter was added to the logarithmic image. Control and test regions were selected and the mean value of the gray level of the histogram of these selected areas was obtained. This process was carried out in the digitized conventional radiographs (DCR) and the two methods of DSI. After that, the images were divided into two groups, with and without bone loss, and statistical analysis was performed.

Results: The results indicate that differences between the jaws did not reach significance, in all the images and in the two groups with and without bone loss. Furthermore, there was no statistically significant difference between the radiographic density assessed in the DCR and the two methods of subtraction images.

Conclusions: Monitoring of peri‐implant bone density by the mean gray value of the histogram in a selected area can be assessed either by linear and logarithmic DSI or by DCR.
Can bile acids function as a migratory pheromone in banded kokopu, Galaxias fasciatus (Gray)?
Authors: Baker C. F. , Carton A. G. , Fine J. M. , Sorensen P. W.
Published: July 2006

Abstract –  Migratory banded kokopu juveniles exhibit a species‐specific attraction to adult conspecifics. The potential for bile acids to function as a component of a migratory pheromone in banded kokopu was investigated by examining which bile acids are present in the gallbladder of adult fish, are released into the water and are detected by adult fish. High‐performance liquid chromatography (HPLC) and mass spectrometry (MS) of gallbladder extracts showed that banded kokopu contained high quantities of taurocholic acid (TCA) and taurochenodeoxycholic acid (TCD), and a very small quantity of cyprinol sulphate (5α‐CS). The holding water of adult banded kokopu was found to contain only TCA and TCD. In addition, three unknown peaks were evident. Electro‐olfactogram recordings revealed that banded kokopu showed strong responses to four bile acids [5α‐CS, petromyzonol (P), petromyzonol sulphate (PS), and allocholic acid (ACA)] and low responses to TCA and TCD (<30% of the l‐serine standard). The bile acids TCA and TCD, produced and released by adult banded kokopu, are common among teleosts and are not species specific. Therefore, it is unlikely that these bile acids will function as a migratory pheromone in banded kokopu.
Stream spawning of Arctic charr in Scotland
Authors: Walker A. F.
Published: July 2006

Abstract –  Scotland is a stronghold for Arctic charr, with about 200 freshwater, wholly loch‐resident populations, most of which have yet to be studied. To date, no anadromous populations or individual sea‐run charr, have been reported. In Scotland, most Arctic charr spawn in stillwater, during autumn and early winter (September to January), with only one population spawning in spring. Spawning in running water does occur, but has been regarded as rare. This paper examines the status of stream spawning of charr in Scotland, describing instances from 10 populations, although two of these are now extinct. Most stream‐spawning charr migrate relatively short distances to running water and construct redds in gently flowing water. The longest recorded migration occurs in Loch Insh, Speyside, with fish travelling 15 km within the River Spey. Information on the extent of stream spawning is essential to help conserve the rich phenotypic and genetic diversity of our remaining charr populations.
Human Fallopian Tube Neutrophils – A Distinct Phenotype from Blood Neutrophils
Authors: Smith Jennifer M. , Wira Charles R. , Fanger Michael W. , Shen Li
Published: July 2006

Problem  The role of neutrophils in the human Fallopian tube (FT) is unknown. In order to provide insights into their functions in the FT, we systematically compared neutrophils from normal FT and peripheral blood (PB).

Method of study  Flow cytometric analysis of surface receptors, granule proteins, and intracellular cytokines expressed by neutrophils from enzymatically dispersed FT and PB was performed.

Results  Fallopian tube neutrophils expressed significantly higher levels of CD64, human class II histocompatibility antigen DR (HLA‐DR), γ‐interferon, and vascular endothelial growth factor than those from PB. Fewer FT neutrophils expressed IL‐8 receptors compared to PB, while more expressed the receptor for the bacterial‐derived chemoattractant formyl‐Met‐Leu‐Phe (fMLP). The number of FT neutrophils containing the granule proteins matrix metalloproteinase‐9, lactoferrin, and myeloperoxidase was decreased versus PB.

Conclusion  Fallopian tube neutrophils exhibit a phenotype distinct from PB neutrophils, suggesting functional activation of innate immune defense in the female reproductive tract as well as a potential role in maintaining normal FT physiology.
Prophylactic Therapy for Patients with Reproductive Failure Who were Positive for Anti‐Phospholipid Antibodies
Authors: Takakuwa Koichi , Ooki Izumi , Nonaka Taro , Tamura Nozomi , Ishii Keisuke , Kikuchi Akira , Tamura Masaki , Tanaka Kenichi
Published: July 2006

Problem  To elucidate the efficacy of the treatment using a Japanese‐modified Chinese herbal medicine, Sairei‐to, and low‐dose aspirin with or without a corticosteroid hormone for the patients with adverse pregnancy histories positive for anti‐phospholipid antibodies.

Methods of study  Fifteen cases positive for anti‐phospholipid antibodies, who had experienced preterm delivery in which an extremely low birthweight infant (<1000 g) was born as a result of intrauterine growth restriction with or without severe preeclampsia, were treated with the medication according to the current protocol. Four cases with the same condition, who were treated with only low‐dose aspirin, or without medication, were chosen as a control population. The pregnancy outcome was compared between the two groups.

Results  The rate of patients in whom the next pregnancy continued until the 36th week of gestation or later was significantly higher in treated patients (80.0%) compared with the control population (0%).

Conclusions  In this series, we obtained case report data that Sairei‐to may provide some benefit for patients with reproductive disorders positive for anti‐phospholipid antibodies; however, randomized controlled trial evidence is needed before current treatment can be recommended.
Oral manifestations in HIV/AIDS infected patients from India
Authors: Sharma G , Pai KM , Suhas S , Ramapuram JT , Doshi D , Anup N
Published: July 2006

Objectives:  To assess types and prevalence of HIV‐related oral lesions among HIV‐infected individuals in south India and to correlate common oral findings with co‐morbidities, gender, age and medication.

Subjects and methods:  One hundred and one patients with HIV infection or AIDS at infectious diseases units of Attavar Hospital, Mangalore, and medical wards of Kasturba Medical College, Manipal, were selected. Sociodemographic information was obtained using a structured questionnaire. Oral lesions were diagnosed according to the presumptive criteria of EEC‐Clearinghouse Classification. Clinical history was retrieved from patient's medical records.

Results:  Erythematous candidiasis (44.5%), melanotic hyperpigmentaion (34.6%) and xerostomia (29.7%) were among the most common oral manifestations. A significant association was found between oral candidiasis and advanced immunosuppression (P < 0.05). Oral hairy leukoplakia (OHL) was predominant in individuals <35 years (P < 0.05). Melanotic hyperpigmentation was significantly associated with highly active antiretroviral therapy (P < 0.05). OHL was more frequent in patients with HIV‐associated tuberculosis. Linear gingival erythema was more predominant in females.

Conclusions:  Oral hairy leukoplakia showed a positive relationship with patients younger than 35 years. Oral candidiasis can act as a marker for immunosuppression. Angular cheilitis was predominant in the symptomatic stage.
Constant-depth Frege systems with counting axioms polynomially simulate Nullstellensatz refutations
Authors: Impagliazzo Russell , Segerlind Nathan
Published: July 2006

We show that constant-depth Frege systems with counting axioms modulo
m
polynomially simulate Nullstellensatz refutations modulo
m
. Central to this is a new definition of reducibility from propositional formulas to systems of polynomials. Using our definition of reducibility, most previously studied propositional formulas reduce to their polynomial translations. When combined with a previous result of the authors, this establishes the first size separation between Nullstellensatz and polynomial calculus refutations. We also obtain new upper bounds on refutation sizes for certain CNFs in constant-depth Frege with counting axioms systems.
Propositional computability logic II
Authors: Japaridze Giorgi
Published: July 2006

Computability logic is a formal theory of computational tasks and resources. Its formulas represent interactive computational problems, logical operators stand for operations on computational problems, and validity of a formula is understood as its being a scheme of problems that always have algorithmic solutions. The earlier article “Propositional computability logic I” proved soundness and completeness for the (in a sense) minimal nontrivial fragment
CL1
of computability logic. The present article extends that result to the significantly more expressive propositional system
CL2
. What makes
CL2
more expressive than
CL1
is the presence of two sorts of atoms in its language:
elementary atoms
, representing elementary computational problems (i.e. predicates), and
general atoms
, representing arbitrary computational problems.
CL2
conservatively extends
CL1
, with the latter being nothing but the general-atom-free fragment of the former.
On preservation under homomorphisms and unions of conjunctive queries
Authors: Atserias Albert , Dawar Anuj , Kolaitis Phokion G.
Published: July 2006

Unions of conjunctive queries, also known as select-project-join-union queries, are the most frequently asked queries in relational database systems. These queries are definable by existential positive first-order formulas and are preserved under homomorphisms. A classical result of mathematical logic asserts that the existential positive formulas are the only first-order formulas (up to logical equivalence) that are preserved under homomorphisms on all structures, finite and infinite. The question of whether the homomorphism-preservation theorem holds for the class of all finite structures resisted solution for a long time. It was eventually shown that, unlike other classical preservation theorems, the homomorphism-preservation theorem does hold in the finite. In this article, we show that the homomorphism-preservation theorem holds also for several restricted classes of finite structures of interest in graph theory and database theory. Specifically, we show that this result holds for all classes of finite structures of bounded degree, all classes of finite structures of bounded treewidth, and, more generally, all classes of finite structures whose cores exclude at least one minor.
Mining semantically related terms from biomedical literature
Authors: Nenadić Goran , Ananiadou Sophia
Published: July 2006

Discovering links and relationships is one of the main challenges in biomedical research, as scientists are interested in uncovering entities that have similar functions, take part in the same processes, or are coregulated. This article discusses the extraction of such semantically related entities (represented by domain terms) from biomedical literature. The method combines various text-based aspects, such as lexical, syntactic, and contextual similarities between terms. Lexical similarities are based on the level of sharing of word constituents. Syntactic similarities rely on expressions (such as term enumerations and conjunctions) in which a sequence of terms appears as a single syntactic unit. Finally, contextual similarities are based on automatic discovery of relevant contexts shared among terms. The approach is evaluated using the Genia resources, and the results of experiments are presented. Lexical and syntactic links have shown high precision and low recall, while contextual similarities have resulted in significantly higher recall with moderate precision. By combining the three metrics, we achieved F measures of 68% for
semantically related
terms and 37% for
highly related
entities.
Extracting contrastive information from negation patterns in biomedical literature
Authors: Kim Jung-Jae , Park Jong C.
Published: July 2006

Expressions of negation in the biomedical literature often encode information of contrast as a means for explaining significant differences between the objects that are so contrasted. We show that such information gives additional insights into the nature of the structures and/or biological functions of these objects, leading to valuable knowledge for subcategorization of protein families by the properties that the involved proteins do not have in common. Based on the observation that the expressions of negation employ mostly predictable syntactic structures that can be characterized by subclausal coordination and by clause-level parallelism, we present a system that extracts such contrastive information by identifying those syntactic structures with natural language processing techniques and with additional linguistic resources for semantics. The implemented system shows the performance of 85.7% precision and 61.5% recall, including 7.7% partial recall, or an F score of 76.6. We apply the system to the biological interactions as extracted by our biomedical information-extraction system in order to enrich proteome databases with contrastive information.
Two-phase learning for biological event extraction and verification
Authors: Kim Eunju , Song Yu , Lee Cheongjae , Kim Kyoungduk , Lee Gary Geunbae , Yi Byoung-Kee , Cha Jeongwon
Published: July 2006

Many previous biological event-extraction systems were based on hand-crafted rules which were specifically tuned to a specific biological application domain. But manually constructing and tuning the rules are time-consuming processes and make the systems less portable. So supervised machine-learning methods were developed to generate the extraction rules automatically, but accepting the trade-off between precision and recall (high recall with low precision, and vice versa) is a barrier to improving performance. To make matters worse, a text in the biological domain is more complex because it often contains more than two biological events in a sentence, and one event in a noun chunk can be an entity for the other event. As a result, there are as yet no systems that give a good performance in extracting events in biological domains by using supervised machine learning.To overcome the limitations of previous systems and the complexity of biological texts, we present the following new ideas. First, we adopted a supervised machine-learning method to reduce the human effort in making extraction rules in order to obtain a highly domain-portable system. Second, we overcame the classical trade-off between precision and recall by using an event component verification method. Thus, machine learning occurs in two phases in our architecture. In the first phase, the system focuses on improving recall in extracting events between biological entities during a supervised machine-learning period. After extracting the biological events with automatically learned rules, in the second phase the system removes incorrect biological events by verifying the extracted event components with a maximum entropy (ME) classification method. In other words, the system targets for high recall in the first phase and tries to achieve high precision with a classifier in the second phase. Finally, we improved a supervised machine-learning algorithm so that it could learn a rule in a noun chunk and a rule extending throughout a sentence at two different levels, separately, for nested biological events.
Integrating automated test generation into the WYSIWYT spreadsheet testing methodology
Authors: Fisher Marc , Rothermel Gregg , Brown Darren , Cao Mingming , Cook Curtis , Burnett Margaret
Published: July 2006

Spreadsheet languages, which include commercial spreadsheets and various research systems, have had a substantial impact on end-user computing. Research shows, however, that spreadsheets often contain faults. Thus, in previous work we presented a methodology that helps spreadsheet users test their spreadsheet formulas. Our empirical studies have shown that end users can use this methodology to test spreadsheets more adequately and efficiently; however, the process of generating test cases can still present a significant impediment. To address this problem, we have been investigating how to incorporate automated test case generation into our testing methodology in ways that support incremental testing and provide immediate visual feedback. We have used two techniques for generating test cases, one involving random selection and one involving a goal-oriented approach. We describe these techniques and their integration into our testing environment, and report results of an experiment examining their effectiveness and efficiency.
Collaborative operating system and compiler power management for real-time applications
Authors: AbouGhazaleh Nevine , Mossé Daniel , Childers Bruce R. , Melhem Rami
Published: July 2006

Managing energy consumption has become vitally important to battery-operated portable and embedded systems.
Dynamic voltage scaling
(DVS) reduces the processor's dynamic power consumption quadratically at the expense of linearly decreasing the performance. When reducing energy with DVS for real-time systems, one must consider the performance penalty to ensure that deadlines can be met. In this paper, we introduce a novel collaborative approach between the compiler and the operating system (OS) to reduce energy consumption. We use the compiler to annotate an application's source code with path-dependent information called
power-management hints
(PMHs). This fine-grained information captures the temporal behavior of the application, which varies by executing different paths. During program execution, the OS periodically changes the processor's frequency and voltage based on the temporal information provided by the PMHs. These speed adaptation points are called
power-management points
(PMPs). We evaluate our scheme using three embedded applications: a video decoder, automatic target recognition, and a sub-band tuner. Our scheme shows an energy reduction of up to 57% over no power-management and up to 32% over a static power-management scheme. We compare our scheme to other schemes that solely utilize PMPs for power-management and show experimentally that our scheme achieves more energy savings. We also analyze the advantages and disadvantages of our approach relative to another compiler-directed scheme.
FAST
Authors: Seth Kiran , Anantaraman Aravindh , Mueller Frank , Rotenberg Eric
Published: July 2006

Energy is a valuable resource in embedded systems as the lifetime of many such systems is constrained by their battery capacity. Recent advances in processor design have added support for dynamic frequency/voltage scaling (DVS) for saving energy. Recent work on real-time scheduling focuses on saving energy in static as well as dynamic scheduling environments by exploiting idle time and slack because of early task completion for DVS of subsequent tasks. These scheduling algorithms rely on
a priori
knowledge of worst-case execution times (WCET) for each task. They assume that DVS has no effect on the worst-case execution cycles (WCEC) of a task and scale the WCET according to the processor frequency. However, for systems with memory hierarchies, the WCEC typically
does
change under DVS because of requency modulation. Hence, current assumptions used by DVS schemes result in a highly exaggerated WCET. This paper contributes novel techniques for tight and flexible static timing analysis, particularly well-suited for dynamic scheduling schemes. The technical contributions are as follows: (1) We assess the problem of changing execution cycles owing to scaling techniques. (2) We propose a parametric approach toward bounding the WCET statically with respect to the frequency. Using a parametric model, we can capture the effect of changes in frequency on the WCEC and, thus, accurately model the WCET over any frequency range. (3) We discuss design and implementation of the frequency-aware static timing analysis (FAST) tool based on our prior experience with static timing analysis. (4) We demonstrate in experiments that our FAST tool provides safe upper bounds on the WCET, which are tight. The FAST tool allows us to capture the WCET of six benchmarks using equations that overestimate the WCET by less than 1%. FAST equations can also be used to improve existing DVS scheduling schemes to ensure that the effect of frequency scaling on WCET is considered and that the WCET used is
not
exaggerated. (5) We leverage three DVS scheduling schemes by incorporating FAST into them and by showing that the energy consumption further decreases. (6) We compare experimental results using two different energy models to demonstrate or verify the validity of simulation methods. To the best of our knowledge, this study of DVS effects on timing analysis is unprecedented.
Bit-split string-matching engines for intrusion detection and prevention
Authors: Tan Lin , Brotherton Brett , Sherwood Timothy
Published: July 2006

Network Intrusion Detection and Prevention Systems have emerged as one of the most effective ways of providing security to those connected to the network and at the heart of almost every modern intrusion detection system is a string-matching algorithm. String matching is one of the most critical elements because it allows for the system to make decisions based not just on the headers, but the actual content flowing through the network. Unfortunately, checking every byte of every packet to see if it matches one of a set of thousands of strings becomes a computationally intensive task as network speeds grow into the tens, and eventually hundreds, of gigabits/second. To keep up with these speeds, a specialized device is required, one that can maintain tight bounds on worst-case performance, that can be updated with new rules without interrupting operation, and one that is efficient enough that it could be included on-chip with existing network chips or even into wireless devices. We have developed an approach that relies on a special purpose architecture that executes novel string matching algorithms specially optimized for implementation in our design. We show how the problem can be solved by converting the large database of strings into many tiny state machines, each of which searches for a portion of the rules and a portion of the bits of each rule. Through the careful codesign and optimization of our architecture with a new string-matching algorithm, we show that it is possible to build a system that is 10 times more efficient than the currently best known approaches.
Optimal register reassignment for register stack overflow minimization
Authors: Choi Yoonseo , Han Hwansoo
Published: July 2006

Architectures with a register stack can implement efficient calling conventions. Using the overlapping of callers' and callees' registers, callers are able to pass parameters to callees without a memory stack. The most recent instance of a register stack can be found in the Intel Itanium architecture. A hardware component called the register stack engine (RSE) provides an illusion of an infinite-length register stack using a memory-backed process to handle overflow and underflow for a physically limited number of registers. Despite such hardware support, some applications suffer from the overhead required to handle register stack overflow and underflow. The memory latency associated with the overflow and underflow of a register stack can be reduced by generating multiple register allocation instructions within a procedure [Settle et al. 2003]. Live analysis is utilized to find a set of registers that are not required to keep their values across procedure boundaries. However, among those dead registers, only the registers that are consecutively located in a certain part of the register stack frame can be removed. We propose a compiler-supported register reassignment technique that reduces RSE overflow/underflow further. By reassigning registers based on live analysis, our technique forces as many dead registers to be removed as possible. We define the problem of optimal register reassignment, which minimizes interprocedural register stack heights considering multiple call sites within a procedure. We present how this problem is related to a
path-finding problem
in a graph called a
sequence graph
. We also propose an efficient heuristic algorithm for the problem. Finally, we present the measurement of effects of the proposed techniques on SPEC CINT2000 benchmark suite and the analysis of the results. The result shows that our approach reduces the RSE cycles by 6.4% and total cpu cycles by 1.7% on average.
Plagiarism on the rise
Authors: Boisvert Ronald F. , Irwin Mary Jane
Published: July 2006

ACM's Publications Board issues a plagiarism policy to help stem the disturbing increase in occurrences.
Wireless hotspots
Authors: Potter Bruce
Published: July 2006

Laptops and PDAs are so vulnerable in wireless hotspots, users would do well to turn them off.
Explorations in namespace
Authors: Kaminsky Dan
Published: July 2006

DNS cache scanning across a sample set of more than 500,000 name servers revealed the extent of last year's Sony rootkit infestation on client machines.
Integrating XML data sources using approximate joins
Authors: Guha Sudipto , Jagadish H. V. , Koudas Nick , Srivastava Divesh , Yu Ting
Published: July 2006

XML is widely recognized as the data interchange standard of tomorrow because of its ability to represent data from a variety of sources. Hence, XML is likely to be the format through which data from multiple sources is integrated. In this article, we study the problem of integrating XML data sources through correlations realized as join operations. A challenging aspect of this operation is the XML document structure. Two documents might convey approximately or exactly the same information but may be quite different in structure. Consequently, an approximate match in structure, in addition to content, has to be folded into the join operation. We quantify an approximate match in structure and content for pairs of XML documents using well defined notions of distance. We show how notions of distance that have metric properties can be incorporated in a framework for joins between XML data sources and introduce the idea of reference sets to facilitate this operation. Intuitively, a reference set consists of data elements used to project the data space. We characterize what constitutes a good choice of a reference set, and we propose sampling-based algorithms to identify them. We then instantiate our join framework using the tree edit distance between a pair of trees. We next turn our attention to utilizing well known index structures to improve the performance of approximate XML join operations. We present a methodology enabling adaptation of index structures for this problem, and we instantiate it in terms of the R-tree. We demonstrate the practical utility of our solutions using large collections of real and synthetic XML data sets, varying parameters of interest, and highlighting the performance benefits of our approach.
Indexing the past, present, and anticipated future positions of moving objects
Authors: Pelanis Mindaugas , Šaltenis Simonas , Jensen Christian S.
Published: July 2006

With the proliferation of wireless communications and geo-positioning, e-services are envisioned that exploit the positions of a set of continuously moving users to provide context-aware functionality to each individual user. Because advances in disk capacities continue to outperform Moore's Law, it becomes increasingly feasible to store online all the position information obtained from the moving e-service users. With the much slower advances in I/O speeds and many concurrent users, indexing techniques are of the essence in this scenario.Existing indexing techniques come in two forms. Some techniques capture the position of an object up until the time of the most recent position sample, while other techniques represent an object's position as a constant or linear function of time and capture the position from the current time and into the (near) future. This article offers an indexing technique capable of capturing the positions of moving objects at all points in time. The index substantially modifies partial persistence techniques, which support transaction time, to support valid time for monitoring applications. The performance of a timeslice query is independent of the number of past position samples stored for an object. No existing indices exist with these characteristics.
Approximation and streaming algorithms for histogram construction problems
Authors: Guha Sudipto , Koudas Nick , Shim Kyuseok
Published: July 2006

Histograms and related synopsis structures are popular techniques for approximating data distributions. These have been successful in query optimization and a variety of applications, including approximate querying, similarity searching, and data mining, to name a few. Histograms were a few of the earliest synopsis structures proposed and continue to be used widely. The histogram construction problem is to construct the best histogram restricted to a space bound that reflects the data distribution most accurately under a given error measure.The histograms are used as quick and easy estimates. Thus, a slight loss of accuracy, compared to the optimal histogram under the given error measure, can be offset by fast histogram construction algorithms. A natural question arises in this context: Can we find a fast near optimal approximation algorithm for the histogram construction problem? In this article, we give the first linear time (1+ϵ)-factor approximation algorithms (for any ϵ > 0) for a large number of histogram construction problems including the use of piecewise small degree polynomials to approximate data, workloads, etc. Several of our algorithms extend to data streams.Using synthetic and real-life data sets, we demonstrate that in many scenarios the approximate histograms are almost identical to optimal histograms in quality and are significantly faster to construct.
Association mining
Authors: Ceglar Aaron , Roddick John F.
Published: July 2006

The task of finding correlations between items in a dataset, association mining, has received considerable attention over the last decade. This article presents a survey of association mining fundamentals, detailing the evolution of association mining algorithms from the seminal to the state-of-the-art. This survey focuses on the fundamental principles of association mining, that is, itemset identification, rule generation, and their generic optimizations.
Quantified types in an imperative language
Authors: Grossman Dan
Published: July 2006

We describe universal types, existential types, and type constructors in Cyclone, a strongly typed C-like language. We show how the language naturally supports first-class polymorphism and polymorphic recursion while requiring an acceptable amount of explicit type information. More importantly, we consider the soundness of type variables in the presence of C-style mutation and the address-of operator. For polymorphic references, we describe a solution more natural for the C level than the ML-style “value restriction.” For existential types, we discover and subsequently avoid a subtle unsoundness issue resulting from the address-of operator. We develop a formal abstract machine and type-safety proof that capture the essence of type variables at the C level.
A lifetime optimal algorithm for speculative PRE
Authors: Xue Jingling , Cai Qiong
Published: July 2006

A lifetime optimal algorithm, called MC-PRE, is presented for the first time that performs speculative PRE based on edge profiles. In addition to being computationally optimal in the sense that the total number of dynamic computations for an expression in the transformed code is minimized, MC-PRE is also lifetime optimal since the lifetimes of introduced temporaries are also minimized. The key in achieving lifetime optimality lies not only in finding a unique minimum cut on a transformed graph of a given CFG, but also in performing a data-flow analysis directly on the CFG to avoid making unnecessary code insertions and deletions. The lifetime optimal results are rigorously proved. We evaluate our algorithm in GCC against three previously published PRE algorithms, namely, MC-PRE
copt
(Qiong and Xue's computationally optimal version of MC-PRE), LCM (Knoop, Rüthing, and Steffen's lifetime optimal algorithm for performing nonspeculative classic PRE), and CMP-PRE (Bodik, Gupta, and Soffa's PRE algorithm based on code-motion preventing (CMP) regions, which is speculative but not computationally optimal). We report and analyze our experimental results, obtained from both actual program execution and instrumentation, for all 22 C, C++ and FORTRAN 77 benchmarks from SPECcpu2000 on an Itanium 2 computer system. Our results show that MC-PRE (or MC-PRE
copt
) is capable of eliminating more partial redundancies than both LCM and CMP-PRE (especially in functions with complex control flow), and, in addition, MC-PRE inserts temporaries with shorter lifetimes than MC-PRE
copt
. Each of both benefits has contributed to the performance improvements in benchmark programs at the costs of only small compile-time and code-size increases in some benchmarks.