bluuebunny/crossref_metadata_2025 huggingface dataset:
GREATER ARC INJURIES OF THE WRIST TREATED BY INTERNAL AND EXTERNAL FIXATION — SIX CASES WITH MID-TERM FOLLOW-UP
Authors: Kohut G. , Smith A. , Giudici M. , Büchler U.
Published: July 2002

Six cases of greater arc injury, defined as a perilunate dislocation of the carpus with a fracture of at least both the scaphoid and the capitate, were treated by open reposition and both internal and external fixation. Revascularisation of the capitate by implantation of the first dorsal intermetacarpal artery was attempted in three cases. At a mean follow-up of six years and four months, all patients complained of residual pain in the wrist. Carpal mobility and grip strength were reduced, and all patients showed mild or moderate arthritic changes. Progressive cartilage damage over the proximal pole of the capitate seems to be a determining factor in the outcome. Open reposition and both internal and external fixation are recommended in order to possibly diminish the incidence of arthritis and minimise secondary carpal instability.
LESSONS LEARNED FROM APPLYING AI TO THE WEB
Authors: FENSEL DIETER , ANGELE JÜRGEN , DECKER STEFAN , ERDMANN MICHAEL , SCHNURR HANS-PETER , STUDER RUDI , WITT ANDREAS
Published: July 2002

Ontobroker applies Artificial Intelligence techniques to improve access to heterogeneous, distributed and semi-structured information sources as they are presented in the World Wide Web or organization-wide intranets. It relies on the use of ontologies to annotate web pages, formulate queries and derive answers. In this paper we will briefly sketch Ontobroker. Then we will discuss its main shortcomings, i.e. we will share the lessons we learned from our exercise. We will also show how On2broker overcomes these limitations. Most important is the separation of the query and inference engines and the integration of new web standards like XML and RDF.
NONSTEROIDAL ANTI-INFLAMMATORY DRUGS ARREST CELL CYCLE IN G0/G1PHASE AND INDUCE CELL DEATH IN OSTEOBLAST-ENRICHED CULTURES
Authors: HO MEI-LING , CHANG JE-KEN , TSAI HSIU-TING , CHO MING-HSUANG , WANG GWO-JAW
Published: July 2002

Nonsteroidal anti-inflammatory drugs have been widely prescribed for orthopaedic patients to relieve pain and chronic inflammation. However, it has been demonstrated that NSAIDs suppress bone repair and remodeling in vivo. We have reported that ketorolac inhibits bone repair in vivo and its critical effective timing is at the early stage of endochondral ossification. Our previous results showed that ketorolac and indomethacin inhibit osteoblast proliferation in vitro, suggesting that this effect may be one of the mechanisms contributing to the suppressive effect of NSAIDs on bone remodeling. Cell proliferation and death of osteoblasts should be well regulated through some relative apoptotic and mitotic factors during normal bone remodeling process. Accordingly, we proposed that the induction of osteoblastic cell death of NSAIDs might be one of the mechanisms involving their suppressive effect on bone remodeling in vivo. In this study, we investigated whether NSAIDs arrest osteoblastic cell cycle and/or induce cell death. Whether the mechanism was mediated through prostaglandin (PG) pathway. We tested the effects of ketorolac, indomethacin, diclofenac, piroxicam on cell cycle kinetics, cytotoxicity, and cell death pattern in osteoblast-enriched cultures derived from fetal rat calvaria. Our results showed that ketorolac and indomethacin arrested cell cycle at G0/G1phase. All the 4 NSAIDs had cytotoxic effects and these effects were concentration dependent. The sequence of the cytotoxic effects of these four NSAIDs at 10-4M were indomethacin > diclofenac > ketorolac > piroxicam. Both PGE1and PGE2(10-10-10-8M) also significantly elevated the LDH leakage of osteoblasts, while PGF2αhad no significant effect. These results revealed that the cytotoxic effects of NSAIDs on osteoblasts might not be through inhibiting prostaglandin synthesis. They may be through PG-independent pathways. The results from flow cytometry followed by AnnexinV-FITC and propidium iodide double staining showed that 24 hours treatment of all the 4 NSAIDs (10-6and 10-4M) significantly induced both apoptosis (p<0.01) and necrosis (p<0.01, or p<0.05) in osteoblast cultures. These effects of NSAIDs on cell cycle arrest and cell death induction in osteoblasts may be one of the important mechanisms contributing to their suppressive effect on bone repair and bone remodeling in vivo.
A LARGE DEVIATION APPROACH TO PORTFOLIO MANAGEMENT
Authors: GARDIOL L. , GIBSON R. , BARES P.-A. , CONT R. , GYGER S.
Published: July 2002

