bluuebunny/crossref_metadata_2025 huggingface dataset:
Example-Based Color Stylization of Images
Authors: Chang Youngha , Saito Suguru , Uchikawa Keiji , Nakajima Masayuki
Published: November 2005

We describe a new computational approach to stylize the colors of an image by using a reference image. During processing, we take the characteristics of human color perception into account to generate more appealing results. Our system starts by classifying each pixel value into one of the basic color categories, derived from our psychophysical experiments. The basic color categories are perceptual categories that are universal to everyone, regardless of nationality or cultural background. These categories are used to provide restrictions on color transformations to avoid generating unnatural results. Our system then renders a new image by transferring colors from a reference image to the input image, based on these categorizations. To avoid artifacts due to the explicit clustering, our system defines fuzzy categorization when pseudocontours appear in the resulting image. We present a variety of results and show that our method performs a large, yet natural, color transformation without any sense of incongruity and that the resulting images automatically capture the characteristics of the colors used in the reference image.
Fast sparse matrix multiplication
Authors: Yuster Raphael , Zwick Uri
Published: November 2005

Let
A
and
B
two
n
×
n
matrices over a ring
R
(e.g., the reals or the integers) each containing at most
m
nonzero elements. We present a new algorithm that multiplies
A
and
B
using
O
(
m
0.7
n
1.2
+
n

2+
o
(1)

) algebraic operations (i.e., multiplications, additions and subtractions) over
R
. The naïve matrix multiplication algorithm, on the other hand, may need to perform Ω(
mn
) operations to accomplish the same task. For
m
≤
n
1.14
, the new algorithm performs an almost optimal number of only
n

2+
o
(1)

operations. For
m
≤
n
1.68
, the new algorithm is also faster than the best known matrix multiplication algorithm for dense matrices which uses
O
(
n
2.38
) algebraic operations. The new algorithm is obtained using a surprisingly straightforward combination of a simple combinatorial idea and existing fast
rectangular
matrix multiplication algorithms. We also obtain improved algorithms for the multiplication of more than two sparse matrices. As the known fast rectangular matrix multiplication algorithms are far from being practical, our result, at least for now, is only of theoretical value.
Black box for constant-time insertion in priority queues (note)
Authors: Alstrup Stephen , Husfeldt Thore , Rauhe Theis , Thorup Mikkel
Published: November 2005

We present a simple black box that takes a priority queue
Q
which supports find-min, insert, and delete in x-time at most
t
. Here x-time may be worst-case, expected, or amortized. The black-box transforms
Q
into a priority queue
Q
* that supports find-min in constant time, insert in constant x-time, and delete in x-time
O
(
t
). Moreover, if
Q
supports dec-key in constant time, then so does
Q
*.
Analysis of linear combination algorithms in cryptography
Authors: Grabner Peter J. , Heuberger Clemens , Prodinger Helmut , Thuswaldner Jörg M.
Published: November 2005

Several cryptosystems rely on fast calculations of linear combinations in groups. One way to achieve this is to use joint signed binary digit expansions of small “weight.” We study two algorithms, one based on nonadjacent forms of the coefficients of the linear combination, the other based on a certain joint sparse form specifically adapted to this problem. Both methods are sped up using the sliding windows approach combined with precomputed lookup tables. We give explicit and asymptotic results for the number of group operations needed, assuming uniform distribution of the coefficients. Expected values, variances and a central limit theorem are proved using generating functions.Furthermore, we provide a new algorithm that calculates the digits of an optimal expansion of pairs of integers from left to right. This avoids storing the whole expansion, which is needed with the previously known right-to-left methods, and allows an online computation.
Behavioral synthesis techniques for intellectual property protection
Authors: Koushanfar Farinaz , Hong Inki , Potkonjak Miodrag
Published: November 2005

We introduce dynamic watermarking techniques for protecting the value of intellectual property of CAD and compilation tools and reusable design components. The essence of the new approach is the addition of a set of design and timing constraints which encodes the author's signature. The constraints are selected in such a way that they result in a minimal hardware overhead while embedding a unique signature that is difficult to remove and forge. Techniques are applicable in conjunction with an arbitrary behavioral synthesis task such as scheduling, assignment, allocation, transformation, and template matching.On a large set of design examples, studies indicate the effectiveness of the new approach that results in signature data that is highly resilient, difficult to detect and remove, and yet is easy to verify and can be embedded in designs with very low hardware overhead. For example, the probability that the same design with the embedded signature is obtained by any other designers by themselves is less than 1 in 10
102
, and no register overhead was incurred. The probability of tampering, the probability that part of the embedded signature can be removed by random attempts, is shown to be extremely low, and the watermark is additionally protected from such tampering with error-correcting codes.
An
o
(
min
(
m
,
n
)) parallel deadlock detection algorithm
Authors: Lee Jaehwan John , Mooney Vincent John
Published: November 2005

