bluuebunny/crossref_metadata_2025 huggingface dataset:
Extended wavelets for multiple measures
Authors: Deligiannakis Antonios , Garofalakis Minos , Roussopoulos Nick
Published: September 2007

Several studies have demonstrated the effectiveness of the Haar wavelet decomposition as a tool for reducing large amounts of data down to compact
wavelet synopses
that can be used to obtain fast, accurate approximate answers to user queries. Although originally designed for minimizing the overall mean-squared (i.e.,
L
2
-norm) error in the data approximation, recently proposed methods also enable the use of Haar wavelets in minimizing other error metrics, such as the relative error in data value reconstruction, which is arguably the most important for approximate query answers. Relatively little attention, however, has been paid to the problem of using wavelet synopses as an approximate query answering tool over complex tabular datasets containing
multiple measures
, such as those typically found in real-life OLAP applications. Existing decomposition approaches will either operate on each measure individually, or treat all measures as a vector of values and process them simultaneously. As we demonstrate in this article, these existing
individual
or
combined
storage approaches for the wavelet coefficients of different measures can easily lead to suboptimal storage utilization, resulting in drastically reduced accuracy for approximate query answers. To address this problem, in this work, we introduce the notion of an
extended
wavelet coefficient as a flexible, efficient storage method for wavelet coefficients over multimeasure data. We also propose novel algorithms for constructing effective (optimal or near-optimal) extended wavelet-coefficient synopses under a given storage constraint, for both sum-squared error and relative-error norms. Experimental results with both real-life and synthetic datasets validate our approach, demonstrating that our techniques consistently obtain significant gains in approximation accuracy compared to existing solutions.
Pseudo-random number generation for sketch-based estimations
Authors: Rusu Florin , Dobra Alin
Published: September 2007

The exact computation of aggregate queries, like the size of join of two relations, usually requires large amounts of memory (constrained in data-streaming) or communication (constrained in distributed computation) and large processing times. In this situation, approximation techniques with provable guarantees, like sketches, are one possible solution. The performance of sketches depends crucially on the ability to generate particular pseudo-random numbers. In this article we investigate both theoretically and empirically the problem of generating
k
-wise independent pseudo-random numbers and, in particular, that of generating 3- and 4-wise independent pseudo-random numbers that are fast range-summable (i.e., they can be summed in sublinear time). Our specific contributions are: (a) we provide a thorough comparison of the various pseudo-random number generating schemes; (b) we study both theoretically and empirically the fast range-summation property of 3- and 4-wise independent generating schemes; (c) we provide algorithms for the fast range-summation of two 3-wise independent schemes, BCH and extended Hamming; and (d) we show convincing theoretical and empirical evidence that the extended Hamming scheme performs as well as any 4-wise independent scheme for estimating the size of join of two relations using AMS sketches, even though it is only 3-wise independent. We use this scheme to generate estimators that significantly outperform state-of-the-art solutions for two problems, namely,
size of spatial joins
and
selectivity estimation
.
Estimating the selectivity of approximate string queries
Authors: Mazeika Arturas , Böhlen Michael H. , Koudas Nick , Srivastava Divesh
Published: September 2007

Approximate queries on string data are important due to the prevalence of such data in databases and various conventions and errors in string data. We present the VSol estimator, a novel technique for estimating the selectivity of approximate string queries. The VSol estimator is based on
inverse strings
and makes the performance of the selectivity estimator independent of the number of strings. To get inverse strings we decompose all database strings into overlapping substrings of length q (q-grams) and then associate each q-gram with its inverse string: the IDs of all strings that contain the q-gram. We use signatures to compress inverse strings, and clustering to group similar signatures.

We study our technique analytically and experimentally. The space complexity of our estimator only depends on the number of neighborhoods in the database and the desired estimation error. The time to estimate the selectivity is
independent
of the number of database strings and
linear
with respect to the length of query string. We give a detailed empirical performance evaluation of our solution for synthetic and real-world datasets. We show that VSol is effective for large skewed databases of short strings.
Natural shadow matting
Authors: Wu Tai-Pang , Tang Chi-Keung , Brown Michael S. , Shum Heung-Yeung
Published: September 2007

This article addresses the problem of
natural shadow matting
, the removal or extraction of natural shadows from a single image. Because textures are maintained in the shadowless image after the extraction process, our approach produces some of the best results to date among shadow removal techniques. Using the image formation equation typical of computer vision, we advocate a new model for shadow formation where shadow effect is understood as light attenuation instead of a mixture of two colors governed by the conventional matting equation. This leads to a new shadow equation with fewer unknowns to solve, where a three-channel shadow matte and a shadowless image are considered in our optimization. Our problem is formulated as one of energy minimization guided by user-supplied hints in the form of a quadmap which can be specified easily by the user. This formulation allows for robust shadow matte extraction while maintaining texture in the shadowed region by considering color transfer, texture gradient, and shadow smoothness. We demonstrate the usefulness of our approach in shadow removal, image matting, and compositing.
Lighting with paint
Authors: Pellacini Fabio , Battaglia Frank , Morley R. Keith , Finkelstein Adam
Published: September 2007