We propose a new framework to measure the risk of a single asset and of a portfolio of financial assets which takes the agent's investment horizon into account. The methodology is based on the moderate and large deviations theory in its simplest form. We show how it can be used to select optimal portfolios given investors' planning horizons and preferences for fatter right or left tails. For practical purposes, we introduce a new parameter, the "dilation exponent" α to characterize asset returns' distributions beyond the information contained in the mean-variance framework. We estimate α for Swiss individual stocks and for MSCI country and sector stock market indices. Finally, we show how to use the dilation exponent in conjunction with Sharpe's ratio for portfolio allocation purposes.
RNA In Silico The Computational Biology of RNA Secondary Structures
Authors: Flamm Chirstoph , Hofacker Ivo L. , Stadler Peter F.
Published: July 2002

RNA secondary structures provide a unique computer model for investigating the most important aspects of structural and evolutionary biology. The existence of efficient algorithms for solving the folding problem, i.e., for predicting the secondary structure given only the sequence, allows the construction of realistic computer simulations. The notion of a "landscape" underlies both the structure formation (folding) and the (in vitro) evolution of RNA.

Evolutionary adaptation may be seen as hill climbing process on a fitness landscape which is determined by the phenotype of the RNA molecule (within the model this is its secondary structure) and the selection constraints acting on the molecules. We find that a substantial fraction of point mutations do not change an RNA secondary structure. On the other hand, a comparable fraction of mutations leads to very different structures. This interplay of smoothness and ruggedness (or robustness and sensitivity) is a generic feature of both RNA and protein sequence-structure maps. Its consequences, "shape space covering" and "neutral networks" are inherited by the fitness landscapes and determine the dynamics of RNA evolution. Punctuated equilibria at phenotype level and a diffusion like evolution of the underlying genotypes are a characteristics feature of such models. As a practical application of these theoretical findings we have designed an algorithm that finds conserved (and therefore potentially functional substructures of RNA virus genomes from spares data sets.

The folding dynamics of particular RNA molecule can also be studied successfully based on secondary structure. Given an RNA sequence, we consider the energy landscape formed by all possible conformations (secondary structures). A straight formward implementation of the Metropolis algorithm is sufficient to produce a quite realistic folding kinetics, allowing to identify meta-stable states and folding pathways. Just as in the protein case there are good and bad folders which can be distinguished by the properties of their landscapes.
Coevolutionary Learning and the Design of Complex Systems
Authors: Juillé Hugues , Pollack Jordan B.
Published: July 2002

Complex systems composed of a large number of loosely coupled entities, with no central coordination offer a number of attractive properties like scalability, robustness or massively distributed computation. However, designing such complex systems presents some challenging issues that are difficult to tackle with traditional top-down engineering methodologies.

Coevolutionary learning, which involves the embedding of adaptive learning agents in a fitness environment that dynamically responds to their progress, is proposed as a paradigm to explore a space of complex system designs. It is argued that coevolution offers a flexible framework for the implementation of search heuristics that can efficiently exploit some of the structural properties exhibited by such state spaces. However, several drawbacks have to be overcome in order for coevolutionary learning to achieve continuous progress in the long term. This paper presents some of those problems and introduces a new strategy based on the concept of an "ideal" trainer to address them. This presentation is illustrated with a case study: the discovery of cellular automata rules to implement a classification task. The application of the "ideal" trainer paradigm to that problem resulted in a significant improvement over previously known best rules for this task.
Sparse extensions to the FORTRAN Basic Linear Algebra Subprograms
Authors: Dodson David S. , Grimes Roger G. , Lewis John G.
Published: July 2002

This paper describes an extension to the set of Basic Linear Algebra Subprograms. The extension is targeted at sparse vector operations, with the goal of providing efficient, but portable, implementations of algorithms for high-performance computers.
Conceptual learning in database design
Authors: Ionnidis Yannis E. , Saulys Tomas , Whitsitt Andrew J.
Published: July 2002

This paper examines the idea of incorporating machine learning algorithms into a database system for monitoring its stream of incoming queries and generating hierarchies with the most important concepts expressed in those queries. The goal is for these hierarchies to provide
valuable input to the database administrator for dynamically modifying the physical and external schemas of a database for improved system performance and user productivity. The criteria for choosing the appropriate learning algorithms are analyzed, and based on them, two such algorithms, UNIMEM and COBWEB, are selected as the most suitable ones for the task. Standard UNIMEM and COBWEB implementations have been modified to support queries as input. Based on the results of experiments with these modified implementations, the whole approach appears to be quite promising, expecially if the concept hierarchy from which the learning algorithms start their processing is initialized with some of the most obvious concepts captured in the database.
Adaptable concurrency control for atomic data types
Authors: Atkins M. S. , Coady M. Y.
Published: July 2002

In many distributed systems concurrent access is required to a shared object, where abstract object servers may incorporate type-specific properties to define consistency requirements. Each operation and its outcome is treated as an event, and conflicts may occur between different event types. Hence concurrency control and synchronization are required at the granularity of conflicting event types. With such a fine granularity of locking, the occurrence of conflicts is likely to be lower than with whole-object locking, so optimistic techniques become more attractive.

This work describes the design, implementation, and performance of servers for a shared atomic object, a semiqueue, where each server employs either pessimistic or optimistic locking techniques on each conflicting event type. We compare the performance of a purely optimistic server, a purely pessimistic server, and a hybrid server which treats certain event types optimistically and others pessimistically, to demonstrate the most appropriate environment for using pessimistic, optimistic, or hybrid control. We show that the advantages of low overhead on optimistic locking at low conflict levels is offset at higher conflict levels by the wasted work done by aborted transactions.

To achieve optimum performance over the whole range of conflict levels, an adaptable server is required, whereby the treatment of conflicting event types can be changed dynamically between optimistic and pessimistic, according to various criteria depending on the expected frequency of conflict.

We describe our implementations of adaptable servers which may allocate concurrency control strategy on the basis of state information, the history of conflicts encountered, or by using preset transaction priorities.

We show that the adaptable servers perform almost as well as the best of the purely optimistic, pessimistic, or hybrid servers under the whole range of conflict levels, showing the versatility and efficiency of the dynamic servers.

Finally we outline a general design methodology for implementing adaptable concurrency control in servers for atomic objects, illustrated using an atomic shared B-tree.
File-system development with stackable layers
Authors: Heidemann John S. , Popek Gerald J.
Published: July 2002

Filing services have experienced a number of innovations in recent years, but many of these promising ideas have failed to enter into broad use. One reason is that current filing environments present several barriers to new development. For example, file systems today typically stand alone instead of building on the work of others, and support of new filing services often requires changes that invalidate existing work.

Stackable file-system design addresses these issues in several ways. Complex filing services are constructed from layer “building blocks,” each of which may be provided by independent parties. There are no syntactic constraints to layer order, and layers can occupy different address spaces, allowing very flexible layer configuration. Independent layer evolution and development are supported by an extensible interface bounding each layer.

This paper discusses stackable layering in detail and presents design techniques it enables. We describe an implementation providing these facilities that exhibits very high performance. By lowering barriers to new filing design, stackable layering offers the potential of broad third-party file-system development not feasible today.
A really temporal logic
Authors: Alur Rajeev , Henzinger Thomas A.
Published: July 2002

We introduce a temporal logic for the specification of real-time systems. Our logic, TPTL, employs a novel quantifier construct for referencing time: the
freeze quantifier
binds a variable to the time of the local temporal context.

TPTL is both a natural language for specification and a suitable formalism for verification. We present a tableau-based decision procedure and a model-checking algorithm for TPTL. Several generalizations of TPTL are shown to be highly undecidable.
Line search algorithms with guaranteed sufficient decrease
Authors: Moré Jorge J. , Thuente David J.
Published: July 2002

The development of software for minimization problems is often based on a line search method. We consider line search methods that satisfy sufficient decrease and curvature conditions, and formulate the problem of determining a point that satisfies these two conditions in terms of finding a point in a set
T(μ)
. We describe a search algorithm for this problem that produces a sequence of iterates that converge to a point in
T(μ)
and that, except for pathological cases, terminates in a finite number of steps. Numerical results for an implementation of the search algorithm on a set of test functions show that the algorithm terminates within a small number of iterations.
The complexity of probabilistic verification
Authors: Courcoubetis Costas , Yannakakis Mihalis
Published: July 2002

We determine the complexity of testing whether a finite state, sequential or concurrent probabilistic program satisfies its specification expressed in linear-time temporal logic. For sequential programs, we present an algorithm that runs in time linear in the program and exponential in the specification, and also show that the problem is in PSPACE, matching the known lower bound. For concurrent programs, we show that the problem can be solved in time polynomial in the program and doubly exponential in the specification, and prove that it is complete for double exponential time. We also address these questions for specifications described by ω-automata or formulas in extended temporal logic.
A note on combination generators
Authors: Gan C. T.
Published: July 2002

A recent study by Akl indicates that Mifsud's algorithm, which involves unnecessary searching operations, is the fastest existing combination generator. A modified Page and Wilson's algorithm, which is essentially similar to Mifsud's algorithm, is presented. A theoretical analysis of the modified algorithm is also given.
Electronic markets and electronic hierarchies
Authors: Malone Thomas W. , Yates Joanne , Benjamin Robert I.
Published: July 2002

By reducing the costs of coordination, information technology will lead to an overall shift toward proportionately more use of markets—rather than hierarchies—to coordinate economic activity.
Describing Prolog by its interpretation and compilation
Authors: Cohen Jacques
Published: July 2002

Since its conception, Prolog has followed a developmental course similar to the early evolution of LISP. Although the version of Prolog described here typifies that currently in use, it should be considered within the framework of language evolution.
Production and playback of human figure motion for visual simulation
Authors: Granieri John P. , Crabtree Jonathan , Badler Norman I.
Published: July 2002

We describe a system for off-line production and real-time playback of motion for articulated human figures in 3D virtual environments. The key notion are (1) the logical storage of full-body motion in posture graphs, which provides a simple motion access method for playback, and (2) mapping the motions of high DOF figures to lower DOF figures using slaving to provide human models at several levels of detail, both in geometry and articulation, for later playback. We present our system in the context of a simple problem: animating human figures in a distributed simulation, using DIS protocols for communicating the human state information. We also discuss several related techniques for real-time animation of articulated figures in visual simulation.
Risks of social security numbers
Authors: Garfinkel Simson L.
Published: July 2002

The problem with social security numbers today is that some organizations are using these ubiquitous numbers for identification, others are using them for authentication, and still others are using them for both. I call up my bank, tell them my account number and ask them for a balance. Just to make sure that I am really who I claim to be, my bank asks for my SSN—as if this is a number that is some kind of secret that we share.
Interpolation with interval and point tension controls using cubic weighted
v
-splines
Authors: Foley Thomas A.
Published: July 2002

Various methods have been developed to control the shape of an interpolating curve for computer-aided design applications. Some methods are better suited for controlling the tension of the curve on an interval, while others are better suited for controlling the tension at the individual interpolation points. The weighted
v
-spline is a C
1
piecewise cubic polynomial interpolant that generalizes C
2
cubic splines, weighted splines, and
v
-splines. Shape controls are available to “tighten” the weighted
v
-spline on intervals and/or at the interpolation points. The mathematical theory is presented together with short algorithms for parametric interpolation.
Algorithm 759: VLUGR3
Authors: Blom J. G. , Verwer J. G.
Published: July 2002

This article describes an ANSI Fortran 77 code, VLUGR3, autovectorizable on the Cray Y-MP, that is based on an adaptive-grid finite-difference method to solve time-dependent three-dimensional systems of partial differential equations.
A field study of exploratory learning strategies
Authors: Rieman John
Published: July 2002

It has suggested that interactive computer users find “exploratory learning” to be an effective and attractive strategy for learning a new system or investigating unknown features of familiar software. In exploratory learning, instead of working through precisely sequenced training materials, the user investigates a system on his or her own initiative, often in pursuit of a real or artificial task. The value of exploratory learning has been studied in controlled settings, with special attention newly acquired systems, be there has been little investigation of its occurrence in natural situations or in support of ongoing learning. To address this question, a field study of the behavior and attitudes of computer users in everyday working situations was performed, using diaries and structured interviews that focused on learning events. The study showed that task-oriented exploration was a widely accepted method for learning, but that it often required support from manuals and from other users or system support personnel. Exploration not related to a current or pending task was infrequent, and most users believed it to be inefficient. These findings have implications for the design of systems, documentation, and training.
A new approach to the minimum cut problem
Authors: Karger David R. , Stein Clifford
Published: July 2002

This paper present a new approach to finding minimum cuts in undirected graphs. The fundamental principle is simple: the edges in a graph's minimum cut form an extremely small fraction of the graph's edges. Using this idea, we give a randomized, strongly polynomial algorithm that finds the minimum cut in an arbitrarily weighted undirected graph with high probability. The algorithm runs in

O(n
2
log
3
n)

time, a significant improvement over the previous
O˜(mn)
time bounds based on maximum flows. It is simple and intuitive and uses no complex data structures. Our algorithm can be parallelized to run in
RNC
with

n
2

processors; this gives the first proof that the minimum cut problem can be solved in
RNC
. The algorithm does more than find a single minimum cut; it finds all of them.

With minor modifications, our algorithm solves two other problems of interest. Our algorithm finds all cuts with value within a multiplicative factor of α of the minimum cut's in expected

O˜(n
2α
)

time, or in
RNC
with

n
2α

processors. The problem of finding a minimum multiway cut of graph into
r
pieces is solved in expected

O˜(n
2(r-1)
)

time, or in
RNC
with

n
2(r-1)

processors. The “trace” of the algorithm's execution on these two problems forms a new compact data structure for representing all small cuts and all multiway cuts in a graph. This data structure can be efficiently transformed into the more standard cactus representing for minimum cuts.
Scheduling techniques for variable voltage low power designs
Authors: Lin Yann-Rue , Hwang Cheng-Tsung , Wu Allen C.-H.
Published: July 2002

This paper presents an integer linear programming (ILP) model and a heuristic for the variable voltage scheduling problem. We present the variable voltage scheduling techniques that consider in turn timing constraints alone, resource constraints alone, and timing and resource constraints together for design space exploration. Experimental results show that our heuristic produces results competitive with those of the ILP method in a fraction of the run-time. The results also show that a wide range of design alternatives can be generated using our design space exploration method. Using different cost/delay combinations, power consumption in a single design can differ by as much as a factor of 6 when using mixed 3.3V and 5V supply voltages.
Nanites
Authors: Rodham Kenneth J. , Olsen Dan R.
Published: July 2002

The focal point of many interactive systems is an information artifact being created and manipulated by one or more users through a user interface. The software components of such an interactive system perform their tasks relative to the data structures that represent the information artifact. System components interact with each other by changing these data and responding when relevant changes are made to them by other components. Perhaps the most difficult problem to be solved when building such data-centric systems is the monitoring problem. System components require the ability to watch for and respond to changes made to complex data structures. Previous monitoring approaches are geared toward monitoring single data items rather than entire data structures. This article describes an new monitoring approach called Nanites that is designed to simplify the task of monitoring complex data structures.
Optimal signature extraction and information loss
Authors: Faloutsos Christos , Christodoulakis Stavros
Published: July 2002

Signature files seem to be a promising access method for text and attributes. According to this method, the documents (or records) are stored sequentially in one file ("text file"), while abstractions of the documents ("signatures") are stored sequentially in another file ("signature file"). In order to resolve a query, the signature file is scanned first, and many nonqualifying documents are immediately rejected. We develop a framework that includes primary key hashing, multiattribute hashing, and signature files. Our effort is to find the optimal signature extraction method.

The main contribution of this paper is that we present optimal and efficient suboptimal algorithms for assigning words to signatures in several environments. Another contribution is that we use information theory, and study the relationship of the false drop probability

F
d

and the information that is lost during signature extraction. We give tight lower bounds on the achievable

F
d

and show that a simple relationship holds between the two quantities in the case of optimal signature extraction with uniform occurrence and query frequencies. We examine hashing as a method to map words to signatures (instead of the optimal way), and show that the same relationship holds between

F
d

and
loss
, indicating that an invariant may exist between these two quantities for every signature extraction method.
The part-time parliament
Authors: Lamport Leslie
Published: July 2002

Recent archaeological discoveries on the island of Paxos reveal that the parliament functioned despite the peripatetic propensity of its part-time legislators. The legislators maintained consistent copies of the parliamentary record, despite their frequent forays from the chamber and the forgetfulness of their messengers. The Paxon parliament's protocol provides a new way of implementing the state machine approach to the design of distributed systems.
A hypermedia version control framework
Authors: Hicks David L. , Leggett John J. , Nürnberg Peter J. , Schnase John L.
Published: July 2002

The areas of application of hypermedia technology, combined with the capabilities that hypermedia provides for manipulating structure, create an environment in which version control is very important. A hypermedia version control framework has been designed to specifically address the version control problem in open hypermedia environments. One of the primary distinctions of the framework is the partitioning of hypermedia version control functionality into intrinsic and application-specific categories. The version control has been used as a model for the design of version control services for a hyperbase management system that provides complete version support for both data and structural entities. In addition to serving as a version control model for open hypermedia environments, the framework offers a clarifying and unifying context in which to examine the issues of version control in hypermedia.
Technical note
Authors: Coe P. S. , Howell F. W. , Ibbett R. N. , Williams L. M.
Published: July 2002

A hierarchical computer architecture design and simulation environment (HASE) has been developed at the University of Edinburgh. HASE allows rapid development and exploration of computer architectures at multiple levels of abstraction, encompassing both hardware and software. It has five modes of operation (Design, Model Validation, Build Simulation, Simulate System, and Experiment) which formalize the design cycle and allow a proper separation of concerns among the different phases of simulation activity. The software of HASE itself includes a project data storage facility, a discrete-event simulation engine, graphical display/ editing mechanisms, a visualization mechanism, and tools for setting up experiments and gathering results. HASE has been used in a number of research and student projects and these exemplify many of the interesting features of HASE and their relation to designing, simulating and evaluating scalable systems. They include the modeling of scalable implementations of the hierarchical PRAM model of parallel computation on a 2-D mesh, the evaluation of the performance of multiprocessor interconnection networks, and a model of the Stanford DASH architecture.
Modeling reactive systems in Java
Authors: Passerone C. , Sansoe C. , Lavagno L. , McGeer R. , Martin J. , Passerone R. , Sangiovanni-Vincentelli A.
Published: July 2002

We present an application of the Java
TM
programming language to specify and implement reactive real-time systems. We have developed and tested a collection of classes and methods to describe concurrent modules and their asynchronous communication by means of signals. The control structures are closely patterned after those of the synchronous language
Esterel
, succinctly describing concurrency, sequencing and preemption. We show the user-friendliness and efficiency of the proposed technique by using an example from the automotive domain.
GENOA—a customizable, front-end-retargetable source code analysis framework
Authors: Devanbu Premkumar T.
Published: July 2002

Code analysis
tools provide support for such software engineering tasks as program understanding, software metrics, testing, and reengineering. In this article we describe GENOA, the framework underlying application generators such as Aria and GEN++ which have been used to generate a wide range of practical code analysis tools. This experience illustrates
front-end retargetability
of GENOA; we describe the features of the GENOA framework that allow it to be used with different front ends. While permitting arbitrary parse tree computations, the GENOA specification language has special, compact iteration operators that are tuned for expressing simple, polynomial-time analysis programs; in fact, there is a useful sublanguage of the GENOA language that can express precisely all (and only)
polynomial-time
(PTIME) analysis programs on parse trees. Thus, we argue that the GENOA language is a simple and convenient vehicle for implementing a range of analysis tools. We also argue that the “front-and reuse” approach of GENOA offers an important advantage for tools aimed at large software projects: the reuse of complex, expensive build procedures to run generated tools over large source bases. In this article, we describe the GENOA framework and our experiences with it.
Algorithm 790: CSHEP2D
Authors: Renka Robert J.
Published: July 2002

We describe a new algorithm for scattered data interpolation. The method is similar to that of Algorithm 660 but achieves cubic precision and
C
2
continuity at very little additional cost. An accompanying article presents test results that show the method to be among the most accurate available.
A partial test of the task-medium fit proposition in a group support system environment
Authors: Tan Bernard C. Y. , Wei Kwok-kee , Sia Choon-Ling , Raman Krishnamurthy S.
Published: July 2002

A laboratory experiment was carried out to partially test the
task-medium fit proposition in a GSS environment. Communication medium was varied using a face-to-face GSS and a dispersed GSS setting. Task type was varied using an intellective and a preference task. Group decision outcome variables of interest were (actual and perceived) decision quality, decision time, decision satisfaction, and decision process satisfaction. With the intellective task, there were no significant differences between face-to-face GSS and dispersed GSS groups for all group decision outcome variables. With the preference task, face-to-face GSS groups performed significantly better than dispersed GSS groups for all group decision outcome variables. These findings suggest that group decision outcomes in a GSS environment tend to be adversely affected when the communication medium is too lean for the task but not when the communication medium is too rich for the task. Consequences of providing groups with too rich and too lean a communication medium for their task are discussed. Implications of these findings, and other related results, for practice and for future revisions of media richness theory are explored.
A statistical approach to incomplete information in database systems
Authors: Wong Eugene
Published: July 2002

There are numerous situations in which a database cannot provide a precise answer to some of the questions that are posed. Sources of imprecision vary and include examples such as recording errors, incompatible scaling, and obsolete data. In many such situations, considerable prior information concerning the imprecision exists and can be exploited to provide valuable information for queries to which no exact answer can be given. The objective of this paper is to provide a framework for doing so.
Retrospection on a database system
Authors: Stonebraker Michael
Published: July 2002

This paper describes the implementation history of the INGRES database system. It focuses on mistakes that were made in progress rather than on eventual corrections. Some attention is also given to the role of structured design in a database system implementation and to the problem of supporting nontrivial users. Lastly, miscellaneous impressions of UNIX, the PDP-11, and data models are given.
A Study of Methods for Systematically Abbreviating English Words and Names
Authors: Bourne Charles P. , Ford Donald F.
Published: July 2002

This study investigated various techniques for systematically abbreviating English words and names. Most of the attention was given to the techniques which could be mechanized with a digital device such as a general purpose digital computer. Particular attention was paid to techniques that could process incoming information without prior knowledge of its existence (i.e., no table lookups). Thirteen basic techniques and their modifications are described. In addition, most of the techniques were tested on a sample of several thousand subject words and several thousand proper names in order to provide a quantitative measure of comparison.
On a Continuous Method of Approximating Solutions of the Heat Equation
Authors: Sigillito V. G.
Published: July 2002

Theoretical methods, based on a priori pointwise bounds, for approximating solutions of many elliptic and parabolic initial and/or boundary value problems, have been developed in recent years. These methods, however, are relatively unknown to potential users since applications of the methods have not appeared in the literature. In this paper their usefulness is illustrated by employing some of the author's theoretical results as a basis for the construction of a digital program to compute an approximate solution of an initial boundary value problem for the heat equation.
An Algorithm for the Inversion of Block Matrices of Toeplitz Form
Authors: Watson G. A.
Published: July 2002

An algorithm of W. F. Trench is generalized to apply to the inversion of block matrices of Toeplitz form.
New Algorithms and Lower Bounds for the Parallel Evaluation of Certain Rational Expressions and Recurrences
Authors: Kung H. T.
Published: July 2002

The parallel evaluation of rational expressions is considered. New algorithms which minimize the number of multiplication or division steps are given. They are faster than the usual algorithms when multiplication or division takes more time than addition or subtraction. It is shown, for example, that

x
n

can be evaluated in two steps of parallel division and ⌈log
2
n
⌉ steps of parallel addition, while the usual algorithm takes ⌈log
2
n
⌉ steps of parallel multiplication.

Lower bounds on the time required are obtained in terms of the degree of the expressions to be evaluated. From these bounds, the algorithms presented in the paper are shown to be asymptotically optimal. Moreover, it is shown that by using parallelism the evaluation of any first-order rational recurrence of degree greater than 1, e.g.
y

i
+1

= 1/2;(

y
i

+
a
/

y
i

), and any nonlinear polynomial recurrence can be sped up at most by a constant factor, no matter how many processors are used and how large the size of the problem is.
A Simple Approximation to the Average Queue Size in the Time-Dependent M/M/1 Queue
Authors: Rider Kenneth Lloyd
Published: July 2002

The time-dependent equations for the M/M/1 queue can be reduced to a single equation for the expected queue size, but the equation is dependent on
P
0
(
t
), the probability of no jobs in the system. An exact equation for the behavior of
P
0
(
t
) under special conditions is derived and an approximation relating
P
0
(
t
) to
Q
(
t
), the expected queue size at time
t
, is derived for the case when the change in queue size is slow compared to the service rate. It is found that the approximation affords a significant improvement over the use of a steady state approximation to the time-dependent queue and is simpler to use than the exact equations.
Restructuring of Arithmetic Expressions For Parallel Evaluation
Authors: Muller David E. , Preparata Franco P.
Published: July 2002

Let
E
be an arithmetic expression involving
n
variables, each of which appears just once, and the possible operations of addition, multiplication, and division. Although other cases are considered, when these three operations take unit time the restructuring algorithms presented in this paper yield evaluation times no greater than 2.88 log
2
n
+ 1 and 2.08 log
2
n
for general expressions and division-free expressions, respectively. The coefficients are precisely given by 2/log
2
α ≈ 2.88 and 1/log
2
β
≈ 2.08, where
α
and
β
are the positive real roots of the equations
z
2
=
z
+ 1 and
z
4
= 2
z
+ 1, respectively. While these times were known to be of order log
2
n
, the best previously known coefficients were 4 and 2.15 for the two cases.

The authors conjecture that the present coefficients are the best possible, since they have exhibited expressions which seem to require these times within an additive constant.

The paper also gives upper bounds to the restructuring time of a given expression
E
and to the number of processors required for its parallel evaluation. It is shown that at most
O
(n
1.44
)
and
O
(n
1.82
)
operations are needed for restructuring general expressions and division-free expression, respectively.

It is pointed out that, since the order of the compiling time is greater than
n
log
n
, the numbers of required processors exhibit the same rate of growth in
n
as the corresponding compiling times.
Heuristic Algorithms for Scheduling Independent Tasks on Nonidentical Processors
Authors: Ibarra Oscar H. , Kim Chul E.
Published: July 2002

The finishing time properties of several heuristic algorithms for scheduling
n
independent tasks on
m
nonidentical processors are studied. In particular, for
m
= 2 an
n
log
n
time-bounded algorithm is given which generates a schedule having a finishing time of at most (√5 + 1)/2 of the optimal finishing time. A simplified scheduling problem involving identical processors and restricted task sets is shown to be P-complete. However, the LPT algorithm applied to this problem yields schedules which are near optimal for large
n
.
A proposed solution to the problem of levels in error-message generation
Authors: Efe Kemal
Published: July 2002

A simple "lets talk about it" strategy is developed that enables users to explore lower level error messages through dialogue.
The vocabulary problem in human-system communication
Authors: Furnas G. W. , Landauer T. K. , Gomez L. M. , Dumais S. T.
Published: July 2002

In almost all computer applications, users must enter correct words for the desired objects or actions. For success without extensive training, or in first-tries for new targets, the system must recognize terms that will be chosen spontaneously. We studied spontaneous word choice for objects in five application-related domains, and found the variability to be surprisingly large. In every case two people favored the same term with probability <0.20. Simulations show how this fundamental property of language limits the success of various design methodologies for vocabulary-driven interaction. For example, the popular approach in which access is via one designer's favorite single word will result in 80-90 percent failure rates in many common situations. An optimal strategy, unlimited aliasing, is derived and shown to be capable of several-fold improvements.
Reaching Agreement in the Presence of Faults
Authors: Pease M. , Shostak R. , Lamport L.
Published: July 2002

The problem addressed here concerns a set of isolated processors, some unknown subset of which may be faulty, that communicate only by means of two-party messages. Each nonfaulty processor has a private value of information that must be communicated to each other nonfaulty processor. Nonfaulty processors always communicate honestly, whereas faulty processors may lie. The problem is to devise an algorithm in which processors communicate their own values and relay values received from others that allows each nonfaulty processor to infer a value for each other processor. The value inferred for a nonfaulty processor must be that processor's private value, and the value inferred for a faulty one must be consistent with the corresponding value inferred by each other nonfaulty processor.

It is shown that the problem is solvable for, and only for,
n
≥ 3
m
+ 1, where
m
is the number of faulty processors and
n
is the total number. It is also shown that if faulty processors can refuse to pass on information but cannot falsely relay information, the problem is solvable for arbitrary
n
≥
m
≥ 0. This weaker assumption can be approximated in practice using cryptographic methods.
Authoritative sources in a hyperlinked environment
Authors: Kleinberg Jon M.
Published: July 2002

The network structure of a hyperlinked environment can be a rich source of information about the content of the environment, provided we have effective means for understanding it. We develop a set of algorithmic tools for extracting information from the link structures of such environments, and report on experiments that demonstrate their effectiveness in a variety of context on the World Wide Web. The central issue we address within our framework is the distillation of broad search topics, through the discovery of “authorative” information sources on such topics. We propose and test an algorithmic formulation of the notion of authority, based on the relationship between a set of relevant authoritative pages and the set of “hub pages” that join them together in the link structure. Our formulation has connections to the eigenvectors of certain matrices associated with the link graph; these connections in turn motivate additional heuristrics for link-based analysis.
Generality in artificial intelligence
Authors: McCarthy John
Published: July 2002

My 1971 Turing Award Lecture was entitled "Generality in Artificial Intelligence." The topic turned out to have been overambitious in that I discovered I was unable to put my thoughts on the subject in a satisfactory written form at that time. It would have been better to have reviewed my previous work rather than attempt something new, but such was not my custom at that time.

I am grateful to ACM for the opportunity to try again. Unfortunately for our science, although perhaps fortunately for this project, the problem of generality in artificial intelligence (AI) is almost as unsolved as ever, although we now have many ideas not available in 1971. This paper relies heavily on such ideas, but it is far from a full 1987 survey of approaches for achieving generality. Ideas are therefore discussed at a length proportional to my familiarity with them rather than according to some objective criterion.

It was obvious in 1971 and even in 1958 that AI programs suffered from a lack of generality. It is still obvious; there are many more details. The first gross symptom is that a small addition to the idea of a program often involves a complete rewrite beginning with the data structures. Some progress has been made in modularizing data structures, but small modifications of the search strategies are even less likely to be accomplished without rewriting.

Another symptom is no one knows how to make a general database of commonsense knowledge that could be used by any program that needed the knowledge. Along with other information, such a database would contain what a robot would need to know about the effects of moving objects around, what a person can be expected to know about his family, and the facts about buying and selling. This does not depend on whether the knowledge is to be expressed in a logical language or in some other formalism. When we take the logic approach to AI, lack of generality shows up in that the axioms we devise to express commonsense knowledge are too restricted in their applicability for a general commonsense database. In my opinion, getting a language for expressing general commonsense knowledge for inclusion in a general database is the key problem of generality in AI.

Here are some ideas for achieving generality proposed both before and after 1971. I repeat my disclaimer of comprehensiveness.
Static scheduling algorithms for allocating directed task graphs to multiprocessors
Authors: Kwok Yu-Kwong , Ahmad Ishfaq
Published: July 2002

Static scheduling of a program represented by a directed task graph on a multiprocessor system to minimize the program completion time is a well-known problem in parallel processing. Since finding an optimal schedule is an NP-complete problem in general, researchers have resorted to devising efficient heuristics. A plethora of heuristics have been proposed based on a wide spectrum of techniques, including branch-and-bound, integer-programming, searching, graph-theory, randomization, genetic algorithms, and evolutionary methods. The objective of this survey is to describe various scheduling algorithms and their functionalities in a contrasting fashion as well as examine their relative merits in terms of performance and time-complexity. Since these algorithms are based on diverse assumptions, they differ in their functionalities, and hence are difficult to describe in a unified context. We propose a taxonomy that classifies these algorithms into different categories. We consider 27 scheduling algorithms, with each algorithm explained through an easy-to-understand description followed by an illustrative example to demonstrate its operation. We also outline some of the novel and promising optimization approaches and current research trends in the area. Finally, we give an overview of the software tools that provide scheduling/mapping functionalities.
Social translucence
Authors: Erickson Thomas , Kellogg Wendy A.
Published: July 2002

We are interested in desiging systems that support communication and collaboration among large groups of people over computing networks. We begin by asking what properties of the physical world support graceful human-human communication in face-to-face situations, and argue that it is possible to design digital systems that support coherent behavior by making participants and their activites visible to one another. We call such systems “socially translucent systems” and suggest that they have three characteristics—visbility, awareness, and accountability—which enable people to draw upon their experience and expertise to structure their interactions with one another. To motivate and focus our ideas we develop a vision of knowledge communities, conversationally based systems that support the creation, management and reuse of knowledge in a social context. We describe our experience in designing and deploying one layer of functionality for knowledge communities, embodied in a working system called “Barbie” and discuss research issues raised by a socially translucent approach to design.