bluuebunny/crossref_metadata_2025 huggingface dataset:
A collaborative platform for fixed and mobile networks
Authors: Bergenti Federico , Poggi Agostino , Somacher Matteo
Published: January 2003

C/Webtop: providing users with a means for collaborating while on the move.
A Java 3d-enabled cyber workspace
Authors: Wang Lihui , Wong Brian , Shen Weiming , Lang Sherman
Published: January 2003

Along with the browser paradigm, Java has fundamentally changed the work environment, helping produce compelling applications for collaborating over the Internet.
Evolution, not revolution
Authors: Selic Bran , Ramackers Guus , Kobryn Cris
Published: January 2003

Any consideration of altering UML must account for its current user base and its potential role as the keystone of a new model-based method of software development.
UML2 must enable a family of languages
Authors: Duddy Keith
Published: January 2003

UML2 needs to take advantage of new infrastructure to enable first-class specialization and variation of the UML superstructure language.
Make models be assets
Authors: Mellor Stephen J.
Published: January 2003

Needed first is a layered UML with a small, well-defined, executable, translatable kernel that enables and supports development of an extensible tool chain.
Be clear, clean, concise
Authors: Frank William , Tyson Kevin P.
Published: January 2003

UML needs to focus on its foundations.
Why significant UML change is unlikely
Authors: Dori Dov
Published: January 2003

Reform may be too little too late to spare software engineers the cognitively overwhelming effort of applying UML to modeling system structure and behavior in a truly unified manner.
Texas licensing of software engineers
Authors: Bagert Donald J.
Published: January 2003

The notion of licensing software engineers has been weighed and argued on global, national, and statewide platforms for many years. Here, we go to the frontlines---Texas and Canada---where the practice of licensing is in fact well under way. Sentiments may not have mellowed regarding this subject, but the perspectives we present here are based on real experiences.
Software engineering considered harmful
Authors: de Champeaux Dennis
Published: January 2003

In search of a resolution to the ongoing software crisis.
Searching for dependencies at multiple abstraction levels
Authors: Calders Toon , Ng Raymond T. , Wijsen Jef
Published: January 2003

The notion of roll-up dependency (RUD) extends functional dependencies with generalization hierarchies. RUDs can be applied in OLAP and database design. The problem of discovering RUDs in large databases is at the center of this paper. An algorithm is provided that relies on a number of theoretical results. The algorithm has been implemented; results on two real-life datasets are given. The extension of functional dependency (FD) with roll-ups turns out to capture meaningful rules that are outside the scope of classical FD mining. Performance figures show that RUDs can be discovered in linear time in the number of tuples of the input dataset.
Fast incremental maintenance of approximate histograms
Authors: Gibbons Phillip B. , Matias Yossi , Poosala Viswanath
Published: January 2003

Many commercial database systems maintain histograms to summarize the contents of large relations and permit efficient estimation of query result sizes for use in query optimizers. Delaying the propagation of database updates to the histogram often introduces errors into the estimation. This article presents new sampling-based approaches for
incremental
maintenance of approximate histograms. By scheduling updates to the histogram based on the updates to the database, our techniques are the first to maintain histograms effectively up to date at all times and avoid computing overheads when unnecessary. Our techniques provide highly accurate approximate histograms belonging to the
equidepth
and
Compressed
classes. Experimental results show that our new approaches provide orders of magnitude more accurate estimation than previous approaches.An important aspect employed by these new approaches is a
backing sample
, an up-to-date random sample of the tuples currently in a relation. We provide efficient solutions for maintaining a uniformly random sample of a relation in the presence of updates to the relation. The backing sample techniques can be used for any other application that relies on random samples of data.
Cost models for overlapping and multiversion structures
Authors: Tao Yufei , Papadias Dimitris , Zhang Jun
Published: January 2003

Overlapping
and
multiversion
techniques are two popular frameworks that transform an ephemeral index into a multiple logical-tree structure in order to support versioning databases. Although both frameworks have produced numerous efficient indexing methods, their performance analysis is rather limited; as a result there is no clear understanding about the behavior of the alternative structures and the choice of the best one, given the data and query characteristics. Furthermore, query optimization based on these methods is currently impossible. These are serious problems due to the incorporation of overlapping and multiversion techniques in several traditional (e.g., financial) and emerging (e.g., spatiotemporal) applications. In this article, we reduce performance analysis of overlapping and multiversion structures to that of the corresponding ephemeral structures, thus simplifying the problem significantly. This reduction leads to accurate cost models that predict the sizes of the trees, the node/page accesses, and selectivity of queries. Furthermore, the models offer significant insight into the behavior of the structures and provide guidelines about the selection of the most appropriate method in practice. Extensive experimentation proves that the proposed models yield errors below 5 and 15% for uniform and nonuniform data, respectively.
Qualitative decision theory
Authors: Dubois Didier , Fargier Hélène , Prade Henri , Perny Patrice
Published: January 2003

