bluuebunny/crossref_metadata_2025 huggingface dataset:
Conditions on input vectors for consensus solvability in asynchronous distributed systems
Authors: Mostefaoui Achour , Rajsbaum Sergio , Raynal Michel
Published: February 2004

This article introduces and explores the
condition-based
approach to solve the consensus problem in asynchronous systems. The approach studies
conditions
that identify sets of input vectors for which it is possible to solve consensus despite the occurrence of up to
f
process crashes. The first main result defines
acceptable
conditions and shows that these are exactly the conditions for which a consensus protocol exists. Two examples of realistic acceptable conditions are presented, and proved to be maximal, in the sense that they cannot be extended and remain acceptable. The second main result is a generic consensus shared-memory protocol for any acceptable condition. The protocol always guarantees agreement and validity, and terminates (at least) when the inputs satisfy the condition with which the protocol has been instantiated, or when there are no crashes. An efficient version of the protocol is then designed for the message passing model that works when
f
<
n
/2, and it is shown that no such protocol exists when
f
≥
n
/2. It is also shown how the protocol's safety can be traded for its liveness.
On the generating sequences of regular languages on
k
symbols
Authors: Béal Marie-Pierre , Perrin Dominique
Published: February 2004

The main result is a characterization of the generating sequences of the length of words in a regular language on
k
symbols. We say that a sequence
s
of integers is regular if there is a finite graph
G
with two vertices
i, t
such that
s

n

is the number of paths of length
n
from
i
to
t
in
G
. Thus the generating sequence of a regular language is regular. We prove that a sequence
s
is the generating sequence of a regular language on
k
symbols if and only if both sequences
s
= (
s

n

)

n
≥0

and
t
= (
k

n

−
s

n

)

n
≥0

are regular.
Using data mining to profile TV viewers
Authors: Spangler William E. , Gal-Or Mordechai , May Jerrold H.
Published: February 2004

Mining thousands of viewing choices and millions of patterns, advertisers and TV networks identify household characteristics, tastes, and desires to create and deliver custom targeted advertising.
Mobile data communications in China
Authors: Yan Xu
Published: February 2004

Despite hundreds of millions of paying mobile subscribers and enormous potential for many more, the key to prosperity is enticing them to pay for extra services like text messaging and IP telephony.
A relationship perspective on IT outsourcing
Authors: Kishore Rajiv , Rao H. R. , Nam K. , Rajagopalan S. , Chaudhury A.
Published: February 2004

A longitudinal study at four companies provides valuable insights about the evolution of IT outsourcing relationships.
A method for developing dimensional data marts
Authors: Chenoweth Tim , Schuff David , St. Louis Robert
Published: February 2004

Decision-oriented dimensional data marts are fundamentally different than transaction-oriented relational databases. A distinctive methodology and a different set of tools are required for their effective development.
The relationship between distributed systems and open software development
Authors: Bayrak Coskun , Davis Chad
Published: February 2004

The behavior and performance of OSD is best appreciated as a distributed system.
Malware month
Authors: Berghel Hal
Published: February 2004

August 2003: SoBig, W32/Blaster, and the malware month of the millennium.
Standards insecurity
Authors: Mercuri Rebecca T.
Published: February 2004

Standards can provide an important component in the computer security environment but they should not be relied on blindly.
Understanding mobile handheld device use and adoption
Authors: Sarker Suprateek , Wells John D.
Published: February 2004

Without device adoption, there is no mobile commerce.
Information requirement elicitation in mobile commerce
Authors: Sun Jun
Published: February 2004

Using an interactive approach to facilitate information searching for mobile users.
Interface design for mobile commerce
Authors: Lee Young Eun , Benbasat Izak
Published: February 2004

Understanding the unique characteristics of m-commerce to enhance and improve the user interface.
Understanding usability in mobile commerce
Authors: Venkatesh Viswanath , Ramesh V. , Massey Anne P.
Published: February 2004

Ramifications for wireless design: 'e' ≠ 'm'.
Designing mobile commerce applications
Authors: Tarasewich Peter
Published: February 2004

Exploring the importance and untangling the complexity of the notion of context.
Managing the transition to bricks and clicks
Authors: Ranganathan C. , Goode Vern , Ramaprasad Arkalgud
Published: February 2004

Egghead, a brick-and-mortar computer retailer, with stores across 200 locations, abandoned its brick establishments to become a pure Internet set-up, Egghead.com.

Charles Schwab was quick to react to the strategies of E*Trade and other competitors and moved its brokerage services to the Web. It gradually expanded its Web services to many areas, integrated its offline and online operations and became a brick-and-click set-up.

