bluuebunny/crossref_metadata_2025 huggingface dataset:
Noise-tolerant learning, the parity problem, and the statistical query model
Authors: Blum Avrim , Kalai Adam , Wasserman Hal
Published: August 2003

We describe a slightly subexponential time algorithm for learning parity functions in the presence of random classification noise, a problem closely related to several cryptographic and coding problems. Our algorithm runs in polynomial time for the case of parity functions that depend on only the first
O
(log
n
log log
n
) bits of input, which provides the first known instance of an efficient noise-tolerant algorithm for a concept class that is not learnable in the Statistical Query model of Kearns [1998]. Thus, we demonstrate that the set of problems learnable in the statistical query model is a strict subset of those problems learnable in the presence of noise in the PAC model.In coding-theory terms, what we give is a poly(
n
)-time algorithm for decoding linear
k
×
n
codes in the presence of random noise for the case of
k
=
c
log
n
log log
n
for some
c
> 0. (The case of
k
=
O
(log
n
) is trivial since one can just individually check each of the 2

k

possible messages and choose the one that yields the closest codeword.)A natural extension of the statistical query model is to allow queries about statistical properties that involve
t
-tuples of examples, as opposed to just single examples. The second result of this article is to show that any class of functions learnable (strongly or weakly) with
t
-wise queries for
t
=
O
(log
n
) is also weakly learnable with standard unary queries. Hence, this natural extension to the statistical query model does not increase the set of weakly learnable functions.
Bounds on delays and queue lengths in input-queued cell switches
Authors: Leonardi Emilio , Mellia Marco , Neri Fabio , Marsan Marco Ajmone
Published: August 2003

In this article, we develop a general methodology, mainly based upon Lyapunov functions, to derive bounds on average delays, and on averages and variances of queue lengths in complex systems of queues. We apply this methodology to cell-based switches and routers, considering first output-queued (OQ) architectures, in order to provide a simple example of our methodology, and then both input-queued (IQ), and combined input/output queued (CIOQ) architectures. These latter switching architectures require a scheduling algorithm to select at each slot a subset of input-buffered cells that can be transferred toward output ports. Although the stability properties (i.e., the limit throughput) of IQ and CIOQ cell-based switches were already studied for several classes of scheduling algorithms, very few analytical results concerning cell delays or queue lengths are available in the technical literature. We concentrate on Maximum Weight Matching (MWM) and Maximal Size Matching (mSM) scheduling algorithms; while the former was proved to maximize throughput, the latter allows simpler implementation. The derived bounds are shown to be rather tight when compared to simulation results.
Minimizing flow time nonclairvoyantly
Authors: Kalyanasundaram Bala , Pruhs Kirk R.
Published: August 2003

We consider the problem of scheduling a collection of dynamically arriving jobs with unknown execution times so as to minimize the average flow time. This is the classic CPU scheduling problem faced by time-sharing operating systems where preemption is allowed. It is easy to see that every algorithm that doesn't unnecessarily idle the processor is at worst
n
-competitive, where
n
is the number of jobs. Yet there was no known nonclairvoyant algorithm, deterministic or randomized, with a competitive ratio provably
O
(
n
1−ϵ
). In this article, we give a randomized nonclairvoyant algorithm, RMLF, that has competitive ratio
O
(log
n
log log
n
) against an oblivious adversary. RMLF is a slight variation of the multilevel feedback (MLF) algorithm used by the UNIX operating system, further justifying the adoption of this algorithm. It is known that every randomized nonclairvoyant algorithm is Ω(log
n
)-competitive, and that every deterministic nonclairvoyant algorithm is Ω(
n
1/3
)-competitive.
How asymmetry helps load balancing
Authors: Vöcking Berthold
Published: August 2003

This article deals with randomized allocation processes placing sequentially
n
balls into
n
bins. We consider multiple-choice algorithms that choose
d
locations (bins) for each ball at random, inspect the content of these locations, and then place the ball into one of them, for example, in a location with minimum number of balls. The goal is to achieve a good load balancing. This objective is measured in terms of the maximum load, that is, the maximum number of balls in the same bin.Multiple-choice algorithms have been studied extensively in the past. Previous analyses typically assume that the
d
locations for each ball are drawn uniformly and independently from the set of all bins. We investigate whether a nonuniform or dependent selection of the
d
locations of a ball may lead to a better load balancing. Three types of selection, resulting in three classes of algorithms, are distinguished: (1) uniform and independent, (2) nonuniform and independent, and (3) nonuniform and dependent.Our first result shows that the well-studied uniform greedy algorithm (class 1) does not obtain the smallest possible maximum load. In particular, we introduce a nonuniform algorithm (class 2) that obtains a better load balancing. Surprisingly, this algorithm uses an unfair tie-breaking mechanism, called Always-Go-Left, resulting in an asymmetric assignment of the balls to the bins. Our second result is a lower bound showing that a dependent allocation (class 3) cannot yield significant further improvement.Our upper and lower bounds on the maximum load are tight up to additive constants, proving that the Always-Go-Left algorithm achieves an almost optimal load balancing among all sequential multiple-choice algorithm. Furthermore, we show that the results for the Always-Go-Left algorithm can be generalized to allocation processes with more balls than bins and even to infinite processes in which balls are inserted and deleted by an oblivious adversary.
PFIRES
Authors: Rees Jackie , Bandyopadhyay Subhajyoti , Spafford Eugene H.
Published: August 2003