Lighting is a fundamental aspect of computer cinematography that involves the placement and configuration of lights to establish mood and enhance storytelling. This process is labor intensive as artists repeatedly adjust the parameters of a large set of complex lights to achieve a desired effect. Typical lighting controls affect the final image indirectly, requiring a large number of trials to obtain a suitable result.

We present an interactive system wherein an artist paints desired lighting effects directly into the scene, and the computer solves for parameters that achieve the desired look. The artist can paint color, light shape, shadows, highlights, and reflections using a suite of tools designed for painting light. Our system matches these effects using a nonlinear optimizer made robust by a combination of initial estimates, system design, and user-guided optimization. In contrast, previous work on painting light has not permitted the lights to move, allowing for linear optimization but preventing its use in computer cinematography.

To demonstrate our approach we lit several scenes, mainly using a direct illumination renderer designed for computer animation, but also including two other rendering styles. We show that painting interfaces can quickly produce high quality lighting setups, easing the lighting artist's workflow.
Adaptive sampling of reflectance fields
Authors: Fuchs Martin , Blanz Volker , Lensch Hendrik P.A. , Seidel Hans-Peter
Published: September 2007

Image-based relighting achieves high quality in rendering, but it requires a large number of measurements of the reflectance field. This article discusses sampling techniques that improve on the trade-offs between measurement effort and reconstruction quality.

Specifically, we (i) demonstrate that sampling with point lights and from a sparse set of incoming light directions creates artifacts which can be reduced significantly by employing extended light sources for sampling, (ii) propose a sampling algorithm which incrementally chooses light directions adapted to the properties of the reflectance field being measured, thus capturing significant features faster than fixed-pattern sampling, and (iii) combine reflectance fields from two different light domain resolutions.

We present an automated measurement setup for well-defined angular distributions of the incident, indirect illumination. It is based on programmable spotlights with controlled aperture that illuminate the walls around the scene.
Velocity-based shock propagation for multibody dynamics animation
Authors: Erleben Kenny
Published: September 2007

Multibody dynamics are used in interactive and real-time applications, ranging from computer games to virtual prototyping, and engineering. All these areas strive towards faster and larger scale simulations. Particularly challenging are large-scale simulations with highly organized and structured stacking. We present a stable, robust, and versatile method for multibody dynamics simulation. Novel contributions include a new, explicit, fixed time-stepping scheme for velocity-based complementarity formulations using shock propagation with a simple reliable implementation strategy for an iterative complementarity problem solver specifically optimized for multibody dynamics.
Model checking the Java metalocking algorithm
Authors: Basu Samik , Smolka Scott A.
Published: September 2007

We report on our efforts to use the XMC model checker to model and verify the Java metalocking algorithm. XMC [Ramakrishna et al. 1997] is a versatile and efficient model checker for systems specified in XL, a highly expressive value-passing language. Metalocking [Agesen et al. 1999] is a highly-optimized technique for ensuring mutually exclusive access by threads to object monitor queues and, therefore; plays an essential role in allowing Java to offer concurrent access to objects. Metalocking can be viewed as a two-tiered scheme. At the upper level, the
metalock
level, a thread waits until it can enqueue itself on an object's monitor queue in a mutually exclusive manner. At the lower level, the
monitor-lock
level, enqueued threads race to obtain exclusive access to the object. Our abstract XL specification of the metalocking algorithm is fully parameterized, both on the number of threads
M
, and the number of objects
N
. It also captures a sophisticated optimization of the basic metalocking algorithm known as
extra-fast
locking and unlocking of uncontended objects. Using XMC, we show that for a variety of values of
M
and
N
, the algorithm indeed provides mutual exclusion and freedom from deadlock and lockout at the metalock level. We also show that, while the monitor-lock level of the protocol preserves mutual exclusion and deadlock-freedom, it is not lockout-free because the protocol's designers chose to give equal preference to awaiting threads and newly arrived threads.
Distributed simulation of agent-based systems with HLA
Authors: Lees Michael , Logan Brian , Theodoropoulos Georgios
Published: September 2007

In this article we describe HLA_AGENT, a tool for the distributed simulation of agent-based systems, which integrates the SIM_AGENT agent toolkit and the High Level Architecture (HLA) simulator interoperability framework. HLA_AGENT offers enhanced simulation scalability and allows interoperation with other HLA-compliant simulators, promoting simulation reuse. Using a simple Tileworld example, we show how HLA_AGENT can be used to flexibly distribute a SIM_AGENT simulation so as to exploit available computing resources. We present experimental results that illustrate the performance of HLA_AGENT on a Linux cluster running a distributed version of Tileworld and compare this with the original nondistributed SIM_AGENT version.
Simulation output analysis using integrated paths
Authors: Calvin James M.
Published: September 2007

