bluuebunny/crossref_metadata_2025 huggingface dataset:
A Real-Time Debye-Sears Effect Spectrum Analyzer for Audio Frequencies
Authors: Slaymaker F. H.
Published: November 2005

The Debye-Sears effect is usually thought of as involving the generation of a Fraunhofer diffraction pattern (the Fourier transform) from the spatial phase variations produced in a coherent light beam that has passed through an ultrasonic beam in a direction parallel to the sound wave front. For a typical audio frequency, 1000 Hz for example, the acoustic wavelength in a water filled diffraction cell is 146 cm, which is too long to be included in any reasonable optical aperture. A spectrum analysis of an audio frequency can be performed in real time if the audio frequency is time compressed (or frequency multiplied) before being fed into the Debye-Sears analyzer. A spectrum analyzer is described in which the audio signal has been time compressed by a factor of 154 before analysis. The resultant bandwidth is limited by the length of the sample stored in the DELTIC frequency multipliers to a band of 88 Hz. Motion pictures will be shown of the analyzer output with various input signals, including speech.
Search-Tone Measurements in Blown Wind Instruments
Authors: Benade A. H. , Worman W. W.
Published: November 2005

A variable-frequency search tone is injected into an instrument's air column, and the response is detected by a probe microphone and narrow-band voltmeter tuned to the search-tone frequency. Accurate response curves are obtained at all frequencies except for narrow regions surrounding each of the strong (discrete) spectrum lines produced by the instrument as it plays. The search tone can be weak, or strong enough to produce nonlinear (heterodyne and synchronism) effects in the instrument's regeneration mechanism. The “blown” resonance peak for a bottle rises above the “unblown” natural frequency as the exciting air-jet velocity increases, but the playing frequency rises at a different rate. The width of the resonance is also somewhat sensitive to jet velocity. The first-mode resonance of a diapason organ pipe behaves similarly, but the higher “blown” modes show little change. There is considerable nonlinearity found in the regeneration mechanism of the organ pipe, but little in that of the bottle.
A Schlieren System for Acoustic Measurements
Authors: Sanders J. V.
Published: November 2005

Acoustic measurements with photographic-schlieren techniques are limited to regions of strong density gradients such as those found in shock waves and at the leading edge of intense sound waves. To study waves of less-than-finite amplitudes, a system employing photomultiplier-schlieren techniques was constructed. With this system, acoustic pressures as low as 20 dyn/cm2 at 6 kHz were measured in air. A unique feature of the design is that the knife edge is vibrated at 300 Hz. This permits the absolute value of the pressure to be determined from known constants and a few length measurements. Microphone calibrations obtained using values of the pressure determined with this equipment agree with pistonphone calibrations to within ±1 dB.
General Evaluation of Sonar Transducers by Average Time Holographic Interferometry
Authors: Grant Ralph M. , Jacobson Charles F.
Published: November 2005

A brief explanation of the average time holographic interferometry technique applied to the evaluation of sonar transducers [R. M. Grant and W. Von Winkle, “Interferometric Holography as a Tool for the Study of Flexures in Active Sonar Transducers,” paper invited and presented at the First Intern. Conf. Laser App. Paris, France (July 1967)] will be presented. In addition to a brief theoretical discussion of the average time technique, examples will be given of the application of the above technique to both design and nondestructive testing of sonar transducers. Results will be given for both single elements and arrays.
STUDY OF THE RELATIONSHIP BETWEEN STRUCTURE AND O-17 ELECTRIC FIELD GRADIENT PARAMETERS IN SOME ALUMINOSILICATES
Authors: YILDIRIM ERDEM KAMIL , DUPREE RAY
Published: November 2005

The relation between O-17 quadrupolar parameters and the local structure in silicates is of considerable interest if these parameters are to be used as a local probe. Although there are a number of investigations and some theoretical work on Si—O—Si bonds, there seems to be very little experimental data on Si—O—Al bonds. We have therefore investigated a number of sodalites with a general formula of M 8 [AlSiO 4 ]Cl 2 where M is an alkali cation. They have only one oxygen site and a Si:Al ratio of one. By varying the alkali we were able to change the Si—O—Al bond angle about five degrees steps from 125 to 152 degrees. The value of the electric field gradient (EFG), CQ of O-17, followed a roughly similar angular dependence to that found for Si—O—Si bonds with CQ180= 4.2 MHz . The asymmetry parameter of O-17 also behaved in a similar fashion to that found for Si—O—Si bonds although it increased more rapidly at small angles.
NEW COLLECTOR OF PLANAR INSULATED GATE BIPOLAR TRANSISTOR FOR BROAD APPLICATIONS
Authors: ZHANG FEI , SHI LINA , YU WEN , LI CHENGFANG , SUN XIAOWEI
Published: November 2005

