bluuebunny/crossref_metadata_2025 huggingface dataset:
Information access at the data item level
Authors: Mochmann Ekkehard
Published: April 2007

Data archives are being challenged to provide more transparent and directly accessible data. Given the scope of already available materials and the yearly increase of the data base, effective means of information retrieval had to be developed.
Managing information access through documentation of the data base
Authors: Robbin Alice
Published: April 2007

If data are to be accessed, text documentation must adequately describe the processes of data collection, development, testing and evaluation of the file in order that analysis of the data file can be adequately performed. Text documentation can be conceptualized as a minimal information system with the functions of providing a conceptual framework for the collection process, communication and coordination of processing staff, historical reference, general instruction for communication between specialist and non-specialist, and a report on successful output. Text documentation has three components: source, codebook and technical. This discussion focuses only on the components of source and codebook documentation.
A model for the correction for guessing on multiple-choice tests
Authors: Hansen E. A. , Schmidt F. L. , Hansen J. C.
Published: April 2007

Multiple-choice tests are used widely because of obvious practical advantages, but inherent in them is the problem of dealing with the effects of guessing. The only widely used model for predicting effects of guessing is based on the primary assumption that, the probability of making a correct response on each test item is either 1.0 or the reciprocal of the number of available choices. The assumption that the subject either makes the correct response on each trial or guesses blindly is clearly too restrictive. Nunnally in [1] relates that because in most educational tests there is some opportunity for "narrowing" alternatives before guessing the standard correction for guessing tends to be an underestimate of the actual effects of guessing. The model proposed in this paper attempts to correct for this.
The expert assistance system
Authors: Watkins Shirley Ward
Published: April 2007

The Network Access Machine, developed at the National Bureau of Standards, is directed towards the objective of people-oriented systems. I will begin by providing some background information concerning what stimulated our work, highlight very briefly some of the capabilities of the Network Access Machine, and then review the current extension to this Network Access Machine which in effect reflects our continuing interest in people-oriented systems.
Formative evaluation
Authors: Martin Thomas H.
Published: April 2007

Let me tell you what I mean by formative evaluation. For example, in the design of something like Sesame Street or FreeStyle, social science researchers have gotten away from the role they're usually cast in - that is, to come in afterwards and explain why things failed. Instead, they get in right near the beginning and try to make sure that things turn out to be successes. You've all heard of the success of Sesame Street, and you're probably beginning to hear of the success of FreeStyle. When you have a big project and there is a great disparity between the people who are doing it and the people they're supposed to be impacting or who are going to be their users, the possibilities of misunderstanding and potential failure are great. This is a very common problem with large systems that are being designed today. Even though people think they are talking the same language, they find out they aren't. We have a lot of systems that are designed now where the system designers or the system analysts come up with specifications, let out bids, someone gets the bid, and that supposedly is it. Although misunderstandings between the systems analysts and the contractors may exist, that doesn't guarantee that the system analysts have a very good understanding of the end users. The idea in formative evaluation is that as you're getting the design put together and putting the concepts in place, you go out and start gathering representative data from the end user population to see whether in fact it is possible to attain the goals. Everybody knows that design is an iterative process, and evaluation should be a component of it. We give it lip service but very rarely do we do it, and the cliches are, "Well, you know the users don't know what they're going to want, they're going to keep on changing." To some extent that is true, but that is very often used as an excuse to skip the data gathering completely. By focusing on the misunderstandings, by trying to clarify the goals, one can early on learn whether in fact a system can be developed that is useable and satisfactory to those users.
Instant turnaround revisited
Authors: Kreider Glen D. , Sim Francis M.
Published: April 2007

In earlier reports (Kreider, et. al., 1970; Williams, et. al., 1970; Sim, et. al., 1971a, Sim, et. al., 1971b) we have described and discussed the general character and some social science applications of a system of instructional computing developed at the Pennsylvania State University. The service is one of "Speed Batch" processing (Bernitt, 1971) which gives immediate response to "small" jobs. It was originally based on the WATFOR dialect and processor, so we have used the acronym WIT (for Watfor Instant Turnaround) to refer to the system. In this report we note progress in the further development of the service. In a later report we will discuss applications in social science instruction.
Structured programming in Fortran
Authors: Sakoda James M.
Published: April 2007

The basic spirit of structured programming is to write programs that are easy to read and debug. Students who are taught programming should be encouraged to use structured programming principles. Ingredients of structured programming include:
Some effects of considerate and inconsiderate systems
Authors: Anderson Ronald E.
Published: April 2007