This article considers the steady-state simulation output analysis problem for a process that satisfies a functional central limit theorem. We construct an estimator for the time-average variance constant that is based on iterated integrations of the sample path. When the observations are batched, the method generalizes the method of batch means. One advantage of the method is that it can be used without batching the observations; that is, it can allow for the process variance to be estimated at any time as the simulation runs without waiting for a fixed time horizon to complete. When used in conjunction with batching, the method can improve efficiency (the reciprocal of work times mean-squared error) compared with the standard method of batch means. In numerical experiments, efficiency improvement ranged from a factor of 1.5 (for the waiting time sequence in an M/M/1 queueing system with a single integrated path) up to a factor of 14 (for an autoregressive process and 19 integrated paths).
PELCR
Authors: Pedicini Marco , Quaglia Francesco
Published: September 2007

In this article we present the implementation of an environment supporting Lévy's
optimal reduction
for the λ-calculus on parallel (or distributed) computing systems. In a similar approach to Lamping's, we base our work on a graph reduction technique, known as
directed virtual reduction
, which is actually a restriction of Danos-Regnier virtual reduction.

The environment, which we refer to as PELCR (parallel environment for optimal lambda-calculus reduction), relies on a strategy for directed virtual reduction, namely
half combustion
. While developing PELCR we adopted both a message aggregation technique, allowing reduction of the communication overhead, and a fair policy for distributing dynamically originated load among processors.

We also present an experimental study demonstrating the ability of PELCR to definitely exploit the parallelism intrinsic to λ-terms while performing the reduction. We show how PELCR allows achieving up to 70--80% of the ideal speedup on last generation multiprocessor computing systems. As a last note, the software modules have been developed with the C language and using a standard interface for message passing, that is, MPI, thus making PELCR itself a highly portable software package.
Semantical characterizations and complexity of equivalences in answer set programming
Authors: Eiter Thomas , Fink Michael , Woltran Stefan
Published: September 2007

In recent research on nonmonotonic logic programming, repeatedly strong equivalence of logic programs
P
and
Q
has been considered, which holds if the programs
P
∪
R
and
Q
∪
R
have the same answer sets for any other program
R
. This property strengthens the equivalence of
P
and
Q
with respect to answer sets (which is the particular case for
R
=∅), and has its applications in program optimization, verification, and modular logic programming. In this article, we consider more liberal notions of strong equivalence, in which the actual form of
R
may be syntactically restricted. On the one hand, we consider uniform equivalence where
R
is a set of facts, rather than a set of rules. This notion, which is well-known in the area of deductive databases, is particularly useful for assessing whether programs
P
and
Q
are equivalent as components of a logic program which is modularly structured. On the other hand, we consider relativized notions of equivalence where
R
ranges over rules over a fixed alphabet, and thus generalize our results to relativized notions of strong and uniform equivalence. For all these notions, we consider disjunctive logic programs in the propositional (ground) case as well as some restricted classes, providing semantical characterizations and analyzing the computational complexity. Our results, which naturally extend to answer set semantics for programs with strong negation, complement the results on strong equivalence of logic programs and pave the way for optimizations in answer set solvers as a tool for input-based problem solving.
Online supervised spam filter evaluation
Authors: Cormack Gordon V. , Lynam Thomas R.
Published: September 2007

Eleven variants of six widely used open-source spam filters are tested on a chronological sequence of 49086 e-mail messages received by an individual from August 2003 through March 2004. Our approach differs from those previously reported in that the test set is large, comprises uncensored raw messages, and is presented to each filter sequentially with incremental feedback. Misclassification rates and Receiver Operating Characteristic Curve measurements are reported, with statistical confidence intervals. Quantitative results indicate that content-based filters can eliminate 98% of spam while incurring 0.1% legitimate email loss. Qualitative results indicate that the risk of loss depends on the nature of the message, and that messages likely to be lost may be those that are less critical. More generally, our methodology has been encapsulated in a free software toolkit, which may used to conduct similar experiments.
Temporal profiles of queries
Authors: Jones Rosie , Diaz Fernando
Published: September 2007

Documents with timestamps, such as email and news, can be placed along a timeline. The timeline for a set of documents returned in response to a query gives an indication of how documents relevant to that query are distributed in time. Examining the timeline of a query result set allows us to characterize both how temporally dependent the topic is, as well as how relevant the results are likely to be. We outline characteristic patterns in query result set timelines, and show experimentally that we can automatically classify documents into these classes. We also show that properties of the query result set timeline can help predict the mean average precision of a query. These results show that meta-features associated with a query can be combined with text retrieval techniques to improve our understanding and treatment of text search on documents with timestamps.
Online diagnosis of hard faults in microprocessors
Authors: Bower Fred A. , Sorin Daniel J. , Ozev Sule
Published: September 2007