Creating and maintaining effective security strategy and policy for software applications.
Digital music and online sharing
Authors: Bhattacharjee Sudip , Gopal Ram D. , Sanders G. Lawrence
Published: August 2003

Considering the similarities and unique characteristics of online file sharing and software piracy.
E-speak e-xplained
Authors: Karp Alan H.
Published: August 2003

HP's e-speak is an open software platform designed to simplify Internet-based e-services by making it easier for unrelated Web sites to work together.
The telecommunication industry revisited
Authors: Grover Varun , Saeed Khawaja
Published: August 2003

The flourishing number of partnerships in the telecom arena tell a fascinating story of forging new business strategies in a frail economy. They also demonstrate how some joint ventures may be stronger than others.
Mobile agents in distributed network management
Authors: Du Timon C. , Li Eldon Y. , Chang An-Pin
Published: August 2003

By helping to disperse centralized network management tasks to subnet hosts, mobile agent technology helps conserve network bandwidth and improves management efficiency by decreasing network traffic.
Insight into mental models of novice Internet searchers
Authors: Brandt D. Scott , Uden Lorna
Published: August 2003

Task knowledge structures can be adapted to determine the cognitive abilities of Net newbies and help create support systems to help shape their search experiences.
Coping with Internet channel conflict
Authors: Lee Younghwa , Lee Zoonky , Larsen Kai R. T.
Published: August 2003

If you do not sell your products directly over the Internet, people will go to your competitors who do, while if you do sell your products directly, your distributors and dealers will desert you and only carry products from manufacturers who do not compete with them. ---Manufacturers' Dilemma [10]
Beware the lure of the horizontal
Authors: Cusumano Michael
Published: August 2003

The correct choice of market segmentation can determine product success and help a company rise above the competition.
Accomplishment
Authors: Denning Peter J.
Published: August 2003

Language-action philosophy uncovers the truth about effective coordination and accomplishment.
Introduction
Authors: Rosenbloom Andrew
Published: August 2003

Playful yet powerful 3D computer graphics and natural interaction make possible a new generation of non-entertainment applications.
Making virtual environments compelling
Authors: Whitton Mary C.
Published: August 2003

Delivering a compelling user experience and ensuring application success both depend on the fidelity of the user's sensory immersion.
Experiential computing
Authors: Jain Ramesh
Published: August 2003

Seeking insight from data, users experience, explore, and experiment, no longer limited to just generating lists of possible answers to simplistic queries.
Game-like navigation and responsiveness in non-game applications
Authors: Tsang Michael , Fitzmaurice George , Kurtenbach Gord , Khan Azam
Published: August 2003

Real-time response and interactive narrative provide a game-like experience in two systems: Boom Chameleon for evaluating virtual models and StyleCam for developing online product marketing and advertising.
Tracking contact and free gesture across large interactive surfaces
Authors: Paradiso Joseph A.
Published: August 2003

Built into store windows, museum exhibits, and other communal spaces, these surfaces entice even casual passersby to playfully interact with information---and each other---by knocking on the glass.
Interactive robot theatre
Authors: Breazeal Cynthia , Brooks Andrew , Gray Jesse , Hancher Matt , McBean John , Stiehl Dan , Strickon Joshua
Published: August 2003

Engaging a human audience through sight, sound, scent, and touch while following a loosely constrained storyline, the Public Anemone and fellow autonomous characters are let loose to entertain---sociably.
Siren songs and swan songs debugging with music
Authors: Vickers Paul , Alty James L.
Published: August 2003

Program execution behavior can be mapped to a structured musical framework that helps locate and diagnose software errors.
Moving vs. inviting software agents
Authors: Maamar Zakaria , Labbé Paul
Published: August 2003

What is the best strategy to adopt?
A Chinese dictionary construction algorithm for information retrieval
Authors: Jin Honglan , Wong Kam-Fai
Published: August 2003