This article presents a novel Parallel Deadlock Detection Algorithm (PDDA) and its hardware implementation, Deadlock Detection Unit (DDU). PDDA uses simple Boolean representations of request, grant, and no activity so that the hardware implementation of PDDA becomes easier and operates faster. We prove the correctness of PDDA and that the DDU has a runtime complexity of
O
(
min
(
m
,
n
)), where
m
is the number of resources and
n
is the number of processes. The DDU reduces deadlock detection time by 99%, (i.e., 100X) or more compared to software implementations of deadlock detection algorithms. An experiment involving a practical situation with an early deadlock condition showed that the time measured from application initialization to deadlock detection was reduced by 46% by employing the DDU as compared to detecting deadlock in software.
A market-based approach to recommender systems
Authors: Wei Yan Zheng , Moreau Luc , Jennings Nicholas R.
Published: November 2005

Recommender systems have been widely advocated as a way of coping with the problem of information overload for knowledge workers. Given this, multiple recommendation methods have been developed. However, it has been shown that no one technique is best for all users in all situations. Thus we believe that effective recommender systems should incorporate a wide variety of such techniques and that some form of overarching framework should be put in place to coordinate the various recommendations so that only the best of them (from whatever source) are presented to the user. To this end, we show that a marketplace, in which the various recommendation methods compete to offer their recommendations to the user, can be used in this role. Specifically, this article presents the
principled
design of such a marketplace (including the auction protocol, the reward mechanism, and the bidding strategies of the individual recommendation agents) and evaluates the market's capability to effectively coordinate multiple methods. Through analysis and simulation, we show that our market is capable of shortlisting recommendations in decreasing order of user perceived quality and of correlating the individual agent's internal quality rating to the user's perceived quality.
Trustworthy 100-year digital objects
Authors: Gladney H. M. , Lorie R. A.
Published: November 2005

How can an author store digital information so that it will be reliably intelligible, even years later when he or she is no longer available to answer questions? Methods that
might
work are not good enough; what is preserved today should be reliably intelligible whenever someone wants it. Prior proposals fail because they generally confound saved data with irrelevant details of today's information technology---details that are difficult to define, extract, and save completely and accurately.We use a virtual machine to represent and eventually to render any data whatsoever. We focus on a case of intermediate difficulty---an executable procedure---and identify a variant for every other data type.This solution might be more elaborate than needed to render some text, image, audio, or video data. Simple data can be preserved as representations using well-known standards. We sketch practical methods for files ranging from simple structures to those containing computer programs, treating simple cases here and deferring complex cases for future work. Enough of the complete solution is known to enable practical aggressive preservation programs today.
Evaluating implicit feedback models using searcher simulations
Authors: White Ryen W. , Ruthven Ian , Jose Joemon M. , Rijsbergen C. J. Van
Published: November 2005

In this article we describe an evaluation of relevance feedback (RF) algorithms using searcher simulations. Since these algorithms select additional terms for query modification based on inferences made from searcher interaction, not on relevance information searchers explicitly provide (as in traditional RF), we refer to them as
implicit feedback models
. We introduce six different models that base their decisions on the interactions of searchers and use different approaches to rank query modification terms. The aim of this article is to determine which of these models should be used to assist searchers in the systems we develop. To evaluate these models we used searcher simulations that afforded us more control over the experimental conditions than experiments with human subjects and allowed complex interaction to be modeled without the need for costly human experimentation. The simulation-based evaluation methodology measures how well the models learn the distribution of terms across relevant documents (i.e., learn what information is relevant) and how well they improve search effectiveness (i.e., create effective search queries). Our findings show that an implicit feedback model based on Jeffrey's rule of conditioning outperformed other models under investigation.
A state-transition approach to application service provider client-vendor relationship development
Authors: Yao Yurong , Murphy Lisa
Published: November 2005

Application Services Providers (ASPs) exploit the economics of delivering commercial off-the-shelf software over the Internet to many dispersed users. This form of outsourcing differs from traditional ones on attributes of vendors and clients, contract terms, customization, and functionality. We develop a state-transition model for ASP client-vendor relationship development reflecting that shorter contract terms affect the nature, strength, and timing of interactions ASP vendors have with their clients and the resulting patterns of information flows and mutual learning that lead to relationship outcomes. Using marketing and economic theories, we put forward factors originating in pre-contract exposure and diffuse sources (i.e., credibility, capability, expectation-capability match) and those arising from the direct collaboration experience (i.e., communications, trust, dependence, conflict-resolution). In addition to providing a solid foundation for vendor relationship research, this paper rectifies a bias of prior work by considering both the vendor and the client's perspectives on relationship development. By using contract status, the state-transition approach offered here mitigates a number of problems arising from indistinct stage boundaries and the reliance of stage membership on multiple characteristics.
An empirical study of the relationships between IT infrastructure flexibility, mass customization, and business performance
Authors: Chung Sock H. , Byrd Terry Anthony , Lewis Bruce R. , Ford F. Nelson
Published: November 2005

