bluuebunny/crossref_metadata_2025 huggingface dataset:
Microtus population biology: demography of M. oregoni in southwestern British Columbia
Authors: Sullivan Thomas P. , Krebs Charles J.
Published: April 2009

Populations of Microtus oregoni were livetrapped from 1971 to 1974 in old field and grassland habitats at the University of British Columbia Research Forest, Maple Ridge, B.C. Forest (1974–1978) and shrub (1975–1980) habitats were also sampled intensively. An additional population was livetrapped (1971–1974) in abandoned grassland near Ladner, B.C. Microtus oregoni exhibited a 3–4 year cyclic fluctuation in abundance in the old field and shrub habitats. Maximum density (72 voles/ha) was recorded on the old field grid which was optimum habitat for this species. Winter breeding and a long reproductive period prior to the peak year, and larger body size during the peak than in other phases of the cycle were characteristic features of the old field population. This vole species did not have a multiannual cycle in habitats where the competitor, M. townsendii, was present. Oregon voles were 3–4 g heavier at the Research Forest than at the Ladner study area. Female voles were more prevalent than males in all populations.
Population dynamics of island populations of subarctic Clethrionomys rutilus
Authors: Burns Gordon R.
Published: April 2009

Populations of Clethrionomys rutilus were studied on two islands (Island 2 and Green Island) in the Mackenzie River during the summers of 1976 to 1978. This was done to examine the demographic parameters related to confinement of northern red-backed vole populations on islands.The number of voles on Island 2 in 1977 increased until late June and then remained nearly constant until trapping ceased in late August. On Green Island in 1977 and 1978 and Island 2 in 1978, populations grew all summer and even in August had not reached the densities found during the 1977 high on Island 2. Island 2 in 1977 had an unusually low number of maturing young voles. Higher wounding rates and shorter adjusted range lengths were associated with higher population densities.Although high densities of voles were reached early in the summer of 1977 on Island 2, numbers stopped increasing before the end of the breeding season. Restraint of growth potential was seen in poor maturation of the young and in declining juvenile survival and recruitment of young through summer.
Changes in hematology and metabolites in the serum and urine of the badger, Taxidea taxus, during food deprivation
Authors: Harlow Henry J. , Seal Ulysses S.
Published: April 2009

Urine and blood samples were obtained from six female adult badgers before, during, and after 22 days of fasting. The badgers lost an average of 67 g body weight per day and decreased both water consumption and urine production during the fast. No consistent changes in hematological parameters occurred during the fast and all animals appeared in good health at the termination of the study. Serum T3 levels dropped during the first few days of fasting and then plateaued, whereas serum glucose didn't significantly decline until after the 8th day of the fast. Nonesterified fatty acids increased through the first few days of the fast and achieved significantly higher levels after the 6th day. Urine potassium and nitrogen levels progressively declined throughout the fast. These data suggest that gluconeogenesis is diminished during the 22-day fast, thereby providing the badger with an adaptation to conserve protein during periods of prolonged food deprivation.
Taxonomy and distribution of marine Enchytraeidae (Oligochaeta) in British Columbia
Authors: Coates Kathryn , Ellis Derek V.
Published: April 2009

Twenty-one species of marine enchytraeid oligochaetes within the genera Enchytraeus, Grania, Marionina, and Lumbricillus are confirmed as occurring on the Pacific Coast of Canada. Taxonomic reviews with redescriptions where necessary are provided for 48 species, bringing 13 into synonymy. A further three species were left as taxa inquirenda. Marionina is the least homogeneous of the genera, and further species revisions may change the present concept of the genus. Species habitat preference is largely intertidal, often with decomposing algae, but some subtidal species have been found. There appears to be a Pacific regional fauna.
Behavioral response of Dendroctonus pseudotsugae and Trypodendron lineatum (Coleoptera: Scolytidae) to selected wavelength regions of the visible spectrum
Authors: Groberman L. J. , Borden J. H.
Published: April 2009

Behavioral experiments using a phototactic response by adult Dendroctonus pseudotsugae Hopkins and Trypodendron lineatum Olivier were tested in a two-choice, walking bioassay to all possible pairs of a series of wavelengths within the visible spectrum. With Corning band-pass and cut-off filters sensitivity maxima for both sexes of D. pseudotsugae were to the shortest wavelengths (425 and 476 nm), with a secondary response to the longest wavelengths (600–625 nm). With more precise Balzer band-pass filters both D. pseudotsugae and T. lineatum responded similarly, with sensitivity maxima for both sexes to wavelengths in the region of 420–480 nm and an additional response peak around 500–525 nm. These results correspond well with other behavioral and electrophysiological data from scolytid beetles.
The invasion route of the gill parasite Urocleidus adspectus Mueller, 1936 (Monogenea: Ancyrocephalinae)
Authors: Cone D. K. , Burt M. D. B.
Published: April 2009