A new concept of Insulated Gate Bipolar Transisitor (IGBT) with a Si/Ge layer collector is proposed to meet different requirements for turn-on voltage and turn-off time. The operation principles of IGBT are discussed and the energy band diagram of Si/Ge heterojunction is employed to explain the inner dynamic mechanism of the proposed IGBT. Two-dimensional (2D) device-circuit mixed-mode simulations indicate that the tail-current, which is a major cause of the power loss and limits the operation speed of the device, is suppressed effectively by using the Si/Ge layer collector. On the other hand, turn-on voltage is increased by the use of the Si/Ge collector. Furthermore, the turn-on voltage is increasing with the increase of the areal rate of the Ge region in the whole collector, while the turn-off time is reversed. This valuable information leads to the freely tunable planar IGBT by adapting the different areal rates of the Ge region to cast to different actual situations. Detailed physical explanations are also given.
SPECTRAL PROPERTIES OF MAGNETIC EXCITATIONS IN CUPRATE TWO-LEG LADDER SYSTEMS
Authors: SCHMIDT KAI P. , UHRIG GÖTZ S.
Published: November 2005

This article summarizes and extends the recent developments in the microscopic modeling of the magnetic excitations in cuprate two-leg ladder systems. The microscopic Hamiltonian comprises dominant Heisenberg exchange terms plus an additional four-spin interaction which is about five times smaller. We give an overview over the relevant energies like the one-triplon dispersion, the energies of two-triplon bound states and the positions of multi-triplon continua and over relevant spectral properties like spectral weights and spectral densities in the parameter regime appropriate for cuprate systems. It is concluded that an almost complete understanding of the magnetic excitations in undoped cuprate ladders has been obtained as measured by inelastic neutron scattering, inelastic light (Raman) scattering and infrared absorption.
QUANTUM IMPLEMENTATION OF PARRONDO'S PARADOX
Authors: GAWRON PIOTR , MISZCZAK JAROSŁAW A.
Published: November 2005

We propose a quantum implementation of a capital-dependent Parrondo's paradox that uses O( log 2(n)) qubits, where n is the number of Parrondo games. We present its implementation in the quantum computer language (QCL) and show simulation results.
DISCRIMINATING FLUCTUATION DYNAMICS IN BURNED AND UNBURNED VEGETATIONAL COVERS
Authors: TELESCA LUCIANO , LASAPONARA ROSA , LANORTE ANTONIO
Published: November 2005

Fluctuation dynamics of time series of satellite SPOT-VEGETATION Normalized Difference of Vegetation Index (NDVI) data from 1998 to 2003 were analyzed to discriminate fire-induced variability in the vegetational dynamics of shrub-land in southern Italy. We used detrended fluctuation analysis (DFA), which permits the detection of persistent properties in nonstationary signal fluctuations. We analyzed two shrub-land covers, one in "healthy conditions" (fire-unaffected) and the other in "ill conditions" (fire-affected). Our findings suggest that fires play an important role in the temporal evolution of the shrub-land, increasing the persistence of the vegetation dynamics.
A PATH INTEGRAL APPROACH FOR DISORDERED QUANTUM WALKS IN ONE DIMENSION
Authors: KONNO NORIO
Published: November 2005

The present letter gives a rigorous way from quantum to classical random walks by introducing an independent random fluctuation and then taking expectations based on a path integral approach.
A deductive database architecture based on partial evaluation
Authors: Lei Li , Moll G.-H. , Kouloumdjian J.
Published: November 2005

The implementation of a logic programming language for database management systems is a possible way to build a knowledge base management system. It allows to re-use the know-how in the fields:

of inference engines,

of data management.

However, the strategy of each component is very different. SLD resolution leads to a one tuple at a time access to facts, opposed to the set oriented approach of databases. To face this problem, a new strategy, has been designed to keep the advantages of each part avoiding the drawbacks. The kernel of the system is a Partial Evaluator, designed as a metaprogram, which allows to bridge the impedance mismatch gap.
Piers
Authors: Cao Xia , Li Shuai Cheng , Ooi Beng Chin , Tung Anthony K. H.
Published: November 2005

Growing interest in genomic research has resulted in the creation of huge biological sequence databases. In this paper, we present a hash-based pier model for efficient homology search in large DNA sequence databases. In our model, only certain segments in the databases called 'piers' need to be accessed during searches as opposite to other approaches which require a full scan on the biological sequence database. To further improve the search efficiency, the piers are stored in a specially designed hash table which helps to avoid expensive alignment operation. The has table is small enough to reside in main memory, hence avoiding I/O in the search steps. We show theoretically and empirically that the proposed approach can efficiently detect biological sequences that are similar to a query sequence with very high sensitivity.
BIO-AJAX
Authors: Herbert Katherine G. , Gehani Narain H. , Piel William H. , Wang Jason T. L. , Wu Cathy H.
Published: November 2005