This paper investigates to what extent a purely symbolic approach to decision making under uncertainty is possible, in the scope of artificial intelligence. Contrary to classical approaches to decision theory, we try to rank acts without resorting to any numerical representation of utility or uncertainty, and without using any scale on which
both
uncertainty and preference could be mapped. Our approach is a variant of Savage's where the setting is finite, and the strict preference on acts is a partial order. It is shown that although many axioms of Savage theory are preserved and despite the intuitive appeal of the ordinal method for constructing a preference over acts, the approach is inconsistent with a probabilistic representation of uncertainty. The latter leads to the kind of paradoxes encountered in the theory of voting. It is shown that the assumption of ordinal invariance enforces a qualitative decision procedure that presupposes a comparative possibility representation of uncertainty, originally due to Lewis, and usual in nonmonotonic reasoning. Our axiomatic investigation thus provides decision-theoretic foundations to the preferential inference of Lehmann and colleagues. However, the obtained decision rules are sometimes either not very decisive or may lead to overconfident decisions, although their basic principles look sound. This paper points out some limitations of purely ordinal approaches to Savage-like decision making under uncertainty, in perfect analogy with similar difficulties in voting theory.
Dense quantum coding and quantum finite automata
Authors: Ambainis Andris , Nayak Ashwin , Ta-Shma Amnon , Vazirani Umesh
Published: January 2003

We consider the possibility of encoding
m
classical bits into many fewer
n
quantum bits (qubits) so that an arbitrary bit from the original
m
bits can be recovered with good probability. We show that nontrivial quantum codes exist that have no classical counterparts. On the other hand, we show that quantum encoding cannot save more than a logarithmic additive factor over the best classical encoding. The proof is based on an entropy coalescence principle that is obtained by viewing Holevo's theorem from a new perspective.In the existing implementations of quantum computing, qubits are a very expensive resource. Moreover, it is difficult to reinitialize existing bits during the computation. In particular, reinitialization is impossible in NMR quantum computing, which is perhaps the most advanced implementation of quantum computing at the moment. This motivates the study of quantum computation with restricted memory and no reinitialization, that is, of quantum finite automata. It was known that there are languages that are recognized by quantum finite automata with sizes exponentially smaller than those of corresponding classical automata. Here, we apply our technique to show the surprising result that there are languages for which quantum finite automata take exponentially more states than those of corresponding classical automata.
On the complexity analysis of static analyses
Authors: McAllester David
Published: January 2003

This paper argues that for many algorithms, and static analysis algorithms in particular, bottom-up logic program presentations are clearer and simpler to analyze, for both correctness andcomplexity, than classical pseudo-code presentations. The main technical contribution consists of two theorems which allow, in many cases, the asymptotic running time of a bottom-up logic program to be determined by inspection. It is well known that a datalog program runs inO(nk) time wherekis the largest number of free variables in any single rule. The theorems given here are significantly more refined. A variety of algorithms are presented and analyzed as examples.
Formal verification of standards for distance vector routing protocols
Authors: Bhargavan Karthikeyan , Obradovic Davor , Gunter Carl A.
Published: January 2003

We show how to use an interactive theorem prover, HOL, together with a model checker, SPIN, to prove key properties of distance vector routing protocols. We do three case studies: correctness of the RIP standard, a sharp real-time bound on RIP stability, and preservation of loop-freedom in AODV, a distance vector protocol for wireless networks. We develop verification techniques suited to routing protocols generally. These case studies show significant benefits from automated support in reduced verification workload and assistance in finding new insights and gaps for standard specifications.
Symmetric and asymmetric action integration during cooperative object manipulation in virtual environments
Authors: Ruddle Roy A. , Savage Justin C.D. , Jones Dylan M.
Published: January 2003

The following abstracts are from recent issues and the forthcoming issue of ACM's
Transactions of Computer Human Interaction
(ToCHI). They are included here to alert
Interactions'
readers to what research is being done in the field of Computer Human Interaction. The complete papers, when published, can be found in ACM's Digital Library at www.acm.org/pubs/contents/journals/tochi/
Letter from the dark side
Authors: McCoy Thomas
Published: January 2003

The usability/development drama sometimes feels like a wrestling match that both teams despair of winning. No matter which part you play, I'll bet you'll recognize yourself or someone you know in this month's column. Tom McCoy expresses in a delightful whinge the attitudes and resentments of the development team towards the imposition of usability as an add-on, and offers suggestions for improving the communication and the overall process.
---Elizabeth Buie
How to cope with success
Authors: Stewart Tom
Published: January 2003