Concern for the human factors in computer systems continues to grow as computerization becomes more and more pervasive. In the early period of computing such concern was expressed in terms of "user orientation" and "user requirements." As interactive systems evolved it became more common to hear terms like "responsive systems," and "end-user requirements." In the early Seventies, when the computer profession experienced a wave of social responsibility, discussions emerged on "humanizing" systems [1]. More recent discussions on these issues describe ideal systems as people-oriented, convivial, or friendly [2]. Despite this attention to human factors there is relatively little systematic knowledge about what system features actually take human needs and desires into account, and, in this sense, are considerate.
Solving the pooling problem using generalized reduced gradient and successive linear programming algorithms
Authors: Lasdon L. S. , Waren A. D. , Sarkar S. , Palacios F.
Published: April 2007

In earlier issues of this bulletin, Haverly and Hart discussed solving some simple pooling problems using LP recursion [1]-[3]. We thought it would be interesting to attempt to solve these problems using some nonlinear programming (NLP) codes. This note briefly discusses the codes and algorithms used, presents the results, and discusses some properties of the models.
Distributive recursion at Socal
Authors: White D. L. , Trierwiler L. D.
Published: April 2007

One of the most significant advancements to refinery optimization linear programming at Socal is Distributive Recursion. Distributive Recursion, together with Delta/Base modeling, has allowed us to model our refineries in a more realistic manner:- pooling streams in the model where they are, in fact, pooled in the refinery;- shifting refinery operations based on pooled feed qualities;- allowing us to model many refinery non-linearities, previously not modeled.Our refinery LP models are approaching the accuracy of non-linear refinery simulators while retaining the ability to optimize.In this paper, we will discuss the implementation and impact of Distributive Recursion at Socal.
The apex systems past and future
Authors: Krabek C. B. , Sjoouist R. J. , Sommer D. C.
Published: April 2007

A number of features of the APEX-I and/or APEX-III Mathematical Programming Systems that were novel when they were introduced are discussed. These include the use of supersparsity, a numerically stable variant of the Hellerman-Rarick invert, some extensions to matrix reduction algorithms new and methods of model analysis. There is a short discussion of development methodology and overall data structure in the systems. Finally a short discussion of some promising areas of future development is presented.
VMCWD
Authors: Powell M. J. D.
Published: April 2007

A listing is given of a Fortran subroutine that calculates the least value of a function of several variables subject to general equality and inequality constraints. The user must provide an auxiliary subroutine that computes the objective and constraint functions and their gradients for any vector of variables. The underlying algorithm is a variable Metric method for Constrained optimization that includes the Watch-Dog technique, which gives the acronym VMCWD. This method is particularly efficient in terms of the number of function and gradient evaluations, but the overheads per iteration are expensive when the time to calculate functions and gradients is negligible.
An interactive query system for MPS solution information
Authors: O'Neill Richard P.
Published: April 2007

This paper describes the design, development and use of an interactive query system for the MPS solution. A packed data structure is presented which reduces the storage requirement of the file by an order of magnitude allowing larger files to be resident in core. The language syntax is described and examples are presented.
A static type system for JVM access control
Authors: Higuchi Tomoyuki , Ohori Atsushi
Published: April 2007

This article presents a static type system for the Java virtual machine (JVM) code that enforces an access control mechanism similar to that found in a Java implementation. In addition to verifying type consistency of a given JVM code, the type system statically verifies whether the code accesses only those resources that are granted by the prescribed access policy. The type system is proved to be sound with respect to an operational semantics that enforces access control dynamically, similar to Java stack inspection. This result ensures that “well-typed code cannot violate access policy.” The authors then develop a type inference algorithm and show that it is sound with respect to the type system. These results allow us to develop a static system for JVM access control, without resorting to costly runtime stack inspection.
Logical characterizations of heap abstractions
Authors: Yorsh Greta , Reps Thomas , Sagiv Mooly , Wilhelm Reinhard
Published: April 2007

Shape analysis concerns the problem of determining “shape invariants” for programs that perform destructive updating on dynamically allocated storage. In recent work, we have shown how shape analysis can be performed using an abstract interpretation based on three-valued first-order logic. In that work, concrete stores are finite two-valued logical structures, and the sets of stores that can possibly arise during execution are represented (conservatively) using a certain family of finite three-valued logical structures. In this article, we show how three-valued structures that arise in shape analysis can be characterized using formulas in first-order logic with transitive closure. We also define a nonstandard (“supervaluational”) semantics for three-valued first-order logic that is more precise than a conventional three-valued semantics, and demonstrate that the supervaluational semantics can be implemented using existing theorem provers.
Specifying memory consistency of write buffer multiprocessors
Authors: Higham Lisa , Jackson Lillanne , Kawash Jalal
Published: April 2007