As databases become more pervasive through the biological sciences, various data quality issues regarding data legacy, data uniformity and data duplication arise. Due to the nature of this data, each of these problems is non-trivial. For biological data to be corrected and standardized, new methods and frameworks must be developed. This paper proposes one such framework, called BIO-AJAX, which uses principles from data cleaning to improve data quality in biological information systems, specifically in TreeBASE.
A distributed database for bio-molecular images
Authors: Singh Ambuj K. , Manjunath B. S. , Murphy Robert F.
Published: November 2005

Information technology research has played a significant role in the genomics revolution over the past decade, from aiding with large-scale sequence assembly to automating gene identification to efficiently searching databases by sequence similarity. The tremendous amount of information gathered from genomics will be dwarfed in the next decade by the knowledge to be gained from comprehensive, systematic studies of the properties and behaviors of all proteins and other biomolecules. High-resolution imaging of molecules and cells will be critical for understanding complex systems such as the nervous system, whether it be for the localization of specific neuron types within a region of the central nervous system, the branching pattern of dendritic trees, or the localization of molecules at the subcellular level. Furthermore, knowing how these distribution patterns and subcellular locations change as a function of time is critical to understanding how cells respond to stress, injury, aging, and disease. We are developing sophisticated information technologies for collecting and interpreting the enormous volume of biological image data. A major outcome of the research will be a unique, fully operational, distributed digital library of biomolecular image data accessible to researchers around the world. Such searchable databases will make it possible to optimally understand and interpret the data, leading to a more complete and integrated understanding of cellular structure, function and regulation.
Mobile databases
Authors: Bernard Guy , Ben-othman Jalel , Bouganim Luc , Canals Gérôme , Chabridon Sophie , Defude Bruno , Ferrié Jean , Gançarski Stéphane , Guerraoui Rachid , Molli Pascal , Pucheral Philippe , Roncancio Claudia , Serrano-Alvarado Patricia , Valduriez Patrick
Published: November 2005

This paper reports on the main results of a specific action on mobile databases conducted by CNRS in France from October 2001 to December 2002. The objective of this action was to review the state of progress in mobile databases and identify major research directions for the French database community. Rather than provide a survey of all important issues in mobile databases, this paper gives an outline of the directions in which the action participants are now engaged, namely: copy synchronization in disconnected computing, mobile transactions, database embedded in ultra-light devices, data confidentiality, P2P dissemination models and middleware adaptability.
Introducing an annotated bibliography on temporal and evolution aspects in the World Wide Web
Authors: Grandi Fabio
Published: November 2005

Time is a pervasive dimension of reality as everything evolves as time elapses. Information systems and applications at least mirror, and often have to capture, the time-varying and evolutionary nature of the phenomena they model and the activities they support. This aspect has been acknowledged and long studied in the field of temporal databases but it truly applies also to the World Wide Web, although it has not seemingly considered as a primary issue yet. However, several papers addressing, in an explicit or implicit way, the representation and management of time and change in the World Wide Web appeared recently and, on some aspects, showed a clear upward trend in last months, witnessing a sustained and/or growing interest.
Jeffrey naughton speaks out on database systems as control freaks, how to choose students, how to choose problems, how to get attention, the importance of being true to yourself, and more
Authors: Winslett Marianne
Published: November 2005

Welcome to this installment of ACM SIGMOD Record's series of interviews with distinguished members of the database community. I'm Marianne Winslett, and today we're in the Department of Computer Science at the University of Illinois at Urbana-Champaign. I have here with me Jeffrey Naughton, who is a professor of computer science at the University of Wisconsin at Madison. Jeff's research has focused on improving the performance and functionality of database management systems. He received the National Science Foundation's Presidential Young Investigator Award, and he is an ACM Fellow. Jeff's PhD is from Stanford University. So, Jeff, welcome!
Spatial, temporal and spatio-temporal databases - hot issues and directions for phd research
Authors: Roddick John F. , Hoel Erik , Egenhofer Max J. , Papadias Dimitris , Salzberg Betty
Published: November 2005

Spatial and temporal database systems, both in theory and in practice, have developed dramatically over the past two decades to the point where usable commercial systems, underpinned by a robust theoretical foundation, are now starting to appear. While much remains to be done, topics for research must be chosen carefully to avoid embarking on impractical or unprofitable areas. This is particularly true for doctoral research where the candidate must build a tangible contribution in a relatively short time.The panel session at the Eighth International Symposium on Spatial and Temporal Databases (SSTD 2003) held on Santorini Island, Greece [7] in July 2003 thus took as its focus the question
What to focus on (and what to avoid) in Spatial and Temporal Databases: recommendations for doctoral research.
This short paper, authored by the panel members, summarizes these discussions.
A denotational semantics for continuous queries over streams and relations
Authors: Arasu Arvind , Widom Jennifer
Published: November 2005

Continuous queries over data streams are an important new class of queries motivated by a number of applications [BBD+02, Geh03, GO03], and several languages for continuous queries have been proposed recently [ABW03, CC+02, CC+03, WZL03]. To date the semantics of these languages have been specified fairly informally, sometimes solely through illustrative examples.
A read-only transaction anomaly under snapshot isolation
Authors: Fekete Alan , O'Neil Elizabeth , O'Neil Patrick
Published: November 2005