Many of you know Tom Stewart from his many years of leading System Concepts in the United Kingdom, as well as for his work on standards and his editorship of the journal
Behaviour and Information Technology
. We asked him to give us his perspective on where the business of human--computer interaction is heading. We hope you will find it to be as interesting---and provocative---as we did.
---Susan Dray and David Siegel
An equilibrium of value
Authors: Donoghue Karen
Published: January 2003

The following essay is based on a chapter from the recently published book entitled
Built for Use: Driving Profitability Through the User Experience
by Karen Donoghue
Understanding the global semantics of referential actions using logic rules
Authors: May Wolfgang , Ludäscher Bertram
Published: January 2003

Referential actions are specialized triggers for automatically maintaining referential integrity in databases. While the
local effects
of referential actions can be grasped easily, it is far from obvious what the
global semantics
of a set of interacting referential actions should be. In particular, when using procedural execution models, ambiguities due to the execution ordering can occur. No
global, declarative
semantics of referential actions has yet been defined.We show that the well-known logic programming semantics provide a natural
global
semantics of referential actions that is based on their
local
characterization: To capture the global meaning of a set
RA
of referential actions, we first define their abstract (but non-constructive)
intended semantics
. Next, we
formalize RA
as a
logic program

P
RA

. The declarative, logic programming semantics of

P
RA

then provide the constructive,
global
semantics of the referential actions. So, we do not
define
a semantics for referential actions, but we show that there
exists
a unique
natural
semantics if one is ready to accept (i) the intuitive local semantics of local referential actions, (ii) the formalization of those and of the local "effect-propagating" rules, and (iii) the well-founded or stable model semantics from logic programming as "reasonable" global semantics for local rules.We first focus on the subset of referential actions for deletions only. We prove the equivalence of the logic programming semantics and the abstract semantics via a game-theoretic characterization, which provides additional insight into the meaning of interacting referential actions. In this case a
unique maximal admissible solution exists
, computable by a ptime algorithm.Second, we investigate the general case---including modifications. We show that in this case there can be
multiple maximal admissible subsets
and that all maximal admissible subsets can be characterized as
3-valued stable models
of

P
RA

. We show that for a given set of user requests, in the presence of referential actions of the form ON UPDATE CASCADE, the admissibility check and the computation of the subsequent database state, and (for non-admissible updates) the derivation of debugging hints all are in ptime. Thus, full referential actions can be implemented efficiently.
Searching in metric spaces with user-defined and approximate distances
Authors: Ciaccia Paolo , Patella Marco
Published: January 2003

Novel database applications, such as multimedia, data mining, e-commerce, and many others, make intensive use of similarity queries in order to retrieve the objects that better fit a user request. Since the effectiveness of such queries improves when the user is allowed to personalize the similarity criterion according to which database objects are evaluated and ranked, the development of access methods able to efficiently support user-defined similarity queries becomes a basic requirement. In this article we introduce the first index structure, called the QIC-M-tree, that can process user-defined queries in generic metric spaces, that is, where the only information about indexed objects is their relative distances. The QIC-M-tree is a metric access method that can deal with several distinct distances at a time: (1) a
query (user-defined) distance
, (2) an
index distance
(used to build the tree), and (3) a
comparison (approximate) distance
(used to quickly discard from the search uninteresting parts of the tree). We develop an analytical cost model that accurately characterizes the performance of the QIC-M-tree and validate such model through extensive experimentation on real metric data sets. In particular, our analysis is able to predict the best evaluation strategy (i.e., which distances to use) under a variety of configurations, by properly taking into account relevant factors such as the distribution of distances, the cost of computing distances, and the actual index structure. We also prove that the overall saving in CPU search costs when using an approximate distance can be estimated by using information on the data set only (thus such measure is independent of the underlying access method) and show that performance results are closely related to a novel "indexing" error measure.
SilkRoute
Authors: Fernández Mary , Kadiyska Yana , Suciu Dan , Morishima Atsuyuki , Tan Wang-Chiew
Published: January 2003

XML is the "lingua franca" for data exchange between interenterprise applications. In this work, we describe SilkRoute, a framework for publishing relational data in XML. In SilkRoute, relational data is published in three steps: the relational tables are presented to the database administrator in a canonical XML view; the database administrator defines in the XQuery query language a public, virtual XML view over the canonical XML view; and an application formulates an XQuery query over the public view. SilkRoute composes the application query with the public-view query, translates the result into SQL, executes this on the relational engine, and assembles the resulting tuple streams into an XML document. This work makes some key contributions to XML query processing. First, it describes an algorithm that translates an XQuery expression into SQL. The translation depends on a query representation that separates the
structure
of the output XML document from the
computation
that produces the document's content. The second contribution addresses the optimization problem of how to decompose an XML view over a relational database into an optimal set of SQL queries. We define formally the optimization problem, describe the search space, and propose a greedy, cost-based optimization algorithm, which obtains its cost estimates from the relational engine. Experiments confirm that the algorithm produces queries that are nearly optimal.
Probabilistic models of information retrieval based on measuring the divergence from randomness
Authors: Amati Gianni , Van Rijsbergen Cornelis Joost
Published: January 2003