Write buffering is one of many successful mechanisms that improves the performance and scalability of multiprocessors. However, it leads to more complex memory system behavior, which cannot be described using intuitive consistency models, such as Sequential Consistency. It is crucial to provide programmers with a specification of the exact behavior of such complex memories. This article presents a uniform framework for describing systems at different levels of abstraction and proving their equivalence. The framework is used to derive and prove correct simple specifications in terms of program-level instructions of the sparc total store order and partial store order memories.The framework is also used to examine the sparc relaxed memory order. We show that it is not a memory consistency model that corresponds to any implementation on a multiprocessor that uses write-buffers, even though we suspect that the sparc version 9 specification of relaxed memory order was intended to capture a general write-buffer architecture. The same technique is used to show that Coherence does not correspond to a write-buffer architecture. A corollary, which follows from the relationship between Coherence and Alpha, is that any implementation of Alpha consistency using write-buffers cannot produce all possible Alpha computations. That is, there are some computations that satisfy the Alpha specification but cannot occur in the given write-buffer implementation.
Comprehensive multivariate extrapolation modeling of multiprocessor cache miss rates
Authors: Gluhovsky Ilya , Vengerov David , O'Krafka Brian
Published: April 2007

Cache miss rates are an important subset of system model inputs. Cache miss rate models are used for broad design space exploration in which many cache configurations cannot be simulated directly due to limitations of trace collection setups or available resources. Often it is not practical to simulate large caches. Large processor counts and consequent potentially high degree of cache sharing are frequently not reproducible on small existing systems. In this article, we present an approach to building multivariate regression models for predicting cache miss rates beyond the range of collectible data. The extrapolation model attempts to accurately estimate the high-level trend of the existing data, which can be extended in a natural way. We extend previous work by its applicability to multiple miss rate components and its ability to model a wide range of cache parameters, including size, line size, associativity and sharing. The stability of extrapolation is recognized to be a crucial requirement. The proposed extrapolation model is shown to be stable to small data perturbations that may be introduced during data collection.We show the effectiveness of the technique by applying it to two commercial workloads. The wide design space contains configurations that are much larger than those for which miss rate data were available. The fitted data match the simulation data very well. The various curves show how a miss rate model is useful for not only estimating the performance of specific configurations, but also for providing insight into miss rate trends.
Adapting Web information extraction knowledge via mining site-invariant and site-dependent features
Authors: Wong Tak-Lam , Lam Wai
Published: April 2007

We develop a novel framework that aims at automatically adapting previously learned information extraction knowledge from a source Web site to a new unseen target site in the same domain. Two kinds of features related to the text fragments from the Web documents are investigated. The first type of feature is called, a site-invariant feature. These features likely remain unchanged in Web pages from different sites in the same domain. The second type of feature is called a site-dependent feature. These features are different in the Web pages collected from different Web sites, while they are similar in the Web pages originating from the same site. In our framework, we derive the site-invariant features from previously learned extraction knowledge and the items previously collected or extracted from the source Web site. The derived site-invariant features will be exploited to automatically seek a new set of training examples in the new unseen target site. Both the site-dependent features and the site-invariant features of these automatically discovered training examples will be considered in the learning of new information extraction knowledge for the target site. We conducted extensive experiments on a set of real-world Web sites collected from three different domains to demonstrate the performance of our framework. For example, by just providing training examples from one online book catalog Web site, our approach can automatically extract information from ten different book catalog sites achieving an average precision and recall of 71.9% and 84.0% respectively without any further manual intervention.
A formal model of services
Authors: Broy Manfred , Krüger Ingolf H. , Meisinger Michael
Published: April 2007

Service-oriented software systems rapidly gain importance across application domains: They emphasize functionality (services), rather structural entities (components), as the basic building block for system composition. More specifically, services coordinate the interplay of components to accomplish specific tasks. In this article, we establish a foundation of service orientation: Based on the Focus theory of distributed systems (see Broy and Stølen [2001]), we introduce a theory and formal model of services. In Focus, systems are composed of interacting components. A component is atotalbehavior. We introduce a formal model of services where, in contrast, a service is apartialbehavior. For services and components, we work out foundational specification techniques and outline methodological development steps. We show how services can be structured and how software architectures can be composed of services and components. Although our emphasis is on a theoretical foundation of the notion of services, we demonstrate utility of the concepts we introduce by means of a running example from the automotive domain.
Operational semantics for multi-language programs
Authors: Matthews Jacob , Findler Robert Bruce
Published: April 2007

