bluuebunny/crossref_metadata_2025 huggingface dataset:
Equipping smart devices with public key signatures
Authors: Ding Xuhua , Mazzocchi Daniele , Tsudik Gene
Published: April 2007

One of the major recent trends in computing has been towards so-called smart devices, such as PDAs, cell phones and sensors. Such devices tend to have a feature in common: limited computational capabilities and equally limited power, as most operate on batteries. This makes them ill-suited for public key signatures. This article explores practical and conceptual implications of using Server-Aided Signatures (SAS) for these devices. SAS is a signature method that relies on partially-trusted servers for generating (normally expensive) public key signatures for regular users. Although the primary goal is to aid small, resource-limited devices in signature generation, SAS also offers fast certificate revocation, signature causality and reliable timestamping. It also has some interesting features such as built-in attack detection for users and DoS resistance for servers. Our experimental results also validate the feasibility of deploying SAS on smart devices.
Provisioning servers in the application tier for e-commerce systems
Authors: Villela Daniel , Pradhan Prashant , Rubenstein Dan
Published: April 2007

Server providers that support e-commerce applications as a service for multiple e-commerce Web sites traditionally use a tiered server architecture. This architecture includes an application tier to process requests for dynamically generated content. How this tier is provisioned can significantly impact a provider's profit margin. In this article we study methods to provision servers in the application serving tier that increase a server provider's profits. First, we examine actual traces of request arrivals to the application tier of an e-commerce site, and show that the arrival process is effectively Poisson. Next, we construct an optimization problem in the context of a set of application servers modeled as
M
/
G
/1/
PS
queueing systems, and derive three simple methods that approximate the allocation that maximizes profits. Simulation results demonstrate that our approximation methods achieve profits that are close to optimal, and are significantly higher than those achieved via simple heuristics.
Representing concerns in source code
Authors: Robillard Martin P. , Murphy Gail C.
Published: April 2007

A software modification task often addresses several
concerns
. A concern is anything a stakeholder may want to consider as a conceptual unit, including features, nonfunctional requirements, and design idioms. In many cases, the source code implementing a concern is not encapsulated in a single programming language module, and is instead scattered and tangled throughout a system. Inadequate separation of concerns increases the difficulty of evolving software in a correct and cost-effective manner. To make it easier to modify concerns that are not well modularized, we propose an approach in which the implementation of concerns is documented in artifacts, called concern graphs. Concern graphs are abstract models that describe which parts of the source code are relevant to different concerns. We present a formal model for concern graphs and the tool support we developed to enable software developers to create and use concern graphs during software evolution tasks. We report on five empirical studies, providing evidence that concern graphs support views and operations that facilitate the task of modifying the code implementing scattered concerns, are cost-effective to create and use, and robust enough to be used with different versions of a software system.
Designing and comparing automated test oracles for GUI-based software applications
Authors: Xie Qing , Memon Atif M.
Published: April 2007

Test designers widely believe that the overall effectiveness and cost of software testing depends largely on the type and number of test cases executed on the software. This article shows that the
test oracle
, a mechanism that determines whether a software is executed correctly for a test case, also significantly impacts the fault detection effectiveness and cost of a test case. Graphical user interfaces (GUIs), which have become ubiquitous for interacting with today's software, have created new challenges for test oracle development. Test designers manually “assert” the expected values of specific properties of certain GUI widgets in each test case; during test execution, these assertions are used as test oracles to determine whether the GUI executed correctly. Since a test case for a GUI is a sequence of events, a test designer must decide: (1) what to assert; and (2) how frequently to check an assertion, for example, after each event in the test case or after the entire test case has completed execution. Variations of these two factors significantly impact the fault-detection ability and cost of a GUI test case. A technique to declaratively specify different types of automated GUI test oracles is described. Six instances of test oracles are developed and compared in an experiment on four software systems. The results show that test oracles do affect the fault detection ability of test cases in different and interesting ways: (1) Test cases significantly lose their fault detection ability when using “weak” test oracles; (2) in many cases, invoking a “thorough” oracle at the end of test case execution yields the best cost-benefit ratio; (3) certain test cases detect faults only if the oracle is invoked during a small “window of opportunity” during test execution; and (4) using thorough and frequently-executing test oracles can compensate for not having long test cases.
Cork
Authors: Jump Maria , McKinley Kathryn S.
Published: April 2007