In this article we propose a method for constructing, from raw Chinese text, a statistics-based automatic dictionary. The method makes use of local statistical information (i.e., data within a document) to identify and discard repeated string patterns, which, at an earlier stage, were substrings of legitimate words. Global statistical information (which exists throughout the entire corpus) and contextual constraints are then used for further filtering. The method can be used to alleviate the out-of-vocabulary (OOV) problem, which is commonly found in dictionary-based natural language information-processing applications, e.g., word segmentation. It can handle text corpora dynamically and, further, it does not impose any strict requirements on the size and quality of the training corpora. Based on our method, we constructed Chinese dictionaries from different Chinese corpora. We then applied the words in the constructed dictionaries to indexing in information retrieval (IR). Retrieval performance using such indexes was compared to the same, but based on indexes produced by static dictionaries. Three Chinese corpora using various character-encoding schemes and language styles were used in the experiments. The results show that retrieval using indexes based on the constructed dictionary is effective. This implies that fully automatic Chinese dictionary construction based on dynamic data sources, e.g., from the Internet, for the purposes of IR is feasible. Drawing on the experiment, we were able to make some interesting observations: (1) using only a portion of a dictionary is enough to produce good retrieval performance, e.g., a dictionary consisting of only the 500 highest-frequency strings extracted from the NTCIR 2 Chinese corpus produced as good a retrieval result as using a more complete dictionary with over 100K entries; and (2) complete word segmentation is not a strict requirement for achieving practical information retrieval.
Combining character-based bigrams with word-based bigrams in contextual postprocessing for Chinese script recognition
Authors: Li Yuanxiang , Ding Xiaoqing , Tan Chew Lim
Published: August 2003

It is crucial to use contextual information to improve the recognition accuracy of Chinese script in an offline, handwritten Chinese character-recognition system. However, with the increase in the number of candidates given by a character recognizer, contextual postprocessing using a word-based bigram is time-consuming. This article presents a novel contextual postprocessing method that integrates character-based bigram postprocessing with word-based bigram postprocessing in light of the complementary action between Chinese characters and Chinese words. On the basis of isolated character recognition, character-based bigram postprocessing using a forward-backward search is first executed on a big candidate set, which improves both the accuracy and efficiency of the candidate set (the cumulative accuracy of the top ten candidates is greatly boosted). Then, to further improve accuracy, word-based bigram postprocessing (WBP) is executed on a small candidate set. This method obtains high accuracy while paying attention to postprocessing speed at the same time. Experimental results for three Chinese scripts (about 66,000 characters in total) demonstrate the effectiveness of our method: character-based bigram postprocessing improves accuracy from 81.58% to 94.50%, and the cumulative accuracy of the top ten candidates rises from 94.33% to 98.25%. After WBP, 95.75% accuracy is achieved, which is equivalent to the accuracy of WBP executed on a big candidate set. However, our method is more than 100 times faster than that of WBP.
ACETAF
Authors: Eble Ingo , Neher Markus
Published: August 2003

This article presents methods for practical computation of verified bounds for Taylor coefficients of analytic functions. These bounds are constructed from Cauchy's estimate and from some of its modifications. Interval arithmetic is used to obtain rigorous results.
Algorithm 824
Authors: Cools Ronald , Haegemans Ann
Published: August 2003

CUBPACK aims to offer a collection of re-usable code for automatic
n
-dimensional (
n
≥ 1) numerical integration of functions over a collection of regions, i.e., quadrature and cubature. The current version allows this region to consist of a union of
n
-simplices and
n
-parellellepids. The framework of CUBPACK is described as well as its user interface. The functionality of several well known routines is embedded. New features include integration algorithms using the ϵ-algorithm for extrapolation for regions other than triangles and the implementation of a new type of subdivision for 3-cubes.
An adaptive numerical cubature algorithm for simplices
Authors: Genz Alan , Cools Ronald
Published: August 2003

A globally adaptive algorithm for numerical cubature of a vector of functions over a collection of
n
-dimensional simplices is described. The algorithm is based on a subdivision strategy that chooses for subdivision at each stage the subregion (of the input simplices) with the largest estimated error. This subregion is divided into two, three or four equal volume subregions by cutting selected edges. These edges are selected using information about the smoothness of the integrands in the edge directions. The algorithm allows a choice from several embedded cubature rule sequences for approximate integration and error estimation. A Fortran 95 implementation as a part of CUBPACK is also discussed. Testing of the algorithm is described.
Algorithm 825
Authors: Shellman Spencer , Sikorski K.
Published: August 2003

We present the BEDFix (Bisection Envelope Deep-cut Fixed point) algorithm for the problem of approximating a fixed point of a function of two variables. The function must be Lipschitz continuous with constant 1 with respect to the infinity norm; such functions are commonly found in economics and game theory. The computed approximation satisfies a residual criterion given a specified error tolerance. The BEDFix algorithm improves the BEFix algorithm presented in Shellman and Sikorski [2002] by utilizing "deep cuts," that is, eliminating additional segments of the feasible domain which cannot contain a fixed point. The upper bound on the number of required function evaluations is the same for BEDFix and BEFix, but our numerical tests indicate that BEDFix significantly improves the average-case performance. In addition, we show how BEDFix may be used to solve the absolute criterion fixed point problem with significantly better performance than the simple iteration method, when the Lipschitz constant is less than but close to 1. BEDFix is highly efficient when used to compute residual solutions for bivariate functions, having a bound on function evaluations that is twice the logarithm of the reciprocal of the tolerance. In the tests described in this article, the number of evaluations performed by the method averaged 31 percent of this worst-case bound. BEDFix works for nonsmooth continuous functions, unlike methods that require gradient information; also, it handles functions with minimum Lipschitz constants equal to 1, whereas the complexity of simple iteration approaches infinity as the minimum Lipschitz constant approaches 1. When BEDFix is used to compute absolute criterion solutions, the worst-case complexity depends on the logarithm of the reciprocal of 1-q, where q is the Lipschitz constant, as well as on the logarithm of the reciprocal of the tolerance.
Algorithm 826
Authors: Fahey Mark R.
Published: August 2003