Inter-language interoperability is big business, as the success of Microsoft's .NET and COM and Sun's JVM show. Programming language designers are designing programming languages that reflect that fact --- SML#, Mondrian, and Scala, to name just a few examples, all treat interoperability with other languages as a central design feature. Still, current multi-language research tends not to focus on the semantics of interoperation features, but only on how to implement them efficiently. In this paper, we take first steps toward higher-level models of interoperating systems. Our technique abstracts away the low-level details of interoperability like garbage collection and representation coherence, and lets us focus on semantic properties like type-safety and observable equivalence.Beyond giving simple expressive models that are natural compositions of single-language models, our studies have uncovered several interesting facts about interoperability. For example, higher-order contracts naturally emerge as the glue to ensure that interoperating languages respect each other's type systems. While we present our results in an abstract setting, they shed light on real multi-language systems and tools such as the JNI, SWIG, and Haskell's stable pointers.
Modular type classes
Authors: Dreyer Derek , Harper Robert , Chakravarty Manuel M. T. , Keller Gabriele
Published: April 2007

ML modules and Haskell type classes have proven to be highly effective tools for program structuring. Modules emphasize explicit configuration of program components and the use of data abstraction. Type classes emphasize implicit program construction and
ad hoc
polymorphism. In this paper, we show how the implicitly-typed style of type class programming may be supported within the framework of an explicitly-typed module language by viewing type classes as a particular mode of use of modules. This view offers a harmonious integration of modules and type classes, where type class features, such as class hierarchies and associated types, arise naturally as uses of existing module-language constructs, such as module hierarchies and type components. In addition, programmers have explicit control over which type class instances are available for use by type inference in a given scope. We formalize our approach as a Harper-Stone-style elaboration relation, and provide a sound type inference algorithm as a guide to implementation.
Context logic as modal logic
Authors: Calcagno Cristiano , Gardner Philippa , Zarfaty Uri
Published: April 2007

Separation Logic, Ambient Logic and Context Logic are based on a similar style of reasoning about structured data. They each consist of a structural (separating) composition for reasoning about disjoint subdata, and corresponding structural adjoint(s) for reasoning hypothetically about data. We show how to interpret these structural connectives as modalities in Modal Logic and prove completeness results. The structural connectives are essential for describing properties of the underlying data, such as weakest preconditions for Hoare reasoning for Separation and Context Logic, and security properties for Ambient Logic. In fact, we introduced Context Logic to reason about tree update, precisely because the structural connectives of the Ambient Logic did not have enough expressive power. Despite these connectives being essential, first Lozes then Dawar, Gardner and Ghelli proved elimination results for Separation Logic and Ambient Logic (without quantifiers). In this paper, we solve this apparent contradiction. We study parametric inexpressivity results, which demonstrate that the structural connectives are indeed fundamental for this style of reasoning.
Towards a mechanized metatheory of standard ML
Authors: Lee Daniel K. , Crary Karl , Harper Robert
Published: April 2007

We present an internal language with equivalent expressive power to Standard ML, and discuss its formalization in LF and the machine-checked verification of its type safety in Twelf. The internal language is intended to serve as the target of elaboration in an elaborative semantics for Standard ML in the style of Harper and Stone. Therefore, it includes all the programming mechanisms necessary to implement Standard ML, including translucent modules, abstraction, polymorphism, higher kinds, references, exceptions, recursive types, and recursive functions. Our successful formalization of the proof involved a careful interplay between the precise formulations of the various mechanisms, and required the invention of new representation and proof techniques of general interest.
Extracting queries by static analysis of transparent persistence
Authors: Wiedermann Ben , Cook William R.
Published: April 2007

Transparent persistence promises to integrate programming languages and databases by allowing procedural programs to access persistent data with the same ease as non-persistent data. When the data is stored in a relational database, however, transparent persistence does not naturally leverage the performance benefits of relational query optimization. We present a program analysis that combines the benefits of both approaches by extracting database queries from programs with transparent access to persistent data. The analysis uses a sound abstract interpretation of the original program to approximate the data traversal paths in the program and the conditions under which the paths are used. The resulting paths are then converted into a query, and the program is simplified by removing redundant tests. We study an imperative kernel language with read-only access to persistent data and identify the conditions under which the transformations can be applied. This analysis approach promises to combine the software engineering benefits of transparent data persistence with the performance benefits of database query optimization.
Assessing security threats of looping constructs
Authors: Malacaria Pasquale
Published: April 2007

There is a clear intuitive connection between the notion of leakage of information in a program and concepts from information theory. This intuition has not been satisfactorily pinned down, until now. In particular, previous information-theoretic models of programs are imprecise, due to their overly conservative treatment of looping constructs. In this paper we provide the first precise information-theoretic semantics of looping constructs. Our semantics describes both the amount and rate of leakage; if either is small enough, then a program might be deemed "secure". Using the semantics we provide an investigation and classification of bounded and unbounded covert channels.
Advanced programming language design in enterprise software
Authors: Murthy Chet
Published: April 2007

