bluuebunny/crossref_metadata_2025 huggingface dataset:
Lower bounds for distributed coin-flipping and randomized consensus
Authors: Aspnes James
Published: July 2002

We examine a class of
collective coin-flipping games
that arises from randomized distributed algorithms with halting failures. In these games, a sequence of
local coin flips
is generated, which must be combined to form a single
global coin flip
. An adversary monitors the game and may attempt to bias its outcome by hiding the result of up to
t
local coin flips. We show that to guarantee at most constant bias, ω(
t
2
) local coins are needed, even if (a) the local coins can have arbitrary distributions and ranges, (b) the adversary is required to decide immediately wheter to hide or reveal each local coin, and (c) the game can detect which local coins have been hidden. If the adversary is permitted to control the outcome of the coin except for cases whose probability is polynomial in
t
, ω(
t
2
/log
2
t
) local coins are needed. Combining this fact with an extended version of the well-known Fischer-Lynch-Paterson impossibility proof of deterministic consensus, we show that given an adaptive adversary, any
t
-resilient asynchronous consensus protocol requires ω(
t
2
/log
2
t
) local coin flips in any model that can be simulated deterministically using atomic registers. This gives the first nontrivial lower bound on the total work required by wait-free consensus and is tight to within logarithmic factors.
Infinitesimal perturbation analysis for general discrete event systems
Authors: Suri Rajan
Published: July 2002

A rigorous extension of the recent perturbation analysis approach to more general discrete event systems is given. First, a general class of systems and performance measures is defined, and some basic reprsentational and linearity properties are derived. Next a
sample gradient
of performance with respect to a parameter of the system is defined. Then, for certain parameters of such systems, an infinitesimal perturbation analysis algorithm is derived. It is proved that this algorithm gives
exact
values for the sample gradients of performance with respect to the parameters, by observing only
one
sample path of the DEDS. (However, the sample gradient may or may not be a good estimate of the gradient of the performance measure; this point is elaborated in the body of the paper.) The computational complexity of this algorithm is bound to be linear in the number of events. These results offer the potential for very efficient calculation of the gradients—a fact that can be used for design/operation of computer systems, communication networks, manufacturing systems, and many other real-world systems, particularly since restrictive assumptions (e.g., exponential distributions) are not required of the system.
Electrostatic fields without singularities
Authors: Pellegrini Marco
Published: July 2002

The following problems that arise in the computation of electrostatic forces and in the Boundary Element Method are considered. Given two convex interior-disjoint polyhedra in 3-space endowed with a volume charge density which is a polynomial in the Cartesian coordinates of
R
3
, compute the Coulomb force acting on them. Given two interior-disjoint polygons in 3-space endowed with a surface charge density which is polynomial in the Cartesian coordinates of
R
3
, compute the normal component of the Coulomb force acting on them. For both problems adaptive Gaussian approximation algorithms are given, which, for
n
Gaussian points, in time O(
n
), achieve absolute error

O(c
-√n

) for a constant
c
> 1. Such a result improves upon previously known best asymptotic bounds. This result is achieved by blending techniques from integral geometry, computational geometry and numerical analysis. In particular, integral geometry is used in order to represent the forces as integrals whose kernal is free from singularities.
A corpus analysis approach for automatic query expansion and its extension to multiple databases
Authors: Gauch Susan , Wang Jianying , Rachakonda Satya Mahesh
Published: July 2002

Searching online text collections can be both rewarding and
frustrating. While valuable information can be found, typically many irrelevant documents are also retrieved, while many relevant ones are missed. Terminology mismatches between the user's query and document contents are a main cause of retrieval failures. Expanding a user's query with related words can improve search performances, but finding and using related words is an open problem. This research uses corpus analysis techniques to automatically discover similar words directly from the contents of the databases which are not tagged with part-of-speech labels. Using these similarities, user queries are automatically expanded, resulting in conceptual retrieval rather than requiring exact word matches between queries and documents. We are able to achieve a 7.6% improvement for TREC 5 queries and up to a 28.5% improvement on the narrow-domain Cystic Fibrosis collection. This work has been extended to multidatabase collections where each subdatabase has a collection-specific similarity matrix associated with it. If the best matrix is selected, substantial search improvements are possible. Various techniques to select the appropriate matrix for a particular query are analyzed, and a 4.8% improvement in the results is validated.
A practical guide to the design of differential files for recovery of on-line databases
Authors: Aghili Houtan
Published: July 2002

The concept of a differential file has previously been proposed as an efficient means of collecting database updates for on-line systems. This paper studies the problem of database backup and recovery for such systems, and presents an analytic model of their operation. Five key design decisions are identified and an optimization procedure for each is developed. A design algorithm that quickly provides parameters for a near-optimal differential file architecture is provided.
Multivariable Curve Interpolation
Authors: Ferguson James
Published: July 2002