A
memory leak
in a garbage-collected program occurs when the program inadvertently maintains references to objects that it no longer needs. Memory leaks cause systematic heap growth, degrading performance and resulting in program crashes after perhaps days or weeks of execution. Prior approaches for detecting memory leaks rely on heap differencing or detailed object statistics which store state proportional to the number of objects in the heap. These overheads preclude their use on the same processor for deployed long-running applications.This paper introduces a dynamic heap-summarization technique based on type that accurately identifies leaks, is space efficient (adding less than 1% to the heap), and is time efficient (adding 2.3% on average to total execution time). We implement this approach in
Cork
which utilizes dynamic type information and garbage collection to summarize the live objects in a
type points-from graph
(
TPFG
) whose nodes (types) and edges (references between types) are annotated with volume.
Cork
compares
TPFG
s across multiple collections, identifies growing data structures, and computes a
type slice
for the user. Cork is accurate: it identifies systematic heap growth with no false positives in 4 of 15 benchmarks we tested. Cork's slice report enabled us (non-experts) to quickly eliminate growing data structures in SPECjbb2000 and Elipse, something their developers had not previously done. Cork is accurate, scalable, and efficient enough to consider using online.
Locality approximation using time
Authors: Shen Xipeng , Shaw Jonathan , Meeker Brian , Ding Chen
Published: April 2007

Reuse distance (i.e. LRU stack distance) precisely characterizes program locality and has been a basic tool for memory system research since the 1970s. However, the high cost of measuring has restricted its practical uses in performance debugging, locality analysis and optimizations of long-running applications.In this work, we improve the efficiency by exploring the connection between time and locality. We propose a statistical model that converts cheaply obtained time distance to the more costly reuse distance. Compared to the state-of-the-art technique, this approach reduces measuring time by a factor of 17, and approximates cache line reuses with over 99% accuracy and the cache miss rate with less than 0.4% average error for 12 SPEC 2000 integer and floating-point benchmarks. By exploiting the strong correlations between time and locality, this work makes precise locality as easy to obtain as data access frequency, and opens new opportunities for program optimizations.
First-class nonstandard interpretations by opening closures
Authors: Siskind Jeffrey Mark , Pearlmutter Barak A.
Published: April 2007

We motivate and discuss a novel functional programming construct that allows convenient modular run-time nonstandard interpretation via reflection on closure environments. This map-closure construct encompasses both the ability to examine the contents of a closure environment and to construct a new closure with a modified environment. From the user's perspective, map-closure is a powerful and useful construct that supports such tasks as tracing, security logging, sandboxing, error checking, profiling, code instrumentation and metering, run-time code patching, and resource monitoring. From the implementor's perspective, map-closure is analogous to call/cc. Just as call/cc is a non-referentially-transparent mechanism that reifies the continuations that are only implicit in programs written in direct style, map-closure is a non-referentially-transparent mechanism that reifies the closure environments that are only implicit in higher-order programs. Just as CPS conversion is a non-local but purely syntactic transformation that can eliminate references to call/cc, closure conversion is a non-local but purely syntactic transformation that can eliminate references to map-closure. We show how the combination of map-closure and call/cc can be used to implement set! as a procedure definition and a local macro transformation.
PADS/ML
Authors: Mandelbaum Yitzhak , Fisher Kathleen , Walker David , Fernandez Mary , Gleyzer Artem
Published: April 2007

Massive amounts of useful data are stored and processed in
ad hoc
formats for which common tools like parsers, printers, query engines and format converters are not readily available. In this paper, we explain the design and implementation of
PADS/ML
, a new language and system that facilitates the generation of data processing tools for ad hoc formats. The
PADS/ML
design includes features such as dependent, polymorphic and recursive datatypes, which allow programmers to describe the syntax and semantics of ad hoc data in a concise, easy-to-read notation. The
PADS/ML
implementation compiles these descriptions into
ml
structures and functors that include types for parsed data, functions for parsing and printing, and auxiliary support for user-specified, format-dependent and format-independent tool generation.
Generative unbinding of names
Authors: Pitts Andrew M. , Shinwell Mark R.
Published: April 2007

This paper is concerned with a programming language construct for typed name binding that enforces αequivalence. It proves a new result about what operations on names can co-exist with this construct. The particular form of typed name binding studied is that used by the FreshML family of languages. Its characteristic feature is that a name binding is represented by an abstract (name,value)-pair that may only be deconstructed via the generation of fresh bound names. In FreshML the only observation one can make of names is to test whether or not they are equal. This restricted amount of observation was thought necessary to ensure that there is no observable difference between αequivalent name binders. Yet from an algorithmic point of view it would be desirable to allow other operations and relations on names, such as a total ordering. This paper shows that, contrary to expectations, one may add not just ordering, but almost any relation or numerical function on names without disturbing the fundamental correctness result about this form of typed name binding (that object-level αequivalence precisely corresponds to contextual equivalence at the programming meta-level), so long as one takes the state of dynamically created names into account.
Types, bytes, and separation logic
Authors: Tuch Harvey , Klein Gerwin , Norrish Michael
Published: April 2007