Urocleidus adspectus is transmitted experimentally to yellow perch (Perca flavescens) and the route of invasion and the behaviour of the parasite during the migration to the gills of the host is studied.The oncomiracidia invade the full length of the host and. as postoncomiracidia, attach at secluded sites such as beneath scales, at the base of fins, and in nooks in the body surface. The postoncomiracidia gradually migrate anteriorly and reach the gills by entering the opercular cavity and possibly the buccal cavity. In young-of-the-year perch, migrating worms appear to invade the primary lamella from the base or from the distal tip. In older perch the majority appear to invade the primary lamella from the base. Over 90% of the postoncomiracidia reach the gills of the young perch by day 5 postinfection and experimental studies indicate that few worms are dislodged during the migration.
Genetic and environmental aspects of the response to water current by rainbow trout (Salmo gairdneri) originating from inlet and outlet streams of two lakes
Authors: Kelso B. W. , Northcote T. G. , Wehrhahn C. F.
Published: April 2009

Directional responses to water current by young rainbow trout fry, originating from seven parental stocks spawning in inlet or outlet streams of two British Columbia lakes, were studied in laboratory channels at three levels of temperature and two of illumination (light, dark). Intrastock and one complete 7 × 7 diallel cross were propagated for the experiment. The response of fry to water current was significantly affected by parental stock, illumination, and temperature. Significant genetic differences in current response scores were found among stocks in both light and dark trials. Mean upstream movement scores were generally higher for fry with outlet fathers than for those with inlet fathers. When data for the light and dark diallel experiments were combined, the mean difference in upstream movement scores between fry with outlet fathers and those with inlet fathers was 0.94 ± 0.26 which is significant at the 0.001 level. The corresponding mean difference between fry from outlet × outlet and inlet × inlet crosses was 1.34 ± 0.38 which is significant at the 0.0005 level. The interplay of genetic and environmental factors regulating lakeward migration of the young trout from the different types of parental spawning streams is discussed.
Antifreeze glycoproteins in the plasma of Newfoundland Atlantic cod (Gadus morhua)
Authors: Hew Choy L. , Slaughter Don , Fletcher Garth L. , Joshi Shashikant B.
Published: April 2009

The plasma of the Atlantic cod, Gadus morhua, contained antifreeze glycoproteins which were present only during the winter months. The antifreeze proteins were isolated, using gel filtration and ion exchange chromatography, and characterized by high performance liquid chromatography. The antifreeze proteins appeared to consist of at least seven components with molecular weights ranging from 2 500 to 33 000. Chemical analysis of the larger components showed a predominance of alanine, threonine, and galactosamine in a ratio of 2:1:1. The smaller peptides contained proline, in addition to alanine and threonine. The amino acid sequence of the smallest glycopeptide (molecular weight 2500) was found to be Ala Ala Thr Pro Ala Thr Ala Ala Thr Pro Ala Thr Ala Ala.These glycoproteins are very similar, if not identical, in amino acid and carbohydrate composition to those isolated from Antaractic nototheniids and several northern gadoids. The sequence of the smallest glycopeptide from the Atlantic cod is identical to that reported for the polar cod, Boreogadus saida.
Species of Ascarophis van Beneden, 1870 (Nematoda: Cystidicolidae) in North Atlantic fishes
Authors: Appy Ralph G.
Published: April 2009

Ascarophis arctica Poljansky, 1952, A. filiformis Poljansky, 1952 and Ascarophis extalicola sp.nov. are described from cod, Gadus morhua L. (Gadidae), collected in the northwestern Atlantic. All three species have narrow pseudolabia, four sublabia, deirids anterior to the nerve ring, and six postanal papillae. Ascarophis extalicola sp.nov. has a small blunt elevation on each pseudolabium, body length of 4 to 6 mm in males and 6 to 9 mm in females, vulva well posterior to midbody, right spicule 61 to 83 μm long, left spicule 276 to 359 μm long, and eggs with many filaments at one pole. This species occurs in the rectum and posterior intestine of cod and Myoxocephalus octodecemspinosus. Ascarophis arctica has pseudolabia each with a prominent conical apex, pronounced cuticular striations, left spicule 585 to 882 μm long with a bent and blunt tip, and eggs with many filaments at both poles. Ascarophis arctica infects the stomach of cod and eight other fish species. Ascarophis filiformis has pseudolabia each with a prominent conical apex, faint cuticular striations, left spicule 271 to 392 μm long with a straight and pointed tip, and eggs with two filaments at one pole. Ascarophis filiformis was found only in the stomach of cod. Local distributions, prevalence, and intensity of each species in cod are noted.
Neobakernema n. gen. (Nematoda: Criconematidae) with an emendation of Bakernema Wu, 1964
Authors: Ebsary B. A.
Published: April 2009

A new genus, Neobakernema, is proposed and the diagnosis of Bakernema emended. Neobakernema differs from Bakernema by the open vulva, straight vagina, and spined juveniles. Type and only species is Neobakernema variabile (Raski &Golden, 1966) n. comb.
Population ecology of Columbian ground squirrels in southwestern Alberta
Authors: Boag D. A. , Murie J. O.
Published: April 2009