Information technology (IT) infrastructure deserves serious attention from both the practitioner and academic communities, especially concerning the factors for IT infrastructure flexibility. The issue of flexibility is viewed as a critical aspect of IT infrastructure, because organizations are faced with an ever-increasing rate of change in their business environments. One effort most business sectors have made to prepare for this change is the trend toward mass customization. Recently, many organizations have embraced mass customization in an attempt to provide unique value to their customers in a cost-efficient manner.The purpose of this study is to empirically investigate a sequential relationship between IT infrastructure flexibility, mass customization, and business performance. The process involves an investigation of the critical factors for IT infrastructure flexibility, along with the firm's mass customization and business performance indicators. The findings of this study provide evidence that integration and modularity of an organization's IT infrastructure facilitate the organization's effort to accommodate mass customization. Additionally, the flexibility of the IT personnel, the human component of IT infrastructure, and mass customization directly affect the organization's business performance.
Virtual organization and electronic commerce
Authors: Travica Bob
Published: November 2005

The purpose of this article is to contribute to understanding the virtual organization and its relationship with electronic commerce. The relevant literature on virtual organization forms through which business-to-business e-commerce is organized is reviewed. A model of the virtual organization is presented and its use in a case study demonstrated. Implications for further research are discussed.
High Efficiency Counter Mode Security Architecture via Prediction and Precomputation
Authors: Shi Weidong , Lee Hsien-Hsin S. , Ghosh Mrinmoy , Lu Chenghuai , Boldyreva Alexandra
Published: November 2005

Encrypting data in unprotected memory has gained much interest lately for digital rights protection and security reasons. Counter Mode is a well-known encryption scheme. It is a symmetric-key encryption scheme based on any block cipher, e.g. AES. The schemeýs encryption algorithm uses a block cipher, a secret key and a counter (or a sequence number) to generate an encryption pad which is XORed with the data stored in memory. Like other memory encryption schemes, this method suffers from the inherent latency of decrypting encrypted data when loading them into the on-chip cache. One solution that parallelizes data fetching and encryption pad generation requires the sequence numbers of evicted cache lines to be cached on-chip. On-chip sequence number caching can be successful in reducing the latency at the cost of a large area overhead. In this paper, we present a novel technique to hide the latency overhead of decrypting counter mode encrypted memory by predicting the sequence number and pre-computing the encryption pad that we call one-time-pad or OTP. In contrast to the prior techniques of sequence number caching, our mechanism solves the latency issue by using idle decryption engine cycles to speculatively predict and pre-compute OTPs before the corresponding sequence number is loaded. This technique incurs very little area overhead. In addition, a novel adaptive OTP prediction technique is also presented to further improve our regular OTP prediction and precomputation mechanism. This adaptive scheme is not only able to predict encryption pads associated with static and infrequently updated cache lines but also those frequently updated ones as well. Experimental results using SPEC2000 benchmark show an 82% prediction rate. Moreover, we also explore several optimization techniques for improving the prediction accuracy. Two specific techniques, Two-level prediction and Context-based prediction are presented and evaluated. For the two-level prediction, the prediction rate was improved from 82% to 96%. With the context-based prediction, the prediction rate approaches 99%. Context-based OTP prediction outperforms a very large 512KB sequence number cache for many memory-bound SPEC programs. IPC results show an overall 15% to 40% performance improvement using our prediction and precomputation, and another 7% improvement when context-based prediction techniques is used.
Design and Implementation of the AEGIS Single-Chip Secure Processor Using Physical Random Functions
Authors: Suh G. Edward , O'Donnell Charles W. , Sachdev Ishan , Devadas Srinivas
Published: November 2005

Secure processors enable new applications by ensuring private and authentic program execution even in the face of physical attack. In this paper we present the AEGIS secure processor architecture, and evaluate its RTL implementation on FPGAs. By using Physical Random Functions, we propose a new way of reliably protecting and sharing secrets that is more secure than existing solutions based on non-volatile memory. Our architecture gives applications the flexibility of trusting and protecting only a portion of a given process, unlike prior proposals which require a process to be protected in entirety. We also put forward a specific model of how secure applications can be programmed in a high-level language and compiled to run on our system. Finally, we evaluate a fully functional FPGA implementation of our processor, assess the implementation tradeoffs, compare performance, and demonstrate the benefits of partially protecting a program.
RENO
Authors: Petric Vlad , Sha Tingting , Roth Amir
Published: November 2005

