bluuebunny/crossref_metadata_2025 huggingface dataset:
Burial diagenesis of Brent sandstones: a study of Statfjord, Hutton and Lyell fields
Authors: Harris Nicholas B.
Published: September 2007

Brent sandstone compositions vary systematically with increasing depth and temperature in three North Sea fields. At Statfjord field (
c.
2500 m), sandstones are arkoses, lithic arkoses and subarkoses. At Hutton field (
c
. 3050 m), sandstones are subarkoses and quartzarenites, whereas at Lyell field (
c
. 3500 m), sandstones are mostly quartzarenites. Compositions are transformed by pervasive dissolution of plagioclase at relatively shallow depth, dissolution of K-feldspar at greater depth, and alteration of detrital mica to kaolinite or illite. Quartz cement is a minor constituent at Statfjord, mostly forming early during meteoric water flushing. Quartz cement abundance increases significantly at Hutton and particularly at Lyell, where quartz cement comprises up to 130f rock volume; the increase in quartz cement coincides with dissolution of detrital quartz along stylolites and microstylolites at temperatures greater than 90–100°C as well as the dissolution of feldspar.

The dominant clay at Statfjord is kaolinite; at Hutton, illite forms as a pore-lining precipitate and, at Lyell, also by alteration of previously formed kaolinite. The transition from a kaolinite-dominated to an illite-dominated sandstone is probably controlled by several factors, among these the dissolution of K-feldspar, which may be due either to an influx of organic acids from the overlying Heather and Kimmeridge Clay Formations or to thermodynamic instability of the assemblage kaolinite-illite-K-feldspar at temperatures greater than 100°C. Elevated silica activity due to quartz dissolution on styloites and microstylolites may also induce illite formation.

Chemical analysis of sandstone samples shows the Brent undergoes systematic loss of sodium and, to a lesser extent, potassium during burial diagenesis. The sodium loss is consistent with observed plagioclase dissolution. The potassium loss indicates that the potassium in illite is derived from the Brent itself, probably from dissolved K-feldspar, and not from an external source such as a basinal brine.
The petrophysical characteristics of the Brent sandstones
Authors: Moss Brian
Published: September 2007

The commonly occurring ranges and the principal controlling factors of the porosity, permeability, capillary characteristics and fluid saturations of the Brent sandstones are presented. Whilst there is insufficient space to discuss these parameters in specific detail, their variability and the degree to which they are influenced by the geological characteristics of the Brent sandstones is reviewed. The paper shows, through the use of examples, that a thorough understanding of the petrophysical characteristics of a reservoir rock requires the integration of several types of data into a single model. The wireline log and laboratory core analyses provide a quantitative input, whilst geological factors such as mineralogy, diagenetic history, and sedimentary fabric provide a most necessary framework within which the pore geometry variability, detected by log and core data, can be examined. An appendix summarizes the principal quantitative techniques involved.
Opportunities for the development and utilization of coalbed methane in three coal basins in Russia and Ukraine
Authors: Marshall James S. , Pilcher Raymond C. , Bibler Carol J.
Published: September 2007

The coal mining regions of Russia and Ukraine liberate almost 4.5 × 10
9
m
3
of methane annually, of which only 3.9% is being utilized. Preliminary estimates suggest that the methane resources contained in coal mines of the Donetsk, Kuznetsk and L’vov-Volyn basins range from 0.6 to 1.1 × 10
12
m
3
. Various opportunities exist for increasing the quantity and quality of methane recovered from coal mines in these basins. The most attractive options for utilization of this methane include generating heat and power for use at mine facilities and nearby industries or residences.
Nature and origin of fractures in Permian coals from the Bowen Basin, Queensland, Australia
Authors: Pattison C. I. , Fielding C. R. , McWatters R. H. , Hamilton L. H.
Published: September 2007

A field investigation into the development of cleat and other fractures within Permian coal measures was undertaken in the Bowen Basin of eastern Queensland, Australia to provide predictive information on coal permeability for use in coalbed methane exploration. Data were collected from five open-cut and three underground mines in the southern and central Bowen Basin, covering the Upper Permian German Creek Formation and Rangal Coal Measures. Fractures noted in the coals fall readily into the four categories of faults and shear zones, extension and compression-related joint sets, mining-induced fractures and coal cleats. Four geometric varieties of coal cleats were identified: class A orthogonal sets, class B sinusoidal sets, class C polygonal sets and class D chaotic sets. Superimposed or overprinted type A sets were also observed locally. On a regional scale the cleats typically parallel dip (face cleats) and strike (butt cleats), but local departures from this pattern occur in proximity to faults, where face and butt cleat directions were often reversed, rotated or multimodal. Field data suggest that coal cleats of classes A B and C were formed by brittle fracturing of the coal during burial, wheras class D and superimposed cleats were formed during later compressional events. Constraints on the timing of deformation events affecting the Bowen Basin, and geochemical data provided by other workers indicate that the cleats were formed within 5 Ma of formation of precursor peats, but were in many instances modified by later structural events.
Palaeoceanographic information derived from acoustic surveys of glaciated continental margins: examples from eastern Canada
Authors: Syvitski James P. M. , Lewis C. F. Michael , Piper David J. W. , Syvitski James P. M.
Published: September 2007