The characteristics of a large population of Columbian ground squirrels (Spermophilus columbianus), the numbers of which varied between ca. 700 and 1000 animals emerging in the spring, were studied over a 7-year period in southwestern Alberta. Over time, the density of nonjuvenile squirrels varied between 11.6 and 16.1/ha, with a sex ratio that consistently favoured females; the density of juveniles varied between 4.6 and 20.7/ha, but with a sex ratio that was usually balanced. Spatially, the density of squirrels also varied with a certain part of the study area (17%) annually supporting proportionately more animals of each sex than the remaining 83%. Dispersal was recorded primarily among yearlings, with more males than females involved in this movement. Most dispersal occurred in late June and early July, centred on the time juveniles emerged from natal burrows. We recorded squirrels dispersing up to 6.7 km. Survival of squirrels in their 1st year of life was lower (females 40%; males 35%) than in any subsequent year (females 50–64%; males 37–54%). These attributes of Columbian ground squirrels are compared with those of other members of the genus, and the evidence they provide for population regulation is discussed.
Gyrodactylus pleuronecti n. sp. (Monogenea) from winter flounder (Pseudopleuronectes americanus) in Newfoundland, Canada
Authors: Cone D. K.
Published: April 2009

Gyrodactylus pleuronecti n. sp. is described from the fins, body surface, and gills of winter flounder (Pseudopleuronectes americanus) held in saltwater tanks at the Marine Sciences Research Laboratory, Memorial University of Newfoundland. Gyrodactylus pleuronecti n. sp. resembles G. avalonia Hanek and Threlfall, 1969, G. errabundus Malmberg, 1970, G. grönlandicus Levinsen, 1881, G. gymneli Zhukov, 1960, G. nainum Hanek and Threlfall, 1970, G. perlucidus Bychowsky and Poljansky, 1953, and G. pharyngicus Malmberg, 1964, in having a short hamulus root, a ventral bar with prominent anterolateral projections, and a posteriorly directed ventral membrane that tapers to a rounded extremity. However, compared with the similar species, G. pleuronecti n. sp. has relatively long hamuli (55 to 59 μm) but short marginal hooklets (27 to 29 μm). It also has a very well-developed ventral bar, which includes a comparatively long posteriorly directed ventral membrane (26 to 30 μm) of unique shape. The species description of G. pleuronecti n. sp. includes the digestive and reproductive organs but these systems proved to be similar to those of many gyrodactylids.
Alimentary tract parasites of haddock (Melanogrammus aeglefinus L.) on the Scotian Shelf
Authors: Scott J. S.
Published: April 2009

Nineteen species of alimentary tract (including gall and swim bladders) parasites were found in haddock (Melanogrammus aeglefinus) on the Scotian Shelf, of which eight species were new Canadian records for haddock. Prevalence ranged up to 82.3% for Hysterothylacium aduncum and 70.9% for Echinorhynchus gadi, the most abundant parasites, with Lepidapedon rachion and Echinorhynchus gadi showing highest intensities (14.9 and 76.5, respectively). Prevalence decreased from summer to winter, was not related to sex of host, but showed geographical variation characterizing different geographical areas. The Bay of Fundy showed higher nematode and lower trematode abundance than the offshore Scotian Shelf which showed general clines in abundance of several species from southwest to northeast. There was no evidence of growth-related change in parasite prevalence in adult fish, but the parasite complex of young-of-the-year haddock indicated planktonic feeding, in contrast with benthic feeding in the adult. Site specificity within the alimentary tract was shown by several species. Echinorhynchus gadi changed its site seasonally. Lepidapedon rachion showed size differentiation in the gut, smaller trematodes occupying more anterior sites than larger. Only two parasite species offer prospects as biological tags, L. rachion and Myxidium bergense, but all may provide evidence of ecological, behavioral, seasonal and developmental changes in the host.
Analysis of variation in the Elaphrus americanus complex of North America (Coleoptera: Carabidae)
Authors: Goulet Henri , Baum Bernard R.
Published: April 2009

Elaphrus americanus Dejean (sensu Lindroth, 1961) is a complex of two nearctic species: E. americanus and E. finitimus Casey. This study is primarily devoted to E. americanus, which includes two subspecies: a boreal subspecies and a newly described western subspecies, E. americanus sylvanus Goulet n. subsp., for which the type locality is Oregon, Coos Co., 16 miles north of Powers.The species and subspecies mentioned above were recognized by means of numerical taxonomic analysis. Most intuitively acceptable were the results of phenetic clustering of Mahalanobis distances followed by a series of discriminant analyses. Various analyses were carried out based directly on computed euclidean distances, e.g. principal coordinate analyses, nonmetric multidimensional scaling, and still others by computing first the variance–covariance matrix, e.g., principal component analyses. Other geographically distinct populations were recognized by univariate analysis of nominal characters.Phylogenetic relationships between various populations of E. americanus are partly reconstructed. A reconstruction of past distribution of these populations is presented and their evolutionary significance discussed.
Ultrastructure et mise en place des organelles buccaux au cours de la régénération orale chez Stentor coeruleus (Cilié Hétérotriche)
Authors: Bernard Françoise , Bohatier Jacques
Published: April 2009