RENO is a modified MIPS R10000 register renamer that uses map-table "short-circuiting" to implement dynamic versions of several well-known static optimizations: move elimination, common subexpression elimination, register allocation, and constant folding. Because it implements these optimizations dynamically, RENO can apply optimizations in certain situations where static compilers cannot. Several of RENOýs component optimizations have been previously proposed as independent mechanisms. Unified renaming [13] implements dynamic move elimination and speculative memory bypassing [19] (the dynamic counterpart of register allocation). Register integration [21] implements common-subexpression elimination and speculative memory bypassing. RENO unifies these mechanisms and adds a dynamic version of constant folding, RENOCF. RENOCF uses an extended map table format and a limited form of dynamic operation fusion. Cycle-level simulation shows that RENO dynamically eliminates (i.e., optimizes away) 22% of the dynamic instructions in both SPECint2000 and MediaBench. RENOCF is responsible for 12% and 17% of the eliminations, respectively. Because dataflow dependences are collapsed around eliminated instructions, performance improves by 8% and 13%, respectively. Alternatively, because eliminated instructions do not consume issue queue entries, physical registers, or issue, bypass, register file, and execution bandwidth, RENO can be used to absorb the performance impact of a significantly scaled-down execution core.
A High Throughput String Matching Architecture for Intrusion Detection and Prevention
Authors: Tan Lin , Sherwood Timothy
Published: November 2005

Network Intrusion Detection and Prevention Systems have emerged as one of the most effective ways of providing security to those connected to the network, and at the heart of almost every modern intrusion detection system is a string matching algorithm. String matching is one of the most critical elements because it allows for the system to make decisions based not just on the headers, but the actual content flowing through the network. Unfortunately, checking every byte of every packet to see if it matches one of a set of ten thousand strings becomes a computationally intensive task as network speeds grow into the tens, and eventually hundreds, of gigabits/second. To keep up with these speeds a specialized device is required, one that can maintain tight bounds on worst case performance, that can be updated with new rules without interrupting operation, and one that is efficient enough that it could be included on chip with existing network chips or even into wireless devices. We have developed an approach that relies on a special purpose architecture that executes novel string matching algorithms specially optimized for implementation in our design. We show how the problem can be solved by converting the large database of strings into many tiny state machines, each of which searches for a portion of the rules and a portion of the bits of each rule. Through the careful co-design and optimization of our our architecture with a new string matching algorithm we show that it is possible to build a system that is 10 times more efficient than the currently best known approaches.
An Evaluation Framework and Instruction Set Architecture for Ion-Trap Based Quantum Micro-Architectures
Authors: Balensiefer Steven , Kregor-Stickles Lucas , Oskin Mark
Published: November 2005

The theoretical study of quantum computation has yielded efficient algorithms for some traditionally hard problems. Correspondingly, experimental work on the underlying physical implementation technology has progressed steadily. However, almost no work has yet been done which explores the architecture design space of large scale quantum computing systems. In this paper, we present a set of tools that enable the quantitative evaluation of architectures for quantum computers. The infrastructure we created comprises a complete compilation and simulation system for computers containing thousands of quantum bits. We begin by compiling complete algorithms into a quantum instruction set. This ISA enables the simple manipulation of quantum state. Another tool we developed automatically transforms quantum software into an equivalent, fault-tolerant version required to operate on real quantum devices. Next, our infrastructure transforms the ISA into a set of low-level micro architecture specific control operations. In the future, these operations can be used to directly control a quantum computer. For now, our simulation framework quickly uses them to determine the reliability of the application for the target micro architecture. Finally, we propose a simple, regular architecture for ion-trap based quantum computers. Using our software infrastructure, we evaluate the design trade offs of this micro architecture.
Temporal Streaming of Shared Memory
Authors: Wenisch Thomas F. , Somogyi Stephen , Hardavellas Nikolaos , Kim Jangwoo , Ailamaki Anastassia , Falsafi Babak
Published: November 2005

Coherent read misses in shared-memory multiprocessors account for a substantial fraction of execution time in many important scientific and commercial workloads. We propose Temporal Streaming, to eliminate coherent read misses by streaming data to a processor in advance of the corresponding memory accesses. Temporal streaming dynamically identifies address sequences to be streamed by exploiting two common phenomena in shared-memory access patterns: (1) temporal address correlation - groups of shared addresses tend to be accessed together and in the same order, and (2) temporal stream locality - recently-accessed address streams are likely to recur. We present a practical design for temporal streaming. We evaluate our design using a combination of trace-driven and cycle-accurate full-system simulation of a cache-coherent distributed shared-memory system. We show that temporal streaming can eliminate 98% of coherent read misses in scientific applications, and between 43% and 60% in database and web server workloads. Our design yields speedups of 1.07 to 3.29 in scientific applications, and 1.06 to 1.21 in commercial workloads.
Techniques for Efficient Processing in Runahead Execution Engines
Authors: Mutlu Onur , Kim Hyesoon , Patt Yale N.
Published: November 2005