We introduce and create a framework for deriving probabilistic models of Information Retrieval. The models are nonparametric models of IR obtained in thelanguage modelapproach. We derive term-weighting models by measuring the divergence of the actual term distribution from that obtained under a random process. Among the random processes we study the binomial distribution and Bose--Einstein statistics. We define two types of term frequency normalization for tuning term weights in the document--query matching process. The first normalization assumes that documents have the same length and measures the information gain with the observed term once it has been accepted as a good descriptor of the observed document. The second normalization is related to the document length and to other statistics. These two normalization methods are applied to the basic models in succession to obtain weighting formulae. Results show that our framework produces different nonparametric models forming baseline alternatives to the standardtf-idfmodel.
A semantic network-based design methodology for XML documents
Authors: Feng Ling , Chang Elizabeth , Dillon Tharam
Published: January 2003

The eXtensible Markup Language (XML) is fast emerging as the dominant standard for describing and interchanging data among various systems and databases on the Internet. It offers the Document Type Definition (DTD) as a formalism for defining the syntax and structure of XML documents. The XML Schema definition language, as a replacement for the DTD, provides more rich facilities for defining and constraining the content of XML documents. However, it does not concentrate on the semantics that underlies these documents, representing a logical data model rather than a conceptual model. To enable efficient business application development in large-scale electronic commerce environments, it is necessary to describe and model real-world data semantics and their complex interrelationships. In this article, we describe a design methodology for XML documents. The aim is to enforce XML conceptual modeling power and bridge the gap between software development and XML document structures. The proposed methodology is comprised of two design levels: the
semantic level
and the
schema level
. The first level is based on a semantic network, which provides semantic modeling of XML through four major components: a set of
atomic
and
complex
nodes, representing real-world objects; a set of directed edges, representing
semantic relationships
between the objects; a set of labels denoting different types of semantic relationships, including
aggregation, generalization, association
, and
of-property
relationships; and finally a set of constraints defined over nodes and edges to constrain semantic relationships and object domains. The other level of the proposed methodology is concerned with detailed XML schema design, including
element/attribute declarations
and
simple/complex type definitions
. The mapping between the two design levels is proposed to transform the XML semantic model into the XML Schema, based on which XML documents can be systematically created, managed, and validated.
Cumulated gain-based evaluation of IR techniques
Authors: Järvelin Kalervo , Kekäläinen Jaana
Published: January 2003

Modern large retrieval environments tend to overwhelm their users by their large output. Since all documents are not of equal relevance to their users, highly relevant documents should be identified and ranked first for presentation. In order to develop IR techniques in this direction, it is necessary to develop evaluation approaches and methods that credit IR methods for their ability to retrieve highly relevant documents. This can be done by extending traditional evaluation methods, that is, recall and precision based on binary relevance judgments, to graded relevance judgments. Alternatively, novel measures based on graded relevance judgments may be developed. This article proposes several novel measures that compute the cumulative gain the user obtains by examining the retrieval result up to a given ranked position. The first one accumulates the relevance scores of retrieved documents along the ranked result list. The second one is similar but applies a discount factor to the relevance scores in order to devaluate late-retrieved documents. The third one computes the relative-to-the-ideal performance of IR techniques, based on the cumulative gain they are able to yield. These novel measures are defined and discussed and their use is demonstrated in a case study using TREC data: sample system run results for 20 queries in TREC-7. As a relevance base we used novel graded relevance judgments on a four-point scale. The test results indicate that the proposed measures credit IR methods for their ability to retrieve highly relevant documents and allow testing of statistical significance of effectiveness differences. The graphs based on the measures also provide insight into the performance IR techniques and allow interpretation, for example, from the user point of view.
Truth revelation in approximately efficient combinatorial auctions
Authors: Lehmann Daniel , Oćallaghan Liadan Ita , Shoham Yoav
Published: January 2003