The problem of defining a smooth surface through an array of points in space is well known. Several methods of solution have been proposed. Generally, these restrict the set of points to be one-to-one defined over a planar rectangular grid (
X
,
Y
-plane). Then a set of functions
Z
=
F
(
X
,
Y
) is determined, each of which represents a surface segment of the composite smooth surface. In this paper, these ideas are generalized to include a much broader class of permissible point array distributions: namely (1) the point arrangement (ordering) is topologically equivalent to a planar rectangular grid, (2) the resulting solution is a smooth composite of parametric surface segments, i.e. each surface piece is represented by a vector (point)-valued function. The solution here presented is readily applicable to a variety of problems, such as closed surface body definitions and pressure envelope surface definitions. The technique has been used successfully in these areas and others, such as numerical control milling, Newtonian impact and boundary layer.
Conversion of Limited-Entry Decision Tables to Optimal Computer Programs II
Authors: Reinwald Lewis T. , Soland Richard M.
Published: July 2002

Given the number of words of computer storage required by the individual tests in a limited-entry decision table, it is sometimes desirable to find an equivalent computer program with minimum total storage requirement. In this paper an algorithm is developed to do this. The rules in the decision table are grouped into action sets, so that several rules with the same actions need not be distinguished. Moreover, if certain combinations of conditions can be excluded from consideration, the algorithm will take advantage of this extra information. The algorithm is initially developed for computer programs possessing a treelike form and then extended to a wider class of programs. The algorithm can be combined with one which finds an equivalent computer program with minimum average processing time, and thus used to find an equivalent computer program which minimizes a cost function which is nondecreasing in both average processing time and total storage requirement.
Syntax-Directed Transduction
Authors: Lewis P. M. , Stearns R. E.
Published: July 2002

A transduction is a mapping from one set of sequences to another. A syntax-directed transduction is a particular type of transduction which is defined on the grammar of a context-free language and which is meant to be a model of part of the translation process used in many compilers. The transduction is considered from an automata theory viewpoint as specifying the input-output relation of a machine. Special consideration is given to machines called translators which both transduce and recognize. In particular, some special conditions are investigated under which syntax-directed translations can be performed on (deterministic) pushdown machines. In addition, some time bounds for translations on Turing machines are derived.
The Unit Proof and the Input Proof in Theorem Proving
Authors: Chang C. L.
Published: July 2002

A resolution in which one of the two parent clauses is a unit clause is called a unit resolution, whereas a resolution in which one of the two parent clauses is an original input clause is called an input resolution. A unit (input) proof is a deduction of the empty clause □ such that every resolution in the deduction is a unit (input) resolution. It is proved in the paper that a set
S
of clauses containing its unit factors has a unit proof if and only if
S
has an input proof. A LISP program implementing unit resolution is described and results of experiments are given.
A Combinatorial Problem Which Is Complete in Polynomial Space
Authors: Even S. , Tarjan R. E.
Published: July 2002

This paper considers a generalization, called the Shannon switching game on vertices, of a familiar board game called Hex. It is shown that determining who wins such a game if each player plays perfectly is very hard; in fact, if this game problem is solvable in polynomial time, then any problem solvable in polynomial space is solvable in polynomial time. This result suggests that the theory of combinational games is difficult.
Markup systems and the future of scholarly text processing
Authors: Coombs James H. , Renear Allen H. , DeRose Steven J.
Published: July 2002

Markup practices can affect the move toward systems that support scholars in the process of thinking and writing. Whereas procedural and presentational markup systems retard that movement, descriptive markup systems accelerate the pace by simplifying mechanical tasks and allowing the authors to focus their attention on the content.
A parallel pipelined relational query processor
Authors: Kim Won , Gajski Daniel , Kuck David J.
Published: July 2002

This paper presents the design of a relational query processor. The query processor consists of only four processing PIPEs and a number of random-access memory modules. Each PIPE processes tuples of relations in a bit-serial, tuple-parallel manner for each of the primitive database operations which comprise a complex relational query. The design of the query processor meets three major objectives: the query processor must be manufacturable using existing and near-term LSI (VLSI) technology; it must support in a uniform manner both the numeric and nonnumeric processing requirements a high-level user interface like SQL presents; and it must support the query-processing strategy derived in the query optimizer to satisfy certain system-wide performance optimality criteria.
Generalized stochastic subdivision
Authors: Lewis J. P.
Published: July 2002