Enterprise software systems automate the business processes of most nontrivial organizations in the world economy. These systems are immensely complex, and their function is critical to our living standards and everyday lives. Their design, implementation, and maintenance occupies many thousands of programmers and engineers, who work in what are aptly called the "COBOL dungeons"
1
of the IT sector. These systems have persisted, growing by accretion -- some for decades; there are enterprise systems in existence today whose original and even subsequent authors are retired or deceased. Such extraordinarly old, multi-layered systems might appear to be the last place to apply
avante-garde
techniques, but in fact, they are extremely promising candidates, and for reasons directly connected to their history and structure.In this talk we take a tour of several deployed enterprise software systems, and demonstrate that the appropriate application of methods from functional programming can and does in fact yield dramatic performance improvements and thus commercial advan-tage in the design and implementation of enterprise software. This concrete application is an instance of a general plan for the application of advanced programming language design and analysis methods, to the problem of improving enterprise software. It is the thesis of this talk that to a great extent, it is in enterprise software that advanced PL techniques can find their most advantageous application. This talk literally breaks no new ground in PL research: every technique discussed is nearly two decades old, and our goal is to introduce PL researchers to what we feel is an ideal target for their work.
Geometry of synthesis
Authors: Ghica Dan R.
Published: April 2007

We propose a new technique for hardware synthesis from higher-order functional languages with imperative features based on Reynolds's
Syntactic Control of Interference
. The restriction on contraction in the type system is useful for managing the thorny issue of sharing of physical circuits. We use a semantic model inspired by game semantics and the geometry of interaction, and express it directly as a certain class of digital circuits that form a cartesian, monoidal-closed category. A soundness result is given, which is also a correctness result for the compilation technique.
A semantics-based approach to malware detection
Authors: Preda Mila Dalla , Christodorescu Mihai , Jha Somesh , Debray Saumya
Published: April 2007

Malware detection is a crucial aspect of software security. Current malware detectors work by checking for "signatures," which attempt to capture (syntactic) characteristics of the machine-level byte sequence of the malware. This reliance on a syntactic approach makes such detectors vulnerable to code obfuscations, increasingly used by malware writers, that alter syntactic properties of the malware byte sequence without significantly affecting their execution behavior.This paper takes the position that the key to malware identification lies in their semantics. It proposes a semantics-based framework for reasoning about malware detectors and proving properties such as soundness and completeness of these detectors. Our approach uses a trace semantics to characterize the behaviors of malware as well as the program being checked for infection, and uses abstract interpretation to "hide" irrelevant aspects of these behaviors. As a concrete application of our approach, we show that the semantics-aware malware detector proposed by Christodorescu
et al.
is complete with respect to a number of common obfuscations used by malware writers.
Creating and exploiting a comparable corpus in cross-language information retrieval
Authors: Talvensaari Tuomas , Laurikkala Jorma , Järvelin Kalervo , Juhola Martti , Keskustalo Heikki
Published: April 2007

We present a method for creating a comparable text corpus from two document collections in different languages. The collections can be very different in origin. In this study, we build a comparable corpus from articles by a Swedish news agency and a U.S. newspaper. The keys with best resolution power were extracted from the documents of one collection, the source collection, by using the relative average term frequency (RATF) value. The keys were translated into the language of the other collection, the target collection, with a dictionary-based query translation program. The translated queries were run against the target collection and an alignment pair was made if the retrieved documents matched given date and similarity score criteria. The resulting comparable collection was used as a similarity thesaurus to translate queries along with a dictionary-based translator. The combined approaches outperformed translation schemes where dictionary-based translation or corpus translation was used alone.
Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms
Authors: Eppstein David
Published: April 2007

We consider a class of multivariate recurrences frequently arising in the worst-case analysis of Davis-Putnam-style exponential-time backtracking algorithms for NP-hard problems. We describe a technique for proving asymptotic upper bounds on these recurrences, by using a suitable weight function to reduce the problem to that of solving univariate linear recurrences; show how to use quasiconvex programming to determine the weight function yielding the smallest upper bound; and prove that the resulting upper bounds are within a polynomial factor of the true asymptotics of the recurrence. We develop and implement a multiple-gradient descent algorithm for the resulting quasiconvex programs, using a real-number arithmetic package for guaranteed accuracy of the computed worst-case time bounds.
Succinct ordinal trees with level-ancestor queries
Authors: Geary Richard F. , Raman Rajeev , Raman Venkatesh
Published: April 2007