Through effective use of the Internet, UPS has been able to offer all of its services on the Web, as well as extend them. Apart from offering Web-based package tracking and delivery confirmation services, UPS offers document exchange service through which its business clients can transmit documents over the Net.
An analysis of XML database solutions for the management of MPEG-7 media descriptions
Authors: Westermann Utz , Klas Wolfgang
Published: February 2004

MPEG-7 constitutes a promising standard for the description of multimedia content. It can be expected that a lot of applications based on MPEG-7 media descriptions will be set up in the near future. Therefore, means for the adequate management of large amounts of MPEG-7-compliant media descriptions are certainly desirable. Essentially, MPEG-7 media descriptions are XML documents following media description schemes defined with a variant of XML Schema. Thus, it is reasonable to investigate current database solutions for XML documents regarding their suitability for the management of these descriptions. In this paper, we motivate and present critical requirements for the management of MPEG-7 media descriptions and the resulting consequences for XML database solutions. Along these requirements, we discuss current state-of-the-art database solutions for XML documents. The analysis and comparison unveil the limitations of current database solutions with respect to the management of MPEG-7 media descriptions and point the way to the need for a new generation of XML database solutions.
A survey of Web cache replacement strategies
Authors: Podlipnig Stefan , Böszörmenyi Laszlo
Published: February 2004

Web caching is an important technique to scale the Internet. One important performance factor of Web caches is the replacement strategy. Due to specific characteristics of the World Wide Web, there exist a huge number of proposals for cache replacement. This article proposes a classification for these proposals that subsumes prior classifications. Using this classification, different proposals and their advantages and disadvantages are described. Furthermore, the article discusses the importance of cache replacement strategies in modern proxy caches and outlines potential future research topics.
Attack of the killer virus!
Authors: Fowler Dennis
Published: February 2004

Though more than 600 million people worldwide use the Internet, it takes only one virus writer to make just about all of us miserable. Like a single stray neutron in a critical mass of plutonium, a lone virus can trigger a chain reaction that spews thousands of copies from desktop to desktop. Last summer's aptly named SoBig virus was an all-too-real example of this danger. "At [SoBig.F's] peak, one out of 17 e-mails that we were processing was a copy of the…virus," says Josh White of U.S.-based e-mail security group MessageLabs. "Certainly we haven't seen numbers like this before." At that time AOL scanned 40.5 million e-mails and found SoBig.F in half of them. In fact, SoBig accounted for 98 percent of all viruses then circulating---all this from a single virus-writing miscreant. How can we possibly hope to stop the inevitable legions of similarly determined troublemakers? Better get used to it: There are no easy solutions to the virus problem.
Upsetting the apple cart
Authors: Fowler Dennis
Published: February 2004

There's nothing new about disruptive technology. The automobile did a number on the buggy-whip industry and sure sent a lot of horses out to pasture. Commercial air travel relegated passenger trains to the background. Maybe the dot-com bubble burst, but the technology underlying it continues to churn things up.
Just one slice of innovation, please
Authors: Schindler Esther
Published: February 2004

We all like to think that humans are hungry for innovation, anxious to find revolutionary products that improve the way we live and work. Recently, though, I've begun to wonder if that's true. I think we want technology to enhance the quality of life, but not actually to change us. Or, at least, the revolution has to arrive packaged in an already-acceptable form, nice and convenient, so we don't have to bother learning anything new.
Why the newspaper has a great user interface
Authors: Treese Win
Published: February 2004

While reading
The Wall Street Journal
this morning, I found myself thinking about the flood of information I get electronically. In many ways, reading the newspaper is still a more pleasant experience than sorting through (virtual) piles of e-mail, newsgroups, online forums, Web sites, and other Internet information sources. Can more of the lessons of newspaper design be applied to online information tools?
ThreadMentor
Authors: Carr Steve , Mayo Jean , Shene Ching-Kuang
Published: February 2004

ThreadMentor is a multiplatform pedagogical tool designed to ease the difficulty in teaching and learning multithreaded programming. It consists of a C++ class library and a visualization system. The class library supports many thread management functions and synchronization primitives in an object-oriented way, and the visualization system is activated automatically by a user program and shows the inner working of every thread and every synchronization primitive on-the-fly. Events can also be saved for playback. In this way, students will be able to visualize the dynamic behavior of a threaded program and the interaction among threads and synchronization primitives.
WebCoM
Authors: Silva Elaine , Moreira Dilvan
Published: February 2004

The peer review, known by almost everyone in the academic world, is proposed as a method for computer science classes to improve interaction among student groups. By this method, groups of students publish their assignments over the Internet using the WebCoM tool developed to support this activity. A group of fellow students reviews their work and publishes their findings (in the Internet) also using the WebCoM tool. Finally, the two groups debate their points of view in front of the class (in traditional courses) or in a chat room (in distance education courses). Debate and competition between the groups provide a chance for the students to learn more about each other's work. They also gain an opportunity to learn how to give and receive criticisms in a constructive way. This should increase the students' ability to interact and work in groups: an important skill for computer science professionals. We show how the method is applied and how it is supported by WebCoM. In addition, results from past course experiences are presented to help evaluate the method and the tool.
Analysis of predictive spatio-temporal queries
Authors: Tao Yufei , Sun Jimeng , Papadias Dimitris
Published: February 2004