We develop a microprocessor design that tolerates hard faults, including fabrication defects and in-field faults, by leveraging existing microprocessor redundancy. To do this, we must: detect and correct errors, diagnose hard faults at the field deconfigurable unit (FDU) granularity, and deconfigure FDUs with hard faults. In our reliable microprocessor design, we use DIVA dynamic verification to detect and correct errors. Our new scheme for diagnosing hard faults tracks instructions' core structure occupancy from decode until commit. If a DIVA checker detects an error in an instruction, it increments a small saturating error counter for every FDU used by that instruction, including that DIVA checker. A hard fault in an FDU quickly leads to an above-threshold error counter for that FDU and thus diagnoses the fault. For deconfiguration, we use previously developed schemes for functional units and buffers and present a scheme for deconfiguring DIVA checkers. Experimental results show that our reliable microprocessor quickly and accurately diagnoses each hard fault that is injected and continues to function, albeit with somewhat degraded performance.
Code reordering on limited branch offset
Authors: Chen Yu , Zhang Fuxin
Published: September 2007

Since the 1980's code reordering has gained popularity as an important way to improve the spatial locality of programs. While the effect of the processor's microarchitecture and memory hierarchy on this optimization technique has been investigated, little research has focused on the impact of the instruction set. In this paper, we analyze the effect of limited branch offset of the MIPS-like instruction set [Hwu et al. 2004, 2005] on code reordering, explore two simple methods to handle the exceeded branches, and propose the bidirectional code layout (BCL) algorithm to reduce the number of branches exceeding the offset limit. The BCL algorithm sorts the chains according to the position of related chains, avoids cache conflict misses deliberately and lays out the code bidirectionally. It strikes a balance among the distance of related blocks, the instruction cache miss rate, the memory size required, and the control flow transfer. Experimental results show that BCL can effectively reduce exceeded branches by 50.1%, on average, with up to 100% for some programs. Except for some programs with little spatial locality, the BCL algorithm can achieve the performance, as the case with no branch offset limitation.
Inter-cluster communication in VLIW architectures
Authors: Terechko A. S. , Corporaal H.
Published: September 2007

The traditional VLIW (very long instruction word) architecture with a single register file does not scale up well to address growing performance demands on embedded media processors. However, splitting a VLIW processor in smaller clusters, which are comprised of function units fully connected to local register files, can significantly improve VLSI implementation characteristics of the processor, such as speed, energy consumption, and area. In our paper we reveal that achieving the best characteristics of a clustered VLIW requires a thorough selection of an
Inter-cluster Communication (ICC) model
, which is the way clustering is exposed in the Instruction Set Architecture. For our study we, first, define a taxonomy of ICC models including
copy operations
,
dedicated issue slots
,
extended operands
,
extended results
, and
multicast
. Evaluation of the execution time of the models requires both the dynamic cycle count and clock period. We developed an advanced instruction scheduler for all the five ICC models in order to quantify the dynamic cycle counts of our multimedia C benchmarks. To assess the clock period of the ICC models we designed and laid out VLIW datapaths using the RTL hardware descriptions derived from a deeply pipelined commercial TriMedia processor. In contrast to prior art, our research shows that fully distributed register file architectures (with eight clusters in our study) often underperform compared to moderately clustered machines with two or four clusters because of explosion of the cycle count overhead in the former. Among the evaluated ICC models, performance of the
copy operation
model, popular both in academia and industry, is severely limited by the copy operations hampering scheduling of regular operations in high ILP (instruction-level parallelism) code. The
dedicated issue slots
model combats this limitation by dedicating extra VLIW issue slots purely for ICC, reaching the highest 1.74 execution time speedup relative to the unicluster. Furthermore, our VLSI experiments show that the lowest area and energy consumption of 42 and 57% relative to the unicluster, respectively, are achieved by the
extended operands
model, which, nevertheless, provides higher performance than the
copy operation
model.
SSA-based mobile code
Authors: Amme Wolfram , Ronne Jeffery von , Franz Michael
Published: September 2007

Although one might expect transportation formats based on static single-assignment form (SSA) to yield faster just-in-time compilation times than those based on stack-based virtual machines, this claim has not previously been validated, in practice. We attempt to quantify the effect of using an SSA-based mobile code representation by integrating support for a verifiable SSA-based IR into Jikes RVM. Performance results, measured with various optimizations and on both the IA32 and PowerPC, show improvements in both compilation time and code quality.
A block bigram prediction model for statistical machine translation
Authors: Tillmann Christoph , Zhang Tong
Published: September 2007