We consider
succinct
or space-efficient representations of trees that efficiently support a variety of navigation operations. We focus on static
ordinal
trees, that is, arbitrary static rooted trees where the children of each node are ordered. The set of operations is essentially the union of the sets of operations supported by previous succinct representations [Jacobson 1989; Munro and Raman 2001; Benoit et al. 1999] to which we add the
level-ancestor
operation.Our representation takes 2
n
+
o
(
n
) bits to represent an
n
-node tree, which is within
o
(
n
) bits of the information-theoretic minimum, and supports all operations in
O
(1) time on the RAM model. These operations also provide a mapping from the
n
nodes of the tree onto the integers {1, …,
n
}. In addition to the existing motivations for studying such data structures, we are motivated by the problem of representing XML documents compactly so that XPath queries can be supported efficiently.
Melding priority queues
Authors: Mendelson Ran , Tarjan Robert E. , Thorup Mikkel , Zwick Uri
Published: April 2007

We show that any priority queue data structure that supports
insert
,
delete
, and
find-min
operations in
pq
(
n
) amortized time, where
n
is an upper bound on the number of elements in the priority queue, can be converted into a priority queue data structure that also supports fast
meld
operations with essentially no increase in the amortized cost of the other operations. More specifically, the new data structure supports
insert
,
meld
and
find-min
operations in
O
(1) amortized time, and
delete
operations in
O
(
pq
(
n
) + α(
n
)) amortized time, where α(
n
) is a functional inverse of the Ackermann function, and where
n
this time is the total number of operations performed on all the priority queues. The construction is very simple. The meldable priority queues are obtained by placing a nonmeldable priority queues at each node of a union-find data structure. We also show that when all keys are integers in the range [1,
N
], we can replace
n
in the bound stated previously by min{
n
,
N
}.Applying this result to the nonmeldable priority queue data structures obtained recently by Thorup [2002b] and by Han and Thorup [2002] we obtain meldable RAM priority queues with
O
(log log
n
) amortized time per operation, or
O
(√log log
n
) expected amortized time per operation, respectively. As a by-product, we obtain improved algorithms for the minimum directed spanning tree problem on graphs with integer edge weights, namely, a deterministic
O
(
m
log log
n
)-time algorithm and a randomized
O
(
m
√log log
n
)-time algorithm. For sparse enough graphs, these bounds improve on the
O
(
m
+
n
log
n
) running time of an algorithm by Gabow et al. [1986] that works for arbitrary edge weights.
Approximate distance oracles for unweighted graphs in expected
O
(
n
2
) time
Authors: Baswana Surender , Sen Sandeep
Published: April 2007

Let
G
= (
V
,
E
) be an undirected graph on
n
vertices, and let δ(
u
,
v
) denote the distance in
G
between two vertices
u
and
v
. Thorup and Zwick showed that for any positive integer
t
, the graph
G
can be preprocessed to build a data structure that can efficiently report
t
-approximate distance between any pair of vertices. That is, for any
u
,
v
∈
V
, the distance reported is at least δ(
u
,
v
) and at most
t
δ(
u
,
v
). The remarkable feature of this data structure is that, for
t
≥3, it occupies subquadratic space, that is, it does not store all-pairs distances explicitly, and still it can answer any
t
-approximate distance query in constant time. They named the data structure “approximate distance oracle” because of this feature. Furthermore, the trade-off between the stretch
t
and the size of the data structure is essentially optimal.In this article, we show that we can actually construct approximate distance oracles in expected
O
(
n
2
) time if the graph is unweighted. One of the new ideas used in the improved algorithm also leads to the first expected linear-time algorithm for computing an optimal size (2, 1)-spanner of an unweighted graph. A (2, 1) spanner of an undirected unweighted graph
G
= (
V
,
E
) is a subgraph (
V
, Ê), Ê ⊆
E
, such that for any two vertices
u
and
v
in the graph, their distance in the subgraph is at most 2δ(
u
,
v
) + 1.
FILTRANE, a Fortran 95 filter-trust-region package for solving nonlinear least-squares and nonlinear feasibility problems
Authors: Gould Nicholas I. M. , Toint Philippe L.
Published: April 2007

FILTRANE, a new Fortran 95 package for finding vectors satisfying general sets of nonlinear equations and/or inequalities, is presented. Several algorithmic variants are discussed and extensively compared on a set of CUTEr test problems, indicating that the default variant is both reliable and efficient. This discussion provides a first experimental study of the parameters inherent in filter algorithms.
Using dense storage to solve small sparse linear systems
Authors: Morandini Marco , Mantegazza Paolo
Published: April 2007

A data structure is used to build a linear solver specialized for relatively small sparse systems. The proposed solver, optimized for run-time performance at the expense of memory footprint, outperforms widely used direct and sparse solvers for systems with between 100 and 3000 equations. A multithreaded version of the solver is shown to give some speedups for problems with medium fill-in, while it does not give any benefit for very sparse problems.
Editorial
Authors: Snodgrass Richard T.
Published: April 2007