Stochastic techniques have assumed a prominent role in computer graphics because of their success in modeling a variety of complex and natural phenomena. This paper describes the basis for techniques such as stochastic subdivision in the theory of random processes and estimation theory. The popular stochastic subdivision construction is then generalized to provide control of the autocorrelation and spectral properties of the synthesized random functions. The generalized construction is suitable for generating a variety of perceptually distinct high-quality random functions, including those with non-fractal spectra and directional or oscillatory characteristics. It is argued that a spectral modeling approach provides a more powerful and somewhat more intuitive perceptual characterization of random processes than does the fractal model. Synthetic textures and terrains are presented as a means of visually evaluating the generalized subdivision technique.
Web-based simulation
Authors: Page Ernest H. , Buss Arnold , Fishwick Paul A. , Healy Kevin J. , Nance Richard E. , Paul Ray J.
Published: July 2002

The nature of the emerging field of web-based simulation is examined in terms of its relationship to the fundamental aspects of simulation research and practice. The presentation, assuming a form of debate, is based on a panel session held at the first International Conference on Web-Based Modeling and Simulation, which was sponsored by the Society for Computer Simulation during 11-14 January 1998 in San Diego, California. While no clear “winner” is evident in this debate, the issues raised here certainly merit ongoing attention and contemplation.
Contention resolution with constant expected delay
Authors: Goldberg Leslie Ann , Mackenzie Philip D. , Paterson Mike , Srinivasan Aravind
Published: July 2002

We study contention resolution in a multiple-access channel such as the Ethernet channel. In the model that we consider,nusers generate messages for the channel according to a probability distribution. Raghavan and Upfal have given a protocol in which the expecteddelay(time to get serviced) of every message is O(logn) when messages are generated according to a Bernoulli distribution with generation rate up to about 1/10. Our main results are the following protocols: (a) one in which the expected average message delay is O(1) when messages are generated according to a Bernoulli distribution with a generation rate smaller than 1/e, and (b) one in which the expected delay of any message is O(1) for an analogous model in which users are synchronized (i.e., they agree about the time), there are potentially an infinite number of users, and messages are generated according to a Poisson distribution with generation rate up to 1/e. (Each message constitutes a new user.)

To achieve (a), we first show how to simulate (b) usingnsynchronized users, and then show how to build the synchronization into the protocol.
The minimization of spatially-multiplexed character sets
Authors: Gimpel James F.
Published: July 2002

The paper describes a technique for compacting character sets in a digital computer while retaining fast access to individual bits. It considers the problem of minimizing the storage needed to contain such tables. Reduction techniques are developed, and the problem is shown to reduce to a covering problem.
DIAGRAM
Authors: Robinson Jane J.
Published: July 2002

An explanatory overview is given of DIAGRAM, a large and complex grammar used in an artificial intelligence system for interpreting English dialogue. DIAGRAM is an augmented phrase-structure grammar with rule procedures that allow phrases to inherit attributes from their constituents and to acquire attributes from the larger phrases in which they themselves are constituents. These attributes are used to set context-sensitive constraints on the acceptance of an analysis. Constraints can be imposed by conditions on dominance as well as by conditions on constituency. Rule procedures can also assign scores to an analysis to rate it as probable or unlikely. Less likely analyses can be ignored by the procedures that interpret the utterance. For every expression it analyzes, DIAGRAM provides an annotated description of the structure. The annotations supply important information for other parts of the system that interpret the expression in the context of a dialogue.

Major design decisions are explained and illustrated. Some contrasts with transformational grammars are pointed out and problems that motivate a plan to use metarules in the future are discussed. (Metarules derive new rules from a set of base rules to achieve the kind of generality previously captured by transformational grammars but without having to perform transformations on syntactic analyses.)
The “worm” programs—early experience with a distributed computation
Authors: Shoch John F. , Hupp Jon A.
Published: July 2002

The “worm” programs were an experiment in the development of distributed computations: programs that span machine boundaries and also replicate themselves in idle machines. A “worm” is composed of multiple “segments,” each running on a different machine. The underlying worm maintenance mechanisms are responsible for maintaining the worm—finding free machines when needed and replicating the program for each additional segment. These techniques were successfully used to support several real applications, ranging from a simple multimachine test program to a more sophisticated real-time animation system harnessing multiple machines.
The impact of scanners on employment in supermarkets
Authors: Gilchrist Bruce , Shenkin Arlaana
Published: July 2002

A brief review is given of the early estimates of the rate at which scanners would be installed in supermarkets and the resulting labor and consumer responses. The actual situation in 1979 is then discussed and detailed labor savings achieved by one supermarket chain are given. A fully scanner-equipped supermarket is estimated to have a 5 percent lower labor requirement than an unautomated store with the same volume. It is projected that 50 percent of the 23,000 large supermarkets will install scanners by 1984 with the remainder doing so by 1988. At full penetration, scanners will reduce total industry employment by approximately 50,000. Few actual layoffs will occur because of the high turnover in the industry. Furthermore, the stores that install scanners may attract customers from nonautomated stores leaving those stores to handle the job losses.
Computer assisted instruction
Authors: Chambers Jack A. , Sprecher Jerry W.
Published: July 2002