Much palaeoceanographic information can be gleaned from seismic, sidescan and bathymetric data on glaciated continental shelves. High-resolution seismic reflection surveys of regional ice terminus features define palaeo-ice margins, datable using interfingering ice-proximal glacimarine deposits. Isopach maps show differences in regional accumulation rates of sediments during deglaciation phases and help locate positions of former glacifluvial discharge outlets. Maps of ice-distal glacimarine muds suggest that surface currents carrying buoyant plumes of glacial flour may extend >100 km from an ice margin. Transport and melt of icebergs controlled by circulation of deeper outer shelf and slope currents and episodic storms can result in a glacial influence >1000 km from the ice margin, but most iceberg-rafted sedimentation occurs within a few hundred kilometres of calving. The direction of these palaeo-mid-depth currents may be obtained from statistical analysis of relict iceberg scour patterns and from sediment dispersal patterns. The geometry of glacimarine deposits commonly suggests that there was water column stratification with associated weak near-seafloor currents. Comparison of the shape of glacimarine and post-glacial sediment packages shows that in many places the tidal current intensity has increased through the Holocene, reflecting sea-level change on the shelf.
Rock (mineral)-magnetic properties of post-glacial (16–0.5 ka) sediments from the Emerald Basin (Scotian Shelf), Canada
Authors: Hall Frank R. , Reed Stefanie J.
Published: September 2007

The Emerald Basin is a shallow, ice-scoured marine basin located on the central Scotian Shelf. Rock magnetic analyses were performed on (1) four piston cores (H87003-002, 004 and 006; H88-010-005) extracted from the central portion of the basin, (2) outctrop samples collected from 11 sites on the Nova Scotian mainland and (3) a borehole sample collected from the Gulf of St Lawrence. The results of these analyses show that the rock magnetic data have a consistent pattern throughout the Emerald Basin. In particular, magnetic mineral compositional and grain size parameters show a significant change between about 11 and 10 ka, implying a change in sedimentation patterns associated with the Younger Dryas chronozone. Further, the results of these analyses suggest that the rock magnetic data can be used to differentiate between potential sediment sources from the northwest and southeast sides of the mainland. No evidence of red beds from the northwest of the mainland entering the basin is observed, suggesting that sediments from the Gulf of St Lawrence side of Nova Scotia bypassed the shelf, probably being transported to the deep sea via the Laurentian Channel.
Foraminiferal biostratigraphy of the post-mid-Miocene in the Danish Central Trough, North Sea
Authors: Konradi P. B.
Published: September 2007

The formatiniferal content of ditch cutting samples from three exploration wells in the Danish North Sea has been investigated in the sections above the mid-Miocene marker. The wells are Cleo-1, situated at the edge of the Central Trough, and Kim-1 and M-10 situated in the central part of the trough, in the northern and the southern part, respectively. Based on analysis of the benthic foraminiferal faunas, the strata in the boreholes are subdivided in accordance with the standard North Sea zonation. The interpretations of the faunal assemblages indicate the oldest strata to be deposited in an open marine, outer shelf environment. Up-hole through the wells, the content of planktonic species diminishes gradually; the benthic assemblages indicate shallowing water depth reaching an inner shelf to littoral environment. This is interpreted to reflect the filling of the North Sea Basin through the Middle to Late Miocene when sedimentation mainly occurred in the north. In Early Pliocene the sedimentation centre had shifted to the south whereas in Late Pliocene a hiatus is found in the south and northeast and sedimentation only took place in the northwest in the basin centre. The faunas in the Pleistocene deposits indicate an inner shelf to littoral environment, with periods of reduced salinity and non-marine sedimentation.
Tidal sedimentation in Inner Hebrides half grabens, Scotland: the Mid-Jurassic Bearreraig Sandstone Formation
Authors: Mellere D. , Steel R. J.
Published: September 2007

The Bearreraig Sandstone Formation (Late Toarcian-Bajocian), on the islands of Skye and Raasay, in NW Scotland, forms part of the marine infill of one of the Hebridean rift basins that developed during the early stages of the opening of the North Atlantic. The Formation, up to 250 m thick in south Skye, and from 150 m to 180 m thick in north Skye and Raasay, is a spectacular succession of medium to coarse-grained, tidally generated, cross-bedded sandstones, and subordinate shales. The sandstones sharply overlie the Dun Caan Shales and Raasay Ironstone and are abruptly blanketed by the Garantiana Clay Member.