Differentiation of oral organelles during oral regeneration has been studied by electron microscopy. During a first phase, intense kinetosomal proliferation takes place resulting in an unorganized field where kinetosomes are precociously associated in pairs, one kinetosome in each pair being equipped with postciliary derivatives and the other with one transverse derivative. Observation of the next steps shows (a) that the different pairs have no particular orientation within the field and (b) that the differentiation of the adoral and then the paroral ciliatures may be interpreted as a progressive organization of these pairs. To the left, the pairs assemble at different levels along parallel lines; adoral membranelles must thus be considered as transverse sequences of kinetosomal pairs. To the right, the different pairs assemble along longitudinal lines, their positioning being progressive and leading to the formation of the "stychodyad" type at the level of the frontal field and of the "inverted pairs" type at the level of the cytopharynx. The ultrastructure of the paroral complex in Stentor is thus composite. The results demonstrate the possibility of formation of a "stychodyad" type paroral complex in a Polyhymenophora and illustrate that the coupling of kinetosomes as pairs or as dyads is directly dependent on the cell territory.[Journal translation]
Pararetinometra lateralacantha gen. et sp. nov. (Cestoda: Hymenolepididae) in grebes (Podicipedidae) from Alberta
Authors: Stock T. M. , Holmes J. C.
Published: April 2009

Pararetinometra lateralacantha gen. et sp. nov. is a hymenolepidid cyclophyllidean described from the anterior portion of the small intestine of the red-necked grebe, Podiceps grisegena (Boddaert), and the eared grebe, P. nigricollis (Brehm), from Alberta. The scolex bears eight skrjabinoid-type rostellar hooks, 77–83 μm long. The major distinguishing feature is a crescent-shaped ridge bearing a series of sickle-shaped hooks on each posterolateral margin of each proglottid. Other features resemble the genus Retinometra Spassky, 1955.
Trophic ecology of Athene owls in mediterranean-type ecosystems: a comparative analysis
Authors: Jaksić Fabian M. , Marti Carl D.
Published: April 2009

Populations of Athene owls are found in the mediterranean-type ecosystems of Chile (A. cunicularia cunicularia, formerly in the genus Speotyto), California (A. cunicularia hypugea), and Spain (A. noctua). We assess whether the tropic ecology of Athene owls in these chaparral habitats is more similar between these three populations than between any of these and populations in a different kind of habitat. The control is provided by a population of A. cunicularia hypugea inhabiting a grassland in Colorado. The trophic ecology of the four populations is characterized qualitatively by the taxonomic composition of the diets and quantitatively by means of trophic diversity measurements and computation of the mean weights of mammalian prey taken. At the intraspecific level of resolution, Chilean and Californian populations are more similar to each other than they are to the population in Colorado. At the interspecific level of resolution, A. noctua is not more similar to chaparral A. cunicularia than it is to grassland A. cunicularia. The differences between Colorado A. cunicularia and the conspecific populations in Chile and California are shown to be associated with a discrepancy in the size configuration of the owl assemblages between grassland and chaparral habitats, and perhaps to differences in the relative abundance of small-sized mammals. The dissimilarities in the trophic ecology between Spanish A. noctua and the New World A. cunicularia are hypothesized to stem from differential availability of amphibian and reptile prey.
Cycle de développement, croissance et production de Pisidium amnicum (Mollusca: Bivalvia) dans le Saint-Laurent (Québec)
Authors: Vincent B. , Vaillancourt G. , Lafontaine N.
Published: April 2009

The population dynamics of Pisidium amnicum have been studied in one population of the St. Lawrence River over a 2-year period during which 19 samples were taken. The species can live up to 3 years and it is iteroparous; individuals generally attain sexual maturity after 1 year and they reproduce twice, once at 2 and once at 3 years of age. In adults, mortality is lower in winter than during the rest of the year and mortality rates are twice as high during the 1st year than during the 2nd year. Total dry weight (PT, in milligrams) is related to maximum length (L, in millimetres) according to the equation PT = 0.0283∙L3,80 and flesh dry weight (PC, in milligrams) is related to length as follows: PC = 0.007∙L3,18. The annual production to mean biomass (P/B) ratio is 1.4, the mean annual production being 1.298 mg/m2 of total dry weight and 107 mg/m2 of flesh weight. Comparing these results with those obtained for the gastropod Bithynia tentaculata in the same environment and at the same period of the year has shown that the growth of Pisidium amnicum is far less influenced by the temperature regime than that of the other species and that its production is at least 10 times lower.
Tintinnids of Chesterfield Inlet, Northwest Territories
Authors: Rogers G. F. , Roff J. C. , Lynn D. H.
Published: April 2009

Tintinnids were numerically dominant in plankton samples collected from Chesterfield Inlet, Northwest Territories, in September 1978. Thirteen species were identified, 11 of which are new records for the Hudson Bay area. Tintinnopsis fimbriata and T. angusta were the most numerous tintinnids in the upper estuary at salinities below 24‰; their cell numbers were significantly positively correlated to temperature. Parafavella denticulata was the most abundant species in marine waters but it penetrated the estuary to salinities as low as 4‰. Cell numbers and volumes of P. denticulata were significantly positively correlated to salinity and negatively to chlorophyll; this species appeared to act as an almost conservative indicator of marine influence in this estuary. The distributions of the two Tintinnopsis species were not so readily explained, but maximum numbers of T. fimbriata and T. angusta corresponded to a phytoplankton maximum at station 29 in the middle estuary.
The masked shrew (Sorex cinereus), a new host for Capillaria plica
Authors: Bourque Michel
Published: April 2009