We present a formal model of memory that both captures the low-level features of C's pointers and memory, and that forms the basis for an expressive implementation of separation logic. At the low level, we do not commit common oversimplifications, but correctly deal with C's model of programming language values and the heap. At the level of separation logic, we are still able to reason abstractly and efficiently. We implement this framework in the theorem prover Isabelle/HOL and demonstrate it on two case studies. We show that the divide between detailed and abstract does not impose undue verification overhead, and that simple programs remain easy to verify. We also show that the framework is applicable to real, security- and safety-critical code by formally verifying the memory allocator of the L4 microkernel.
Scrap your boilerplate with XPath-like combinators
Authors: Lämmel Ralf
Published: April 2007

XML programming involves idioms for expressing 'structure shyness' such as the descendant axis of XPath or the default templates of XSLT. We initiate a discussion of the relationships between such XML idioms and generic functional programming, while focusing on the (Haskell-based) 'Scrap your boilerplate' style of generic programming (SYB). This work gives insight into mechanisms for traversal and selection. We compare SYB and XSLT. We approximate XPath in SYB. We make a case for SYB's programmability, when compared to XPath's fixed combinators. We allude to strengthened type checking for SYB traversals so as to reject certain, trivial behaviors.
Lightweight fusion by fixed point promotion
Authors: Ohori Atsushi , Sasano Isao
Published: April 2007

This paper proposes a lightweight fusion method for general recursive function definitions. Compared with existing proposals, our method has several significant practical features: it works for general recursive functions on general algebraic data types; it does not produce extra runtime overhea (except for possible code size increase due to the success of fusion); and it is readily incorporated in standard inlining optimization. This is achieved by extending the ordinary inlining process with a new fusion law that transforms a term of the form
f
o (fix
g
λx.
E
) to a new fixed point term fix
h
λx.
E
′ by promoting the function
f
through the fixed point operator. This is a sound syntactic transformation rule that is not sensitive to the types of
f
and
g
. This property makes our method applicable to wide range of functions including those with multi-parameters in both curried and uncurried forms. Although this method does not guarantee any form of completeness, it fuses typical examples discussed in the literature and others that involve accumulating parameters, either in the tt foldl-like specific forms or in general recursive forms, without any additional machinery. In order to substantiate our claim, we have implemented our method in a compiler. Although it is preliminary, it demonstrates practical feasibility of this method.
JavaScript instrumentation for browser security
Authors: Yu Dachuan , Chander Ajay , Islam Nayeem , Serikov Igor
Published: April 2007

It is well recognized that JavaScript can be exploited to launch browser-based security attacks. We propose to battle such attacks using program instrumentation. Untrusted JavaScript code goes through a rewriting process which identifies relevant operations, modifies questionable behaviors, and prompts the user (a web page viewer) for decisions on how to proceed when appropriate. Our solution is parametric with respect to the security policy-the policy is implemented separately from the rewriting, and the same rewriting process is carried out regardless of which policy is in use. Be-sides providing a rigorous account of the correctness of our solution, we also discuss practical issues including policy management and prototype experiments. A useful by-product of our work is an operational semantics of a core subset of JavaScript, where code embedded in (HTML) documents may generate further document pieces (with new code embedded) at runtime, yielding a form of self-modifying code.
Proving that programs eventually do something good
Authors: Cook Byron , Gotsman Alexey , Podelski Andreas , Rybalchenko Andrey , Vardi Moshe Y.
Published: April 2007

In recent years we have seen great progress made in the area of automatic source-level static analysis tools. However, most of today's program verification tools are limited to properties that guarantee the absence of bad events (
safety properties
). Until now no formal software analysis tool has provided fully automatic support for proving properties that ensure that good events eventually happen (
liveness properties
). In this paper we present such a tool, which handles liveness properties of large systems written in C. Liveness properties are described in an extension of the specification language used in the SDV system. We have used the tool to automatically prove critical liveness properties of Windows device drivers and found several previously unknown liveness bugs.
Program verification as probabilistic inference
Authors: Gulwani Sumit , Jojic Nebojsa
Published: April 2007

In this paper, we propose a new algorithm for proving the validity or invalidity of a pre/postcondition pair for a program. The algorithm is motivated by the success of the algorithms for probabilistic inference developed in the machine learning community for reasoning in graphical models. The validity or invalidity proof consists of providing an invariant at each program point that can be locally verified. The algorithm works by iteratively randomly selecting a program point and updating the current abstract state representation to make it more locally consistent (with respect to the abstractions at the neighboring points). We show that this simple algorithm has some interesting aspects: (a) It brings together the complementary powers of forward and backward analyses; (b) The algorithm has the ability to recover itself from excessive under-approximation or over-approximation that it may make. (Because the algorithm does not distinguish between the forward and backward information, the information could get both under-approximated and over-approximated at any step.) (c) The randomness in the algorithm ensures that the correct choice of updates is eventually made as there is no single deterministic strategy that would provably work for any interesting class of programs. In our experiments we use this algorithm to produce the proof of correctness of a small (but non-trivial) example. In addition, we empirically illustrate several important properties of the algorithm.
Lock allocation
Authors: Emmi Michael , Fischer Jeffrey S. , Jhala Ranjit , Majumdar Rupak
Published: April 2007