The succession was deposited under the influence of a series of significant sea-level fluctuations during a 12 Ma interval. During regressive phases of the basin coastline, sedimentation occurred largely at the mouth of a tidal-dominated delta which evolved into a macrotidal estuary during each transgressive phase. Five major facies associations have been recognized: (1) shale/siltstone-dominated successions containing sharply based, strongly bioturbated sandstone beds interpreted as prodelta deposits; (2) medium to coarse sandy successions of thickening-upward, small to very large-scale planar cross-stratified sets, representing dune fields in the tidally dominated delta-front environment; (3) delta-plain, very fine sandstones with roots and fluvial channels; (4) estuarine, tidal channel-fill deposits which overlie erosion surfaces up to 10 m deep and consist of both bioturbated and non-bioturbated, large-scale, tabular or trough cross-bedded medium/coarse sandstones (sets 2–10 m thick) often deformed by water-escape structures and slumping; (5) bioturbated, thinning-upward tabular sandstone beds, interpreted as transgressive shelf deposits.

Palaeocurrent data indicate that during the early stage of deposition of the Bearreraig Formation, tidal-dominated sedimentation occurred separately in the north Skye/Raasay and in the south Skye sub-basins. During a late stage of deposition, the sub-basins merged, and sedimentation occurred uniformly throughout the region. This change in palaeogeographical configuration is associated with a regionally extensive unconformity. Tectonic activity, particularly at an early stage in the form of tilting and block rotation, is believed to have enhanced tidal circulation within the fault-constrained sub-basins.
Nearshore sediment transport processes due to moderate hydrodynamic conditions
Authors: Eitner V. , Kaiser R. , Niemeyer H. D. , Eitner V.
Published: September 2007

On the beach of the island of Norderney sedimentological, morphological and hydrodynamic measurements have been carried out in order to investigate sediment transport processes in the course of a tidal cycle which was characterized by moderate hydrodynamic conditions. Wave heights varied between 0.3 and 0.5 m. An area of 90 m
2
within a groyne field was surveyed. Sediments samples were taken on a 5 m grid at low tide. Sediment flux was determined at each sampling site by means of depth-of-activity rods. The grain size distributions of the sediment samples were determined by dry sieving. Under the prevailing hydrodynamic conditions a landward sediment transport was observed. The mainly negative sediment budget in the seaward section and the landward directed distribution of fluorescent sediment tracers suggest a dominant onshore transport during the investigated tidal cycle. This is also reflected in the changes observed in sediment textures.
An interdisciplinary approach to the evaluation of physical parameters of shallow marine sediments
Authors: Missiaen T. , McGee T. M. , Pearks D. , Ollier G. , Theilen F.
Published: September 2007

A large number of high-resolution seismic investigations and
in situ
geotechnical measurements were carried out in the southern Baltic, offshore Bornholm. The geotechnical measurements, carried out with Ifremer’s Geotechnical Module and Kiel’s GISP system, provided information on cone resistance, induced pore pressure and density of the surficial sediments. The seismic data were subjected to different processing techniques, including detrending and multiple quotient division, which made it possible to deduce the reflection coefficients and impedance contrasts at subbottom interfaces. The different geotechnical and seismic data sets were carefully integrated. There is a good correlation between the
in situ
results and the interpreted seismic units. Strong variations in geotechnical plots correspond with the reflectors identified on processed seismic sections. The general trend of calculated impedances agrees well with the lithological interpretation. However, it would appear that the inversion method does not always result in quantitatively correct values of the sediment parameters. Further development and refining of this method will undoubtedly provide better estimates of the
in situ
bulk properties of the shallow marine sediments.
Lithological and geochemical evidence of Fe and Mn pathways during deposition of Lower Proterozoic banded iron formation in the Krivoy Rog Basin (Ukraine)
Authors: Kulik Dmitri A. , Korzhnev Michael N.
Published: September 2007

Data on stratigraphy, chemical and mineral composition of siliciclastic and ferrugionus rocks of greenschist to epidote-amphibolite metamorphic grade, multi-order cyclicity and banding, isotopic composition of sulphur and carbon and other features of the Krivoy Rog Supergroup metasedimentary rocks are summarized. They provide an insight into the primary sources and the nature of siliciclastic and chemogenic components of banded iron formation (BIF), as well as on pathways of Fe, Mn and Si in the Krivoy Rog palaeobasin at the time of BIF accumulation. Skelevat and Saxagan iron-ore Groups were deposited in a single cyclic transgressive-regressive sequence, probably in a trough-like landlocked basin with complex bottom topography defined by syn-sedimentary faults inherited from the earlier rift structures. Variations in sea level, humidity of climate, continental run-off, oceanic water inflows etc. many times provoked the rapid facies changes ranging from sedimentation of land-derived siliciclastics to deposition of nearly pure chemogenic sediments of the oxide facies BIF in the deeper parts of the basin. Up to seven pairs of schist (
s
-) and BIF (
f
-) horizons were deposited in the Saxagan Group. Lateral variations of their thicknesses, distribution of free carbon in the rocks and other data indicate that only parts of the basin at a given time were optimal for chemical sedimentation; major part of dissolved Fe, Si and Mn was supplied by constant or event inflow of suboxic ocean water.