Some important classical mechanisms considered in Microeconomics and Game Theory require the solution of a difficult optimization problem. This is true of mechanisms for combinatorial auctions, which have in recent years assumed practical importance, and in particular of the gold standard for combinatorial auctions, the Generalized Vickrey Auction (GVA). Traditional analysis of these mechanisms---in particular, their truth revelation properties---assumes that the optimization problems are solved precisely. In reality, these optimization problems can usually be solved only in an approximate fashion. We investigate the impact on such mechanisms of replacing exact solutions by approximate ones. Specifically, we look at a particular greedy optimization method. We show that the GVA payment scheme does not provide for a truth revealing mechanism. We introduce another scheme that does guarantee truthfulness for a restricted class of players. We demonstrate the latter property by identifying natural properties for combinatorial auctions and showing that, for our restricted class of players, they imply that truthful strategies are dominant. Those properties have applicability beyond the specific auction studied.
The greedy path-merging algorithm for contig scaffolding
Authors: Huson Daniel H. , Reinert Knut , Myers Eugene W.
Published: January 2003

Given a collection of contigs and mate-pairs. The
Contig Scaffolding Problem
is to order and orientate the given contigs in a manner that is consistent with as many mate-pairs as possible. This paper describes an efficient heuristic called the
greedy-path merging algorithm
for solving this problem. The method was originally developed as a key component of the
compartmentalized assembly
strategy developed at Celera Genomics. This interim approach was used at an early stage of the sequencing of the human genome to produce a preliminary assembly based on preliminary whole genome shotgun data produced at Celera and preliminary human contigs produced by the Human Genome Project.
Approximation algorithms for classification problems with pairwise relationships
Authors: Kleinberg Jon , Tardos Éva
Published: January 2003

In a traditional classification problem, we wish to assign one of
k labels
(or classes) to each of
n objects
, in a way that is consistent with some observed data that we have about the problem. An active line of research in this area is concerned with classification when one has information about
pairwise relationships
among the objects to be classified; this issue is one of the principal motivations for the framework of Markov random fields, and it arises in areas such as image processing, biometry, and document analysis. In its most basic form, this style of analysis seeks to find a classification that optimizes a combinatorial function consisting of
assignment costs
---based on the individual choice of label we make for each object---and
separation costs
---based on the
pair
of choices we make for two "related" objects.We formulate a general classification problem of this type, the
metric labeling problem
; we show that it contains as special cases a number of standard classification frameworks, including several arising from the theory of Markov random fields. From the perspective of combinatorial optimization, our problem can be viewed as a substantial generalization of the multiway cut problem, and equivalent to a type of
uncapacitated quadratic assignment problem
.We provide the first nontrivial polynomial-time approximation algorithms for a general family of classification problems of this type. Our main result is an
O
(log
k
log log
k
)-approximation algorithm for the metric labeling problem, with respect to an arbitrary metric on a set of
k
labels, and an arbitrary weighted graph of relationships on a set of objects. For the special case in which the labels are endowed with the
uniform metric
---all distances are the same---our methods provide a 2-approximation algorithm.
On the online bin packing problem
Authors: Seiden Steven S.
Published: January 2003

A new framework for analyzing online bin packing algorithms is presented. This framework presents a unified way of explaining the performance of algorithms based on the Harmonic approach. Within this framework, it is shown that a new algorithm, Harmonic++, has asymptotic performance ratio at most 1.58889. It is also shown that the analysis of Harmonic+1 presented in Richey [1991] is incorrect; this is a fundamental logical flaw, not an error in calculation or an omitted case. The asymptotic performance ratio of Harmonic+1 is at least 1.59217. Thus, Harmonic++ provides the best upper bound for the online bin packing problem to date.
Alternating-time temporal logic
Authors: Alur Rajeev , Henzinger Thomas A. , Kupferman Orna
Published: January 2003

Temporal logic comes in two varieties:
linear-time temporal logic
assumes implicit universal quantification over all paths that are generated by the execution of a system;
branching-time temporal logic
allows explicit existential and universal quantification over all paths. We introduce a third, more general variety of temporal logic:
alternating-time temporal logic
offers selective quantification over those paths that are possible outcomes of games, such as the game in which the system and the environment alternate moves. While linear-time and branching-time logics are natural specification languages for closed systems, alternating-time logics are natural specification languages for open systems. For example, by preceding the temporal operator "eventually" with a selective path quantifier, we can specify that in the game between the system and the environment, the system has a strategy to reach a certain state. The problems of receptiveness, realizability, and controllability can be formulated as model-checking problems for alternating-time formulas. Depending on whether or not we admit arbitrary nesting of selective path quantifiers and temporal operators, we obtain the two alternating-time temporal logics ATL and ATL*.ATL and ATL* are interpreted over
concurrent game structures
. Every state transition of a concurrent game structure results from a choice of moves, one for each player. The players represent individual components and the environment of an open system. Concurrent game structures can capture various forms of synchronous composition for open systems, and if augmented with fairness constraints, also asynchronous composition. Over structures without fairness constraints, the model-checking complexity of ATL is linear in the size of the game structure and length of the formula, and the symbolic model-checking algorithm for CTL extends with few modifications to ATL. Over structures with weak-fairness constraints, ATL model checking requires the solution of 1-pair Rabin games, and can be done in polynomial time. Over structures with strong-fairness constraints, ATL model checking requires the solution of games with Boolean combinations of Büchi conditions, and can be done in PSPACE. In the case of ATL*, the model-checking problem is closely related to the synthesis problem for linear-time formulas, and requires doubly exponential time.
Multicast over wireless networks
Authors: Varshney Upkar
Published: January 2003