Runahead execution is a technique that improves processor performance by pre-executing the running application instead of stalling the processor when a long-latency cache miss occurs. Previous research has shown that this technique significantly improves processor performance. However, the efficiency of runahead execution, which directly affects the dynamic energy consumed by a runahead processor, has not been explored. A runahead processor executes significantly more instructions than a traditionalout-of-order processor, sometimes without providing any performance benefit, which makes it inefficient. In this paper, we describe the causes of inefficiency in runahead execution and propose techniques to make a runahead processor more efficient, thereby reducing its energy consumption and possibly increasing its performance. Our analyses and results provide two major insights: (1) the efficiency of runahead execution can be greatly improved with simple techniques that reduce the number of short, overlapping, and useless runahead periods, which we identify as the three major causes of inefficiency, (2) simple optimizations targeting the increase of useful prefetches generated in runahead mode can increase both the performance and efficiency of a runahead processor. The techniques we propose reduce the increase in the number of instructions executed due to runahead execution from 26.5% to 6.2%, on average, without significantly affecting the performance improvement provided by runahead execution.
Piecewise Linear Branch Prediction
Authors: Jimenez Daniel A.
Published: November 2005

Improved branch prediction accuracy is essential to sustaining instruction throughput with todayýs deep pipelines. We introduce piecewise linear branch prediction, an idealized branch predictor that develops a set of linear functions, one for each program path to the branch to be predicted, that separate predicted taken from predicted not taken branches. Taken together, all of these linear functions form a piecewise linear decision surface. We present a limit study of this predictor showing its potential to greatly improve predictor accuracy. We then introduce a practical implementable branch predictor based on piecewise linear branch prediction. In making our predictor practical, we show how a parameterized version of it unifies the previously distinct concepts of perceptron prediction and path-based neural prediction. Our new branch predictor has implementation costs comparable to current prominent predictors in the literature while significantly improving accuracy. For a deeply pipelined simulated microarchitecture our predictor with a 256KB hardware budget improves the harmonic mean normalized instructions-per-cycle rate by 8% over both the original path-based neural predictor and 2Bc-gskew. The average misprediction rate is decreased by 16% over the path-based neural predictor and by 22% over 2Bc-gskew.
Computing Architectural Vulnerability Factors for Address-Based Structures
Authors: Biswas Arijit , Racunas Paul , Cheveresan Razvan , Emer Joel , Mukherjee Shubhendu S. , Rangan Ram
Published: November 2005

Processor designers require estimates of the architectural vulnerability factor (AVF) of on-chip structures to make accurate soft error rate estimates. AVF is the fraction of faults from alpha particle and neutron strikes that result in user-visible errors. This paper shows how to use a performance model to calculate the AVF of address-based structures, using a data cache, a data translation buffer, and a store buffer as examples. We describe how to perform a detailed breakdown of lifetime components (e.g., fill-to-read, read-to-evict) of bits in these structures into ACE (required for architecturally correct execution), un-ACE (unnecessary for ACE), and unknown components. This lifetime analysis produces best estimate AVFs for these three structuresý data arrays of 6%, 36%, and 4%, respectively. We then present a new technique,hamming-distance-one analysis, and show that it predicts surprisingly low best estimate AVFs of 0.41%, 3%, and 7.7% for the structuresý tag arrays. Finally, using our lifetime analysis framework, we show how two AVF reduction techniques - periodic flushing and incremental scrubbing - can reduce the AVF by converting ACE lifetime components into un-ACE without affecting performance significantly.
Distributed Computing in the Modern Enterprise
Authors: Feldman Stuart
Published: November 2005

Welcome to the Alphabet Soup edition of Queue. You are about to wade into a sea of buzzwords and acronyms, but the future of enterprise computing is on the other shore.
News 2.0
Authors: Stanik John
Published: November 2005

You’ve watched in awe as spyware programs cannibalized each other, shook your head in disgust when that vigilante, anti-piracy P2P virus deleted all of your MP3s, and felt instant paranoia after learning about the astonishing number of zombie PCs out there (“could I be a zombie?”). Well, it just keeps getting weirder... and scarier.
Kode Vicious Cycles On
Authors: Neville-Neil George
Published: November 2005

Not only does California give you plenty of sun, it also apparently has employers that give you plenty of time to play around with the smaller problems that you like, in a programming language that’s irrelevant to the later implementation.
A Conversation with David Anderson
Authors: Maurer Jim
Published: November 2005

Millions of PCs on desktops at home helping to solve some of the world’s most compute-intensive scientific problems. And it’s an all-volunteer force of PC users, who, with very little effort, can contribute much-needed PC muscle to the scientific and academic communities.
Enterprise Grid Computing
Authors: Strong Paul
Published: November 2005