Snapshot Isolation (SI), is a multi-version concurrency control algorithm introduced in [BBGMOO95] and later implemented by Oracle. SI avoids many concurrency errors, and it never delays read-only transactions. However it does not guarantee serializability. It has been widely assumed that, under SI, read-only transactions always execute serializably provided the concurrent update transactions are serializable. The reason for this is that all SI reads return values from a single instant of time when all committed transactions have completed their writes and no writes of non-committed transactions are visible. This seems to imply that read-only transactions will not read anomalous results so long as the update transactions with which they execute do not write such results. In the current note, however, we exhibit an example contradicting these assumptions: it is possible for an SI history to be non-serializable while the sub-history containing all update transactions is serializable.
CiVeDi
Authors: Mazzoleni Pietro , Bertino Elisa , Ferrari Elena , Valtolina Stefano
Published: November 2005

This paper presents CiVedi, a scalable system providing a flexible and customizable virtual environment for displaying multimedia contents. Using CiVeDi, both the final users and the exhibition curators can personalize the content of the visit as well as the visit appearance and its duration. The proposed solution aims to be used transparently over different media objects either stored into a database or dynamically collected from online digital libraries.
An evaluation of XML indexes for structural join
Authors: Li Hanyu , Lee Mong Li , Hsu Wynne , Chen Chao
Published: November 2005

XML queries differ from relational queries in that the former are expressed as path expressions. The efficient handling of structural relationships has become a key factor in XML query processing. Many index-based solutions have been proposed for efficient structural join in XML queries. This work explores the state-of-the-art indexes, namely, B+-tree, XB-tree and XR-tree, and analyzes how well they support XML structural joins. Experiment results indicate that all three indexes yield comparable performances for non-recursive XML data, while the XB-tree outperforms the rest for highly recursive XML data.
Integration of biological sources
Authors: Hernandez Thomas , Kambhampati Subbarao
Published: November 2005

This paper surveys the area of biological and genomic sources integration, which has recently become a major focus of the data integration research field. The challenges that an integration system for biological sources must face are due to several factors such as the variety and amount of data available, the representational heterogeneity of the data in the different sources, and the autonomy and differing capabilities of the sources.

This survey describes the main integration approaches that have been adopted. They include warehouse integration, mediator-based integration, and navigational integration. Then we look at the four major existing integration systems that have been developed for the biological domain: SRS, BioKleisli, TAMBIS, and DiscoveryLink. After analyzing these systems and mentioning a few others, we identify the pros and cons of the current approaches and systems and discuss what an integration system for biologists ought to be.
Structured databases on the web
Authors: Chang Kevin Chen-Chuan , He Bin , Li Chengkai , Patel Mitesh , Zhang Zhen
Published: November 2005

The Web has been rapidly "deepened" by the prevalence of databases online. With the potentially unlimited information hidden behind their query interfaces, this "deep Web" of searchable databses is clearly an important frontier for data access. This paper surveys this relatively unexplored frontier, measuring characteristics pertinent to both exploring and integrating structured Web sources. On one hand, our "macro" study surveys the deep Web at large, in April 2004, adopting the random IP-sampling approach, with one million samples. (How large is the deep Web? How is it covered by current directory services?) On the other hand, our "micro" study surveys source-specific characteristics over 441 sources in eight representative domains, in December 2002. (How "hidden" are deep-Web sources? How do search engines cover their data? How complex and expressive are query forms?) We report our observations and publish the resulting datasets to the research community. We conclude with several implications (of our own) which, while necessarily subjective, might help shape research directions and solutions.
NESTREAM
Authors: Chatziantoniou Damianos , Anagnostopoulos Achilleas
Published: November 2005

This article identifies an interesting class of applications where stream sessions may be organized in a hierarchical fashion - i.e. sessions may contain sub-sessions. For example, log streams from call centers belong to different call sessions and call sessions consist of services' sub-sessions. We may want to monitor statistics and perform accounting at any level on this hierarchy, relative to any other higher level (e.g. monitoring the average service session per call vs. the average service session for the entire system.) We argue that data streams of this kind have rich procedural semantics - i.e. behavior - and therefore a semantically rich model should be used: a session may be defined by opening and closing conditions, may have data and methods and may consist of sub-sessions. We propose a simple conceptual model based on the notion of "session" - similar to a class in an object-oriented environment -- having lifetime semantics. Queries on top of this schema can be formulated via HSA (hierarchical stream aggregate) expressions. We describe an algorithm dictating how stream data flow down session hierarchies and discuss potential evaluation and optimization techniques for HSAs. Finally we introduce NESTREAM, a prototype implementation for these ideas and give some preliminary experimental results.
Advancements in SQL/XML
Authors: Eisenberg Andrew , Melton Jim
Published: November 2005