The use of computers to assist in the learning situation in a simulation, game, tutorial, or drill and practice mode is reviewed on an international basis with centers of activity identified in the United States, Canada, the United Kingdom, and Japan. The use of the computer as an adjunct to support learning is compared to its use in a substitution mode. Evaluative studies of CAI are reviewed and costs are examined. The critical issues of CAI are enumerated and analyzed as they pertain to computer hardware, CAI languages, and courseware development and use. The future of CAI is briefly sketched from the viewpoints of individuals prominent in the field. Finally, conclusions are drawn and recommendations are offered to help ensure the most educationally cost-effective use of CAI in learning situations.
Architecture of the IBM system/370
Authors: Case Richard P. , Padegs Andris
Published: July 2002

This paper discusses the design considerations for the architectural extensions that distinguish System/370 from System/360. It comments on some experiences with the original objectives for System/360 and on the efforts to achieve them, and it describes the reasons and objectives for extending the architecture. It covers virtual storage, program control, data-manipulation instructions, timing facilities, multiprocessing, debugging and monitoring, error handling, and input/output operations. A final section tabulates some of the important parameters of the various IBM machines which implement the architecture.
Effective information retrieval using term accuracy
Authors: Yu C. T. , Salton G.
Published: July 2002

The performance of information retrieval systems can be evaluated in a number of different ways. Much of the published evaluation work is based on measuring the retrieval performance of an average user query. Unfortunately, formal proofs are difficult to construct for the average case. In the present study, retrieval evaluation is based on optimizing the performance of a specific user query. The concept of query term accuracy is introduced as the probability of occurrence of a query term in the documents relevant to that query. By relating term accuracy to the frequency of occurrence of the term in the documents of a collection it is possible to give formal proofs of the effectiveness with respect to a given user query of a number of automatic indexing systems that have been used successfully in experimental situations. Among these are inverse document frequency weighting, thesaurus construction, and phrase generation.
The aliasing problem in computer-generated shaded images
Authors: Crow Franklin C.
Published: July 2002

Certain defects, such as jagged edges and disappearing detail, have long been an annoyance in digitally generated shaded images. Although increasing the resolution or defocusing the display can attenuate them, an understanding of these defects leads to more effective methods. This paper explains the observed defects in terms of the aliasing phenomenon inherent in sampled signals and discusses prefiltering as a recognized cure. A method for evaluating filters is presented, the application of prefiltering to hidden-surface algorithms is discussed, and an implementation of a filtering tiler is shown accompanied by examples of its effectiveness.
A lattice model of secure information flow
Authors: Denning Dorothy E.
Published: July 2002

This paper investigates mechanisms that guarantee secure information flow in a computer system. These mechanisms are examined within a mathematical framework suitable for formulating the requirements of secure information flow among security classes. The central component of the model is a lattice structure derived from the security classes and justified by the semantics of information flow. The lattice properties permit concise formulations of the security requirements of different existing systems and facilitate the construction of mechanisms that enforce security. The model provides a unifying view of all systems that restrict information flow, enables a classification of them according to security objectives, and suggests some new approaches. It also leads to the construction of automatic program certification mechanisms for verifying the secure flow of information through a program.
Expected time bounds for selection
Authors: Floyd Robert W. , Rivest Ronald L.
Published: July 2002

A new selection algorithm is presented which is shown to be very efficient on the average, both theoretically and practically. The number of comparisons used to select the
i
th smallest of
n
numbers is
n
+ min(
i,n-i
) +
o
(
n
). A lower bound within 9 percent of the above formula is also derived.
Quadratic programming for nonlinear regression
Authors: Shrager Richard I.
Published: July 2002

A quadratic programming algorithm is described for use with the magnified diagonal method of nonlinear regression with linear constraints. The regression method is published in JACM, July 1970.
On the feasibility of voice input to an on-line computer processing system
Authors: Elder Howard A.
Published: July 2002

An on-line digital computer processing system is considered in which an ordinary telephone is the complete terminal device, input to the computer being provided as a sequence of spoken words, and output to the user being audio responses from the machine. The feasibility of implementing such a system with a FORTRAN-like algebraic compiler as the object processor is considered. Details of a specific word recognition program are given. This technique depends on three simplifying restrictions, namely, a “small” vocabulary set, “known” speakers, and a “moment of silence” between each input word. Experimental results are presented giving error rates for different experimental conditions as well as the machine resources required to accommodate several users at a time. The results show that at this time it is both economically and logically feasible to handle at least 40 users at a time with an IBM 360/65 computer.
Accurate floating-point summation
Authors: Linz Peter
Published: July 2002