I have to admit a great measure of sympathy for the IT populace at large, when it is confronted by the barrage of hype around grid technology, particularly within the enterprise. Individual vendors have attempted to plant their flags in the notionally virgin technological territory and proclaim it as their own, using terms such as grid, autonomic, self-healing, self-managing, adaptive, utility, and so forth. Analysts, well, analyze and try to make sense of it all, and in the process each independently creates his or her own map of this terra incognita, naming it policy-based computing, organic computing, and so on. Unfortunately, this serves only to further muddy the waters for most people. All of these terms capture some aspect of the big picture—they all describe parts of solutions that seek to address essentially the same problems in similar ways—but they’re never quite synonymous.
Prepare your mind for learning
Authors: Smith Deborah K. , Moores Trevor , Chang Jerry
Published: November 2005

The learning process must evolve and expand throughout one's IT career. Most would agree that's often easier said than done. Here are some ways professionals can overcome mental blocks that may prevent learning.
Restoring the popularity of computer science
Authors: Patterson David A.
Published: November 2005

Inaccurate impressions of the opportunities of 21st century CS are shrinking the next generation of IT professionals. You can help by dispelling incorrect beliefs about employment and by helping improve pre-college education.
RFID is x-ray vision
Authors: Stajano Frank
Published: November 2005

In a world saturated with RFID tags, protecting the privacy of individuals is technically difficult. Without a proper alignment of interests it may be impossible.
Introduction
Authors: Borriello Gaetano
Published: November 2005

Cheap, tiny, plentiful radio-frequency identification tags will make it possible to tag almost everything, spurring a revolution in how physical objects interact with information services.
Photosensing wireless tags for geometric procedures
Authors: Raskar Ramesh , Beardsley Paul , Dietz Paul , van Baar Jeroen
Published: November 2005

Interacting with a self-describing, self-locating world sprinkled with RFIG tags, physical objects come alive through augmented reality labels and context-sensitive annotation.
An in-place sorting with
O
(
n
log
n
) comparisons and
O
(
n
) moves
Authors: Franceschini Gianni , Geffert Viliam
Published: November 2005

We present the first in-place algorithm for sorting an array of size
n
that performs, in the worst case, at most
O
(
n
log
n
) element comparisons and
O
(
n
) element transports.This solves a long-standing open problem, stated explicitly, for example, in Munro and Raman [1992], of whether there exists a sorting algorithm that matches the asymptotic lower bounds on all computational resources simultaneously.
Source routing and scheduling in packet networks
Authors: Andrews Matthew , Fernández Antonio , Goel Ashish , Zhang Lisa
Published: November 2005

We study
routing
and
scheduling
in packet-switched networks. We assume an adversary that controls the injection time, source, and destination for each packet injected. A set of paths for these packets is
admissible
if no link in the network is overloaded. We present the first on-line routing algorithm that finds a set of admissible paths whenever this is feasible. Our algorithm calculates a path for each packet as soon as it is injected at its source using a simple shortest path computation. The length of a link reflects its current congestion. We also show how our algorithm can be implemented under today's Internet routing paradigms.When the paths are known (either given by the adversary or computed as above), our goal is to schedule the packets along the given paths so that the packets experience small end-to-end delays. The best previous delay bounds for deterministic and distributed scheduling protocols were exponential in the path length. In this article, we present the first deterministic and distributed scheduling protocol that guarantees a polynomial end-to-end delay for every packet.Finally, we discuss the effects of combining routing with scheduling. We first show that some unstable scheduling protocols remain unstable no matter how the paths are chosen. However, the freedom to choose paths can make a difference. For example, we show that a ring with parallel links is stable for all greedy scheduling protocols if paths are chosen intelligently, whereas this is not the case if the adversary specifies the paths.
Boosting textual compression in optimal linear time
Authors: Ferragina Paolo , Giancarlo Raffaele , Manzini Giovanni , Sciortino Marinella
Published: November 2005