Given a set of objects
S
, a spatio-temporal
window query q
retrieves the objects of
S
that will intersect the window during the (future) interval
q

T

. A
nearest neighbor query q
retrieves the objects of
S
closest to
q
during
q

T

. Given a threshold
d
, a spatio-temporal
join
retrieves the pairs of objects from two datasets that will come within distance
d
from each other during
q

T

. In this article, we present probabilistic cost models that estimate the
selectivity
of spatio-temporal window queries and joins, and the
expected distance
between a query and its nearest neighbor(s). Our models capture any query/object mobility combination (moving queries, moving objects or both) and any data type (points and rectangles) in arbitrary dimensionality. In addition, we develop specialized spatio-temporal histograms, which take into account both location and velocity information, and can be incrementally maintained. Extensive performance evaluation verifies that the proposed techniques produce highly accurate estimation on both uniform and non-uniform data.
Efficient dynamic mining of constrained frequent sets
Authors: Lakshmanan Laks V. S. , Leung Carson Kai-Sang , Ng Raymond T.
Published: February 2004

Data mining is supposed to be an iterative and exploratory process. In this context, we are working on a project with the overall objective of developing a practical computing environment for the human-centered exploratory mining of frequent sets. One critical component of such an environment is the support for the dynamic mining of constrained frequent sets of items. Constraints enable users to impose a certain focus on the mining process; dynamic means that, in the middle of the computation, users are able to (i) change (such as tighten or relax) the constraints and/or (ii) change the minimum support threshold, thus having a decisive influence on subsequent computations. In a real-life situation, the available buffer space may be limited, thus adding another complication to the problem.In this article, we develop an algorithm, called DCF, for
Dynamic Constrained Frequent-set computation
. This algorithm is enhanced with a few optimizations, exploiting a lightweight structure called a
segment support map
. It enables DCF to (i) obtain sharper bounds on the support of sets of items, and to (ii) better exploit properties of constraints. Furthermore, when handling dynamic changes to constraints, DCF relies on the concept of a
delta member generating function
, which generates precisely the sets of items that satisfy the new but not the old constraints. Our experimental results show the effectiveness of these enhancements.
Preference formulas in relational queries
Authors: Chomicki Jan
Published: February 2004

The handling of user preferences is becoming an increasingly important issue in present-day information systems. Among others, preferences are used for
information filtering and extraction
to reduce the volume of data presented to the user. They are also used to keep track of
user profiles
and formulate
policies
to improve and automate decision making.We propose here a simple, logical framework for formulating preferences as
preference formulas
. The framework does not impose any restrictions on the preference relations, and allows arbitrary operation and predicate signatures in preference formulas. It also makes the composition of preference relations straightforward. We propose a simple, natural embedding of preference formulas into relational algebra (and SQL) through a single
winnow
operator parameterized by a preference formula. The embedding makes possible the formulation of complex preference queries, for example, involving aggregation, by piggybacking on existing SQL constructs. It also leads in a natural way to the definition of further, preference-related concepts like ranking. Finally, we present general algebraic laws governing the winnow operator and its interactions with other relational algebra operators. The preconditions on the applicability of the laws are captured by logical formulas. The laws provide a formal foundation for the algebraic optimization of preference queries. We demonstrate the usefulness of our approach through numerous examples.
Path sharing and predicate evaluation for high-performance XML filtering
Authors: Diao Yanlei , Altinel Mehmet , Franklin Michael J. , Zhang Hao , Fischer Peter
Published: February 2004

XML filtering systems aim to provide fast, on-the-fly matching of XML-encoded data to large numbers of query specifications containing constraints on both structure and content. It is now well accepted that approaches using event-based parsing and Finite State Machines (FSMs) can provide the basis for highly scalable structure-oriented XML filtering systems. The XFilter system [Altinel and Franklin 2000] was the first published FSM-based XML filtering approach. XFilter used a separate FSM per path query and a novel indexing mechanism to allow all of the FSMs to be executed simultaneously during the processing of a document. Building on the insights of the XFilter work, we describe a new method, called "YFilter" that combines all of the path queries into a single Nondeterministic Finite Automaton (NFA). YFilter exploits commonality among queries by merging common prefixes of the query paths such that they are processed at most once. The resulting shared processing provides tremendous improvements in structure matching performance but complicates the handling of value-based predicates.In this article, we first describe the XFilter and YFilter approaches and present results of a detailed performance comparison of structure matching for these algorithms as well as a hybrid approach. The results show that the path sharing employed by YFilter can provide order-of-magnitude performance benefits. We then propose two alternative techniques for extending YFilter's shared structure matching with support for value-based predicates, and compare the performance of these two techniques. The results of this latter study demonstrate some key differences between shared XML filtering and traditional database query processing. Finally, we describe how the YFilter approach is extended to handle more complicated queries containing nested path expressions.
Automatic high-quality reengineering of database programs by abstraction, transformation and reimplementation
Authors: Cohen Yossi , Feldman Yishai A.
Published: February 2004