We introduce
lock allocation
, an automatic technique that takes a multi-threaded program annotated with
atomic
sections (that must be executed atomically), and infers a lock assignment from global variables to locks and a lock instrumentation that determines where each lock should be acquired and released such that the resulting instrumented program is guaranteed to preserve atomicity and deadlock freedom (provided all shared state is accessed only within atomic sections). Our algorithm works in the presence of pointers and procedures, and sets up the lock allocation problem as a 0-1 ILP which minimizes the conflict cost between atomic sections while simultaneously minimizing the number of locks. We have implemented our algorithm for both C with pthreads and Java, and have applied it to infer locks in 15K lines of AOLserver code. Our automatic allocation produces the same results as hand annotations for most of this code, while solving the optimization instances within a second for most programs.
Modular verification of a non-blocking stack
Authors: Parkinson Matthew , Bornat Richard , O'Hearn Peter
Published: April 2007

This paper contributes to the development of techniques for the modular proof of programs that include concurrent algorithms. We present a proof of a non-blocking concurrent algorithm, which provides a shared stack. The inter-thread interference, which is essential to the algorithm, is confined in the proof and the specification to the modular operations, which perform push and pop on the stack. This is achieved by the mechanisms of separation logic. The effect is that inter-thread interference does not pollute specification or verification of clients of the stack.
On the analysis of interacting pushdown systems
Authors: Kahlon Vineet , Gupta Aarti
Published: April 2007

Pushdown Systems (PDSs) have become an important paradigm for program analysis. Indeed, recent work has shown a deep connection between inter-procedural dataflow analysis for sequential programs and the model checking problem for PDSs. A natural extension of this framework to the concurrent domain hinges on the, somewhat less studied, problem of model checking Interacting Pushdown Systems. In this paper, we therefore focus on the model checking of Interacting Pushdown Systems synchronizing via the standard primitives - locks, rendezvous and broadcasts, for rich classes of temporal properties - both linear and branching time. We formulate new algorithms for model checking interacting PDSs for important fragments of LTL and the Mu-Calculus. Additionally, we also delineate precisely the decidability boundary for each of the standard synchronization primitives.
Specialization of CML message-passing primitives
Authors: Reppy John , Xiao Yingqi
Published: April 2007

Concurrent ML (CML) is a statically-typed higher-order concurrent language that is embedded in Standard ML. Its most notable feature is its support for
first-class synchronous operations
. This mechanism allows programmers to encapsulate complicated communication and synchronization protocols as first-class abstractions, which encourages a modular style of programming where the underlying channels used to communicate with a given thread are hidden behind data and type abstraction.While CML has been in active use for well over a decade, little attention has been paid to optimizing CML programs. In this paper, we present a new program analysis for statically-typed higher-order concurrent languages that enables the compile-time specialization of communication operations. This specialization is particularly important in a multiprocessor or multicore setting, where the synchronization overhead for general-purpose operations are high. Preliminary results from a prototype that we have built demonstrate that specialized channel operations are much faster than the general-purpose operations.Our analysis technique is modular (
i.e.,
, it analyzes and optimizes a single unit of abstraction at a time), which plays to the modular style of many CML programs. The analysis consists of three steps: the first is a type-sensitive control-flow analysis that uses the program's type-abstractions to compute more precise results. The second is the construction of an
extended control-flow graph
using the results of the CFA. The last step is an iterative analysis over the graph that approximates the usage patterns of known channels. Our analysis is designed to detect special patterns of use, such as one-shot channels, fan-in channels, and fan-out channels. We have proven the safety of our analysis and state those results.
A cognitive-conceptual dictionary, and its application in computer analyses of content
Authors: Laffal Julius , MacNaughton Laurence
Published: April 2007

This is a report on an operational technique for the content analysis of free flowing text, employing a conceptual dictionary. The method has been applied in numerous studies, and while it is undergoing constant revision, currently stands as a feasible approach to automatic content analysis. The dictionary is like an interlingual dictionary, translating words into a cognitive-conceptual language by substituting concepts for the words. The cognitiveconceptual language consists of 114 content categories empirically derived by grouping words related in meaning. About 25,000 words of English are so categorized. A text may be analyzed for total content or for selected categories. A recent advance in programming, which we call a "fall back" routine, permits the program to process a virtually unedited text and to match text words with dictionary words even where they differ by suffix. The procedure does this by taking the dictionary word which matches most closely to the text word.
Content-adaptive digital music watermarking based on music structure analysis
Authors: Xu Changsheng , Maddage Namunu C. , Shao Xi , Tian Qi
Published: April 2007