A code for computing the eigenvalues of a complex Hessenberg matrix is presented. This code computes the Schur decomposition of a complex Hessenberg matrix. Together with existing ScaLAPACK routines, the eigenvalues of dense complex matrices can be directly computed using a parallel
QR
algorithm.This parallel complex Schur decomposition routine was developed to fill a void in the ScaLAPACK library and was based on the parallel real Schur decomposition routine already in ScaLAPACK. The real-arithmetic version was appropriately modified to make it work with complex arithmetic and implement a complex multiple bulge
QR
algorithm. This also required the development of new auxiliary routines that perform essential operations for the complex Schur decomposition, and that will provide additional linear algebra computation capability to the parallel numerical library community.
Algorithm 827
Authors: Baglama J. , Calvetti D. , Reichel L.
Published: August 2003

irbleigs is a MATLAB program for computing a few eigenvalues and associated eigenvectors of a sparse Hermitian matrix of large order
n
. The matrix is accessed only through the evaluation of matrix-vector products. Working space of only a few
n
-vectors is required. The program implements a restarted block-Lanczos method. Judicious choices of acceleration polynomials make it possible to compute approximations of a few of the largest eigenvalues, a few of the smallest eigenvalues, or a few eigenvalues in the vicinity of a user-specified point on the real axis. irbleigs also can be applied to certain large generalized eigenproblems as well as to the computation of a few nearby singular values and associated right and left singular vectors of a large general matrix.
We can't afford it!
Authors: Torenvliet Gerard
Published: August 2003

When terminology gets people riled up, you know that something lurks beneath the surface. In this
Whiteboard
, Gerard Torenvliet describes and decries the loss of meaning that the term
affordance
has suffered over the years, as widely read authors have redefined it and as readers and users have muddied it. Gerard argues that clarity in usability work---and the ability to participate in requirements definition---depend on our using the term's original meaning, and he urges us to reclaim it.
Evaluating usability methods
Authors: Wixon Dennis
Published: August 2003

Practitioners who deal in the business world must find ways to keep up-to-date with best practices in the field and must apply them to their work in cost-effective ways. Research should help to define best practices, but often the worlds of research and of practice can seem too dichotomous. Recently, for instance, the fields of usability and user-centered design generally have seen considerable controversy about the relative effectiveness of different methodologies. In this column, Dennis Wixon argues that we need to look at whether we are evaluating methods by the appropriate criteria. He considers the growing body of literature on evaluation of methods unhelpful, or even irrelevant, to the practitioner. He argues that consideration of the factors that determine success of usability efforts in product development organizations will fundamentally change the terms of the debate. ---David A. Siegel
Feature specification and automated conflict detection
Authors: Felty Amy P. , Namjoshi Kedar S.
Published: August 2003

Large software systems, especially in the telecommunications field, are often specified as a collection of features. We present a formal specification language for describing features, and a method of automatically detecting conflicts ("undesirable interactions") amongst features at the
specification
stage. Conflict detection at this early stage can help prevent costly and time consuming problem fixes during implementation. Features are specified using temporal logic; two features conflict essentially if their specifications are mutually inconsistent under axioms about the underlying system behavior. We show how this inconsistency check may be performed automatically with existing model checking tools. In addition, the model checking tools can be used to provide witness scenarios, both when two features conflict as well as when the features are mutually consistent. Both types of witnesses are useful for refining the specifications. We have implemented a conflict detection tool, FIX (Feature Interaction eXtractor), which uses the model checker COSPAN for the inconsistency check. We describe our experience in applying this tool to a collection of telecommunications feature specifications obtained from the Telcordia (Bellcore) standards. Using FIX, we were able to detect most known interactions and some new ones, fully automatically, in a few hours processing time.
Flexible consistency checking
Authors: Nentwich Christian , Emmerich Wolfgang , Finkelsteiin Anthony , Ellmer Ernst
Published: August 2003

The problem of managing the consistency of heterogeneous, distributed software engineering documents is central to the development of large and complex systems. We show how this problem can be addressed using xlinkit, a lightweight framework for consistency checking that leverages standard Internet technologies. xlinkit provides flexibility, strong diagnostics, and support for distribution and document heterogeneity. We use xlinkit in a comprehensive case study that demonstrates how design, implementation and deployment information of an Enterprise JavaBeans system can be checked for consistency, and rechecked incrementally when changes are made.
Higher-order architectural connectors
Authors: Lopes Antónia , Wermelinger Michel , Fiadeiro José Luiz
Published: August 2003