Old-generation database models, such as the indexed-sequential, hierarchical, or network models, provide record-level access to their data, with all application logic residing in the hosting program. In contrast, relational databases can perform complex operations, such as filter, aggregation, and join, on multiple records without an external specification of the record-access logic. Programs written for relational databases attempt to move as much of the application logic as possible into the database, in order to make the most of the optimizations performed internally by the database.This conceptual gap between the programming styles makes automatic high-quality translation of programs written for the older database models to the relational model difficult. It is not enough to convert just the database-access operations, since this would result in unacceptably inefficient programs. It is necessary to convert parts of the application logic from the procedural style of the hosting program (which is almost always Cobol) to the declarative style of SQL.This article describes an automatic system, called MIDAS, that performs high-quality reengineering of legacy database programs in this way. MIDAS is based on the paradigm of translation by abstraction, transformation, and reimplementation. The abstract representation is based on the Plan Calculus, with the addition of Query Graphs, introduced in this article in order to abstract the temporal behavior of database access patterns.The results of MIDAS's translation were found to be superior to those of the naive translation that only converts database-access operations in terms of readability, size of code, speed, and network data traffic. Initial industrial experience with MIDAS also demonstrates the high quality of its translations on large-scale programs.
Developing multiagent systems
Authors: Zambonelli Franco , Jennings Nicholas R. , Wooldridge Michael
Published: February 2004

Systems composed of interacting autonomous agents offer a promising software engineering approach for developing applications in complex domains. However, this
multiagent system
paradigm introduces a number of new abstractions and design/development issues when compared with more traditional approaches to software development. Accordingly, new analysis and design methodologies, as well as new tools, are needed to effectively engineer such systems. Against this background, the contribution of this article is twofold. First, we synthesize and clarify the key abstractions of agent-based computing as they pertain to agent-oriented software engineering. In particular, we argue that a multiagent system can naturally be viewed and architected as a
computational organization
, and we identify the appropriate organizational abstractions that are central to the analysis and design of such systems. Second, we detail and extend the Gaia methodology for the analysis and design of multiagent systems. Gaia exploits the aforementioned organizational abstractions to provide clear guidelines for the analysis and design of complex and open software systems. Two representative case studies are introduced to exemplify Gaia's concepts and to show its use and effectiveness in different types of multiagent system.
Network and computing research infrastructure
Authors: Aiken Robert J. , Boroumand Javad , Wolff Stephen
Published: February 2004

Return to the historical ARPANET and NSFNET model to support simultaneous application, computational, middleware, storage, and network research on the same experimental infrastructure.
Global software piracy revisited
Authors: Shin Seung Kyoon , Gopal Ram D. , Sanders G. Lawrence , Whinston Andrew B.
Published: February 2004

Determining why the roots of the disparity in national piracy levels lie beyond economics.
Trust-building measures
Authors: Luo Wenhong , Najdawi Mohammad
Published: February 2004

Health Web sites are employ a medley of trust-building approaches. But does a definitive formula exist for winning consumer trust?
RFID
Authors: McGinity Meg
Published: February 2004

Tracking the circuitous tradeoffs of potential consumer benefit versus marketer intrusiveness.
When executives code
Authors: Armour Phillip
Published: February 2004

Corporate executives are realizing that not only is managing software important, it is the essence of what they do.
Multimodal processing by finding common cause
Authors: Nock Harriet J. , Iyengar Giridharan , Neti Chalapathy
Published: February 2004

Commonalities help answer many context-aware questions that arise in human-computer interaction.
Computer vision in the interface
Authors: Turk Matthew
Published: February 2004

There are still obstacles to achieving general, robust, high-performance computer vision systems. The last decade, however, has seen significant progress in vision technologies for human-computer interaction.
Challenges in adopting speech recognition
Authors: Deng Li , Huang Xuedong
Published: February 2004

Although progress has been impressive, there are still several hurdles that speech recognition technology must clear before ubiquitous adoption can be realized. R&D in spontaneous and free-flowing speech style is critical to its success.
Digging in the wrong spot
Authors: Marine Larry
Published: February 2004