A novel content-adaptive music watermarking technique is proposed in this article. To optimally balance inaudibility and robustness when embedding and extracting watermarks, the embedding scheme is highly related to the music structure and human auditory system (HAS). A note-based segmentation method is proposed and used for music vocal/instrumental boundary detection. A multiple bit hopping and hiding scheme with different embedding parameters is applied to vocal and instrumental frames of the music. The experimental results in inaudibility and robustness are provided to support all novel features in the proposed watermarking scheme.
Virtual videography
Authors: Heck Rachel , Wallick Michael , Gleicher Michael
Published: April 2007

Well-produced videos provide a convenient and effective way to archive lectures. In this article, we offer a new way to create lecture videos that retains many of the advantages of well-composed recordings, without the cost and intrusion of a video production crew. We present an automated system called
Virtual Videography
that employs the art of videography to mimic videographer-produced videos, while unobtrusively recording lectures. The system uses the data recorded by unattended video cameras and microphones to produce a new edited video as an offline postprocess. By producing videos offline, our system can use future information when planning shot sequences and synthesizing new shots. Using simple syntactic cues gathered from the original video and a novel shot planning algorithm, the system makes cinematic decisions without any semantic understanding of the lecture.
Performance statistics of the Fortran IV (H) library for the IBM system/360
Authors: Clark N. A. , Cody W. J. , Hillstrom K. E. , Thieleker E. A.
Published: April 2007

Testing procedures are described and results tabulated for accuracy and timing tests of the basis FORTRAN IV (H) Subroutine Library provided by the manufacturer for the IBM System/360 computer.
Optimally scheduling video-on-demand to minimize delay when sender and receiver bandwidth may differ
Authors: Evans William , Kirkpatrick David
Published: April 2007

We establish tight bounds on the intrinsic cost (either minimizing delay
d
for fixed sender and receiver bandwidths, or minimizing sender bandwidth for fixed delay and receiver bandwidth) of broadcasting a video of length
m
over a channel of bandwidth
S
in such a way that a receiver (with bandwidth
R
), starting at an arbitrary time
s
, can download the video so that it can begin playback at time
s
+
d
.Our bounds are realized by a simple just-in-time protocol that partitions the video into a fixed number of segments, partitions the sender bandwidth into an equivalent number of equal bandwidth subchannels, and broadcasts each segment repeatedly on its own subchannel. The protocol is suitable for the broadcast of compressed video and it can be implemented so that video information is packaged into discrete fixed length packets incurring only a modest overhead (measured in terms of increased delay).Our primary contribution is a lower bound on the required delay that applies to all protocols. This lower bound matches the behavior of our just-in-time protocol in the limit as the number of segments approaches infinity, provided the video compression satisfies some uniform upper bound. For a fixed number of segments, our protocol is optimal within a broad class of protocols, even if the video is compressed arbitrarily.
Computing equilibria for a service provider game with (Im)perfect information
Authors: Beier Rene , Czumaj Artur , Krysta Piotr , Vöcking Berthold
Published: April 2007

We study fundamental algorithmic questions concerning the complexity of market equilibria under perfect and imperfect information by means of a basic microeconomic game. Suppose a provider offers a service to a set of potential customers. Each customer has a particular demand of service and her behavior is determined by a utility function that is nonincreasing in the sum of demands that are served by the provider.Classical game theory assumes
complete information
: the provider has full knowledge of the behavior of all customers. We present a complete characterization of the
complexity of computing optimal pricing strategies
and of
computing best/worst equilibria
in this model. Basically, we show that most of these problems are inapproximable in the worst case but admit an FPAS in the average case. Our average case analysis covers large classes of distributions for customer utilities. We generalize our analysis to robust equilibria in which players change their strategies only when this promises a significant utility improvement.A more realistic model considers providers with
incomplete information
. Following the game theoretic framework of Bayesian games introduced by Harsanyi, the provider is aware of probability distributions describing the behavior of the customers and aims at estimating its expected revenue under best/worst equilibria. Somewhat counterintuitively, we obtain an FPRAS for the equilibria problem in the model with imperfect information although the problem with perfect information is inapproximable under the worst-case measures. In particular, the worst-case complexity of the considered problems increases with the precision of the available knowledge.
Generic quantum Fourier transforms
Authors: Moore Cristopher , Rockmore Daniel , Russell Alexander
Published: April 2007