This editorial analyzes from a variety of perspectives the controversial issue of single-blind versus double-blind reviewing. In single-blind reviewing, the reviewer is unknown to the author, but the identity of the author is known to the reviewer. Double-blind reviewing is more symmetric: The identity of the author and the reviewer are not revealed to each other. We first examine the significant scholarly literature regarding blind reviewing. We then list six benefits claimed for double-blind reviewing and 21 possible costs. To compare these benefits and costs, we propose a double-blind policy for
TODS
that attempts to minimize the costs while retaining the core benefit of fairness that double-blind reviewing provides, and evaluate that policy against each of the listed benefits and costs. Following that is a general discussion considering several questions: What does this have to do with
TODS
, does bias exist in computer science, and what is the appropriate decision procedure? We explore the “knobs” a policy design can manipulate to fine-tune a double-blind review policy. This editorial ends with a specific decision.
Composition of mappings given by embedded dependencies
Authors: Nash Alan , Bernstein Philip A. , Melnik Sergey
Published: April 2007

Composition of mappings between schemas is essential to support schema evolution, data exchange, data integration, and other data management tasks. In many applications, mappings are given by embedded dependencies. In this article, we study the issues involved in composing such mappings.

Our algorithms and results extend those of Fagin et al. [2004], who studied the composition of mappings given by several kinds of constraints. In particular, they proved that full source-to-target tuple-generating dependencies (tgds) are closed under composition, but embedded source-to-target tgds are not. They introduced a class of second-order constraints,
SO tgds
, that is closed under composition and has desirable properties for data exchange.

We study constraints that need not be source-to-target and we concentrate on obtaining (first-order) embedded dependencies. As part of this study, we also consider full dependencies and second-order constraints that arise from Skolemizing embedded dependencies. For each of the three classes of mappings that we study, we provide: (a) an algorithm that attempts to compute the composition; and (b) sufficient conditions on the input mappings which guarantee that the algorithm will succeed.

In addition, we give several negative results. In particular, we show that full and second-order dependencies that are not limited to be source-to-target are not closed under composition (for the latter, under the additional restriction that no new function symbols are introduced). Furthermore, we show that determining whether the composition can be given by these kinds of dependencies is undecidable.
Optimizing top-k queries for middleware access
Authors: Hwang Seung-won , Chang Kevin Chen-chuan
Published: April 2007

This article studies optimizing top-
k
queries in middlewares. While many assorted algorithms have been proposed, none is generally applicable to a wide range of possible scenarios. Existing algorithms lack both the “generality” to support a wide range of access scenarios and the systematic “adaptivity” to account for runtime specifics. To fulfill this critical lacking, we aim at taking a cost-based optimization approach: By runtime search over a space of algorithms, cost-based optimization is
general
across a wide range of access scenarios, yet
adaptive
to the specific access costs at runtime. While such optimization has been taken for granted for relational queries from early on, it has been clearly lacking for ranked queries. In this article, we thus identify and address the barriers of realizing such a unified framework. As the first barrier, we need to define a “comprehensive” space encompassing all possibly optimal algorithms to search over. As the second barrier and a conflicting goal, such a space should also be “focused” enough to enable efficient search. For SQL queries that are explicitly composed of relational operators, such a space, by definition, consists of schedules of relational operators (or “query plans”). In contrast, top-
k
queries do not have
logical tasks
, such as relational operators. We thus define the logical tasks of top-
k
queries as building blocks to identify a comprehensive and focused space for top-
k
queries. We then develop efficient search schemes over such space for identifying the optimal algorithm. Our study indicates that our framework not only unifies, but also outperforms existing algorithms specifically designed for their scenarios.
Help!!
Authors: Carta David G.
Published: April 2007

Around 1970 I saw a journal article describing a modified Newton iteration for square roots. It involved changing the usual factor of 0.5 in x
n+1
= 0.5 (x
n
+ a/x
n
) to c
n
where c
n
→ 0.5, thereby increasing the asymptotic rate of convergence from e
n+1
= 0.5 e
n
2
to e
n+1
= 0.25 e
n
2
.
Name standardization and value specification for machine dependent constants
Authors: Aird Thomas J. , Battiste Edward L. , Bosten Nancy E. , Darilek Henry L. , Gregory Walton C.
Published: April 2007

There are a number of factors which limit the ease of transfer of mathematical software from one computer sytem to another. For FORTRAN implementations of mathematical and statistical algorithms, a primary portability problem is caused by necessary variation in machine dependent constants. The problem occurs for both decimal and machine-specific representations. Redish and Ward (1971) discuss the problem, and propose a solution. This note extends their ideas to additional constants and computer types.
Cramer's rule on 2-by-2 systems
Authors: Moler Cleve
Published: April 2007