Capillaria plica (Rudolphi, 1819) was identified in an additional host species in North America, the masked shrew (Sorex cinereus).
Recognition of Leuroglossus schmidti and L. stilbius (Bathylagidae, Pisces) as distinct species in the North Pacific Ocean
Authors: Peden Alex E.
Published: April 2009

Data from vertebral counts suggest two species of Leuroglossus occur off the west coast of North America: Leuroglossus schmidti north of the Strait of Juan de Fuca and L. stilbius off Oregon and southward.
Word Topic Models for Spoken Document Retrieval and Transcription
Authors: Chen Berlin
Published: April 2009

Statistical language modeling (LM), which aims to capture the regularities in human natural language and quantify the acceptability of a given word sequence, has long been an interesting yet challenging research topic in the speech and language processing community. It also has been introduced to information retrieval (IR) problems, and provided an effective and theoretically attractive probabilistic framework for building IR systems. In this article, we propose a word topic model (WTM) to explore the co-occurrence relationship between words, as well as the long-span latent topical information, for language modeling in spoken document retrieval and transcription. The document or the search history as a whole is modeled as a composite WTM model for generating a newly observed word. The underlying characteristics and different kinds of model structures are extensively investigated, while the performance of WTM is thoroughly analyzed and verified by comparison with the well-known probabilistic latent semantic analysis (PLSA) model as well as the other models. The IR experiments are performed on the TDT Chinese collections (TDT-2 and TDT-3), while the large vocabulary continuous speech recognition (LVCSR) experiments are conducted on the Mandarin broadcast news collected in Taiwan. Experimental results seem to indicate that WTM is a promising alternative to the existing models.
Testing bipartiteness of geometric intersection graphs
Authors: Eppstein David
Published: April 2009

We show how to test the bipartiteness of an intersection graph of
n
line segments or simple polygons in the plane, or of an intersection graph of balls in
d
-dimensional Euclidean space, in time
O
(
n
log
n
). More generally, we find subquadratic algorithms for connectivity and bipartiteness testing of intersection graphs of a broad class of geometric objects. Our algorithms for these problems return either a bipartition of the input or an odd cycle in its intersection graph. We also consider lower bounds for connectivity and
k
-colorability problems of geometric intersection graphs. For unit balls in
d
dimensions, connectivity testing has equivalent randomized complexity to construction of Euclidean minimum spanning trees, and for line segments in the plane connectivity testing has the same lower bounds as Hopcroft's point-line incidence testing problem; therefore, for these problems, connectivity is unlikely to be solved as efficiently as bipartiteness. For line segments or planar disks, testing
k
-colorability of intersection graphs for
k
> 2 is NP-complete.
Online conflict-free coloring for halfplanes, congruent disks, and axis-parallel rectangles
Authors: Chen Ke , Kaplan Haim , Sharir Micha
Published: April 2009

We present randomized algorithms for online conflict-free coloring (CF in short) of points in the plane, with respect to halfplanes, congruent disks, and nearly-equal axis-parallel rectangles. In all three cases, the coloring algorithms use
O
(log
n
) colors, with high probability.

We also present a deterministic algorithm for online CF coloring of points in the plane with respect to nearly-equal axis-parallel rectangles, using
O
(log
3
n
) colors. This is the first efficient (i.e, using polylog(
n
) colors) deterministic online CF coloring algorithm for this problem.
Throughput maximization of real-time scheduling with batching
Authors: Bar-Noy Amotz , Guha Sudipto , Katz Yoav , Naor Joseph (Seffi) , Schieber Baruch , Shachnai Hadas
Published: April 2009

We consider the following scheduling with batching problem that has many applications, for example, in multimedia-on-demand and manufacturing of integrated circuits. The input to the problem consists of
n
jobs and
k
parallel machines. Each job is associated with a set of time intervals in which it can be scheduled (given either explicitly or nonexplicitly), a weight, and a family. Each family is associated with a processing time. Jobs that belong to the same family can be batched and executed together on the same machine. The processing time of each batch is the processing time of the family of jobs it contains. The goal is to find a nonpreemptive schedule with batching that maximizes the weight of the scheduled jobs. We give constant factor (4 or 4 + ε) approximation algorithms for two variants of the problem, depending on the precise representation of the input. When the batch size is unbounded and each job is associated with a time window in which it can be processed, these approximation ratios reduce to 2 and 2 + ε, respectively. We also give approximation algorithms for two special cases when all release times are the same.
Bicriteria approximation tradeoff for the node-cost budget problem
Authors: Rabani Yuval , Scalosub Gabriel
Published: April 2009

We consider an optimization problem consisting of an undirected graph, with cost and profit functions defined on all vertices. The goal is to find a connected subset of vertices with maximum total profit, whose total cost does not exceed a given budget. The best result known prior to this work guaranteed a (2,
O
(log
n
)) bicriteria approximation, that is, the solution's profit is at least a fraction of 1/
O
(log
n
) of an optimum solution respecting the budget, while its cost is at most twice the given budget. We improve these results and present a bicriteria tradeoff that, given any ε ∈ (0,1], guarantees a (1 + ϵ,
O
(1/ε log
n
))-approximation.
A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2
Authors: Even Guy , Feldman Jon , Kortsarz Guy , Nutov Zeev
Published: April 2009