Since we last wrote about SQL/XML in [2], the first edition of that new part of the SQL standard has been officially published as an international standard [1], commonly called SQL/XML:2003. At the time of that earlier column, SQL/XML was just entering its first official ballot, meaning that (possibly significant) changes to the text were expected in response to ballot comments submitted by the various participants in the SQL standardization process.
Automatic direct and indirect schema mapping
Authors: Embley David W. , Xu Li , Ding Yihong
Published: November 2005

Schema mapping produces a semantic correspondence between two schemas. Automating schema mapping is challenging. The existence of 1:
n
(or
n
:1) and
n:m
mapping cardinalities makes the problem even harder. Recently, we have studied automated schema mapping techniques (using data frames and domain ontology snippets) that not only address the traditional 1:1 mapping problem, but also the harder 1:
n
and
n:m
mapping problems. Experimental results show that the approach can achieve excellent precision and recall. In this paper, we share our experiences and lessons we have learned during our schema mapping studies.
Matching large XML schemas
Authors: Rahm Erhard , Do Hong-Hai , Maßmann Sabine
Published: November 2005

Current schema matching approaches still have to improve for very large and complex schemas. Such schemas are increasingly written in the standard language W3C XML schema, especially in E-business applications. The high expressive power and versatility of this schema language, in particular its type system and support for distributed schemas and name-spaces, introduce new issues. In this paper, we study some of the important problems in matching such large XML schemas. We propose a fragment-oriented match approach to decompose a large match problem into several smaller ones and to reuse previous match results at the level of schema fragments.
Industrial-strength schema matching
Authors: Bernstein Philip A. , Melnik Sergey , Petropoulos Michalis , Quix Christoph
Published: November 2005

Schema matching identifies elements of two given schemas that correspond to each other. Although there are many algorithms for schema matching, little has been written about building a system that can be used in practice. We describe our initial experience building such a system, a customizable schema matcher called Protoplasm.
Book review column
Authors: Aberer Karl
Published: November 2005

This is the last issue of the book review column that will appear under my responsibility. I would like to thank here all authors of book reviews for their very interesting contributions over the last four years. I also hope the readers of SIGMOD RECORD found the articles in this column of interest and that they motivated in some cases to have a more detailed look at one of the reviewed books. For me it was surely an interesting experience seeing which new books have arrived over the last four years and also how they are appreciated by the community.
Data base directions
Authors: Berg John L.
Published: November 2005

What information about data base technology does a manager need to make prudent decisions about using this new technology? To provide this information the National Bureau of Standards and the Association for Computing Machinery established a workshop of approximately 80 experts in five major subject areas. The five subject areas were auditing, evolving technology, government regulations, standards, and user experience. Each area prepared a report contained in these proceedings. The proceedings provide guidance of steps managers should follow to prepare themselves and their organization for the installation of data base management concepts. The auditing working panel noted the increased vulnerability of organizations who integrate their formerly dispersed and redundant files into a data base and suggest actions to address this risk. The technology report noted several promising parallel developments but concluded that the future would see evolving, rather than revolutionary data base progress. Government regulations, particularly the drive for individual privacy rights, were seen to play an important role in determining data base directions and the panel's guidance on cost impact suggest that organizations would experience reduced costs with data base technology. Standards pervaded all issues and were found necessary in several sub-areas of data base technology but the panel saw no immediate likelihood of national data base standards. The user experience working panel noted that data base systems had impacted their organizations to the extent of reconsidering existing data flows, areas of responsibilities, and procedures.
A LVQ-based neural network anti-spam email approach
Authors: Chuan Zhan , Xianliang Lu , Mengshu Hou , Xu Zhou
Published: November 2005

Along with wide application of e-mail nowadays, many spam e-mails flood into people's email inboxes and bring catastrophe to their study and work. This paper presents a novel anti-spam e-mail filter based-LVQ network in terms of spam e-mails which are mainly made up of several kinds commercial or political spam emails at present. Our experiment has proved that the filter based on LVQ is superior to Bayes-based and BP-based approaches in total performances apparently.
Distributed approximation
Authors: Elkin Michael
Published: November 2005

Recently considerable progress was achieved in designing efficient
distributed approximation algorithms
, and in demonstrating
hardness of distributed approximation
for various problems. In this survey we overview the research in this area and propose several directions for future research.
Candidates for the upcoming ACM SIGMOD elections
Authors: Franklin Mike
Published: November 2005

A clear sign of a healthy organization is the willingness of its members to volunteer their time to support and guide it. SIGMOD is particularly fortunate in this regard. As evidence is the slate of candidates listed on the following pages. These six people have agreed to run for positions as SIGMOD officers, and if elected, are committed to overseeing and improving the wide-ranging activities of SIGMOD and continuing the progress that has made us one of the leading SIGs in ACM.
A unified spatiotemporal schema for representing and querying moving features
Authors: Xie Rong , Shibasaki Ryosuke
Published: November 2005