The
quantum Fourier transform
(QFT) is a principal ingredient appearing in many efficient quantum algorithms. We present a generic framework for the construction of efficient quantum circuits for the QFT by “quantizing” the highly successful
separation of variables
technique for the construction of efficient classical Fourier transforms. Specifically, we apply Bratteli diagrams, Gel'fand-Tsetlin bases, and strong generating sets of small adapted diameter to provide efficient quantum circuits for the QFT over a wide variety of finite Abelian and non-Abelian groups, including all families of groups for which efficient QFTs are currently known and many new families as well. Moreover, our method provides the first subexponential-size quantum circuits for the QFT over the linear groups GL

k

(
q
), SL

k

(
q
), and the finite groups of Lie type, for any fixed prime power
q
.
Middleware for streaming 3D progressive meshes over lossy networks
Authors: Li H. , Li M. , Prabhakaran B.
Published: April 2007

Streaming 3D graphics have been widely used in multimedia applications such as online gaming and virtual reality. However, a gap exists between the zero-loss-tolerance of the existing compression schemes and the lossy network transmissions. In this article, we propose a generic 3D middleware between the 3D application layer and the transport layer for the transmission of triangle-based progressively compressed 3D models. Significant features of the proposed middleware include. 1) handling 3D compressed data streams from multiple progressive compression techniques. 2) considering end user hardware capabilities for effectively saving the data size for network delivery. 3) a minimum cost dynamic reliable set selector to choose the transport protocol for each sublayer based on the real-time network traffic. Extensive simulations with TCP/UDP and SCTP show that the proposed 3D middleware can achieve the dual objectives of maintaining low transmission delay and small distortion, and thus supporting high quality 3D streaming with high flexibility.
A graphics architecture for high-end interactive television terminals
Authors: Cesar Pablo , Vuorimaa Petri , Vierinen Juha
Published: April 2007

This article presents a graphics software architecture for next-generation digital television receivers. We propose that such receivers should include a standardised Java-based procedural environment capable of rendering 2D/3D graphics and video, and a declarative environment supporting W3C recommendations such as SMIL and XForms. We also introduce a graphics architecture model that meets such requirements. As a proof-of-concept, a prototype implementation of the model is presented. This implementation enhances television content by allowing the user to play 3D graphics games, to run Java applications, and to browse XML-based documents while meeting current hardware restrictions.
The complexity of homomorphism and constraint satisfaction problems seen from the other side
Authors: Grohe Martin
Published: April 2007

We give a complexity theoretic classification of homomorphism problems for graphs and, more generally, relational structures obtained by restricting the left hand side structure in a homomorphism. For every class C of structures, let HOM(C,−) be the problem of deciding whether a given structure A ∈C has a homomorphism to a given (arbitrary) structure ß. We prove that, under some complexity theoretic assumption from parameterized complexity theory, HOM(C,−) is in polynomial time if and only if C has bounded tree width modulo homomorphic equivalence.

Translated into the language of constraint satisfaction problems, our result yields a characterization of the tractable structural restrictions of constraint satisfaction problems. Translated into the language of database theory, it implies a characterization of the tractable instances of the evaluation problem for conjunctive queries over relational databases.
Polymorphic higher-order recursive path orderings
Authors: Jouannaud Jean-Pierre , Rubio Albert
Published: April 2007

This article extends the termination proof techniques based on reduction orderings to a higher-order setting, by defining a family of recursive path orderings for terms of a typed lambda-calculus generated by a signature of polymorphic higher-order function symbols. These relations can be generated from two given well-founded orderings, on the function symbols and on the type constructors. The obtained orderings on terms are well founded, monotonic, stable under substitution and include β-reductions. They can be used to prove the strong normalization property of higher-order calculi in which constants can be defined by higher-order rewrite rules using first-order pattern matching. For example, the polymorphic version of Gödel's recursor for the natural numbers is easily oriented. And indeed, our ordering is polymorphic, in the sense that a single comparison allows to prove the termination property of all monomorphic instances of a polymorphic rewrite rule. Many nontrivial examples are given that exemplify the expressive power of these orderings. All have been checked by our implementation.

This article is an extended and improved version of Jouannaud and Rubio [1999]. Polymorphic algebras have been made more expressive than in our previous framework. The intuitive notion of a polymorphic higher-order ordering has now been made precise. The higher-order recursive path ordering itself has been made much more powerful by replacing the congruence on types used there by an ordering on types satisfying some abstract properties. Besides, using a restriction of Dershowitz's recursive path ordering for comparing types, we can integrate both orderings into a single one operating uniformly on both terms and types.
Algorithm 865
Authors: Gustavson Fred G. , Reid John K. , Waśniewski Jerzy
Published: April 2007