How to ensure the participation of mobile users (no matter how disruptive the circumstances), especially for mobile commerce applications distributed over multiple networks.
Security considerations for remote electronic voting
Authors: Rubin Aviel D.
Published: January 2003

Introducing state-of-the art technology into the election process implies new risks that may not be worth taking.
The value of seller trustworthiness in C2C online markets
Authors: Strader Troy J. , Ramaswami Sridhar N.
Published: January 2003

Trust has value in online markets, and individual and company actions can improve or impair how trustworthy they are perceived in these markets.
Emergent patterns of integration in electronic channel systems
Authors: Schlueter-Langdon Christoph , Shaw Michael J.
Published: January 2003

What should producers and consumers alike make of the emerging class of middlemen and intermediaries in electronic channels?
Cyberspace across sub-Saharan Africa
Authors: Mbarika Victor , Jensen Mike , Meso Peter
Published: January 2003

Moving from technological desert toward emergent sustainable growth.
Teaching reviewing to graduate students
Authors: Palsberg Jens , Baxter Scott J.
Published: January 2003

Incorporating the principles and practices of formal review into a Ph.D. education, smoothly and inexpensively, as part of the existing coursework.
Theory, theory on the wall
Authors: Castel Felipe
Published: January 2003

Could it be that computing itself is just too unwieldy a field for any theory of substance?
Anytime/anyplace computing and the future of knowledge work
Authors: Davis Gordon B.
Published: January 2003

Considering the implications and consequences of the always-connected lifestyle.
Group dynamics and ubiquitous computing
Authors: Grudin Jonathan
Published: January 2003

From "Here and Now" to "Everywhere and Forever."
New frontiers of application design
Authors: Siewiorek Daniel P.
Published: January 2003

Applying the lessons learned from wearable and context-aware computers.
The future of business services in the age of ubiquitous computing
Authors: Fano Andrew , Gershman Anatole
Published: January 2003

Redefining the key aspects of the business-customer relationship.
The relevance of social issues in ubiquitous computing environments
Authors: Jessup Leonard M. , Robey Daniel
Published: January 2003

New forms of social interaction and organization require modifying existing models.
Software infrastructure and design challenges for ubiquitous computing applications
Authors: Banavar Guruduth , Bernstein Abraham
Published: January 2003

Striving to integrate computing into everyday activities in a seamless manner.
Component-based data mining frameworks
Authors: Berzal Fernando , Blanco Ignacio , Cubero Juan-Carlos , Marin Nicolas
Published: January 2003

OLAP Vs. OLTP in the middle tier.
A scalable method for deductive generalization in the spreadsheet paradigm
Authors: Burnett Margaret , Yang Sherry , Summet Jay
Published: January 2003

In this paper, we present an efficient method for automatically generalizing programs written in spreadsheet languages. The strategy is to do generalization through incremental analysis of logical relationships among concrete program entities from the perspective of a particular computational goal. The method uses deductive dataflow analysis with algebraic back-substitution rather than inference with heuristics, and there is no need for generalization-related dialog with the user. We present the algorithms and their time complexities and show that, because the algorithms perform their analyses incrementally, on only the on-screen program elements rather than on the entire program, the method is scalable. Performance data is presented to help demonstrate the scalability.
Symmetric and asymmetric action integration during cooperative object manipulation in virtual environments
Authors: Ruddle Roy A. , Savage Justin C. D. , Jones Dylan M.
Published: January 2003

Cooperation between multiple users in a virtual environment (VE) can take place at one of three levels. These are defined as where users can perceive each other (Level 1), individually change the scene (Level 2), or simultaneously act on and manipulate the same object (Level 3). Despite representing the highest level of cooperation, multiuser object manipulation has rarely been studied. This paper describes a behavioral experiment in which the
piano movers' problem
(maneuvering a large object through a restricted space) was used to investigate object manipulation by pairs of participants in a VE. Participants' interactions with the object were integrated together either symmetrically or asymmetrically. The former only allowed the common component of participants' actions to take place, but the latter used the mean. Symmetric action integration was superior for sections of the task when both participants had to perform similar actions, but if participants had to move in different ways (e.g., one maneuvering him/herself through a narrow opening while the other traveled down a wide corridor) then asymmetric integration was superior. With both forms of integration, the extent to which participants coordinated their actions was poor and this led to a substantial
cooperation overhead
(the reduction in performance caused by having to cooperate with another person).
Undo as concurrent inverse in group editors
Authors: Sun Chengzheng
Published: January 2003