A conceptual schema is essentially required to effectively and efficiently manage and manipulate dynamically and continuously changing data and information of moving features. In the paper, spatiotemporal schema (STS) is proposed to describe characteristics of moving features and to efficiently manage moving features data, including the necessity aspects: abstract data types, dynamic attributes, spatiotemporal topological relationships and a minimum set of spatiotemporal operations. On the basis of the proposal of schema, spatiotemporal object-based class library (STOCL) is further developed for the implementation of STS, which allows development of various spatiotemporal queries and simulations. The conceptual schema and implemented object library are then applied to the development of passengers' movement simulation and pattern analysis in railway stations in Tokyo.
Measuring the evolution of transport protocols in the internet
Authors: Medina Alberto , Allman Mark , Floyd Sally
Published: November 2005

In this paper we explore the evolution of both the Internet's most heavily used transport protocol, TCP, and the current network environment with respect to how the network's evolution ultimately impacts end-to-end protocols. The traditional end-to-end assumptions about the Internet are increasingly challenged by the introduction of intermediary network elements (middleboxes) that intentionally or unintentionally prevent or alter the behavior of end-to-end communications. This paper provides measurement results showing the impact of the current network environment on a number of traditional and proposed protocol mechanisms (e.g., Path MTU Discovery, Explicit Congestion Notification, etc.). In addition, we investigate the prevalence and correctness of implementations using proposed TCP algorithmic and protocol changes (e.g., selective acknowledgment-based loss recovery, congestion window growth based on byte counting, etc.). We present results of measurements taken using an active measurement framework to study web servers and a passive measurement survey of clients accessing information from our web server. We analyze our results to gain further understanding of the differences between the behavior of the Internet in theory versus the behavior we observed through measurements. In addition, these measurements can be used to guide the definition of more realistic Internet modeling scenarios. Finally, we present several lessons that will benefit others taking Internet measurements.
Proving multilevel security of a system design
Authors: Feiertag R. J. , Levitt K. N. , Robinson L.
Published: November 2005

Two nearly equivalent models of multilevel security are presented. The use of multiple models permits the utilization of each model for purposes where that model is particularly advantageous. In this case, the more general model is simple and easily comprehensible, being more abstract, and is useful for exposition of the meaning of multilevel security. The less general model relates well to design specifications and permits straightforward proof of the security of a system design. The correspondence between the two models is easily demonstrated. The two models when applied appropriately are more useful for defining and proving the multilevel security of systems than existing models. The utility of the two models and their relationship to existing models is discussed and the proof of the security of one particular system design is illustrated. The technique for accomplishing the security proof is straightforward and can be extensively automated.
Protocol enhancements for intermittently connected hosts
Authors: Schütz Simon , Eggert Lars , Schmid Stefan , Brunner Marcus
Published: November 2005

Internet users are increasingly mobile. Their hosts are often only intermittently connected to the Internet, due to using multiple access networks, gaps in wireless coverage or explicit user choice. When such hosts communicate using the current Internet protocols, intermittent connectivity can significantly decrease performance and even cause connections to fail altogether. This paper experimentally measures the behavior of Internet communication across a dynamically changing, intermittently connected path. An analysis of the experimental results finds that address changes together with transport-layer timeout and retransmission behaviors are the main limiting factors. Based on these experimental results, this paper proposes a solution that combines the Host Identity Protocol (HIP) with two new protocol enhancements, the TCP User Timeout Option and the TCP Retransmission Trigger. Detailed experiments with HIP and a prototype implementation of these protocol enhancements show that they tolerate address changes and arbitrary-length disconnections while significantly increasing performance under intermittent connectivity to within 86-96% of a scenario with constant connectivity.
Performance relighting and reflectance transformation with time-multiplexed illumination
Authors: Wenger Andreas , Gardner Andrew , Tchou Chris , Unger Jonas , Hawkins Tim , Debevec Paul
Published: November 2005

We present a technique for capturing an actor's live-action performance in such a way that the lighting and reflectance of the actor can be designed and modified in postproduction. Our approach is to illuminate the subject with a sequence of time-multiplexed basis lighting conditions, and to record these conditions with a high-speed video camera so that many conditions are recorded in the span of the desired output frame interval. We investigate several lighting bases for representing the sphere of incident illumination using a set of discrete LED light sources, and we estimate and compensate for subject motion using optical flow and image warping based on a set of tracking frames inserted into the lighting basis. To composite the illuminated performance into a new background, we include a time-multiplexed matte within the basis. We also show that the acquired data enables time-varying surface normals, albedo, and ambient occlusion to be estimated, which can be used to transform the actor's reflectance to produce both subtle and stylistic effects.
A linear-time approximation algorithm for weighted matchings in graphs
Authors: Vinkemeier Doratha E. Drake , Hougardy Stefan
Published: November 2005