We present a 1.8-approximation algorithm for the following NP-hard problem: Given a connected graph
G
= (
V
,
E
) and an edge set
E
on
V
disjoint to
E
, find a minimum-size subset of edges
F
⊆
E
such that (
V
,
E
∪
F
) is 2-edge-connected. Our result improves and significantly simplifies the approximation algorithm with ratio 1.875 + ε of Nagamochi.
Approximating the distance to properties in bounded-degree and general sparse graphs
Authors: Marko Sharon , Ron Dana
Published: April 2009

We address the problem of approximating the distance of bounded-degree and general sparse graphs from having some predetermined graph property
P
. That is, we are interested in sublinear algorithms for estimating the fraction of edge modifications (additions or deletions) that must be performed on a graph so that it obtains
P
. This fraction is taken with respect to a given upper bound
m
on the number of edges. In particular, for graphs with degree bound
d
over
n
vertices,
m
=
dn
. To perform such an approximation the algorithm may ask for the degree of any vertex of its choice, and may ask for the neighbors of any vertex.

The problem of estimating the distance to having a property was first explicitly addressed by Parnas et al. [2006]. In the context of graphs this problem was studied by Fischer and Newman [2007] in the dense graphs model. In this model the fraction of edge modifications is taken with respect to
n
2
, and the algorithm may ask for the existence of an edge between any pair of vertices of its choice. Fischer and Newman showed that every graph property that has a testing algorithm in this model, with query complexity independent of the size of the graph, also has a distance approximation algorithm with query complexity that is independent of the size of graph.

In this work we focus on bounded-degree and general sparse graphs, and give algorithms for all properties shown to have efficient testing algorithms by Goldreich and Ron [2002]. Specifically, these properties are
k
-edge connectivity, subgraph freeness (for constant-size subgraphs), being an Eulerian graph, and cycle freeness. A variant of our subgraph-freeness algorithm approximates the size of a minimum vertex cover of a graph in sublinear time. This approximation improves on a recent result of Parnas and Ron [2007].
System-level PVT variation-aware power exploration of on-chip communication architectures
Authors: Pasricha Sudeep , Park Young-Hwan , Dutt Nikil , Kurdahi Fadi J.
Published: April 2009

With the shift towards deep submicron (DSM) technologies, the increase in leakage power and the adoption of power-aware design methodologies have resulted in potentially significant variations in power consumption under different process, voltage, and temperature (PVT) corners. In this article, we first investigate the impact of PVT corners on power consumption at the system-on-chip (SoC) level, especially for the on-chip communication infrastructure. Given a target technology library, we then show how it is possible to “scale up” and abstract the PVT variability at the system level, allowing characterization of the PVT-aware design space early in the design flow. We conducted several experiments to estimate power for PVT corner cases, at the gate level, as well as at the higher system level. Our preliminary results are very interesting, and indicate that (i) there are significant variations in power consumption across PVT corners; and (ii) the PVT-aware power estimation problem may be amenable to a reasonably simple abstraction at the system level.
Trade-offs in loop transformations
Authors: Palkovic Martin , Catthoor Francky , Corporaal Henk
Published: April 2009

Nowadays, multimedia systems deal with huge amounts of memory accesses and large memory footprints. To alleviate the impact of these accesses and reduce the memory footprint, high-level memory exploration and optimization techniques have been proposed. These techniques try to more efficiently utilize the memory hierarchy. An important step in these optimization techniques are loop transformations (LT). They have a crucial effect on later data memory footprint optimization steps and code generation. However, the state-of-the-art work has focused only on individual objectives. The main one in literature involves improving the locality of data accesses, and thus reducing the data memory footprint. It does not consider the trade-offs in the LT step in relation to successive optimization steps. Therefore, it is not globally efficient in mapping the application on the target platform.

In this article we will discuss several trade-offs during the loop transformations. To our knowledge, we are the first ones considering these global trade-offs. Previous work always gave mostly one solution, having the best locality and thus the optimized memory footprint, even though some research in two-dimensional trade-offs in this area exists as well. We start from this state-of-the-art solution with minimal footprint. We show that by sacrificing the footprint, we can obtain gains in data reuse (crucial for energy reduction) and reduce the control-flow complexity. We demonstrate our approach on a real-life application, namely the QSDPCM video coder. At the end, we show that considering trade-offs for this application leads to 16% energy reduction in a two-layer memory subsystem and 10% cycle reduction on the ARM platform.
Reducing fault dictionary size for million-gate large circuits
Authors: Hong Yu-Ru , Huang Juinn-Dar
Published: April 2009

In general, fault dictionary is prevented from practical applications in fault diagnosis due to its extremely large size. Several previous works are proposed for the fault dictionary size reduction. However, some of them fail to bring down the size to an acceptable level, and others might not be able to handle today's million-gate circuits due to their high time and space complexity. In this article, an algorithm is presented to reduce the size of pass-fail dictionary while still preserving high diagnostic resolution. The proposed algorithm possesses low time and space complexity by avoiding constructing the huge distinguishability table, which inevitably boosts up the required computation complexity. Experimental results demonstrate that the proposed algorithm is capable of handling industrial million-gate large circuits in a reasonable amount of runtime and memory.
Efficient partial scan cell gating for low-power scan-based testing
Authors: Kavousianos Xrysovalantis , Bakalis Dimitris , Nikolos Dimitris
Published: April 2009