We develop a notion of higher-order connector towards supporting the systematic construction of architectural connectors for software design. A higher-order connector takes connectors as parameters and allows for services such as security protocols and fault-tolerance mechanisms to be superposed over the interactions that are handled by the connectors passed as actual arguments. The notion is first illustrated over CommUnity, a parallel program design language that we have been using for formalizing aspects of architectural design. A formal, algebraic semantics is then presented which is independent of any Architectural Description Language. Finally, we discuss how our results can impact software design methods and tools.
A brief history of just-in-time
Authors: Aycock John
Published: August 2003

Software systems have been using "just-in-time" compilation (JIT) techniques since the 1960s. Broadly, JIT compilation includes any translation performed dynamically, after a program has started execution. We examine the motivation behind JIT compilation and constraints imposed on JIT compilation systems, and present a classification scheme for such systems. This classification emerges as we survey forty years of JIT work, from 1960--2000.
The many faces of publish/subscribe
Authors: Eugster Patrick Th. , Felber Pascal A. , Guerraoui Rachid , Kermarrec Anne-Marie
Published: August 2003

Well adapted to the loosely coupled nature of distributed interaction in large-scale applications, the publish/subscribe communication paradigm has recently received increasing attention. With systems based on the publish/subscribe interaction scheme, subscribers register their interest in an event, or a pattern of events, and are subsequently asynchronously notified of events generated by publishers. Many variants of the paradigm have recently been proposed, each variant being specifically adapted to some given application or network model. This paper factors out the common denominator underlying these variants: full decoupling of the communicating entities in time, space, and synchronization. We use these three decoupling dimensions to better identify commonalities and divergences with traditional interaction paradigms. The many variations on the theme of publish/subscribe are classified and synthesized. In particular, their respective benefits and shortcomings are discussed both in terms of interfaces and implementations.
Requirements interaction management
Authors: Robinson William N. , Pawlowski Suzanne D. , Volkov Vecheslav
Published: August 2003

Requirements interaction management (RIM) is the set of activities directed toward the discovery, management, and disposition of critical relationships among sets of requirements, which has become a critical area of requirements engineering. This survey looks at the evolution of supporting concepts and their related literature, presents an issues-based framework for reviewing processes and products, and applies the framework in a review of RIM state-of-the-art. Finally, it presents seven research projects that exemplify this emerging discipline.
Product metrics for object-oriented systems
Authors: Purao Sandeep , Vaishnavi Vijay
Published: August 2003

We survey metrics proposed for object-oriented systems, focusing on product metrics. The survey is intended for the purposes of understanding, classifying, and analyzing ongoing research in object-oriented metrics. The survey applies fundamental measurement theory to artifacts created by development activities. We develop a mathematical formalism that captures this perspective clearly, giving appropriate attention to the peculiarities of the object-oriented system developmenr process. Consistent representation of the available metrics, following this mathematical formalism, shows that current research in this area contains varying coverage of different products and their properties at different development stages. The consistent representation also facilitates several analyses including aggregation across metrics, usage across metrics, equivalent formulation of metrics by multiple researchers, and exploitation of traditional metrics for object-oriented metrics. We also trace the chronological development of research in this area, and uncover gaps that suggest opportunities for future research.
Developing a bidding agent for multiple heterogeneous auctions
Authors: Anthony Patricia , Jennings Nicholas R.
Published: August 2003

Due to the proliferation of online auctions, there is an increasing need to monitor and bid in multiple auctions in order to procure the best deal for the desired good. To this end, this paper reports on the development of a heuristic decision making framework that an autonomous agent can exploit to tackle the problem of bidding across multiple auctions with varying start and end times and with varying protocols (including English, Dutch and Vickrey). The framework is flexible, configurable, and enables the agent to adopt varying tactics and strategies that attempt to ensure that the desired item is delivered in a manner consistent with the user's preferences. Given this large space of possibilities, we employ a genetic algorithm to search (offline) for effective strategies in common classes of environment. The strategies that emerge from this evolution are then codified into the agent's reasoning behaviour so that it can select the most appropriate strategy to employ in its prevailing circumstances. The proposed framework has been implemented in a simulated marketplace environment and its effectiveness has been empirically demonstrated.
Location management for mobile commerce applications in wireless Internet environment
Authors: Varshney Upkar
Published: August 2003