We provide a general boosting technique for Textual Data Compression. Qualitatively, it takes a good compression algorithm and turns it into an algorithm with a better compression performance guarantee. It displays the following remarkable properties: (a) it can turn
any memoryless
compressor into a compression algorithm that uses the “best possible” contexts; (b) it is very simple and
optimal
in terms of time; and (c) it admits a decompression algorithm again optimal in time. To the best of our knowledge, this is the first boosting technique displaying these properties.Technically, our boosting technique builds upon three main ingredients: the Burrows--Wheeler Transform, the Suffix Tree data structure, and a greedy algorithm to process them. Specifically, we show that there exists a proper partition of the Burrows--Wheeler Transform of a string
s
that shows a deep combinatorial relation with the
k
th order entropy of
s
. That partition can be identified via a greedy processing of the suffix tree of
s
with the aim of minimizing a proper objective function over its nodes. The final compressed string is then obtained by compressing individually each substring of the partition by means of the base compressor we wish to boost.Our boosting technique is inherently combinatorial because it does not need to assume any prior probabilistic model about the source emitting
s
, and it does not deploy any training, parameter estimation and learning. Various corollaries are derived from this main achievement. Among the others, we show analytically that using our booster, we get better compression algorithms than some of the best existing ones, that is, LZ77, LZ78, PPMC and the ones derived from the Burrows--Wheeler Transform. Further, we settle analytically some long-standing open problems about the algorithmic structure and the performance of BWT-based compressors. Namely, we provide the first family of BWT algorithms that do not use Move-To-Front or Symbol Ranking as a part of the compression process.
Common Industry Format approved as international standard
Authors: Theofanos Mary
Published: November 2005

Hot off the press! The ink is barely dry on the release about the newest User Experience ISO standard---Common Industry Format (CIF)---and it is already settling arguments. Indeed, some big companies are quickly moving to adopt CIF as a standard because of the weight of an ISO stamp of approval. CIF is sure to have a big impact on how we "do business" in the usability realm---both for internal folks and external consultants.---Susan Dray and David Siegel
The STAMPede approach to thread-level speculation
Authors: Steffan J. Gregory , Colohan Christopher , Zhai Antonia , Mowry Todd C.
Published: November 2005

Multithreaded processor architectures are becoming increasingly commonplace: many current and upcoming designs support chip multiprocessing, simultaneous multithreading, or both. While it is relatively straightforward to use these architectures to improve the throughput of a multithreaded or multiprogrammed workload, the real challenge is how to easily create
parallel software
to allow single programs to effectively exploit all of this raw performance potential. One promising technique for overcoming this problem is
Thread-Level Speculation (TLS)
, which enables the compiler to optimistically create parallel threads despite uncertainty as to whether those threads are actually independent. In this article, we propose and evaluate a design for supporting TLS that seamlessly scales both within a chip and beyond because it is a straightforward extension of write-back invalidation-based cache coherence (which itself scales both up and down). Our experimental results demonstrate that our scheme performs well on single-chip multiprocessors where the first level caches are either private or shared. For our private-cache design, the program performance of two of 13 general purpose applications studied improves by 86% and 56%, four others by more than 8%, and an average across all applications of 16%---confirming that TLS is a promising way to exploit the naturally-multithreaded processing resources of future computer systems.
Barriers to disseminating off-the-shelf based development theories to IT industry
Authors: Li Jingyue , Conradi Reidar , Slyngstad Odd Petter N. , Bunse Christian , Khan Umair , Morisio Maurizio , Torchiano Marco
Published: November 2005

In this position paper, we have reported results of an industrial seminar. The seminar was intended to show our findings in an international survey, conducted in Norway, Italy and Germany, on off-the-shelf component-based development. Discussion in the second section of the seminar revealed several obstacles of popularizing the OTS based development theories into IT industry.
Tool support for optimization-based architectural evaluation
Authors: Al-Naeem Tariq , Gorton Ian , Rabhi Fethi , Benatallah Boualem
Published: November 2005

Architecting enterprise applications is a complex design activity. This is especially true when considering the myriad of interdependent architectural decisions with an arbitrary number of alternatives that can be employed at each decision point. Further complexities stem from the fact that different alternatives often vary considerably in their support for different quality attributes. Existing software architecture evaluation approaches and tools lack the explicit consideration of design decision interdependencies, as they primarily focus on one decision in isolation. For this purpose, we have earlier developed the ArchDesigner approach to help determining the optimal mix of architectural alternatives. This paper discusses an architectural evaluation support tool that implements the ArchDesigner approach. The novelty of this tool is in its support for evaluating combinations of alternatives against one other, and not only alternatives belonging to one decision. It treats the architectural evaluation problem as a search problem and leverages optimization techniques for evaluating candidate application architectures.
A process for identifying changes when source code is not available
Authors: Zheng Jiang , Robinson Brian , Williams Laurie , Smiley Karen
Published: November 2005

Various regression test selection techniques have been developed and shown to improve fault detection effectiveness. The majority of these test selection techniques rely on access to source code for change identification. However, when new releases of COTS components are made available for integration and testing, source code is often not available to guide regression test selection. This paper describes a process for identifying changed functions when code is not available. This change information is beneficial for selecting white-box regression tests of customer/glue code. This process is applicable when COTS licensing agreements do not preclude decompilation. A feasibility study of the process was conducted with four releases of a medium-scale internal ABB product. The results of the feasibility study indicate that this process can be effective in identifying changed functions.
Decision support for customization of the COTS selection process
Authors: Mohamed Abdallah , Ruhe Guenther , Eberlein Armin
Published: November 2005