As an important mechanism for error recovery and exploration of alternatives in interactive and collaborative applications, an undo facility should have the capability of undoing any operation at any time. However, supporting undo in collaborative applications is technically challenging and none of the existing group undo solutions is able to offer such a capability. In this article, we contribute an undo solution with such a capability for group text editors. The basic idea is to interpret an undo command as a concurrent inverse operation by means of operational transformation. To cope with the high complexity of group undo, a generic undo framework has been adopted to separate undo policy from the undo mechanism and to separate transformation control algorithms from transformation functions. The proposed undo solution consists of a generic transformation control algorithm that is capable of generating, transforming, and representing valid inverse operations in any context, and a set of transformation functions that are capable of preserving undo-related transformation conditions and properties. Formal proofs are provided to show the correctness of the undo transformation control algorithm in achieving the required undo effect, undo property, and consistency properties. Solutions to the known undo puzzles are provided to show soundness of the transformation functions. A Web-based group text editor REDUCE (REal-time Distributed Unconstrained Cooperative Editing) has been implemented to demonstrate the feasibility and usability of the proposed undo and other technical solutions. The proposed undo solution is generally applicable to collaborative applications that support concurrent insertion and deletion on shared documents consisting of one or multiple dimensions of linearly ordered data objects with positional references.
Navigation patterns and usability of zoomable user interfaces with and without an overview
Authors: Hornbæk Kasper , Bederson Benjamin B. , Plaisant Catherine
Published: January 2003

The literature on information visualization establishes the usability of interfaces with an overview of the information space, but for zoomable user interfaces, results are mixed. We compare zoomable user interfaces with and without an overview to understand the navigation patterns and usability of these interfaces. Thirty-two subjects solved navigation and browsing tasks on two maps. We found no difference between interfaces in subjects' ability to solve tasks correctly. Eighty percent of the subjects preferred the interface with an overview, stating that it supported navigation and helped keep track of their position on the map. However, subjects were faster with the interface without an overview when using one of the two maps. We conjecture that this difference was due to the organization of that map in multiple levels, which rendered the overview unnecessary by providing richer navigation cues through semantic zooming. The combination of that map and the interface without an overview also improved subjects' recall of objects on the map. Subjects who switched between the overview and the detail windows used more time, suggesting that integration of overview and detail windows adds complexity and requires additional mental and motor effort.
On the usefulness of type and liveness accuracy for garbage collection and leak detection
Authors: Hirzel Martin , Diwan Amer , Henkel Johannes
Published: January 2003

The effectiveness of garbage collectors and leak detectors in identifying dead objects depends on theaccuracyof their reachability traversal. Accuracy has two orthogonal dimensions: (i) whether the reachability traversal can distinguish between pointers and nonpointers (type accuracy), and (ii) whether the reachability traversal can identify memory locations that will be dereferenced in the future (liveness accuracy). This article presents an experimental study of the importance of type and liveness accuracy for reachability traversals. We show that liveness accuracy reduces the reachable heap size by up to 62% for our benchmark programs. However, the simpler liveness schemes (e.g., intraprocedural analysis of local variables) are largely ineffective for our benchmark runs: one must analyze global variables using interprocedural analysis to obtain significant benefits. Type accuracy has an insignificant impact on a garbage collector's ability to find unreachable objects in our benchmark runs. We report results for programs written in C, C++, and Eiffel.
Practical extraction techniques for Java
Authors: Tip Frank , Sweeney Peter F. , Laffra Chris , Eisma Aldo , Streeter David
Published: January 2003

Reducing application size is important for software that is distributed via the internet, in order to keep download times manageable, and in the domain of embedded systems, where applications are often stored in (Read-Only or Flash) memory. This paper explores extraction techniques such as the removal of unreachable methods and redundant fields, inlining of method calls, and transformation of the class hierarchy for reducing application size. We implemented a number of extraction techniques in
Jax
, an application extractor for Java, and evaluated their effectiveness on a set of large Java applications. We found that, on average, the class file archives for these benchmarks were reduced to 37.5% of their original size. Modeling dynamic language features such as reflection, and extracting software distributions other than complete applications requires additional user input. We present a uniform approach for supplying this input that relies on MEL, a modular specification language. We also discuss a number of issues and challenges associated with the extraction of embedded systems applications.
Efficient and effective branch reordering using profile data
Authors: Yang Minghui , Uh Gang-Ryung , Whalley David B.
Published: January 2003