This paper describes an alternate method for summing a set of floating-point numbers. Comparison of the error bound for this method with that of the standard summation method shows that it is considerably less sensitive to propagation of round-off error.
Universal computer-oriented language
Authors: Dobrusky W. B. , Steel T. B.
Published: July 2002

The basic idea of UNCOL Universal Computer-Oriented Language—is to introduce a language between problem-oriented languages, POLs, and machine languages, MLs. This third level consists of a single language, UNCOL, which has the character of a generalized machine-line language.
Automatic coding
Authors: Bratman Harvey
Published: July 2002

SDC is currently engaged in producing a “JOVIAL” compiler for each of its computers. The compilers are being produced by a bootstrapping method similar to that described in a report on UNCOL [1]. In discussing the steps involved, we resorted to diagrams to clear up the confusion that arose when trying to describe, for example, how a JOVIAL generator for the IBM 709 could produce a JOVIAL translator to the Philco S-2000 that would run on the 709 and then use the resulting 709 - S-2000 translator to produce a JOVIAL translator to the S-2000 that would run on the S-2000.
A randomized protocol for signing contracts
Authors: Even Shimon , Goldreich Oded , Lempel Abraham
Published: July 2002

Randomized protocols for signing contracts, certified mail, and flipping a coin are presented. The protocols use a 1-out-of-2 oblivious transfer subprotocol which is axiomatically defined.

The 1-out-of-2 oblivious transfer allows one party to transfer exactly one secret, out of two recognizable secrets, to his counterpart. The first (second) secret is received with probability one half, while the sender is ignorant of which secret has been received.

An implementation of the 1-out-of-2 oblivious transfer, using any public key cryptosystem, is presented.
Algorithm 808
Authors: Schneider Tapio , Neumaier Arnold
Published: July 2002

ARfit is a collection of Matlab modules for modeling and analyzing multivariate time series with autoregressive (AR) models. ARfit contains modules to given time series data, for analyzing eigen modes of a fitted model, and for simulating AR processes. ARfit estimates the parameters of AR models from given time series data with a stepwise least squares algorithm that is computationally efficient, in particular when the data are high-dimensional. ARfit modules construct approximate confidence intervals for the estimated parameters and compute statistics with which the adequacy of a fitted model can be assessed. Dynamical characteristics of the modeled time series can be examined by means of a decomposition of a fitted AR model into eigenmodes and associated oscillation periods, damping times, and excitations. The ARfit module that performs the eigendecomposition of a fitted model also constructs approximate confidence intervals for the eigenmodes and their oscillation periods and damping times.
Binomial random variate generation
Authors: Kachitvichyanukul Voratas , Schmeiser Bruce W.
Published: July 2002

Existing binomial random-variate generators are surveyed, and a new generator designed for moderate and large means is developed. The new algorithm, BTPE, has fixed memory requirements and is faster than other such algorithms, both when single, or when many variates are needed.
Some distributions that allow perfect packing
Authors: Rhee Wansoo T. , Talagrand Michel
Published: July 2002

A probability distribution
μ
on [0, 1] allows perfect packing if
n
items of size
X
1
, … ,
X

n

, independent and identically distributed according to
μ
can be packed in unit size bins in such a way that the expected wasted space is
o
(
n
). A large class of distributions that allow perfect packing is exhibited. As a corollary, the intervals [
a, b
] for which the uniform distribution on [
a, b
] allows perfect packing are determined.
Searching for information in a hypertext medical handbook
Authors: Frisse Mark,E.
Published: July 2002

Medicine is an ideal domain for hypertext applications and research. Implementing a popular medical handbook in hypertext underscores the need to study hypertext in the context of full-text document retrieval, machine learning, and user interface issues.
Logics with aggregate operators
Authors: Hella Lauri , Libkin Leonid , Nurmonen Juha , Wong Limsoon
Published: July 2002

We study adding aggregate operators, such as summing up elements of a column of a relation, to logics with counting mechanisms. The primary motivation comes from database applications, where aggregate operators are present in all real life query languages. Unlike other features of query languages, aggregates are not adequately captured by the existing logical formalisms. Consequently, all previous approaches to analyzing the expressive power of aggregation were only capable of producing partial results, depending on the allowed class of aggregate and arithmetic operations.We consider a powerful counting logic, and extend it with the set of all aggregate operators. We show that the resulting logic satisfies analogs of Hanf's and Gaifman's theorems, meaning that it can only express local properties. We consider a database query language that expresses all the standard aggregates found in commercial query languages, and show how it can be translated into the aggregate logic, thereby providing a number of expressivity bounds, that do not depend on a particular class of arithmetic functions, and that subsume all those previously known. We consider a restricted aggregate logic that gives us a tighter capture of database languages, and also use it to show that some questions on expressivity of aggregation cannot be answered without resolving some deep problems in complexity theory.
Incomplete information costs and database design
Authors: Mendelson Haim , Saharia Aditya N.
Published: July 2002