We present subroutines for the Cholesky factorization of a positive-definite symmetric matrix and for solving corresponding sets of linear equations. They exploit cache memory by using the block hybrid format proposed by the authors in a companion article. The matrix is packed into
n
(
n
+ 1)/2 real variables, and the speed is usually better than that of the LAPACK algorithm that uses full storage (
n
2
variables). Included are subroutines for rearranging a matrix whose upper or lower-triangular part is packed by columns to this format and for the inverse rearrangement. Also included is a kernel subroutine that is used for the Cholesky factorization of the diagonal blocks since it is suitable for any positive-definite symmetric matrix that is small enough to be held in cache. We provide a comprehensive test program and simple example programs.
Efficient estimation of joint queries from multiple OLAP databases
Authors: Pourabbas Elaheh , Shoshani Arie
Published: April 2007

Given an OLAP query expressed over multiple source OLAP databases, we study the problem of estimating the resulting OLAP target database. The problem arises when it is not possible to derive the result from a single database. The method we use is linear indirect estimation, commonly used for statistical estimation. We examine two obvious computational methods for computing such a target database, called the
full cross-product
(F) and
preaggregation
(P) methods. We study the accuracy and computational cost of these methods. While the F method provides a more accurate estimate, it is more expensive computationally than P. Our contribution is in proposing a third, new method, called the
partial preaggregation
method (PP), which is significantly less expensive than F, but just as accurate. We prove formally that the PP method yields the same results as the F method, and provide analytical and experimental results on the accuracy and computational benefits of the PP method.
Forward node-selecting queries over trees
Authors: Olteanu Dan
Published: April 2007

Node-selecting queries over trees lie at the core of several important XML languages for the web, such as the node-selection language XPath, the query language XQuery, and the transformation language XSLT. The main syntactic constructs of such queries are the backward predicates, for example, ancestor and preceding, and the forward predicates, for example, descendant and following. Forward predicates are included in the depth-first, left-to-right preorder relation associated with the input tree, whereas backward predicates are included in the inverse of this preorder relation.

This work is devoted to an expressiveness study of node-selecting queries with proven theoretical and practical applicability, especially in the field of query evaluation against XML streams. The main question it answers positively is whether, for each input query with forward and backward predicates, there exists an equivalent forward-only output query. This question is then positively answered for input and output queries of varying structural complexity, using LOGLIN and PSPACE reductions.

Various existing applications based on the results of this work are reported, including query optimization and streamed evaluation.
Mining constraint violations
Authors: Ceri Stefano , Giunta Francesco Di , Lanzi Pier Luca
Published: April 2007

In this article, we introduce
pesudoconstraints
, a novel data mining pattern aimed at identifying rare events in databases. At first, we formally define pesudoconstraints using a probabilistic model and provide a statistical test to identify pesudoconstraints in a database. Then, we focus on a specific class of pesudoconstraints, named
cycle pesudoconstraints
, which often occur in databases. We define cycle pesudoconstraints in the context of the ER model and present an automatic method for detecting cycle pesudoconstraints from a relational database. Finally, we present an experiment to show cycle pesudoconstraints “at work” on real data.
The Molen compiler for reconfigurable processors
Authors: Panainte Elena Moscu , Bertels Koen , Vassiliadis Stamatis
Published: April 2007

In this paper, we describe the compiler developed to target the Molen reconfigurable processor and programming paradigm. The compiler automatically generates optimized binary code for C applications, based on pragma annotation of the code executed on the reconfigurable hardware. For the IBM PowerPC 405 processor included in the Virtex II Pro platform FPGA, we implemented code generation, register, and stack frame allocation following the PowerPC EABI (embedded application binary interface). The PowerPC backend has been extended to generate the appropriate instructions for the reconfigurable hardware and data transfer, taking into account the information of the specific hardware implementations and system. Starting with an annotated C application, a complete design flow has been integrated to generate the executable bitstream for the reconfigurable processor. The flexible design of the proposed infrastructure allows to consider the special features of the reconfigurable architectures. In order to hide the reconfiguration latencies, we implemented an instruction-scheduling algorithm for the dynamic hardware configuration instructions. The algorithm schedules, in advance, the hardware configuration instructions, taking into account the conflicts for the reconfigurable hardware resources (FPGA area) between the hardware operations. To verify the Molen compiler, we used the multimedia video frame M-JPEG encoder of which the extended discrete cosine transform (DCT*) function was mapped on the FPGA. We obtained an overall speedup of 2.5 (about 84% efficiency over the maximal theoretical speedup of 2.96). The performance efficiency is achieved using automatically generated nonoptimized DCT* hardware implementation. The instruction-scheduling algorithm has been tested for DCT, quantization, and VLC operations. Based on simulation results, we determine that, while a simple scheduling produces a significant performance decrease, our proposed scheduling contributes for up to 16x M-JPEG encoder speedup.
An approach to virtual allocation in storage systems
Authors: Kang Sukwoo , Reddy A. L. Narasimha
Published: April 2007