Gating of the outputs of a portion of the scan cells (partial gating) has been recently proposed as a method for reducing the dynamic power dissipation during scan-based testing. We present a new systematic method for selecting, under area and performance design constraints, the most suitable for gating subset of scan cells as well as the proper gating value for each one of them, aiming at the reduction of the average switching activity during testing. We show that the proposed method outperforms the corresponding already known methods, with respect to average dynamic power dissipation reduction.
Battery voltage modeling for portable systems
Authors: Rakhmatov Daler
Published: April 2009

Limited battery life imposes stringent constraints on the operation of battery-powered portable systems. During battery discharge, the battery voltage decreases, until a certain cutoff value is reached, marking the end of battery life. The amount of discharge capacity and energy delivered by the battery during its life depends not only on the battery characteristics, but also on the load conditions. A different system design may result in a different battery current (load) profile over time, leading to a different battery voltage profile over time. This article presents an analytical model that relates the battery voltage to the battery current, thus facilitating system design optimizations with respect to the battery performance. It captures well-known nonlinear phenomena of capacity loss at high discharge rates, charge recovery, and capacity fading. The proposed model has been validated against measurements taken on Li-ion batteries. We also describe techniques for efficient calculations of model's estimates, which lets a user exploit accuracy-complexity tradeoffs.
External memory layout vs. schematic
Authors: Kumar Yokesh , Gupta Prosenjit
Published: April 2009

The circuit represented by a VLSI layout must be verified by checking it against the schematic circuit as an important part of the functional verification step. This involves two central problems of matching the circuit graphs with each other (graph isomorphism) and extracting a higher level of circuit from a given level by finding subcircuits in the circuit graph (subgraph isomorphism). Modern day VLSI layouts contain millions of devices. Hence the memory requirements of the data structures required by tools for verifying them become huge and can easily exceed the amount of internal memory available on a computer. In such a scenario, a program not aware of the memory hierarchy performs badly because of its unorganized input/output operations (I/Os) as the speed of a disk access is about a million times slower than accessing a main memory location. In this article, we present I/O-efficient algorithms for the graph isomorphism and subgraph isomorphism problems in the context of verification of VLSI layouts. Experimental results show the need and utility of I/O-efficient algorithms for handling problems with large memory requirements.
BoxRouter 2.0
Authors: Cho Minsik , Lu Katrina , Yuan Kun , Pan David Z.
Published: April 2009

In this article, we present BoxRouter 2.0, and discuss its architecture and implementation. As high-performance VLSI design becomes more interconnect-dominant, efficient congestion elimination in global routing is in greater demand. Hence, we propose a global router which has a strong ability to improve routability and minimize the number of vias with blockages, while minimizing wirelength. BoxRouter 2.0 is extended from BoxRouter 1.0, but can perform multi-layer routing with 2D global routing and layer assignment. Our 2D global routing is equipped with two ideas: node shifting for congestion-aware Steiner tree and robust negotiation-based A* search for routing stability. After 2D global routing, 2D-to-3D mapping is done by the layer assignment which is powered by progressive via/blockage-aware integer linear programming. Experimental results show that BoxRouter 2.0 has better routability with comparable wirelength than other routers on ISPD07 benchmark, and it can complete (no overflow) the widely used ISPD98 benchmark for the first time in the literature with the shortest wirelength. We further generate a set of harder ISPD98 benchmarks to push the limit of BoxRouter 2.0, and propose the hardened ISPD98 benchmarks to map state-of-the-art solutions for future routing research.
FPGA-based hardware acceleration for Boolean satisfiability
Authors: Gulati Kanupriya , Paul Suganth , Khatri Sunil P. , Patil Srinivas , Jas Abhijit
Published: April 2009

We present an FPGA-based hardware solution to the Boolean satisfiability (SAT) problem, with the main goals of scalability and speedup. In our approach the traversal of the implication graph as well as conflict clause generation are performed in hardware, in parallel. The experimental results and their analysis, along with the performance models are discussed. We show that an order of magnitude improvement in runtime can be obtained over MiniSAT (the best-in-class software based approach) by using a Virtex-4 (XC4VFX140) FPGA device. The resulting system can handle instances with as many as 10K variables and 280K clauses.
Semi-analytical method for analyzing models and model selection measures based on moment analysis
Authors: Dhurandhar Amit , Dobra Alin
Published: April 2009

In this article we propose a moment-based method for studying models and model selection measures. By focusing on the probabilistic space of classifiers induced by the classification algorithm rather than on that of datasets, we obtain efficient characterizations for computing the moments, which is followed by visualization of the resulting formulae that are too complicated for direct interpretation. By assuming the data to be drawn independently and identically distributed from the underlying probability distribution, and by going over the space of all possible datasets, we establish general relationships between the generalization error, hold-out-set error, cross-validation error, and leave-one-out error. We later exemplify the method and the results by studying the behavior of the errors for the naive Bayes classifier.
Closed patterns meet
n
-ary relations
Authors: Cerf Loïc , Besson Jérémy , Robardet Céline , Boulicaut Jean-François
Published: April 2009