This paper presents a methodology for trading-off the cost of incomplete information against the data-related costs in the design of database systems. It investigates how the usage patterns of the database, defined by the characteristics of information requests presented to it, affect its conceptual design. The construction of minimum-cost answers to information requests for a variety of query types and cost structures is also studied. The resulting costs of incomplete database information are balanced against the data-related costs in the derivation of the optimal design.
Queuing analysis of polling models
Authors: Takagi Hideaki
Published: July 2002

A polling model is a system of multiple queues accessed by a single server in cyclic order. Polling models provide performance evaluation criteria for a variety of demand-based, multiple-access schemes in computer and communication systems. This paper presents an overview of the state of the art of polling model analysis, as well as an extensive list of references. In particular, single-buffer systems and infinite-buffer systems with exhaustive, gated, and limited service disciplines are treated. There is also some discussion of systems with a noncyclic order of service and systems with priority. Applications to computer networks are illustrated, and future research topics are suggested.
Formative design evaluation of superbook
Authors: Egan Dennis E. , Remde Joel R. , Gomez Louis M. , Landauer Thomas K. , Eberhardt Jennifer , Lochbaum Carol C.
Published: July 2002

SuperBook is a hypertext browsing system designed to improve the usability of conventional documents. Successive versions of SuperBook were evaluated in a series of behavioral studies. Students searched for information in a statistics text. presented either in conventional printed form or in SuperBook form. The best version of SuperBook enabled students to answer search questions more quickly and accurately than they could with the conventional text. Students wrote higher quality “open-book” essays using SuperBook than they did with the conventional text, and their subjective ratings of the documentation strongly favored SuperBook.

This work is a case study of formative design-evaluation. Behavioral evaluation of the first version of SuperBook showed how design factors and user strategies affected search and established baseline performance measures with printed text. The second version of SuperBook was implemented with the goal of improving search accuracy and speed. User strategies that had proved effective in the first study were made very easy and attractive to use. System response time for common operations was greatly improved. Behavioral evaluation of the new SuperBook demonstrated its superiority to printed text and suggested additional improvements that were incorporated into “MiteyBook,” a SuperBook implementation for PC-size screens. Search with MiteyBook proved to be approximately 25 percent faster and 25 percent more accurate than that obtained with a conventional printed book.
Algorithm 642
Authors: Hutchinson M. F.
Published: July 2002

The procedure CUBGCV is an implementation of a recently developed algorithm for fastO(n)calculation of a cubic smoothing spline fitted tonnoisy data points, with the degree of smoothing chosen to minimize the expected mean square error at the data points when the variance of the error associated with the data is known, or, to minimize the generalized cross validation (GCV) when the variance of the error associated with the data is unknown. The data may be unequally spaced and nonuniformly weighted. The algorithm exploits the banded structure of the matrices associated with the cubic smoothing spline problem. Bayesian point error estimates are also calculated inO(n)operations.
Information technologies for the 1990s: an organizational impact perspective
Authors: Straub Detmar W. , Wetherbe James C.
Published: July 2002

When a thing is new, people say: "It is not true." Later, when its truth becomes obvious, they say: "It is not important." Finally, when its importance cannot be denied, they say: "Anyway, it is not new."

Adapted from William James
An experimental evaluation of computer graphics imagery
Authors: Meyer Gary W. , Rushmeier Holly E. , Cohen Michael F. , Greenberg Donald P. , Torrance Kenneth E.
Published: July 2002

Accurate simulation of light propagation within an environment and perceptually based imaging techniques are necessary for the creation of realistic images. A physical experiment that verifies the simulation of reflected light intensities for diffuse environments was conducted. Measurements of radiant energy flux densities are compared with predictions using the radiosity method for those physical environments. By using color science procedures the results of the light model simulation are then transformed to produce a color television image. The final image compares favorably with the original physical model. The experiment indicates that, when the physical model and the simulation were viewed through a view camera, subjects could not distinguish between them. The results and comparison of both test procedures are presented within this paper.
An experimental program investigating color-enhanced and graphical information presentation: an integration of the findings
Authors: Benbasat Izak , Dexter Albert S. , Todd Peter
Published: July 2002