With recent advances in devices, middleware, applications and networking infrastructure, the wireless Internet is becoming a reality. We believe that some of the major drivers of the wireless Internet will be emerging mobile applications such as mobile commerce. Although many of these are futuristic, some applications including user-and location-specific mobile advertising, location-based services, and mobile financial services are beginning to be commercialized. Mobile commerce applications present several interesting and complex challenges including location management of products, services, devices, and people. Further, these applications have fairly diverse requirements from the underlying wireless infrastructure in terms of location accuracy, response time, multicast support, transaction frequency and duration, and dependability. Therefore, research is necessary to address these important and complex challenges. In this article, we present an integrated location management architecture to support the diverse location requirements of m-commerce applications. The proposed architecture is capable of supporting a range of location accuracies, wider network coverage, wireless multicast, and infrastructure dependability for m-commerce applications. The proposed architecture can also support several emerging mobile applications. Additionally, several interesting research problems and directions in location management for wireless Internet applications are presented and discussed.
Estimating frequency of change
Authors: Cho Junghoo , Garcia-Molina Hector
Published: August 2003

Many online data sources are updated autonomously and independently. In this article, we make the case for estimating the change frequency of data to improve Web crawlers, Web caches and to help data mining. We first identify various scenarios, where different applications have different requirements on the accuracy of the estimated frequency. Then we develop several "frequency estimators" for the identified scenarios, showing analytically and experimentally how precise they are. In many cases, our proposed estimators predict change frequencies much more accurately and improve the effectiveness of applications. For example, a Web crawler could achieve 35% improvement in "freshness" simply by adopting our proposed estimator.
Logical and physical design issues for smart card databases
Authors: Bolchini Cristiana , Salice Fabio , Schreiber Fabio A. , Tanca Letizia
Published: August 2003

The design of very small databases for smart cards and for portable embedded systems is deeply constrained by the peculiar features of the physical medium. We propose a joint approach to the logical and physical database design phases and evaluate several data structures with respect to the performance, power consumption, and endurance parameters of read/program operations on the Flash-EEPROM storage medium.
Query-independent evidence in home page finding
Authors: Upstill Trystan , Craswell Nick , Hawking David
Published: August 2003

Hyperlink recommendation evidence, that is, evidence based on the structure of a web's link graph, is widely exploited by commercial Web search systems. However there is little published work to support its popularity. Another form of query-independent evidence, URL-type, has been shown to be beneficial on a home page finding task. We compared the usefulness of these types of evidence on the home page finding task, combined with both content and anchor text baselines. Our experiments made use of five query sets spanning three corpora---one enterprise crawl, and the WT10g and VLC2 Web test collections.We found that, in optimal conditions, all of the query-independent methods studied (in-degree, URL-type, and two variants of PageRank) offered a better than random improvement on a content-only baseline. However, only URL-type offered a better than random improvement on an anchor text baseline. In realistic settings, for either baseline, only URL-type offered consistent gains. In combination with URL-type the anchor text baseline was more useful for finding popular home pages, but URL-type with content was more useful for finding randomly selected home pages. We conclude that a general home page finding system should combine evidence from document content, anchor text, and URL-type classification.
Variable-sample methods for stochastic optimization
Authors: Homem-De-Mello Tito
Published: August 2003

In this article we discuss the application of a certain class of Monte Carlo methods to stochastic optimization problems. Particularly, we study
variable-sample
techniques, in which the objective function is replaced,
at each iteration
, by a sample average approximation. We first provide general results on the
schedule
of sample sizes, under which variable-sample methods yield consistent estimators as well as bounds on the estimation error. Because the convergence analysis is performed pathwisely, we are able to obtain our results in a flexible setting, which requires mild assumptions on the distributions and which includes the possibility of using different sampling distributions along the algorithm. We illustrate these ideas by studying a modification of the well-known
pure random search
method, adapting it to the variable-sample scheme, and show conditions for convergence of the algorithm. Implementation issues are discussed and numerical results are presented to illustrate the ideas.
Discrete-event simulation optimization using ranking, selection, and multiple comparison procedures
Authors: Swisher James R. , Jacobson Sheldon H. , Yücesan Enver
Published: August 2003

An important use for discrete-event simulation models lies in comparing and contrasting competing design alternatives without incurring any physical costs. This article presents a survey of the literature for two widely used classes of statistical methods for selecting the best design from among a finite set of
k
alternatives: ranking and selection (R&S) and multiple comparison procedures (MCPs). A comprehensive survey of each topic is presented along with a summary of recent unified R&S-MCP approaches. Procedures are recommended based on their statistical efficiency and ease of application; guidelines for procedure application are offered.
A combined procedure for optimization via simulation
Authors: Pichitlamken Juta , Nelson Barry L.
Published: August 2003

We propose an optimization-via-simulation algorithm for use when the performance measure is estimated via a stochastic, discrete-event simulation, and the decision variables may be subject to deterministic linear integer constraints. Our approach---which consists of a global guidance system, a selection-of-the-best procedure, and local improvement---is globally convergent under very mild conditions.
Two-timescale simultaneous perturbation stochastic approximation using deterministic perturbation sequences
Authors: Bhatnagar Shalabh , Fu Michael C. , Marcus Steven I. , Wang I-Jeng
Published: August 2003