Approximation algorithms have so far mainly been studied for problems that are not known to have polynomial time algorithms for solving them exactly. Here we propose an approximation algorithm for the weighted matching problem in graphs which can be solved in polynomial time. The weighted matching problem is to find a matching in an edge weighted graph that has maximum weight. The first polynomial-time algorithm for this problem was given by Edmonds in 1965. The fastest known algorithm for the weighted matching problem has a running time of
O
(
nm
+
n
2
log
n
). Many real world problems require graphs of such large size that this running time is too costly. Therefore, there is considerable need for faster approximation algorithms for the weighted matching problem. We present a linear-time approximation algorithm for the weighted matching problem with a performance ratio arbitrarily close to 2/3. This improves the previously best performance ratio of 1/2. Our algorithm is not only of theoretical interest, but because it is easy to implement and the constants involved are quite small it is also useful in practice.
The NP-completeness column
Authors: Johnson David S.
Published: November 2005

This is the 24th edition of a column that covers new developments in the theory of NP-completeness. The presentation is modeled on that which M. R. Garey and I used in our book “Computers and Intractability: A Guide to the Theory of NP-Completeness,” W. H. Freeman & Co., New York, 1979, hereinafter referred to as “[G&J].”” Previous columns, the first 23 of which appeared in
J. Algorithms
, will be referred to by a combination of their sequence number and year of appearance, e.g. “[Col 1, 1981].” This edition of the column describes the history and purpose of the column and the status of the open problems from [G&J] and previous columns.
Routing-aware scan chain ordering
Authors: Gupta Puneet , Kahng Andrew B. , Mantik Stefanus
Published: November 2005

Scan chain insertion can have a large impact on routability, wirelength, and timing of the design. We present a
routing-driven
methodology for scan chain ordering with minimum wirelength objective. A routing-based approach to scan chain ordering, while potentially more accurate, can result in TSP (Traveling Salesman Problem) instances which are asymmetric and highly nonmetric; this may require a careful choice of solvers. We evaluate our new methodology on recent industry place-and-route blocks with 1200 to 5000 scan cells. We show substantial wirelength reductions for the routing-based flow versus the traditional placement-based flow. In a number of our test cases, over 86% of scan routing overhead is saved. Even though our experiments are, so far, timing oblivious, the routing-based flow also improves evaluated timing, and practical timing-driven extensions appear feasible.
Event-based runtime verification of java programs
Authors: d'Amorim Marcelo , Havelund Klaus
Published: November 2005

We introduce the temporal logic HAWK and its supporting tool for runtime verification of Java programs. A monitor for a HAWK formula checks if a finite trace of program events satisfies the formula. HAWK is a programming-oriented extension of the rule-based EAGLE logic that has been shown capable of defining and implementing a range of finite trace monitoring logics, including future and past time temporal logic, metric (real-time) temporal logics, interval logics, forms of quantified temporal logics, extended regular expressions, state machines, and others. Monitoring is achieved on a state-by-state basis avoiding any need to store the input trace. HAWK extends EAGLE with constructs for capturing parameterized program events such as method calls and method returns. Parameters can be executing thread, the objects that methods are called upon, arguments to methods, and return values. HAWK allows one to refer to these in formulae. The tool synthesizes monitors from formulae and automates program instrumentation.
Peer-to-peer management of XML data
Authors: Koloniari Georgia , Pitoura Evaggelia
Published: November 2005

Peer-to-peer (p2p) systems are attracting increasing attention as an efficient means of sharing data among large, diverse and dynamic sets of users. The widespread use of XML as a standard for representing and exchanging data in the Internet suggests using XML for describing data shared in a p2p system. However, sharing XML data imposes new challenges in p2p systems related to supporting advanced querying beyond simple keyword-based retrieval. In this paper, we focus on data management issues for processing XML data in a p2p setting, namely indexing, replication, clustering and query routing and processing. For each of these topics, we present the issues that arise, survey related research and highlight open research problems.
Mining data streams
Authors: Gaber Mohamed Medhat , Zaslavsky Arkady , Krishnaswamy Shonali
Published: November 2005

The recent advances in hardware and software have enabled the capture of different measurements of data in a wide range of fields. These measurements are generated continuously and in a very high fluctuating data rates. Examples include sensor networks, web logs, and computer network traffic. The storage, querying and mining of such data sets are highly computationally challenging tasks. Mining data streams is concerned with extracting knowledge structures represented in models and patterns in non stopping streams of information. The research in data stream mining has gained a high attraction due to the importance of its applications and the increasing generation of streaming information. Applications of data stream analysis can vary from critical scientific and astronomical applications to important business and financial ones. Algorithms, systems and frameworks that address streaming challenges have been developed over the past three years. In this review paper, we present the state-of-the-art in this growing vital field.
On six degrees of separation in DBLP-DB and more
Authors: Elmacioglu Ergin , Lee Dongwon
Published: November 2005