The Mn content in the Krivoy Rog Supergroup BIFs could serve as an indicator of the fraction of total Fe that precipitated chemically as carbonate. The main part of Fe precipitation in form of Fe(III) hydroxide particles, possibly coated with amorphous silica, is due to a number of oxidation mechanisms operating in the photic surface water layer. On the basis of physicochemical considerations, it is concluded that the Mn CO
3
content in siderite (
c.
2 mol %) contained in the BIF rocks reflects a uniform dissolved Mn concentration (
c.
1 ppm) in the ocean and basin waters. Sedimentation of the typical association of Mg-Fe carbonates and silicates of the carbonate-silicate facies BIF could occur in the near-bottom water only in the case of strong enrichment in dissolved Fe(II) (up to 100–200 ppm) relative to the ocean water (1–10 ppm), which required a stratified brackish-water basin with an estuarine-type circulation. No enrichment in dissolved Mn(II) was possible until
p

O
2

in the atmosphere raised high enough for precipitation of particulate Mn oxide in the photic zone and its dissolution in the suboxic near-bottom waters.
Deep-water manganese deposits in the mid- to late Proterozoic Penganga Group of the Pranhita-Godavari Valley, South India
Authors: Mukhopadhyay Joydip , Chaudhuri Asru K. , Chanda S. K.
Published: September 2007

Facies analysis of the unmetamorphosed sediments enclosing the stratiform manganese oxide deposits of the mid- to late Proterozoic Penganga Group identifies the base of slope of a distally steepened deep-water ramp as their site of accumulation. The interpretation is based on their close association with a variety of mass flow deposits ranging from limestone conglomerates to calcarenites and deep-water, plane-bedded micritic limestone devoid of current- or wave-generated structures as well as detritus coarser than fine silt. These deposits occur within a major transgressive succession. The base of slope origin of stratiform manganese deposits is uncommon in the rock record and their origin is to be constrained against the background of base of slope depositional setting.
Growth history of manganese nodules and crusts of the Peru Basin
Authors: Von Stackelberg U.
Published: September 2007

In the nodule field of the Peru Basin, situated south of the zone of high bioproductivity, a relatively high flux of biogenic matter explains a distinct redox boundary at about 10 cm depth separating very soft oxic surface sediments from stiffer suboxic sediments. Maximum abundance (50 kg m
−2
) of diagenetic nodules is found near the calcite compensation depth (CCD), currently at 4250 m. There, the accretion rate of nodules is much higher (100 mm Ma
−1
) than on ridges (5 mm Ma
−1
). Highest accretion rates are found at the bottom of large nodules that repeatedly sink to a level immediately above the redox boundary. There, distinct diagenetic growth conditions prevail and layers of dense laminated Mn oxide of very pure todorokite are formed. The layering of nodules is mainly the result of organisms moving nodules within the oxic surface sediment from diagenetic to hydrogenetic environments. The frequency of such movements is much higher than that of climatic changes. Two types of nodule burial occur in the Peru Basin. Large nodules are less easily moved by organisms and become buried. Consequently, buried nodules generally are larger than surface nodules. This type of burial predominates in basins. At ridges where smaller nodules prevail, burial is mainly controlled by statistical selection where some nodules are not moved up by organisms.
Distribution and composition of marine hydrogenetic and hydrothermal manganese deposits in the northwest Pacific
Authors: Usui Akira , Someya Masao
Published: September 2007

The distribution and composition of Mn deposits in the northwest Pacific (15–50°N and 120–160°E) are characterized using a Mn deposits database compiled from our original data, published and unpublished papers, published databases, and other international sources. The results demonstrate a close association with geological settings. Hydrogenetic nodules and crusts formed in areas of erosion or nondeposition on Cretaceous seamounts and plateaus of the Pacific plate, and to a lesser extent on seamounts of remnant arcs of Palaeogene to Neogene ages. The Cretaceous seamount deposits are most enriched in Co, and the plateaus less so, while both show moderate Ni enrichment. Nodules and crusts are rare in enclosed backarc basins, which have not been affected by deep water circulation. A slight early-diagenetic influence is observed in some Pacific basin nodules. By contrast, modern hydrothermal Mn deposits are broadly distributed on active submarine volcanoes and backarc rifts. These hydrothermal Mn deposits consist typically of pure Mn oxide containing negligible levels of metals except for Mg, Ba, K and Li. Similar fossil hydrothermal Mn deposits are observed in places on old basement or within deep cores as geological records of past hydrothermal activity.
The partitioning of petrophysical data: a review
Authors: Moss Brian P.
Published: September 2007

Petrophysical analyses are undertaken within a framework of ordered geological systems. The recognition of the natural geological ordering through the grouping and partitioning of petrophysical data is known to be a fundamental requirement of successful petrophysical interpretations.