Simultaneous perturbation stochastic approximation (SPSA) algorithms have been found to be very effective for high-dimensional simulation optimization problems. The main idea is to estimate the gradient using simulation output performance measures at only
two
settings of the
N
-dimensional parameter vector being optimized rather than at the
N
+ 1 or 2
N
settings required by the usual one-sided or symmetric difference estimates, respectively. The two settings of the parameter vector are obtained by
simultaneously
changing the parameter vector in each component direction using
random
perturbations. In this article, in order to enhance the convergence of these algorithms, we consider deterministic sequences of perturbations for two-timescale SPSA algorithms. Two constructions for the perturbation sequences are considered: complete lexicographical cycles and much shorter sequences based on normalized Hadamard matrices. Recently, one-simulation versions of SPSA have been proposed, and we also investigate these algorithms using deterministic sequences. Rigorous convergence analyses for all proposed algorithms are presented in detail. Extensive numerical experiments on a network of
M
/
G
/1 queues with feedback indicate that the deterministic sequence SPSA algorithms perform significantly better than the corresponding randomized algorithms.
Risks and challenges of component-based software development
Authors: Vitharana Padmal
Published: August 2003

Component developers, application assemblers, and customers must all know CBSD advantages and disadvantages before developing components and component-based applications.
Understanding email interaction increases organizational productivity
Authors: Jackson Thomas W. , Dawson Ray , Wilson Darren
Published: August 2003

To minimize the effect of email interruption on employee productivity, limit the frequency of new-email alerts (silence them, too), make it easier to assess each message's importance, and remove the reply-to-all facility.
Relationship quality
Authors: Russell Bruce , Chatterjee Sangit
Published: August 2003

Software service firms that want to win more business, generate referrals, and ensure timely payment of their bills manage the quality of their client relationships, not just of the systems they develop.
Enemy at the gate
Authors: Whitman Michael E.
Published: August 2003

A firm can build more effective security strategies by identifying and ranking the severity of potential threats to its IS efforts.
How a silver bullet may lose its shine
Authors: de Vreede Gert-Jan , Davison Robert M. , Briggs Robert O.
Published: August 2003

One of the best ways to realize the potential of group support systems is to learn from its failed implementations.
Software reuse strategies and component markets
Authors: Ravichandran T. , Rothenberger Marcus A.
Published: August 2003

Black-box reuse with component markets could be the silver bullet solution that makes software reuse a reality, and advances software development to a robust industrial process---but only if market makers address the growing pains plaguing this immature industry.
CMM in uncertain environments
Authors: Zhiying Zhou
Published: August 2003

Injecting ancient Chinese philosophy into modern science and technology provides a unique perspective on uncertainty and rapid change.
The discipline of Internet forensics
Authors: Berghel Hal
Published: August 2003

A well-defined field of study and practice has evolved as a result of network hacker activity.
A mugwump's-eye view of Web work
Authors: Glass Robert L.
Published: August 2003

Choosing a point of entry into a contemporary software development debate.
Voting and technology
Authors: Dill David L. , Schneier Bruce , Simons Barbara
Published: August 2003

Paperless voting machines threaten the integrity of democratic process by what they
don't
do.
Extracting library-based Java applications
Authors: Tip Frank , Sweeney Peter F. , Laffra Chris
Published: August 2003

Reducing the size of Java applications by creating an application extractor.
Post-pass compaction techniques
Authors: De Bus Bruno , Kästner Daniel , Chanet Dominique , Van Put Ludo , De Sutter Bjorn
Published: August 2003

Seeking to resolve many of the problems related to code size in traditional program development environments.
Mixed-width instruction sets
Authors: Krishnaswamy Arvind , Gupta Rajiv
Published: August 2003

Encoding a program's computations to reduce memory and power consumption without sacrificing performance.
Cold code decompression at runtime
Authors: Debray Saumya , Evans William S.
Published: August 2003

Using a software-based technique to dynamically decompress selected code fragments during program execution.
Grammar-based compression of interpreted code
Authors: Evans William S. , Fraser Christopher W.
Published: August 2003

Automatically designing and implementing compact interpretable bytecodes.
Third generation and beyond wireless systems
Authors: Nicopolitidis P. , Papadimitriou G. I. , Obaidat M. S. , Pomportsis A. S.
Published: August 2003

Exploring the capabilities of increased data transmission rates.
BASE
Authors: Castro Miguel , Rodrigues Rodrigo , Liskov Barbara
Published: August 2003

Software errors are a major cause of outages and they are increasingly exploited in malicious attacks. Byzantine fault tolerance allows replicated systems to mask some software errors but it is expensive to deploy. This paper describes a replication technique, BASE, which uses abstraction to reduce the cost of Byzantine fault tolerance and to improve its ability to mask software errors. BASE reduces cost because it enables reuse of off-the-shelf service implementations. It improves availability because each replica can be repaired periodically using an abstract view of the state stored by correct replicas, and because each replica can run distinct or nondeterministic service implementations, which reduces the probability of common mode failures. We built an NFS service where each replica can run a different off-the-shelf file system implementation, and an object-oriented database where the replicas ran the same, nondeterministic implementation. These examples suggest that our technique can be used in practice---in both cases, the implementation required only a modest amount of new code, and our performance results indicate that the replicated services perform comparably to the implementations that they reuse.
New directions in traffic measurement and accounting
Authors: Estan Cristian , Varghese George
Published: August 2003