Ever feel that you were spinning your wheels improving an interface? You made change after change, enhancement after enhancement, all based on design guidelines and usability testing---but nothing seemed to move the product very far toward helping your users accomplish their goals. Maybe you had your sights set on the wrong target. Maybe you were digging in the wrong spot. In this
Whiteboard
, Larry Marine describes two kinds of digging spots---one straightforward and one less obvious---and explains why and how to dig for the more elusive treasure.

--- Elizabeth Buie
The next revolution
Authors: Marcus Aaron
Published: February 2004

Imagine having to think about safety, usability, and aesthetics issues for the user interface of a two-ton mobile device hurtling through space at 100 km/hr. Now you get the picture.
CHI 2004
Authors: Campbell Marisa
Published: February 2004

April 24-29, 2004

Vienna, Austria
Scratching someone else's itch
Authors: Pemberton Steven
Published: February 2004

Every good work of software starts by scratching a developer's personal itch.
---Eric Raymond,

The Cathedral and the Bazaar

There's a closely related issue, however that I don't know how to solve yet without a big player with a lot of money, which is doing systematic user interface end user testing. We're not very good at that yet, we need to find a way to be good at it.
---Eric Raymond,

Why Open Source will Rule
GALAHAD, a library of thread-safe Fortran 90 packages for large-scale nonlinear optimization
Authors: Gould Nicholas I. M. , Orban Dominique , Toint Philippe L.
Published: February 2004

We describe the design of version 1.0 of GALAHAD, a library of Fortran 90 packages for large-scale nonlinear optimization. The library particularly addresses quadratic programming problems, containing both interior point and active set algorithms, as well as tools for preprocessing problems prior to solution. It also contains an updated version of the venerable nonlinear programming package, LANCELOT.
CUTEr and SifDec
Authors: Gould Nicholas I. M. , Orban Dominique , Toint Philippe L.
Published: February 2004

The initial release of CUTE, a widely used testing environment for optimization software, was described by Bongartz, et al. [1995]. A new version, now known as CUTEr, is presented. Features include reorganisation of the environment to allow simultaneous multi-platform installation, new tools for, and interfaces to, optimization packages, and a considerably simplified and entirely automated installation procedure for unix systems. The environment is fully backward compatible with its predecessor, and offers support for Fortran 90/95 and a general C/C++ Application Programming Interface. The SIF decoder, formerly a part of CUTE, has become a separate tool, easily callable by various packages. It features simple extensions to the SIF test problem format and the generation of files suited to automatic differentiation packages.
Parallel frontal solvers for large sparse linear systems
Authors: Scott Jennifer A.
Published: February 2004

Many applications in science and engineering give rise to large sparse linear systems of equations that need to be solved as efficiently as possible. As the size of the problems of interest increases, it can become necessary to consider exploiting multiprocessors to solve these systems. We report on the design and development of parallel frontal solvers for the numerical solution of large sparse linear systems. Three codes have been developed for the mathematical software library HSL (www.cse.clrc.ac.uk/Activity/HSL). The first is for unsymmetric finite-element problems; the second is for symmetric positive definite finite-element problems; and the third is for highly unsymmetric linear systems such as those that arise in chemical process engineering. In each case, the problem is subdivided into a small number of loosely connected subproblems and a frontal method is then applied to each of the subproblems in parallel. We discuss how our software is designed to achieve the goals of portability, ease of use, efficiency, and flexibility, and illustrate the performance using problems arising from real applications.
Fast contouring of solutions to partial differential equations
Authors: Bradbury Emma L. , Enright Wayne H.
Published: February 2004

The application of Differential Equation Interpolants (DEIs) to the visualization of the solutions to Partial Differential Equations (PDEs) is investigated. In particular, we describe how a DEI can be used to generate a fine mesh approximation from a coarse mesh approximation; this fine mesh approximation can then be used by a standard contouring function to render an accurate contour plot of the surface. However, the standard approach has a time complexity equivalent to that of rendering a surface plot,
O
(
fm
2
) for each element of the coarse mesh, (where
fm
is the ratio of the width of the coarse mesh to the fine mesh). To address this concern three fast contouring algorithms are proposed that compute accurate contour lines directly from the DEI, and have time complexity at most
O
(
fm
) for each coarse mesh element.
Modeling the performance of interface contraction
Authors: Bücker H. Martin , Rasch Arno
Published: February 2004

Automatic differentiation is a technique used to transform a computer code implementing some mathematical function into another program capable of evaluating the function and its derivatives. Compared to numerical differentiation, the derivatives obtained from applying automatic differentiation are free from truncation error, and their computation often requires less time. To increase the efficiency of a black box approach of automatic differentiation, a technique called interface contraction may be used. Interface contraction exploits the local structure of a code to temporarily reduce the global number of derivatives propagated through the code. Two performance models are introduced to predict the potential improvement in the execution time of a program making use of interface contraction compared to a program generated by a black box approach of automatic differentiation. The performance models are validated by numerical experiments carried out on different computing platforms. The computer codes used in the experiments stem from the application areas of neutron scattering and biostatistics.
Algorithm 828
Authors: Renka Robert J.
Published: February 2004