An extensive bibliometric study on the db community using the collaboration network constructed from DBLP data is presented. Among many, we have found that (1) the average distance of all db scholars in the network has been stabilized to about 6 for the last 15 years, coinciding with the so-called six degrees of separation phenomenon; (2) In sync with Lotka's law on the frequency of publications, the db community also shows that a few number of scholars publish a large number of papers, while the majority of authors publish a small number of papers (i.e., following the power-law with exponent about -2); and (3) with the increasing demand to publish more, scholars collaborate more often than before (i.e., 3.93 collaborators per scholar and with steadily increasing clustering coefficients).
Semantic characterizations of navigational XPath
Authors: Marx Maarten , de Rijke Maarten
Published: November 2005

We give semantic characterizations of the expressive power of navigational XPath (a.k.a. Core XPath) in terms of first order logic. XPath can be used to specify sets of nodes and sets of paths in an XML document tree. We consider both uses. For sets of nodes, XPath is equally expressive as first order logic in two variables. For paths, XPath can be defined using four simple connectives, which together yield the class of first order definable relations which are safe for bisimulation. Furthermore, we give a characterization of the XPath expressible paths in terms of conjunctive queries.
Nested intervals tree encoding in SQL
Authors: Tropashko Vadim
Published: November 2005

Nested Intervals generalize Nested Sets. They are immune to hierarchy reorganization problem. They allow answering ancestor path hierarchical queries algorithmically - without accessing the stored hierarchy relation.
Report on the International Workshop on Pattern Representation and Management (PaRMa'04)
Authors: Theodoridis Yannis , Vassiliadis Panos
Published: November 2005

The increasing ability to quickly collect and cheaply store large volumes of data, and the need for extracting concise information to be efficiently manipulated and intuitively analyzed, are posing new requirements for Database Management Systems (DBMS) in both industrial and scientific applications. A common approach to deal with huge data volumes is to reduce the available information to knowledge artifacts (i.e., clusters, rules, etc.), hereafter called
patterns
, through data processing methods (pattern recognition, data mining, knowledge extraction). Patterns reduce the number and size of the original information to manageable size while preserving as much as possible its hidden / interesting content. In order to efficiently and effectively deal with patterns, academic groups and industrial consortiums have recently devoted efforts towards modeling, storage, retrieval, analysis and manipulation of patterns with results mainly in the areas of
Inductive Databases
and
Pattern Base Management Systems
(PBMS).
An approach for pipelining nested collections in scientific workflows
Authors: McPhillips Timothy M. , Bowers Shawn
Published: November 2005

We describe an approach for pipelining nested data collections in scientific workflows. Our approach logically delimits arbitrarily nested collections of data tokens using special, paired control tokens inserted into token streams, and provides workflow components with high-level operations for managing these collections. Our framework provides new capabilities for: (1) concurrent operation on collections; (2) on-the-fly customization of workflow component behavior; (3) improved handling of exceptions and faults; and (4) transparent passing of provenance and metadata within token streams. We demonstrate our approach using a workflow for inferring phylogenetic trees. We also describe future extensions to support richer typing mechanisms for facilitating sharing and reuse of workflow components between disciplines. This work represents a step towards our larger goal of exploiting collection-oriented dataflow programming as a new paradigm for scientific workflow systems, an approach we believe will significantly reduce the complexity of creating and reusing workflows and workflow components.
A survey of data provenance in e-science
Authors: Simmhan Yogesh L. , Plale Beth , Gannon Dennis
Published: November 2005

Data management is growing in complexity as large-scale applications take advantage of the loosely coupled resources brought together by grid middleware and by abundant storage capacity. Metadata describing the data products used in and generated by these applications is essential to disambiguate the data and enable reuse. Data provenance, one kind of metadata, pertains to the derivation history of a data product starting from its original sources.In this paper we create a taxonomy of data provenance characteristics and apply it to current research efforts in e-science, focusing primarily on scientific workflow approaches. The main aspect of our taxonomy categorizes provenance systems based on why they record provenance, what they describe, how they represent and store provenance, and ways to disseminate it. The survey culminates with an identification of open research problems in the field.
A notation and system for expressing and executing cleanly typed workflows on messy scientific data
Authors: Zhao Yong , Dobson Jed , Foster Ian , Moreau Luc , Wilde Michael
Published: November 2005

The description, composition, and execution of even logically simple scientific workflows are often complicated by the need to deal with "messy" issues like heterogeneous storage formats and ad-hoc file system structures. We show how these difficulties can be overcome via a typed, compositional workflow notation within which issues of physical representation are cleanly separated from logical typing, and by the implementation of this notation within the context of a powerful runtime system that supports distributed execution. The resulting notation and system are capable both of expressing complex workflows in a simple, compact form, and of enacting those workflows in distributed environments. We apply our technique to cognitive neuroscience workflows that analyze functional MRI image data, and demonstrate significant reductions in code size relative to other approaches.