In this article, we present a novel training method for a localized phrase-based prediction model for statistical machine translation (SMT). The model predicts block neighbors to carry out a phrase-based translation that explicitly handles local phrase reordering. We use a maximum likelihood criterion to train a log-linear block bigram model which uses real-valued features (e.g., a language model score) as well as binary features based on the block identities themselves (e.g., block bigram features). The model training relies on an efficient enumeration of local block neighbors in parallel training data. A novel stochastic gradient descent (SGD) training algorithm is presented that can easily handle millions of features. Moreover, when viewing SMT as a block generation process, it becomes quite similar to sequential natural language annotation problems such as part-of-speech tagging, phrase chunking, or shallow parsing. Our novel approach is successfully tested on a standard Arabic-English translation task using two different phrase reordering models: a block orientation model and a phrase-distortion model.
Promoting extension and reuse in a spoken dialog manager
Authors: Hanna Philip , O'neill Ian , Wootton Craig , Mctear Michael
Published: September 2007

This article describes how an object-oriented approach can be applied to the architectural design of a spoken language dialog system with the aim of facilitating the modification, extension, and reuse of discourse-related expertise. The architecture of the developed system is described and a functionally similar VoiceXML system is used to provide a comparative baseline across a range of modification and reuse scenarios. It is shown that the use of an object-oriented dialog manager can provide a capable means of reusing existing discourse expertise in a manner that limits the degree of structural decay associated with system change.
Visualizing tags over time
Authors: Dubinko Micah , Kumar Ravi , Magnani Joseph , Novak Jasmine , Raghavan Prabhakar , Tomkins Andrew
Published: September 2007

We consider the problem of visualizing the evolution of tags within the Flickr (flickr.com) online image sharing community. Any user of the Flickr service may append a tag to any photo in the system. Over the past year, users have on average added over a million tags each week. Understanding the evolution of these tags over time is therefore a challenging task. We present a new approach based on a characterization of the most interesting tags associated with a sliding interval of time. An animation provided via Flash in a Web browser allows the user to observe and interact with the interesting tags as they evolve over time.

New algorithms and data structures are required to support the efficient generation of this visualization. We combine a novel solution to an interval covering problem with extensions to previous work on score aggregation in order to create an efficient backend system capable of producing visualizations at arbitrary scales on this large dataset in real time.
Scouts, promoters, and connectors
Authors: Mohan Bharath Kumar , Keller Benjamin J. , Ramakrishnan Naren
Published: September 2007

Recommender systems aggregate individual user ratings into predictions of products or services that might interest visitors. The quality of this aggregation process crucially affects the user experience and hence the effectiveness of recommenders in e-commerce. We present a characterization of nearest-neighbor collaborative filtering that allows us to disaggregate global recommender performance measures into contributions made by each individual rating. In particular, we formulate three roles---
scouts
,
promoters
, and
connectors
---that capture how users receive recommendations, how items get recommended, and how ratings of these two types are themselves connected, respectively. These roles find direct uses in improving recommendations for users, in better targeting of items and, most importantly, in helping monitor the health of the system as a whole. For instance, they can be used to track the evolution of neighborhoods, to identify rating subspaces that do not contribute (or contribute negatively) to system performance, to enumerate users who are in danger of leaving, and to assess the susceptibility of the system to attacks such as shilling. We argue that the three rating roles presented here provide broad primitives to manage a recommender system and its community.
The effects of proxy bidding and minimum bid increments within eBay auctions
Authors: Rogers Alex , David Esther , Jennings Nicholas R. , Schiff Jeremy
Published: September 2007

We present a mathematical model of the eBay auction protocol and perform a detailed analysis of the effects that the eBay proxy bidding system and the minimum bid increment have on the auction properties. We first consider the revenue of the auction, and we show analytically that when two bidders with independent private valuations use the eBay proxy bidding system there exists an optimal value for the minimum bid increment at which the auctioneer's revenue is maximized. We then consider the sequential way in which bids are placed within the auction, and we show analytically that independent of assumptions regarding the bidders' valuation distribution or bidding strategy the number of visible bids placed is related to the logarithm of the number of potential bidders. Thus, in many cases, it is only a minority of the potential bidders that are able to submit bids and are visible in the auction bid history (despite the fact that the other hidden bidders are still effectively competing for the item). Furthermore, we show through simulation that the minimum bid increment also introduces an inefficiency to the auction, whereby a bidder who enters the auction late may find that its valuation is insufficient to allow them to advance the current bid by the minimum bid increment despite them actually having the highest valuation for the item. Finally, we use these results to consider appropriate strategies for bidders within real world eBay auctions. We show that while last-minute bidding (sniping) is an effective strategy against bidders engaging in incremental bidding (and against those with common values), in general, delaying bidding is disadvantageous even if delayed bids are sure to be received before the auction closes. Thus, when several bidders submit last-minute bids, we show that rather than seeking to bid as late as possible, a bidder should try to be the first sniper to bid (i.e., it should “snipe before the snipers”).
Decoding the structure of the WWW
Authors: Serrano M. Ángeles , Maguitman Ana , Boguñá Marián , Fortunato Santo , Vespignani Alessandro
Published: September 2007