Accurate network traffic measurement is required for accounting, bandwidth provisioning and detecting DoS attacks. These applications see the traffic as a collection of flows they need to measure. As link speeds and the number of flows increase, keeping a counter for each flow is too expensive (using SRAM) or slow (using DRAM). The current state-of-the-art methods (Cisco's sampled NetFlow), which count periodically sampled packets are slow, inaccurate and resource-intensive. Previous work showed that at different granularities a small number of "heavy hitters" accounts for a large share of traffic. Our paper introduces a paradigm shift by concentrating the measurement process on large flows only---those above some threshold such as 0.1% of the link capacity.We propose two novel and scalable algorithms for identifying the large flows:
sample and hold
and
multistage filters
, which take a constant number of memory references per packet and use a small amount of memory. If
M
is the available memory, we show analytically that the errors of our new algorithms are proportional to 1/
M
; by contrast, the error of an algorithm based on classical sampling is proportional to 1/√
M
, thus providing much less accuracy for the same amount of memory. We also describe optimizations such as
early removal
and
conservative update
that further improve the accuracy of our algorithms, as measured on real traffic traces, by an order of magnitude. Our schemes allow a new form of accounting called
threshold accounting
in which only flows above a threshold are charged by usage while the rest are charged a fixed fee. Threshold accounting generalizes usage-based and duration based pricing.
An evaluation of speculative instruction execution on simultaneous multithreaded processors
Authors: Swanson Steven , McDowell Luke K. , Swift Michael M. , Eggers Susan J. , Levy Henry M.
Published: August 2003

Modern superscalar processors rely heavily on speculative execution for performance. For example, our measurements show that on a 6-issue superscalar, 93% of committed instructions for SPECINT95 are speculative. Without speculation, processor resources on such machines would be largely idle. In contrast to superscalars, simultaneous multithreaded (SMT) processors achieve high resource utilization by issuing instructions from multiple threads every cycle. An SMT processor thus has two means of hiding latency: speculation and multithreaded execution. However, these two techniques may conflict; on an SMT processor, wrong-path speculative instructions from one thread may compete with and displace useful instructions from another thread. For this reason, it is important to understand the trade-offs between these two latency-hiding techniques, and to ask whether multithreaded processors should speculate differently than conventional superscalars.This paper evaluates the behavior of instruction speculation on SMT processors using both multiprogrammed (SPECINT and SPECFP) and multithreaded (the Apache Web server) workloads. We measure and analyze the impact of speculation and demonstrate how speculation on an 8-context SMT differs from superscalar speculation. We also examine the effect of speculation-aware fetch and branch prediction policies in the processor. Our results quantify the extent to which (1) speculation is critical to performance on a multithreaded processor because it ensures an ample supply of parallelism to feed the functional units, and (2) SMT actually enhances the effectiveness of speculative execution, compared to a superscalar processor by reducing the impact of branch misprediction. Finally, we quantify the impact of both hardware configuration and workload characteristics on speculation's usefulness and demonstrate that, in nearly all cases, speculation is beneficial to SMT performance.
Extracellular Superoxide Dismutase Polymorphism in Mice
Authors: Pierce Anson , Whitlark Jason , Dory Ladislav
Published: August 2003

Objective—

In this study, we describe a previously unrecognized murine extracellular superoxide dismutase (ecSOD) allele and examine its distribution among various strains and its effect on the ecSOD phenotype.

Methods and Results—

Polymerase chain reaction analysis of genomic and cDNA from apolipoprotein E/LDLR
−/−
mice indicates the presence of 2 distinct transcripts for this enzyme independent of the extent of atherosclerosis or age. Sequencing and genotyping analyses reveal the presence of 2 alleles for ecSOD. One is a short variant with a 10-base pair deletion in the 3′UTR, accompanied by a single nucleotide substitution (position 61) found in the 129P3/J strain of mice. By contrast, all other strains examined carry the long form. Both free and heparin-releasable ecSOD activities in the 129P3/J strain are more than 3-fold higher than those in the C57Bl/6 mice. Corresponding differences in plasma enzyme mass are observed by immunoblotting. A clear allele dose effect can be observed in F2 hybrids of these 2 strains; free and total ecSOD activities in mice homozygous for the short allele are twice those of mice homozygous for the long allele, with the heterozygote values in between.

Conclusions—

These data clearly demonstrate the allele-specific effects on the ecSOD phenotype independent of other strain-specific factors and underline the need for backcrossing of genetically modified mice.