A series of three laboratory experiments were conducted to assess the influence of graphical and color-enhanced information presentation modes on decision quality, decision making time, use of information, and user perceptions. The experimental design allowed for the unconfounded study of line graphs and color using a variety of information presentation designs for the same decision making task. Based on the findings of these studies, propositions about the impact of graphics and color on individual decision makers are presented. The influence of presentation mode on human performance and the perceived value of information is related to how well it supports the solution approach to a particular task. The benefits of graphics are limited to reducing decision making time but only when the graphical report has been designed to directly assist in solving the task. Multicolor reports aid in decision making, but only in specific circumstances, that is, their benefits are not pervasive. It appears that color is more advantageous when associated with graphical reports, for certain decision maker types, during learning periods, and in time constrained environments.
On the execution of parallel programs on multiprocessor systems—a queuing theory approach
Authors: Baccelli François , Liu Zhen
Published: July 2002

The new class of queuing models, calledSynchronized Queuing Networks, is proposed for evaluating the performance of multiprogrammed and multitasked multiprocessor systems, where workloads consists of parallel programs of similar structure and where the scheduling discipline is first-come-first-serve.

Pathwise evolution equations are established for these networks that capture the effects of competition for processors and the precedence constraints governing tasks executions.

A general expression is deduced for the stability condition of such queuing networks under general statistical assumptions (basically the stationarity and the ergodicity of input sequences), which yields the maximum program throughput of the multiprocessor system, or equivalently, the maximum rate at which programs can be executed or submitted. The proof is based on the ergodic theory of queues.

Basic integral equations are also derived for the stationary distribution of important performance criteria such as the workload of the queues and program response times. An iterative numerical schema that converges to this solution is proposed and various upper and lower bounds on moments are derived using stochastic ordering techniques.
Some computational aspects of circumscription
Authors: Kolaitis Phokion G. , Papadimitriou Christos H.
Published: July 2002

The effects of circumscribing first-order formulas are explored from a computational standpoint. First, extending work of V. Lifschitz, it is Shown that the circumscription of any existential first-order formula is equivalent to a first-order formula. After this, it is established that a set of universal Horn clauses has a first-order circumscription if and only if it is bounded (when considered as a logic program); thus it is undecidable to tell whether such formulas have first-order circumscription. Finally, it is shown that there arefirst-order formulas whode circumscription has a coNP-complete model-checking problem.
Imprecise information and uncertainty in information systems
Authors: Morrissey J. M.
Published: July 2002

Information systems exist to model, store, and retrieve all types of data. Problems arise when some of the data are missing or imprecisely known or when an attribute is not applicable to a particular object. A consistent and useful treatment of such exceptions is necessary. The approach taken here is to allow any attribute value to be a regular precise value, a string denoting that the value is missing, a string denoting that the attribute is not applicable, or an imprecise value. The imprecise values introduce uncertainty into query evaluation, since it is no longer obvious which objects should be retrieved. To handle the uncertainty, two set of objects are retrieved in response to every query: the set of objects that are known to satisfy with complete certainty and the set that possibly satisfies the query with various degrees of uncertainty. Two methods of estimating this uncertainty, based on information theory, are proposed. The measure of uncertainty is used to rank objects for presentation to a user.
HOLOCENE BIODIVERSITY: An Archaeological Perspective from the Americas
Authors: Stahl Peter W.
Published: July 2002

▪ Abstract  Any understanding of contemporary biodiversity change in the Americas is likely to be uninformative and misleading if it employs a prehistoric baseline imbued with pristine characteristics. Archaeological evidence clearly displays a protracted history of environmental transformations at varying geographical and temporal scales throughout the Holocene (that is, the past 10,000 years). Because of problems inherent to the interpretation of the archaeological record, the genesis of these transformations often can only be ambiguously attributed to environmental and/or anthropogenic origins. However, at any given time or place, both the distribution of the numbers of different kinds of organisms and their relative abundances were in a constant state of flux since the retreat of glacial cover some 10,000 years ago. Here I review archaeological evidence to illustrate the dynamism of prehistoric biodiversity, which can be attributed to environmental events, to anthropogenic causation, or as a response of these to each other.
“THE POPULAR” IN AMERICAN CULTURE
Authors: Traube Elizabeth G.
Published: July 2002

▪ Abstract  This review contrasts the relative lack of interest in “popular culture” within anthropology with the close, increasingly critical attention this concept has received within cultural studies. Rejecting both a production-oriented model of a manipulative mass culture imposed from above and a reception-oriented model of an expressive culture of the people, cultural studies scholars broke with essentialized conceptions and redefined the popular in Gramscian terms, as a zone of contestation, a site where the struggle for hegemony unfolds. The review uses this approach to relate the production of popular culture to class formation in the United States. Against overemphasis on the ideological effectivity of popular culture and a revisionist tendency to redefine it in affirmative, politically essentialized terms, the review suggests that contradictions and instabilities characterize all stages of the popular cultural circuit: commodity, text, and lived culture.
THE COLOR-BLIND SUBJECT OF MYTH; Or, Where To Find Africa in the Nation
Authors: Segato R. L.
Published: July 2002