We describe a new method and a Fortran-77 code for constructing discrete approximations to nonparametric interpolating nonlinear spline curves. Our approach consists of minimizing the discretized strain energy by a descent method with a Sobolev gradient in place of the standard gradient. It serves as a demonstration of the Sobolev gradient method, which is much more generally applicable. The effectiveness of the method in rapidly producing smooth interpolatory curves is demonstrated by test results for several challenging data sets.
Algorithm 829
Authors: Gaviano Marco , Kvasov Dmitri E. , Lera Daniela , Sergeyev Yaroslav D.
Published: February 2004

A procedure for generating non-differentiable, continuously differentiable, and twice continuously differentiable classes of test functions for multiextremal multidimensional box-constrained global optimization is presented. Each test class consists of 100 functions. Test functions are generated by defining a convex quadratic function systematically distorted by polynomials in order to introduce local minima. To determine a class, the user defines the following parameters: (i) problem dimension, (ii) number of local minima, (iii) value of the global minimum, (iv) radius of the attraction region of the global minimizer, (v) distance from the global minimizer to the vertex of the quadratic function. Then, all other necessary parameters are generated randomly for all 100 functions of the class. Full information about each test function including locations and values of all local minima is supplied to the user. Partial derivatives are also generated where possible.
Applying associative retrieval techniques to alleviate the sparsity problem in collaborative filtering
Authors: Huang Zan , Chen Hsinchun , Zeng Daniel
Published: February 2004

Recommender systems are being widely applied in many application settings to suggest products, services, and information items to potential consumers. Collaborative filtering, the most successful recommendation approach, makes recommendations based on past transactions and feedback from consumers sharing similar interests. A major problem limiting the usefulness of collaborative filtering is the sparsity problem, which refers to a situation in which transactional or feedback data is sparse and insufficient to identify similarities in consumer interests. In this article, we propose to deal with this sparsity problem by applying an associative retrieval framework and related spreading activation algorithms to explore transitive associations among consumers through their past transactions and feedback. Such transitive associations are a valuable source of information to help infer consumer interests and can be explored to deal with the sparsity problem. To evaluate the effectiveness of our approach, we have conducted an experimental study using a data set from an online bookstore. We experimented with three spreading activation algorithms including a constrained Leaky Capacitor algorithm, a branch-and-bound serial symbolic search algorithm, and a Hopfield net parallel relaxation search algorithm. These algorithms were compared with several collaborative filtering approaches that do not consider the transitive associations: a simple graph search approach, two variations of the user-based approach, and an item-based approach. Our experimental results indicate that spreading activation-based approaches significantly outperformed the other collaborative filtering methods as measured by recommendation precision, recall, the F-measure, and the rank score. We also observed the over-activation effect of the spreading activation approach, that is, incorporating transitive associations with past transactional data that is not sparse may "dilute" the data used to infer user preferences and lead to degradation in recommendation performance.
Send-receive considered harmful
Authors: Gorlatch Sergei
Published: February 2004

During the software crisis of the 1960s, Dijkstra's famous thesis
"goto considered harmful"
paved the way for structured programming. This short communication suggests that many current difficulties of parallel programming based on message passing are caused by poorly structured communication, which is a consequence of using low-level
send-receive
primitives. We argue that, like
goto
in sequential programs,
send-receive
should be avoided as far as possible and replaced by
collective operations
in the setting of message passing. We dispute some widely held opinions about the apparent superiority of pairwise communication over collective communication and present substantial theoretical and empirical evidence to the contrary in the context of MPI (Message Passing Interface).
Access control for mobile agents
Authors: Bugliesi Michele , Castagna Giuseppe , Crafa Silvia
Published: February 2004

Boxed Ambients
are a variant of Mobile Ambients that result from dropping the open capability and introducing new primitives for ambient communication. The new model of communication is faithful to the principles of distribution and location-awareness of Mobile Ambients, and complements the constructs in and out for mobility with finer-grained mechanisms for ambient interaction. We introduce the new calculus, study the impact of the new mechanisms for communication of typing and mobility, and show that they yield an effective framework for resource protection and access control in distributed systems.
Offline partial evaluation can be as accurate as online partial evaluation
Authors: Christensen Niels H. , Glück Robert
Published: February 2004

We show that the accuracy of online partial evaluation, or polyvariant specialization based on constant propagation, can be simulated by offline partial evaluation using a maximally polyvariant binding-time analysis. We point out that, while their accuracy is the same, online partial evaluation offers better opportunities for powerful generalization strategies. Our results are presented using a flowchart language with recursive procedures.
Deterministic generators and games for Ltl fragments
Authors: Alur Rajeev , La Torre Salvatore
Published: February 2004