The mathematical basis and examples of the use of a variety of techniques of value in partitioning data are reviewed. Beginning with the simple use of curve discrimination on conventional crossplots, the discussion proceeds by covering increasingly complex but relatively well-known methods including discriminant function analysis, cluster analysis and principal component analysis, and goes on to include multi-dimensional scaling, ‘pigeon-holing’, fuzzy clustering, characteristic analysis, projection pursuit and neural networks. The discussion highlights some of the benefits, and some of the pitfalls, of each technique through the included examples.

The discussion encourages the use of exploratory data analysis techniques in the processing and interpretation of petrophysical data and provides a reference framework from which can follow further evaluation of the value of the techniques in circumstances particular to the interested reader
An application of the Moiré Method to a study of local strains during rock failure in tension
Authors: Passas N. , Butenuth C. , De Freitas M. H.
Published: September 2007

The hoop tension test has proved to be a reliable and sensitive test to measure rock strength in tension and provides a convenient method for studying petrophysical aspects of rock failure. However, to make best use of this test it is necessary to be able to compare the strains associated with measured strengths. This paper describes initial experiments to measure by moiré fringes the distribution of strain over the surface of specimens of sandstone, failed under tension in the hoop tension test. The method utilizes the optical interference between two grids of similar size, one on the surface of the specimen which is deformed with the specimen during the test, and another remote from the specimen which remains undeformed. The moiré fringes produced and the strains so measured, were obtained so as to be compared with those obtained from previous investigations on similar samples using holographic and strain gauge measurements. The fringes acquired can be transformed into iso-deformation lines based on the geometrical relationships of the interference grids, to reveal the distribution of strain over the specimen surface observed.
Dynamic ordered sets with exponential search trees
Authors: Andersson Arne , Thorup Mikkel
Published: September 2007

We introduce exponential search trees as a novel technique for converting static polynomial space search structures for ordered sets into fully-dynamic linear space data structures.

This leads to an
optimal
bound of
O
(√log
n
/log log
n
) for searching and updating a dynamic set
X
of
n
integer keys in linear space. Searching
X
for an integer
y
means finding the maximum key in
X
which is smaller than or equal to
y
. This problem is equivalent to the standard text book problem of maintaining an ordered set.

The best previous deterministic linear space bound was
O
(log
n
/log log
n
) due to Fredman and Willard from STOC 1990. No better deterministic search bound was known using polynomial space.

We also get the following worst-case linear space trade-offs between the number
n
, the word length
W
, and the maximal key
U
< 2

W

:
O
(min log log
n
+ log
n
/log
W
, log log
n
⋅ log log
U
/log log log
U
). These trade-offs are, however, not likely to be optimal.

Our results are generalized to finger searching and string searching, providing optimal results for both in terms of
n
.
An analysis of unreliability and asymmetry in low-power wireless links
Authors: Zamalloa Marco Zúñiga , Krishnamachari Bhaskar
Published: September 2007

Experimental studies have demonstrated that the behavior of real links in low-power wireless networks (such as wireless sensor networks) deviates to a large extent from the ideal binary model used in several simulation studies. In particular, there is a large transitional region in wireless link quality that is characterized by significant levels of unreliability and asymmetry, significantly impacting the performance of higher-layer protocols. We provide a comprehensive analysis of the root causes of unreliability and asymmetry. In particular, we derive expressions for the distribution, expectation, and variance of the packet reception rate as a function of distance, as well as for the location and extent of the transitional region. These expressions incorporate important environmental and radio parameters such as the path loss exponent and shadowing variance of the channel, and the modulation, encoding, and hardware variance of the radios.
Minimum power configuration for wireless communication in sensor networks
Authors: Xing Guoliang , Lu Chenyang , Zhang Ying , Huang Qingfeng , Pless Robert
Published: September 2007

This article proposes the
minimum power configuration
(MPC) approach to power management in wireless sensor networks. In contrast to earlier research that treats different radio states (i.e., transmission/reception/idle) in isolation, MPC integrates them in a joint optimization problem that depends on both the set of active nodes and the transmission power. We propose four approximation algorithms with provable performance bounds and two practical routing protocols. Simulations based on realistic radio models show that the MPC approach can conserve more energy than existing minimum power routing and topology control protocols. Furthermore, it can flexibly adapt to network workload and radio platforms.
Distinctive regions of 3D surfaces
Authors: Shilane Philip , Funkhouser Thomas
Published: September 2007

Selecting the most important regions of a surface is useful for shape matching and a variety of applications in computer graphics and geometric modeling. While previous research has analyzed geometric properties of meshes in isolation, we select regions that distinguish a shape from objects of a different type. Our approach to analyzing distinctive regions is based on performing a shape-based search using each region as a query into a database. Distinctive regions of a surface have shape consistent with objects of the same type and different from objects of other types. We demonstrate the utility of detecting distinctive surface regions for shape matching and other graphics applications including mesh visualization, icon generation, and mesh simplification.
Volume illustration using wang cubes
Authors: Lu Aidong , Ebert David S. , Qiao Wei , Kraus Martin , Mora Benjamin
Published: September 2007