▪ Abstract  African influence in a nation must be examined within the framework of the nation's formation of diversity, ethno-racial paradigm, and particular history. Based on the paradigmatic cases of Brazil and the United States, I contend here that racial attitudes and the position and role of African traditions in a nation are interrelated. Discerning racial conceptions, perceptions, and patterns of discrimination in a nation provides us with strong clues about the place and role assigned to the African presence in that context. Racisms may not differ much in intensity, but they do in the cognitive operations they imply, because they are grounded in encoded ethnic knowledge accumulated through specific historical experiences.
THE POLITICS AND POETICS OF DANCE
Authors: Reed Susan A.
Published: July 2002

▪ Abstract  Since the mid-1980s, there has been an explosion of dance studies as scholars from a variety of disciplines have turned their attention to dance. Anthropologists have played a critical role in this new dance scholarship, contributing comparative analyses, critiquing colonial and ethnocentric categories, and situating studies of dance and movement within broader frameworks of embodiment and the politics of culture. This review highlights ethnographic and historical studies that foreground dance and other structured movement systems in the making of colonial cultures; the constitution of gender, ethnic and national identities; the formation of discourses of exoticization; and the production of social bodies. Several works that employ innovative approaches to the study of dance and movement are explored in detail.
MULTIPLE MODERNITIES: Christianity, Islam, and Hinduism in a Globalizing Age
Authors: Hefner Robert W.
Published: July 2002

▪ Abstract  The late twentieth century has seen far-reaching changes in the translocal cultural regimes known as world religions. This review examines the politics and meanings of recent changes in three such religions: Christianity, Islam, and Hinduism. It highlights the nature of the forces reshaping religious meanings and authority, the processes promoting conversion and standardization, and the implications of these religious refigurations for our understanding of late modernity itself. Though modernity is multiple and every tradition unique, this review suggests that all contemporary religions confront a similar structural predicament, related to the globalization of mass societies and the porous pluralism of late modernity.
Emergent Forms of Life: Anthropologies of Late or Postmodernities
Authors: Fischer Michael M.J.
Published: July 2002

▪ Abstract  Anthropologies of late modernity (also called postmodernity, postindustrial society, knowledge society, or information society) provide a number of stimulating challenges for all levels of social, cultural, and psychological theory, as well as for ethnographic and other genres of anthropological writing. Three key overlapping arenas of attention are the centrality of science and technology; decolonization, postcolonialism, and the reconstruction of societies after social trauma; and the role of the new electronic and visual media. The most important challenges of contemporary ethnographic practice include more than merely (a) the techniques of multilocale or multisited ethnography for strategically accessing different points in broadly spread processes, (b) the techniques of multivocal or multiaudience-addressed texts for mapping and acknowledging with greater precision the situatedness of knowledge, (c) the reworking of traditional notions of comparative work for a world that is increasingly aware of difference, and (d) acknowledging that anthropological representations are interventions within a stream of representations, mediations, and unequally inflected discourses competing for hegemonic control. Of equal importance are the challenges of juxtaposing, complementing, or supplementing other genres of writing, working with historians, literary theorists, media critics, novelists, investigative or in-depth journalists, writers of insider accounts (e.g. autobiographers, scientists writing for the public), photographers and film makers, and others.
The Individual Voice in Language
Authors: Johnstone Barbara
Published: July 2002

▪ Abstract  This article presents arguments for supplementing linguistic work focused on abstract social systems (languages, dialects, varieties) with linguistic work focused on individual speakers. It begins by reviewing how the individual speaker has been conceived of (when at all) in linguistics and linguistic anthropology. Two areas of linguistic research, discourse processing and linguistic variation and change, serve as examples of what is to be gained by supplementing a linguistics of systems with a linguistics of speakers. Finally, interest in the individual voice is placed in the context of a larger shift toward a more phenomenological approach to language and greater particularity in methods for its study.
Travels and Adventures in an Unchartable Field
Authors: Smedley Audrey
Published: July 2002

[Figure: see text]

There was considerable optimism about the future of anthropology when I came into the field over forty years ago, at a time when World War II was still a meaningful memory, the Korean War was a subject of great agony, and Vietnam was not yet part of our consciousness. During the late 1950s I had developed an interest in experiencing other cultures, and this led me to the field of international studies and indirectly to anthropology. Anthropology seemed a very positive way to get to know about other peoples and their ways of life. Such knowledge would create greater understanding among all peoples, and particularly, it had the potential for reducing friction and avoiding conflict. Naively, I think, some of my contemporaries and I believed that the field would grow and become a powerful influence in international relations, providing the knowledge and strategies for establishing communication among peoples and promoting peaceful coexistence. We were very young then and inexperienced. In this overview I touch on only some of the high points of my experiences in anthropology over the past decades and briefly comment on some of my reactions to developments in the field.