Cramer's rule expresses the solution to a system of simultaneous linear equaations in terms of ratios of determinants. It is widely known as an example of an impractical method for large systems because of the time required to compute the determinants. For 2-by-2 systems this time difficulty disappears and, since the method does not involve a search for pivots, it may appear to have an advantage over Gaussian elimination. In fact, methods based upon 2-by-2 Cramer's rule have been proposed for use on parallel computers. In this note we wish to point out that Cramer's rule is unsatisfactory even for 2-by-2 systems because of roundoff error difficulties.
The XTREM power and performance simulator for the Intel XScale core
Authors: Contreras Gilberto , Martonosi Margaret , Peng Jinzhang , Lueh Guei-Yuan , Ju Roy
Published: April 2007

Managing power concerns in microprocessors has become a pressing research problem across the domains of computer architecture, CAD, and compilers. As a result, several parameterized cycle-level power simulators have been introduced. While these simulators can be quite useful for microarchitectural studies, their generality limits how accurate they can be for any one chip family. Furthermore, their hardware focus means that they do not explicitly enable studying the interaction of different software layers, such as Java applications and their underlying runtime system software. This paper describes and evaluates XTREM, a power-simulation tool tailored for the Intel XScale microarchitecture. In building XTREM, our goals were to develop a microarchitecture simulator that, while still offering size parameterizations for cache and other structures, more accurately reflected a realistic processor pipeline. We present a detailed set of validations based on multimeter power measurements and hardware performance counter sampling. XTREM exhibits an average performance error of only 6.5% and an even smaller average power error: 4%. The paper goes on to present an application study enabled by the simulator. Namely, we use XTREM to produce an energy consumption breakdown for Java CDC and CLDC applications. Our simulator measurements indicate that a large percentage of the total energy consumption (up to 35%) is devoted to the virtual machine's support functions.
Modeling and improving security of a local disk system for write-intensive workloads
Authors: Nijim Mais , Qin Xiao , Xie Tao
Published: April 2007

Since security is of critical importance for modern storage systems, it is imperative to protect stored data from being tampered with or disclosed. Although an increasing number of secure storage systems have been developed, there is no way to dynamically choose security services to meet disk requests' flexible security requirements. Furthermore, existing security techniques for disk systems are not suitable to guarantee desired response times of disk requests. We remedy this situation by proposing an adaptive strategy (referred to as AWARDS) that can judiciously select the most appropriate security service for each write request, while endeavoring to guarantee the desired response times of all disk requests. To prove the efficiency of the proposed approach, we build an analytical model to measure the probability that a disk request is completed before its desired response time. The model also can be used to derive the expected value of disk requests' security levels. Empirical results based on synthetic workloads as well as real I/O-intensive applications show that AWARDS significantly improves overall performance over an existing scheme by up to 358.9% (with an average of 213.4%).
Distributed protocols for ensuring both coverage and connectivity of a wireless sensor network
Authors: Huang Chi-Fu , Tseng Yu-Chee , Wu Hsiao-Lu
Published: April 2007

Wireless sensor networks have attracted a lot of attention recently. Such environments may consist of many inexpensive nodes, each capable of collecting, storing, and processing environmental information, and communicating with neighboring nodes through wireless links. For a sensor network to operate successfully, sensors must maintain both sensing coverage and network connectivity. This issue has been studied in wang et al. [2003] and Zhang and Hou [2004a], both of which reach a similar conclusion that coverage can imply connectivity as long as sensors' communication ranges are no less than twice their sensing ranges. In this article, without relying on this strong assumption, we investigate the issue from a different angle and develop several necessary and sufficient conditions for ensuring coverage and connectivity of a sensor network. Hence, the results significantly generalize the results in Wang et al. [2003] and Zhang and Hou [2004a]. This work is also a significant extension of our earlier work [Huang and Tseng 2003; Huang et al. 2004], which addresses how to determine the level of coverage of a given sensor network but does not consider the network connectivity issue. Our work is the first work allowing an arbitrary relationship between sensing ranges and communication distances of sensor nodes. We develop decentralized solutions for determining, or even adjusting, the levels of coverage and connectivity of a given network. Adjusting levels of coverage and connectivity is necessary when sensors are overly deployed, and we approach this problem by putting sensors to sleep mode and tuning their transmission powers. This results in prolonged network lifetime.
Evaluating the social and cultural implications of the internet
Authors: Brey Philip
Published: April 2007

Since the internet's breakthrough as a mass medium, it has become a topic of discussion because of its implications for society. At one extreme, one finds those who only see great benefits and consider the Internet a tool for freedom, commerce, connectivity, and other societal benefits. At the other extreme, one finds those who lament the harms and disadvantages of the Internet, and who consider it a grave danger to existing social structures and institutions, to culture, morality and human relations. In between one finds the majority, those who recognize both benefits and harms in the Internet as it currently exists and who recognize its usefulness while worrying about some of its negative impacts.