To create a new, flexible system for volume illustration, we have explored the use of Wang Cubes, the 3D extension of 2D Wang Tiles. We use small sets of Wang Cubes to generate a large variety of nonperiodic illustrative 3D patterns and texture, which otherwise would be too large to use in real applications. We also develop a direct volume rendering framework with the generated patterns and textures. Our framework can be used to render volume datasets effectively and a variety of rendering styles can be achieved with less storage.

Specifically, we extend the nonperiodic tiling process of Wang Tiles to Wang Cubes and modify it for multipurpose tiling. We automatically generate isotropic Wang Cubes consisting of 3D patterns or textures to simulate various illustrative effects. Anisotropic Wang Cubes are generated to yield patterns by using the volume data, curvature, and gradient information. We also extend the definition of Wang Cubes into a set of different sized cubes to provide multiresolution volume rendering. Finally, we provide both coherent 3D geometry-based and texture-based rendering frameworks that can be integrated with arbitrary feature exploration methods.
Test conditions for fault classes in Boolean specifications
Authors: Kapoor Kalpesh , Bowen Jonathan P.
Published: September 2007

Fault-based testing of software checks the software implementation for a set of faults. Two previous papers on fault-based testing [Kuhn 1999; Tsuchiya and Kikuno 2002] represent the required behavior of the software as a Boolean specification represented in Disjunctive Normal Form (DNF) and then show that faults may be organized in a hierarchy. This article extends these results by identifying necessary and sufficient conditions for fault-based testing. Unlike previous solutions, the formal analysis used to derive these conditions imposes no restrictions (such as DNF) on the form of the Boolean specification.
A Co-Plot analysis of logs and models of parallel workloads
Authors: Talby David , Feitelson Dror G. , Raveh Adi
Published: September 2007

We present a multivariate analysis technique called Co-Plot that is especially suitable for few samples of many variables. Co-Plot embeds the multidimensional samples in two dimensions, in a way that allows key variables to be identified, and relations between both variables and observations to be analyzed together. When applied to the workloads on parallel supercomputers, we find two stable perpendicular axes of highly correlated variables, one representing individual job attributes and the other representing multijob attributes. The different workloads, on the other hand, are rather different from one another, and may also change over time. Synthetic models for workload generation are also analyzed, and found to be reasonable in the sense that they span the same range of variable combinations as the real workloads. However, the spread of real workloads implies that a single model cannot be similar to all of them. This leads us to construct a parameterized model, with parameters that correspond to the two axes identified above. We also find that existing models do not model the temporal structure of the workload well, and hence are wanting for tasks such as comparing schedulers, and that the common methodology for load manipulation of workloads is problematic.
Ordinary interactive small-step algorithms, II
Authors: Blass Andreas , Gurevich Yuri
Published: September 2007

This is the second in a series of three articles extending the proof of the Abstract State Machine Thesis---that arbitrary algorithms are behaviorally equivalent to abstract state machines---to algorithms that can interact with their environments during a step, rather than only between steps. As in the first article of the series, we are concerned here with ordinary, small-step, interactive algorithms. This means that the algorithms:

(1) proceed in discrete, global steps,

(2) perform only a bounded amount of work in each step,

(3) use only such information from the environment as can be regarded as answers to queries, and

(4) never complete a step until all queries from that step have been answered.

After reviewing the previous article's formal description of such algorithms and the definition of behavioral equivalence, we define ordinary, interactive, small-step abstract state machines (ASMs). Except for very minor modifications, these are the machines commonly used in the ASM literature. We define their semantics in the framework of ordinary algorithms and show that they satisfy the postulates for these algorithms.

This material lays the groundwork for the final article in the series, in which we shall prove the Abstract State Machine thesis for ordinary, intractive, small-step algorithms: All such algorithms are equivalent to ASMs.
Ordinary interactive small-step algorithms, III
Authors: Blass Andreas , Gurevich Yuri
Published: September 2007

This is the third in a series of three articles extending the proof of the Abstract State Machine thesis---that arbitrary algorithms are behaviorally equivalent to abstract state machines---to algorithms that can interact with their environments during a step, rather than only between steps. As in the first two articles of the series, we are concerned here with ordinary, small-step, interactive algorithms. This means that the algorithms:

(1) proceed in discrete, global steps,

(2) perform only a bounded amount of work in each step,

(3) use only such information from the environment as can be regarded as answers to queries, and

(4) never complete a step until all queries from that step have been answered.

After reviewing the previous articles' definitions of such algorithms, of behavioral equivalence, and of abstract state machines (ASMs), we prove the main result: Every ordinary, interactive, small-step algorithm is behaviorally equivalent to an ASM.

We also discuss some possible variations of and additions to the ASM semantics.
Discovering personally meaningful places
Authors: Zhou Changqing , Frankowski Dan , Ludford Pamela , Shekhar Shashi , Terveen Loren
Published: September 2007