The understanding of the immense and intricate topological structure of the World Wide Web (WWW) is a major scientific and technological challenge. This has been recently tackled by characterizing the properties of its representative graphs, in which vertices and directed edges are identified with Web pages and hyperlinks, respectively. Data gathered in large-scale crawls have been analyzed by several groups resulting in a general picture of the WWW that encompasses many of the complex properties typical of rapidly evolving networks. In this article, we report a detailed statistical analysis of the topological properties of four different WWW graphs obtained with different crawlers. We find that, despite the very large size of the samples, the statistical measures characterizing these graphs differ quantitatively, and in some cases qualitatively, depending on the domain analyzed and the crawl used for gathering the data. This spurs the issue of the presence of sampling biases and structural differences of Web crawls that might induce properties not representative of the actual global underlying graph. In short, the stability of the widely accepted statistical description of the Web is called into question. In order to provide a more accurate characterization of the Web graph, we study statistical measures beyond the degree distribution, such as degree-degree correlation functions or the statistics of reciprocal connections. The latter appears to enclose the relevant correlations of the WWW graph and carry most of the topological information of the Web. The analysis of this quantity is also of major interest in relation to the navigability and searchability of the Web.
(Almost) Tight bounds and existence theorems for single-commodity confluent flows
Authors: Chen Jiangzhuo , Kleinberg Robert D. , Lovász László , Rajaraman Rajmohan , Sundaram Ravi , Vetta Adrian
Published: September 2007

A flow of a commodity is said to be confluent if at any node all the flow of the commodity leaves along a single edge. In this article, we study single-commodity confluent flow problems, where we need to route given node demands to a single destination using a confluent flow. Single- and multi-commodity confluent flows arise in a variety of application areas, most notably in networking; in fact, most flows in the Internet are (multi-commodity) confluent flows since Internet routing is destination based.

We present near-tight approximation algorithms, hardness results, and existence theorems for minimizing congestion in single-commodity confluent flows. The maximum edge congestion of a single-commodity confluent flow occurs at one of the incoming edges of the destination. Therefore, finding a minimum-congestion confluent flow is equivalent to the following problem: given a directed graph
G
with
k
sinks
and non-negative demands on all the nodes of
G
, determine a confluent flow that routes every node demand to some sink such that the maximum congestion at a sink is minimized.

The main result of this article is a polynomial-time algorithm for determining a confluent flow with congestion at most 1 + ln(
k
) in
G
, if
G
admits a splittable flow with congestion at most 1. We complement this result in two directions. First, we present a graph
G
that admits a splittable flow with congestion at most 1, yet no confluent flow with congestion smaller than
H

k

, the
k
th harmonic number, thus establishing tight upper and lower bounds to within an additive constant less than 1. Second, we show that it is NP-hard to approximate the congestion of an optimal confluent flow to within a factor of (log
2
k
)/2, thus resolving the polynomial-time approximability to within a multiplicative constant. We also consider a demand maximization version of the problem. We show that if
G
admits a splittable flow of congestion at most 1, then a variant of the congestion minimization algorithm yields a confluent flow in
G
with congestion at most 1 that satisfies 1/3 fraction of total demand.

We show that the gap between confluent flows and splittable flows is much smaller, if the underlying graph is
k
-connected. In particular, we prove that
k
-connected graphs with
k
sinks admit confluent flows of congestion less than
C
+
d
max
, where
C
is the congestion of the best splittable flow, and
d
max
is the maximum demand of any node in
G
. The proof of this existence theorem is non-constructive and relies on topological techniques introduced by Lovász.
On deciding well-definedness for query languages on trees
Authors: Vansummeren Stijn
Published: September 2007

The well-definedness problem for a database query language consists of checking, given an expression and an input type, that the expression never yields a runtime error on any input adhering to the input type. In this article, we study the well-definedness problem for query languages on trees that are built from a finite set of partially defined base operations by adding variables, constants, conditionals, let bindings, and iteration. We identify properties of base operations that can make the problem undecidable and give restrictions that are sufficient to ensure decidability. As a direct result, we obtain a large fragment of XQuery for which well-definedness is decidable.
Sampling from large matrices
Authors: Rudelson Mark , Vershynin Roman
Published: September 2007

We study random submatrices of a large matrix
A
. We show how to approximately compute
A
from its random submatrix of the smallest possible size
O
(
r
log
r
) with a small error in the spectral norm, where
r
= ‖
A
‖
2

F