This article presents
virtual allocation
, a scheme for flexible storage allocation. Virtual allocation separates storage allocation from the file system. It employs an allocate-on-write strategy which lets applications fit into the actual usage of storage space, without regard to the configured file system size. This improves flexibility by allowing storage space to be shared across different file systems. This article presents the design of virtual allocation and its evaluation through benchmarks. To illustrate our approach, we implemented a prototype system on PCs running Linux. We present the results from the prototype implementation and its evaluation.
Improving duplicate elimination in storage systems
Authors: Bobbarjung Deepak R. , Jagannathan Suresh , Dubnicki Cezary
Published: April 2007

Minimizing the amount of data that must be stored and managed is a key goal for any storage architecture that purports to be scalable. One way to achieve this goal is to avoid maintaining duplicate copies of the same data. Eliminating redundant data at the source by not writing data which has already been stored not only reduces storage overheads, but can also improve bandwidth utilization. For these reasons, in the face of today's exponentially growing data volumes, redundant data elimination techniques have assumed critical significance in the design of modern storage systems.Intelligent object partitioning techniques identify data that is
new
when objects are updated, and transfer only these chunks to a storage server. In this article, we propose a new object partitioning technique, called
fingerdiff
, that improves upon existing schemes in several important respects. Most notably,
fingerdiff
dynamically chooses a partitioning strategy for a data object based on its similarities with previously stored objects in order to improve storage and bandwidth utilization. We present a detailed evaluation of
fingerdiff
, and other existing object partitioning schemes, using a set of real-world workloads. We show that for these workloads, the duplicate elimination strategies employed by
fingerdiff
improve storage utilization on average by 25%, and bandwidth utilization on average by 40% over comparable techniques.
The Design of efficient initialization and crash recovery for log-based file systems over flash memory
Authors: Wu Chin-Hsien , Kuo Tei-Wei , Chang Li-Pin
Published: April 2007

While flash memory has been widely adopted for storage systems for various embedded systems, issues of performance and reliability have started receiving growing attention in recent years. How to provide efficient roll back and quick mounting for flash-memory file systems has become an important research topic in recent years, in addition to the work on effective garbage collection and superb runtime performance. Such an observation motivates our work on the investigation of efficient initialization and crash recovery of flash-memory file systems based on log structures. A methodology is proposed for the acceleration of mounting and crash recovery for log-based file systems. A system prototype based on a well-known flash-memory file system, YAFFS, was implemented with performance evaluation. Experimental results show that the proposed methodology can reduce mounting time significantly, regardless of whether the file system is properly unmounted.
Tracking cyberstalkers
Authors: Burmester Mike , Henry Peter , Kermes Leo S.
Published: April 2007

Stalking is a pattern of behavior over time in which a stalker seeks to gain access to, or control over, an unwilling victim. Such actions range from the benign to the malicious and may cause emotional distress or harm to the victim. With the widespread adoption of new technologies, new forums of Internet-mediated discourse now exist which offer stalkers unprecedented scope to locate and exert influence over victims. Cyberstalking, the convergence of stalking and cyberspace, has created new challenges for the prevention, detection, and prosecution of this new phenomenon as the traditional methods of detection by witnesses and enforcement through physical restraining orders often are inadequate.In this paper we suggest a cryptographic approach for tracking cyberstalkers. We first define the threat model in terms of the profile of a cyberstalker, as well as legal and law enforcement constraints. We then describe a monitoring system that addresses the basic admissibility requirements of our threat model, by capturing and verifying circumstantial evidence for use in cyberstalking investigations.
Analysis of peer-to-peer file dissemination
Authors: Mundinger Jochen , Weber Richard , Weiss Gideon
Published: April 2007

In recent years, overlay networks have proven a popular way of disseminating potentially large files from a single server
S
to a potentially large group of
N
end users via the Internet. A number of algorithms and protocols have been suggested, implemented and studied. In particular, much attention has been given to peer-to-peer (P2P) systems such as BitTorrent [5], Slurpie [20], SplitStream [4], Bullet [11] and Avalanche [6]. The key idea is that the file is divided into
M
parts of equal size and that a given user may download any one of these - or, for Avalanche, linear combinations of these - either from the server or from a peer who has previously downloaded it.
Comparing FB and PS scheduling policies
Authors: Brown Patrick
Published: April 2007

In this paper we obtain new results concerning the expected response time of the foreground-background (FB) scheduling discipline and its comparison with processor sharing (PS). Some results previously derived for job sizes with finite second moment or bounded sizes, are extended to infinite second moments. New bounds and asymptotic results are also derived. We show that for job sizes with infinite second moment large jobs may benefit from the FB scheduling discipline although this discipline favors short jobs. For certain distributions all jobs sizes may even benefit from FB with respect to PS showing that the performance benefits obtained by some job sizes need not be obtained at the expense of others.