Deciding infinite two-player games on finite graphs with the winning condition specified by a linear temporal logic (Ltl) formula, is known to be 2Exptime-complete. In this paper, we identify Ltl fragments of lower complexity. Solving Ltl games typically involves a doubly exponential translation from Ltl formulas to
deterministic
ω-automata. First, we show that the
longest distance
(length of the longest simple path) of the generator is also an important parameter, by giving an
O
(
d
log
n
)-space procedure to solve a Büchi game on a graph with
n
vertices and longest distance
d
. Then, for the Ltl fragment of the Boolean combinations of formulas obtained only by eventualities and conjunctions, we provide a translation to deterministic generators of exponential size and linear longest distance, show both of these bounds to be optimal, and prove the corresponding games to be Pspace-complete. Introducing
next
modalities in this fragment, we give a translation to deterministic generators still of exponential size but also with exponential longest distance, show both of these bounds to be optimal, and prove the corresponding games to be Exptime-complete. For the fragment resulting by further adding disjunctions, we provide a translation to deterministic generators of doubly exponential size and exponential longest distance, show both of these bounds to be optimal, and prove the corresponding games to be Expspace. We also show tightness of the double exponential bound on the size as well as the longest distance for deterministic generators of Ltl formulas without
next
and
until
modalities. Finally, we identify a class of deterministic Büchi automata corresponding to a fragment of Ltl with restricted use of
always
and
until
modalities, for which deciding games is Pspace-complete.
Super logic programs
Authors: Brass Stefan , Dix Jürgen , Przymusinski Teodor C.
Published: February 2004

The Autoepistemic Logic of Knowledge and Belief (AELB) is a powerful nonmonotonic formalism introduced by Teodor Przymusinski in 1994. In this paper, we specialize it to a class of theories called "super logic programs". We argue that these programs form a natural generalization of standard logic programs. In particular, they allow disjunctions and default negation of arbitrary positive objective formulas.Our main results are two new and important characterizations of the static semantics of these programs, one syntactic, and one model-theoretic. The syntactic fixed point characterization is much simpler than the fixed point construction of the static semantics for arbitrary AELB theories. The model-theoretic characterization via Kripke models allows one to construct finite representations of the inherently infinite static expansions.Both characterizations can be used as the basis of algorithms for query answering under the static semantics. We describe a
query-answering interpreter
for super programs that we developed based on the model-theoretic characterization and which is available on the web.
Cross-language spoken document retrieval using HMM-based retrieval model with multi-scale fusion
Authors: Lo Wai-Kit , Meng Helen , Ching P. C.
Published: February 2004

Cross-language spoken document retrieval (CL-SDR) is the technology that facilitates automatic retrieval of relevant information from a collection of spoken documents in a language that is different from that used in the queries. Information sources that are in different languages can then be retrieved automatically with CL-SDR, and the number of searchable information sources will increase significantly. The HMM-based retrieval model is a probabilistic formulation for the retrieval problem. Extensions to this retrieval model can be made by taking advantage of its probabilistic nature. Specifically, we have incorporated the translation component to make it possible to perform cross-language information retrieval (CLIR). In addition, this HMM-based CLIR retrieval model is also extended for retrieval at subword scales.In this work the extended HMM-based retrieval model has been applied to an English-Mandarin CL-SDR task, which is to search the Mandarin spoken document collection with English queries at word and subword scales. Retrieval results obtained from these indexing scales are then fused for multi-scale CL-SDR. Experimental results demonstrate that improvement in CL-SDR retrieval performance can be achieved by fusion of word and subword scales.
Offline handwritten Chinese character recognition by radical decomposition
Authors: Shi Daming , Damper Robert I. , Gunn Steve R.
Published: February 2004

Offline handwritten Chinese character recognition is a very hard pattern-recognition problem of considerable practical importance. Two popular approaches are to extract features holistically from the character image or to decompose characters structurally into component parts---usually strokes. Here we take a novel approach, that of decomposing into radicals on the basis of image information (i.e., without first decomposing into strokes). During training, 60 examples of each radical were represented by "landmark" points, labeled semiautomatically, with radicals in different characteristic positions treated as distinctly different radicals. Kernel principal-component analysis then captured the main (nonlinear) variations around the mean radical. During the recognition, the dynamic tunneling algorithm was used to search for optimal shape parameters in terms of chamfer distance minimization. Considering character composition as a Markov process in which up to four radicals are combined in some assumed sequential order, we can recognize complete, hierarchically-composed characters by using the Viterbi algorithm. This gave a character recognition rate of 93.5% characters correct (writer-independent) on a test set of 430,800 characters from 2,154 character classes composed of 200 radical categories, which is comparable to the best reported results in the literature. Although the initial semiautomatic landmark labeling is time consuming, the decomposition approach is theoretically well-motivated and allows the different sources of variability in Chinese handwriting to be handled separately and by the most appropriate means--either learned from example data or incorporated as prior knowledge. Hence, high generalizability is obtained from small amounts of training data, and only simple prior knowledge needs to be incorporated, thus promising robust recognition performance. As such, there is very considerable potential for further development and improvement in the direction of larger character sets and less constrained writing conditions.
Task adaptation in stochastic language model for Chinese homophone disambiguation
Authors: Lee Yue-Shi
Published: February 2004