/‖
A
‖
2
2
is the numerical rank of
A
. The numerical rank is always bounded by, and is a stable relaxation of, the rank of
A
. This yields an asymptotically optimal guarantee in an algorithm for computing
low-rank approximations
of
A
. We also prove asymptotically optimal estimates on the
spectral norm
and the
cut-norm
of random submatrices of
A
. The result for the cut-norm yields a slight improvement on the best-known sample complexity for an approximation algorithm for MAX-2CSP problems. We use methods of Probability in Banach spaces, in particular the law of large numbers for operator-valued random variables.
Design, implementation, and evaluation of a compilation server
Authors: Lee Han B. , Diwan Amer , Moss J. Eliot B.
Published: September 2007

Modern JVM implementations interleave execution with compilation of “hot” methods to achieve reasonable performance. Since compilation overhead impacts the execution time of the application and induces run-time pauses, we explore offloading compilation onto a compilation server. In this article, we present the design, implementation, and evaluation of a compilation server that compiles and optimizes Java bytecodes on behalf of its clients.

We show that the compilation server provides the following benefits for our benchmark programs: (i) lower execution time by reducing the compilation overhead and by enabling more aggressive optimizations; (ii) lower memory allocation by eliminating allocations due to optimizing compilation and the footprint of the optimizing compiler; (iii) lower execution time of the application due to sharing of profile information across different runs of the same application and runs of different applications.

We implemented the compilation server in Jikes RVM, and our results indicate that it can reduce running time by an average of 20.5%, interruptions due to compilation by an average of 81.0%, and dynamic memory allocation by 8.6% for our benchmark programs. Simulation results indicate that our current implementation of the compilation server can handle more than 50 concurrent clients while still allowing them to outperform the best performing adaptive configuration.
Static validation of XSL transformations
Authors: Møller Anders , Olesen Mads Østerby , Schwartzbach Michael I.
Published: September 2007

XSL Transformations (XSLT) is a programming language for defining transformations among XML languages. The structure of these languages is formally described by schemas, for example using DTD or XML Schema, which allows individual documents to be validated. However, existing XSLT tools offer no static guarantees that, under the assumption that the input is valid relative to the input schema, the output of the transformation is valid relative to the output schema.

We present a validation technique for XSLT based on the XML graph formalism introduced in the static analysis of JWIG Web services and X
ACT
XML transformations. Being able to provide static guarantees, we can detect a large class of errors in an XSLT stylesheet at the time it is written instead of later when it has been deployed, and thereby provide benefits similar to those of static type checkers for modern programming languages.

Our analysis takes a pragmatic approach that focuses its precision on the essential language features but still handles the entire XSLT language. We evaluate the analysis precision on a range of real stylesheets and demonstrate how it may be useful in practice.
Mutatis Mutandis
Authors: Stoyle Gareth , Hicks Michael , Bierman Gavin , Sewell Peter , Neamtiu Iulian
Published: September 2007

This article presents Proteus, a core calculus that models dynamic software updating, a service for fixing bugs and adding features to a running program. Proteus permits a program's type structure to change dynamically but guarantees the updated program remains type-correct by ensuring a property we call con-freeness. We show how con-freeness can be enforced dynamically, and how it can be approximated via a novel static analysis. This analysis can be used to assess the implications of a program's structure on future updates in order to make update success more predictable. We have implemented Proteus for C, and briefly discuss our implementation which we have tested on several well-known programs.
On-chip communication architecture exploration
Authors: Lee Hyung Gyu , Chang Naehyuck , Ogras Umit Y. , Marculescu Radu
Published: September 2007

Traditionally, design-space exploration for systems-on-chip (SoCs) has focused on the computational aspects of the problem at hand. However, as the number of components on a single chip and their performance continue to increase, a shift from computation-based to communication-based design becomes mandatory. As a result, the communication architecture plays a major role in the area, performance, and energy consumption of the overall system. This article presents a comprehensive evaluation of three on-chip communication architectures targeting multimedia applications. Specifically, we compare and contrast the network-on-chip (NoC) with point-to-point (P2P) and bus-based communication architectures in terms of area, performance, and energy consumption. As the main contribution, we present complete P2P, bus-, and NoC-based implementations of a real multimedia application (i. e. the MPEG-2 encoder), and provide direct measurements using an FPGA prototype and actual video clips, rather than simulation and synthetic workloads. We also support the experimental findings through a theoretical analysis. Both experimental and analysis results show that the NoC architecture scales very well in terms of area, performance, energy, and design effort, while the P2P and bus-based architectures scale poorly on all accounts except for performance and area, respectively.
Circuit-simulated obstacle-aware Steiner routing
Authors: Shi Yiyu , Mesa Paul , Yu Hao , He Lei
Published: September 2007