The conditional branch has long been considered an expensive operation. The relative cost of conditional branches has increased as recently designed machines are now relying on deeper pipelines and higher multiple issue. Reducing the number of conditional branches executed often results in a substantial performance benefit. This paper describes a code-improving transformation to reorder sequences of conditional branches that compare a common variable to constants. The goal is to obtain an ordering where the fewest average number of branches in the sequence will be executed. First, sequences of branches that can be reordered are detected in the control flow. Second, profiling information is collected to predict the probability that each branch will transfer control out of the sequence. Third, the cost of performing each conditional branch is estimated. Fourth, the most beneficial ordering of the branches based on the estimated probability and cost is selected. The most beneficial ordering often includes the insertion of additional conditional branches that did not previously exist in the sequence. Finally, the control flow is restructured to reflect the new ordering. The results of applying the transformation are on average reductions of about 8% fewer instructions executed and 13% branches performed, as well as about a 4% decrease in execution time.
Repairing syntax errors in LR parsers
Authors: Corchuelo Rafael , Pérez, José A. , Ruiz Antonio , Toro Miguel
Published: January 2003

This article reports on an error-repair algorithm for LR parsers. It locally inserts, deletes or shifts symbols at the positions where errors are detected, thus modifying the right context in order to resume parsing on a valid piece of input. This method improves on others in that it does not require the user to provide additional information about the repair process, it does not require precalculation of auxiliary tables, and it can be easily integrated into existing LR parser generators. A Yacc-based implementation is presented along with some experimental results and comparisons with other well-known methods.
Type-Safe linking with recursive DLLs and shared libraries
Authors: Duggan Dominic
Published: January 2003

Component-based programming is an increasingly prevalent theme in software development, motivating the need for expressive and safe module interconnection languages. Dynamic linking is an important requirement for module interconnection languages, as exemplified by dynamic link libraries (DLLs) and class loaders in operating systems and Java, respectively. A semantics is given for a type-safe module interconnection language that supports shared libraries and dynamic linking, as well as circular import dependencies (recursive modules). The core language requirements of the module interconnection language are compatible with programming languages such as Java and C#.
Anisotropic diffusion of surfaces and functions on surfaces
Authors: Bajaj Chandrajit L. , Xu Guoliang
Published: January 2003

We present a unified anisotropic geometric diffusion PDE model for smoothing (fairing) out noise both in triangulated two-manifold surface meshes inIR3and functions defined on these surface meshes, while enhancing curve features on both by careful choice of an anisotropic diffusion tensor. We combine theC1limit representation of Loop's subdivision for triangular surface meshes and vector functions on the surface mesh with the established diffusion model to arrive at a discretized version of the diffusion problem in the spatial direction. The time direction discretization then leads to a sparse linear system of equations. Iteratively solving the sparse linear system yields a sequence of faired (smoothed) meshes as well as faired functions.
Learning style translation for the lines of a drawing
Authors: Freeman William T. , Tenenbaum Joshua B. , Pasztor Egon C.
Published: January 2003

We present an example-based method for translating line drawings into different styles. We fit each line as a linear combination of similar lines in a training set, and interpolate between the corresponding training examples in the output style. The synthesized lines preserve the desired stylistic features of the output style.
Multiresolution green's function methods for interactive simulation of large-scale elastostatic objects
Authors: James Doug L. , Pai Dinesh K.
Published: January 2003

We present a framework for low-latency interactive simulation of linear elastostatic models, and other systems arising from linear elliptic partial differential equations, which makes it feasible to interactively simulate large-scale physical models. The deformation of the models is described using precomputed Green's functions (GFs), and runtime boundary value problems (BVPs) are solved using existing Capacitance Matrix Algorithms (CMAs). Multiresolution techniques are introduced to control the amount of information input and output from the solver thus making it practical to simulate and store very large models. A key component is the efficient compressed representation of the precomputed GFs using second-generation wavelets on surfaces. This aids in reducing the large memory requirement of storing the dense GF matrix, and the fast inverse wavelet transform allows for fast summation methods to be used at run-time for response synthesis. Resulting GF compression factors are directly related to interactive simulation speedup, and examples are provided with hundredfold improvements at modest error levels. We also introduce a multiresolution constraint satisfaction technique formulated as a hierarchical CMA, so named because of its use of hierarchical GFs describing the response due to hierarchical basis constraints. This direct solution approach is suitable for hard real-time simulation since it provides a mechanism for gracefully degrading to coarser resolution constraint approximations. The GFs' multiresolution displacement fields also allow for run-time adaptive multiresolution rendering.