The runtime application domain has a great effect on the performance of practical corpus-based applications. Previous smoothing techniques and class-based and similarity-based models could not handle the dynamic status perfectly. In this paper, an adaptive learning algorithm is proposed for task adaptation that best fits the runtime application domain in applying Chinese homophone disambiguation. The proposed algorithm is first formulated by a neural network model and then generalized to avoid the problem of slow convergence. The resulting techniques are greatly simplified and robust. The experimental results demonstrate the effects of the learning algorithm from a generic domain to a specific one. A methodology is also presented to show how these techniques can be extended to various language models and corpus-based applications.
An efficient accessing technique for Taiwanese phonetic transcriptions
Authors: Shieh Jiann-Cherng
Published: February 2004

Recently, the Taiwan government has been enthusiastically promoting the study of the languages of her native inhabitants, including Taiwanese. Hence the focus of our research is to design and develop an efficient retrieval technique for phonetic transcriptions. This new technique will make possible widespread utilization of Taiwanese, e.g., in PDA (mobile phone applications). In this paper we propose a minimal perfect hashing function for the 3028 existing Taiwanese phonetic transcriptions. Compared to the hashing designs based on the Chinese remainder theorem for various data sets, the proposed design is shown to be superior in space utilization.
Adaptive medial-axis approximation for sphere-tree construction
Authors: Bradshaw Gareth , O'Sullivan Carol
Published: February 2004

Hierarchical object representations play an important role in performing efficient collision handling. Many different geometric primitives have been used to construct these representations, which allow areas of interaction to be localized quickly. For time-critical algorithms, there are distinct advantages to using hierarchies of spheres, known as sphere-trees, for object representation. This article presents a novel algorithm for the construction of sphere-trees. The algorithm presented approximates objects, both convex and non-convex, with a higher degree of fit than existing algorithms. In the lower levels of the representations, there is almost an order of magnitude decrease in the number of spheres required to represent the objects to a given accuracy.
Human facial illustrations
Authors: Gooch Bruce , Reinhard Erik , Gooch Amy
Published: February 2004

We present a method for creating black-and-white illustrations from photographs of human faces. In addition an interactive technique is demonstrated for deforming these black-and-white facial illustrations to create caricatures which highlight and exaggerate representative facial features. We evaluate the effectiveness of the resulting images through psychophysical studies to assess accuracy and speed in both recognition and learning tasks. These studies show that the facial illustrations and caricatures generated using our techniques are as effective as photographs in recognition tasks. For the learning task we find that illustrations are learned two times faster than photographs and caricatures are learned one and a half times faster than photographs. Because our techniques produce images that are effective at communicating complex information, they are useful in a number of potential applications, ranging from entertainment and education to low bandwidth telecommunications and psychology research.
A novel cubic-order algorithm for approximating principal direction vectors
Authors: Goldfeather Jack , Interrante Victoria
Published: February 2004

There are a number of applications in computer graphics that require as a first step the accurate estimation of principal direction vectors at arbitrary vertices on a triangulated surface. Although several methods for calculating principal directions over such models have been previously proposed, we have found in practice that all exhibit unexplained large errors in some cases. In this article, we describe our theoretical and experimental investigations into possible sources of errors in the approximation of principal direction vectors from triangular meshes, and suggest a new method for estimating principal directions that can yield better results under some circumstances.
Formal hardware specification languages for protocol compliance verification
Authors: Bunker Annette , Gopalakrishnan Ganesh , Mckee Sally A.
Published: February 2004

The advent of the system-on-chip and intellectual property hardware design paradigms makes protocol compliance verification increasingly important to the success of a project. One of the central tools in any verification project is the modeling language, and we survey the field of candidate languages for protocol compliance verification, limiting our discussion to languages originally intended for hardware and software design and verification activities. We frame our comparison by first constructing a taxonomy of these languages, and then by discussing the applicability of each approach to the compliance verification problem. Each discussion includes a summary of the development of the language, an evaluation of the language's utility for our problem domain, and, where feasible, an example of how the language might be used to specify hardware protocols. Finally, we make some general observations regarding the languages considered.