Software technologies need to be customized to make them effective and efficient for a specific context. In this position paper, we consider the customization of the COTS selection process. We have developed a methodology which customizes the selection process based on the actual project domain characteristics (PDCs) including attributes such as available effort or project criticality. The customization of the process is done at both the process level and the activity level. We suggest a hybrid approach that integrates formalized knowledge with human expertise. This principle has already been successfully used in the context of the software release planning. The advantage is two-fold: Firstly, we exploit the existing empirical results related to different stages of the COTS selection process. Secondly, we facilitate involvement of human judgment to determine most appropriate decisions among the ones proposed by the formalized and knowledge-based solution techniques.
A COTS architectural component specification stencil for selection and reasoning
Authors: Dong Jing , Yang Sheng , Chung Lawrence , Alencar Paulo , Cowan Donald
Published: November 2005

Reusing commercial-off-the-shelf (COTS) components may reduce cost and time-to-market. It may significantly improve software productivity. However, the selection and assessment of COTS components are still a challenge task. It is hard to find the right components that exactly fit into the requirements. The selection processes are in general ad-hoc. Wrong choice of COTS components may compromise the benefits from reusing these components since the chosen component may mismatch with other components and the environment. In this position paper, we advocate a more detailed architectural specification stencil which may help on the component selection and mismatch detection. The architectural specification of a COTS component is encoded in XML so that searching components can be automated. In addition, inconsistencies and mismatches among components can be detected.
Law-governed multi-agent systems
Authors: Minsky Naftaly
Published: November 2005

I will argue that a multi-agent system should not be viewed as just the totality of its members, but that it should include the set of laws that governs the interaction between these members. Such laws need to be made explicit, as part of the design of the MAS, and they need to be enforced on its implementation.I will discuss the architecture and the scalable implementation of such law-governed MAS, using a coordination and control mechanism called Law-Governed Interaction (LGI); and will consider various implication of this architecture, to issues such as reasoning about a MAS, and making it dependable.
xTAO
Authors: Oliveira Toacy C. , Alencar Paulo , Cowan Don , Lucena Carlos
Published: November 2005

Research on software agents has produced a diversity of conceptual models for high-level abstract descriptions of multi-agent systems (MASs). However, it is still difficult and costly for designers that need a unique set of agent modeling features to either develop a new agent modeling language from scratch or undertake the task of modifying an existing language. In addition to the modeling itself, in both cases a significant effort needs to be expended in building or adapting tools to support the language. An extensible agent modeling language is crucial to experimenting with and building tools for novel modeling constructs that arise from evolving research. Existing approaches typically support a basic set of modeling constructs very well, but adapt to others poorly. A declarative language such as XML and its supporting tools provides an ideal platform upon which to develop an extensible modeling language for multi-agent systems. In this paper we describe xTAO, an extensible agent modeling language, and also demonstrate its value in the context of a real-world application.
Analysis and design of physical and social contexts in multi-agent systems using UML
Authors: Klein Florian , Giese Holger
Published: November 2005

Multi-agent technology promises to provide the ability to adapt to changing external contexts. To tap this potential, context needs to play a central role in the analysis and design of multi-agent systems. In this paper, a pragmatic approach to the classification and modeling of the relevant contexts is presented, focusing on a useful operational description rather than epistemological correctness. We then show how our approach supports the analysis and design of physical and social contexts for embedded multi-agent systems using the UML, providing a number of different examples.
Synthesis of a generic MAS metamodel
Authors: Beydoun Ghassan , Gonzalez-Perez Cesar , Low Graham , Henderson-Sellers Brian
Published: November 2005

Method engineering, which focuses on project-specific methodology construction from existing method fragments, is an appealing approach to organize, appropriately access and effectively harness the software engineering knowledge of MAS methodologies. With the objective of applying method engineering for developing an MAS, in this paper we introduce a generic metamodel to serve as a representational infrastructure to unify existing MAS methodologies into a single specification. Our metamodel does not focus on any class of MAS, nor does it impose any restrictions on the format of the system requirements; rather, our metamodel is an abstraction of how any MAS is structured and behaves both at design time and run-time.
Software engineering research versus software development
Authors: Marcos Esperanza
Published: November 2005

Engineering research differs greatly, both in its aims and in its methods, from traditional "scientific" research. While Sciences deal with the study of existing objects and phenomena, be it physically, metaphysically or conceptually, Engineering is based on
how
to do things,
how
to create new objects. For this reason, "scientific" research methods are not always directly applicable to research problems of an engineering nature.In the present article, we concentrate on the problems and research methods of a specific branch of engineering: Software Engineering, discussing, on the one hand, the nature of the method in this field while and, on the other, the similarity of the methods of research in Software Engineering and those of software development.