This article develops circuit-simulated routing algorithms. We model the routing graph by an RC network with terminals as inputs, and show that the faster an output reaches its peak, the higher the possibility for the corresponding Hanan or escape node to become a Steiner point. This enables us to select Steiner points and then apply any minimum spanning tree algorithm to obtain obstacle-free or obstacle-aware Steiner routing. Compared with existing algorithms, our algorithms have significant gain on either wirelength or runtime for obstacle-free routing, and on both wirelength and runtime for obstacle-aware routing.
Probabilistic system-on-a-chip architectures
Authors: Chakrapani Lakshmi N. , Korkmaz Pinar , Akgul Bilge E. S. , Palem Krishna V.
Published: September 2007

Parameter variations, noise susceptibility, and increasing energy dissipation of cmos devices have been recognized as major challenges in circuit and microarchitecture design in the nanometer regime. Among these, parameter variations and noise susceptibility are increasingly causing cmos devices to behave in an “unreliable” or “probabilistic” manner. To address these challenges, a shift in design paradigm from current-day deterministic designs to “statistical” or “probabilistic” designs is deemed inevitable. To respond to this need, in this article, we introduce and study an entirely novel family of probabilistic architectures: the
probabilistic system-on-a-chip
(psoc). psoc architectures are based on cmos devices rendered probabilistic due to noise, referred to as
probabilistic
CMOS or PCMOS devices. We demonstrate that in addition to harnessing the probabilistic behavior of pcmos devices, psoc architectures yield significant improvements, both in energy consumed as well as performance in the context of probabilistic or randomized applications with broad utility. All of our application and architectural savings are quantified using the product of the energy and performance, denoted (energy × performance): The pcmos-based gains are as high as a substantial multiplicative factor of over 560 when compared to a competing energy-efficient cmos-based realization. Our architectural design is application specific and involves navigating design space spanning the algorithm (application), its architecture (psoc), and the probabilistic technology (pcmos).
A functionality-directed clustering technique for low-power MTCMOS design—computation of simultaneously discharging current
Authors: Hsieh Ang-Chih , Lin Tzu-Teng , Chang Tsuang-Wei , Hwang Tingting
Published: September 2007

Multithreshold CMOS (MTCMOS) is a circuit style that can effectively reduce leakage power consumption. Sleep transistor sizing is the key issue when a MTCMOS circuit is designed. If the size of sleep transistor is large enough, the circuit performance can surely be maintained but the area and dynamic power consumption of the sleep transistor may increase. On the other hand, if the sleep transistor size is too small, there will be significant performance degradation because of the increased resistance to ground. Previous approaches [Kao et al. 1998; Anis et al. 2002] to designing sleep transistor size are based mainly on mutually-exclusive discharge patterns. However, these approaches considered only the topology of a circuit (i.e., interconnections of nodes in the circuit-graph saving the functionality of node). We observed that any two possible simultaneously switching gates may not discharge at the same time in terms of functionality. Thus, we propose an algorithm to determine how to cluster cells to share sleep transistors, while taking both topology and functionality into consideration. Moreover, one placement refinement algorithm that takes clustering information into account will be presented. At the logic level, the results show that the proposed clustering method can achieve an average of 22% reduction in terms of the number of unit-size sleep transistors as compared to a method that does not consider functionality. At the physical level, two placement results are discussed. The first is produced by a traditional placement tool plus topology check (functionality check) for insertion of sleep transistors. It shows that the functionality check algorithm produces 9% less chip area as compared with the topology check algorithm. The second result is produced by a placement refinement algorithm where the initial placement is done in the first placement experiment. It shows that the placement refinement algorithm achieves 5% more reduction in area at the expense of 4% increase in wire length. Totally, around 14% reduction is achieved by utilizing the clustering information.
A verification system for transient response of analog circuits
Authors: Dastidar Tathagato Rai , Chakrabarti P. P.
Published: September 2007

We present a method for application of formal techniques like model checking and equivalence checking for validation of the transient response of nonlinear analog circuits. We propose a temporal logic called Ana CTL (computational tree logic for analog circuit verification) which is suitable for specifying properties specific to analog circuits. The application of Ana CTL for validation of transient behavior of arbitrarily nonlinear analog circuits is presented. The transient response of a circuit under all possible input waveforms is represented as a finite state machine (FSM), by bounding and discretizing the continuous state space of an analog circuit. We have developed algorithms to run Ana CTL queries on this discretized model using search-based methods which reduce the runtime considerably by avoiding creation of the whole FSM. The application of these methods on several real-life analog circuits is presented and we show that this system is a useful aid for detecting and debugging early design errors.

We also present methods for checking the equivalence of transient response of two analog circuits. The behavior of two different analog circuits can rarely be exactly similar. Hence, we introduce a notion of
approximate
equivalence. A query language for checking different notions of user-definable approximate equivalence is presented which extends the syntax of the Ana CTL model checking language. In its extended form, Ana CTL can be used combining model checking with equivalence checking.