Set pattern discovery from binary relations has been extensively studied during the last decade. In particular, many complete and efficient algorithms for frequent closed set mining are now available. Generalizing such a task to
n
-ary relations (
n
≥ 2) appears as a timely challenge. It may be important for many applications, for example, when adding the time dimension to the popular
objects
×
features
binary case. The generality of the task (no assumption being made on the relation arity or on the size of its attribute domains) makes it computationally challenging. We introduce an algorithm called Data-Peeler. From an
n
-ary relation, it extracts all closed
n
-sets satisfying given piecewise (anti) monotonic constraints. This new class of constraints generalizes both monotonic and antimonotonic constraints. Considering the special case of ternary relations, Data-Peeler outperforms the state-of-the-art algorithms CubeMiner and Trias by orders of magnitude. These good performances must be granted to a new clever enumeration strategy allowing to efficiently enforce the closeness property. The relevance of the extracted closed
n
-sets is assessed on real-life 3-and 4-ary relations. Beyond natural 3-or 4-ary relations, expanding a relation with an additional attribute can help in enforcing rather abstract constraints such as the robustness with respect to binarization. Furthermore, a collection of closed
n
-sets is shown to be an excellent starting point to compute a tiling of the dataset.
Bellwether analysis
Authors: Chen Bee-Chung , Ramakrishnan Raghu , Shavlik Jude W. , Tamma Pradeep
Published: April 2009

How to mine massive datasets is a challenging problem with great potential value. Motivated by this challenge, much effort has concentrated on developing scalable versions of machine learning algorithms. However, the cost of mining large datasets is not just computational; preparing the datasets into the “right form” so that learning algorithms can be applied is usually costly, due to the human labor that is typically required and a large number of choices in data preparation, which include selecting different subsets of data and aggregating data at different granularities. We make the key observation that, for a number of practically motivated problems, these choices can be defined using database queries and analyzed in an automatic and systematic manner. Specifically, we propose a new class of data-mining problem, called
bellwether analysis
, in which the goal is to find a few query-defined predictors (e.g., first week sales of Peoria, IL of an item) that can be used to accurately predict the result of a target query (e.g., first year worldwide sales of the item) from a large number of queries that define candidate predictors. To make a prediction for a new item, the data needed to generate such predictors has to be collected (e.g., selling the new item in Peoria, IL for a week and collecting the sales data). A useful predictor is one that has high prediction accuracy and a low data-collection cost. We call such a cost-effective predictor a
bellwether
.

This article introduces bellwether analysis, which integrates database query processing and predictive modeling into a single framework, and provides scalable algorithms for large datasets that cannot fit in main memory. Through a series of extensive experiments, we show that bellwethers do exist in real-world databases, and that our computation techniques achieve good efficiency on large datasets.
Making secure processors OS- and performance-friendly
Authors: Chhabra Siddhartha , Rogers Brian , Solihin Yan , Prvulovic Milos
Published: April 2009

In today's digital world, computer security issues have become increasingly important. In particular, researchers have proposed designs for secure processors that utilize hardware-based memory encryption and integrity verification to protect the privacy and integrity of computation even from sophisticated physical attacks. However, currently proposed schemes remain hampered by problems that make them impractical for use in today's computer systems: lack of virtual memory and Inter-Process Communication support as well as excessive storage and performance overheads. In this article, we propose (1) address independent seed encryption (AISE), a counter-mode-based memory encryption scheme using a novel seed composition, and (2) bonsai Merkle trees (BMT), a novel Merkle tree-based memory integrity verification technique, to eliminate these system and performance issues associated with prior counter-mode memory encryption and Merkle tree integrity verification schemes. We present both a qualitative discussion and a quantitative analysis to illustrate the advantages of our techniques over previously proposed approaches in terms of complexity, feasibility, performance, and storage. Our results show that AISE+BMT reduces the overhead of prior memory encryption and integrity verification schemes from 12% to 2% on average for single-threaded benchmarks on uniprocessor systems, and from 15% to 4% for coscheduled benchmarks on multicore systems while eliminating critical system-level problems.
Optimal trace scheduling using enumeration
Authors: Shobaki Ghassan , Wilken Kent , Heffernan Mark
Published: April 2009

This article presents the first optimal algorithm for trace scheduling. The trace is a global scheduling region used by compilers to exploit instruction-level parallelism across basic block boundaries. Several heuristic techniques have been proposed for trace scheduling, but the precision of these techniques has not been studied relative to optimality. This article describes a technique for finding provably optimal trace schedules, where optimality is defined in terms of a weighted sum of schedule lengths across all code paths in a trace. The optimal algorithm uses branch-and-bound enumeration to efficiently explore the entire solution space. Experimental evaluation of the algorithm shows that, with a time limit of 1 s per problem, 91% of the hard trace scheduling problems in the SPEC CPU 2006 Integer Benchmarks are solved optimally. For 58% of these hard problems, the optimal schedule is improved compared to that produced by a heuristic scheduler with a geometric mean improvement of 3.2% in weighted schedule length and 18% in compensation code size.
Our sentiments, exactly
Authors: Wright Alex
Published: April 2009

With sentiment analysis algorithms, companies can identify and assess the wide variety of opinions found online and create computational models of human opinion.