The discovery of a person's meaningful places involves obtaining the physical locations and their labels for a person's places that matter to his daily life and routines. This problem is driven by the requirements from emerging location-aware applications, which allow a user to pose queries and obtain information in reference to places, for example, “home”, “work” or “Northwest Health Club”. It is a challenge to map from physical locations to personally meaningful places due to a lack of understanding of what constitutes the real users' personally meaningful places. Previous work has explored algorithms to discover personal places from location data. However, we know of no systematic empirical evaluations of these algorithms, leaving designers of location-aware applications in the dark about their choices.

Our work remedies this situation. We extended a clustering algorithm to discover places. We also defined a set of essential evaluation metrics and an interactive evaluation framework. We then conducted a large-scale experiment that collected real users' location data and personally meaningful places, and illustrated the utility of our evaluation framework. Our results establish a baseline that future work can measure itself against. They also demonstrate that that our algorithm discovers places with reasonable accuracy and outperforms the well-known K-Means clustering algorithm for place discovery. Finally, we provide evidence that shapes more complex than “points” are required to represent the full range of people's everyday places.
On setting the hyper-parameters of term frequency normalization for information retrieval
Authors: He Ben , Ounis Iadh
Published: September 2007

The setting of the term frequency normalization hyper-parameter suffers from the query dependence and collection dependence problems, which remarkably hurt the robustness of the retrieval performance. Our study in this article investigates three term frequency normalization methods, namely normalization 2, BM25's normalization and the Dirichlet Priors normalization. We tackle the query dependence problem by modifying the query term weight using a Divergence From Randomness term weighting model, and tackle the collection dependence problem by measuring the correlation of the normalized term frequency with the document length. Our research hypotheses for the two problems, as well as an automatic hyper-parameter setting methodology, are extensively validated and evaluated on four Text REtrieval Conference (TREC) collections.
A study of thread migration in temperature-constrained multicores
Authors: Michaud Pierre , Seznec André , Fetis Damien , Sazeides Yiannakis , Constantinou Theofanis
Published: September 2007

Temperature has become an important constraint in high-performance processors, especially multicores. Thread migration will be essential to exploit the full potential of future thermally constrained multicores. We propose and study a thread migration method that maximizes performance under a temperature constraint, while minimizing the number of migrations and ensuring fairness between threads. We show that thread migration brings important performance gains and that it is most effective during the first tens of seconds following a decrease of the number of running threads.
A new look at survey propagation and its generalizations
Authors: Maneva Elitza , Mossel Elchanan , Wainwright Martin J.
Published: September 2007

This article provides a new conceptual perspective on
survey propagation
, which is an iterative algorithm recently introduced by the statistical physics community that is very effective in solving random
k
-SAT problems even with densities close to the satisfiability threshold. We first describe how any SAT formula can be associated with a novel family of Markov random fields (MRFs), parameterized by a real number ρ ∈ [0, 1]. We then show that applying belief propagation---a well-known “message-passing” technique for estimating marginal probabilities---to this family of MRFs recovers a known family of algorithms, ranging from pure survey propagation at one extreme (ρ = 1) to standard belief propagation on the uniform distribution over SAT assignments at the other extreme (ρ = 0). Configurations in these MRFs have a natural interpretation as partial satisfiability assignments, on which a partial order can be defined. We isolate
cores
as minimal elements in this partial ordering, which are also fixed points of survey propagation and the only assignments with positive probability in the MRF for ρ = 1. Our experimental results for
k
= 3 suggest that solutions of random formulas typically do not possess non-trivial cores. This makes it necessary to study the structure of the space of partial assignments for ρ < 1 and investigate the role of assignments that are very close to being cores. To that end, we investigate the associated lattice structure, and prove a weight-preserving identity that shows how any MRF with ρ > 0 can be viewed as a “smoothed” version of the uniform distribution over satisfying assignments (ρ = 0). Finally, we isolate properties of Gibbs sampling and message-passing algorithms that are typical for an ensemble of
k
-SAT problems.
A practical interprocedural dominance algorithm
Authors: De Sutter Bjorn , Van Put Ludo , De Bosschere Koen
Published: September 2007

Existing algorithms for computing dominators are formulated for control flow graphs of single procedures. With the rise of computing power, and the viability of whole-program analyses and optimizations, there is a growing need to extend the dominator computation algorithms to context-sensitive interprocedural dominators. Because the transitive reduction of the interprocedural dominator graph is not a tree, as in the intraprocedural case, it is not possible to extend existing algorithms directly. In this article, we propose a new algorithm for computing interprocedural dominators. Although the theoretical complexity of this new algorithm is as high as that of a straightforward iterative solution of the data flow equations, our experimental evaluation demonstrates that the algorithm is practically viable, even for programs consisting of several hundred thousands of basic blocks.
PeaCE
Authors: Ha Soonhoi , Kim Sungchan , Lee Choonseung , Yi Youngmin , Kwon Seongnam , Joo Young-Pyo
Published: September 2007

Existent hardware-software (HW-SW) codesign tools mainly focus on HW-SW cosimulation to build a virtual prototyping environment that enables software design and system verification without need of making a hardware prototype. Not only HW-SW cosimulation, but also HW-SW codesign methodology involves system specification, functional simulation, design-space exploration, and hardware-software cosynthesis. The PeaCE codesign environment is the first full-fledged HW-SW codesign environment that provides seamless codesign flow from functional simulation to system synthesis. Targeting for multimedia applications with real-time constraints, PeaCE specifies the system behavior with a heterogeneous composition of three models of computation and utilizes features of the formal models maximally during the whole design process. It is also a reconfigurable framework in the sense that third-party design tools can be integrated to build a customized tool chain. Experiments with industry-strength examples prove the viability of the proposed technique.
A self-organizing defect tolerant SIMD architecture
Authors: Patwardhan Jaidev , Dwyer Chris , Lebeck Alvin R.
Published: September 2007

The continual decrease in transistor size (through either scaled CMOS or emerging nanotechnologies) promises to usher in an era of tera to peta-scale integration but with increasing defects. Regardless of fabrication methodology (top-down or bottom-up), defect-tolerant architectures are necessary to exploit the full potential of future increased device densities.

This article explores a defect-tolerant SIMD architecture (SOSA) that self-organizes a large number of limited capability nodes with high defect rates into SIMD processing elements. Simulation results show that SOSA matches or exceeds the performance of conventional systems for moderate to large problems, but with lower power density.
Just fast keying in the pi calculus
Authors: Abadi Martín , Blanchet Bruno , Fournet Cédric
Published: September 2007

JFK is a recent, attractive protocol for fast key establishment as part of securing IP communication. In this paper, we formally analyze this protocol in the applied pi calculus (partly in terms of observational equivalences and partly with the assistance of an automatic protocol verifier). We treat JFK's core security properties and also other properties that are rarely articulated and rigorously studied, such as plausible deniability and resistance to denial-of-service attacks. In the course of this analysis, we found some ambiguities and minor problems, such as limitations in identity protection, but we mostly obtain positive results about JFK. For this purpose, we develop ideas and techniques that should be more generally useful in the specification and verification of security protocols.
Emstar
Authors: Girod Lewis , Ramanathan Nithya , Elson Jeremy , Stathopoulos Thanos , Lukac Martin , Estrin Deborah
Published: September 2007

Recent work in wireless embedded networked systems has followed
heterogeneous
designs, incorporating a mixture of elements from extremely constrained 8- or 16-bit “Motes” to less resource-constrained 32-bit embedded “Microservers.”

Emstar is a software environment for developing and deploying complex applications on such heterogeneous networks. Emstar is designed to leverage the additional resources of Microservers by trading off some performance for system robustness in sensor network applications. It enables fault isolation, fault tolerance, system visiblity, in-field debugging, and resource sharing across multiple applications.

In order to accomplish these objectives, Emstar is designed to run as a multiprocess system and consists of
libraries
that implement message-passing IPC primitives,
services
that support networking, sensing, and time synchronization, and
tools
that support simulation, emulation, and visualization of live systems, both real and simulated. We evaluate this work by discussing the Acoustic ENSBox, a platform for distributed acoustic sensing that we built using Emstar. We show that by leveraging existing Emstar services, we are able to significantly reduce development time while achieving a high degree of robustness. We also show that a sample application was developed much more quickly on this platform than it would have been otherwise.
Secure pairwise key establishment in large-scale sensor networks
Authors: Huang Dijiang , Medhi Deep
Published: September 2007

Existing pairwise key establishment schemes for large-scale sensor networks are vulnerable to various passive or active attacks. We classify attacks as selective node capture attacks, node fabrication attacks, and insider attacks. In order to improve the security robustness of random key predistribution and pairwise key establishment schemes against these attacks, we propose a five-phase pairwise key predistribution and pairwise key establishment approach by using area partitioning and multigroup key predistribution. Our security performance studies show that our proposed approach is resilient to selective node capture and node fabrication attacks, and restricts the consequence of any insider attack to a minimal level.
Algorithm 868
Authors: Espelid Terje O.
Published: September 2007

We discuss how to modify a recently published Matlab code, coteglob, so that the excellent performance this code demonstrates for low and intermediate accuracy requests is retained while the performance is improved for high accuracy requests. coteglob is a globally adaptive code using a 5 and 9 point pair of Newton-Cotes rules. Combining an extended sequence of rules using 5, 9, 17 and 33 points with a doubly adaptive bisection strategy is the main focus of the paper. We also discuss local versus global adaptivity and conclude that globally adaptive codes are to be preferred. Based on this we develop several new globally adaptive codes that all compare favorably both with coteglob, with Matlab's best currently available quadrature software quadl and the general purpose QUADPACK codes dqk15 and dqk21. We include the results from extensive testing using both a Lyness-Kaganove testing technique and a battery test.