bluuebunny/crossref_metadata_2025 huggingface dataset:
Reconstructing a three-dimensional model with arbitrary errors
Authors: Berger Bonnie , Kleinberg Jon , Leighton Tom
Published: July 2002

A number of current technologies allow for the determination of interatomic distance information in structures such as proteins and RNA. Thus, the reconstruction of a three-dimensional set of points using information about its interpoint distances has become a task of basic importance in determining molecular structure. The distance measurements one obtains from techniques such as NMR are typically sparse and error-prone, greatly complicating the reconstruction task. Many of these errors result in distance measurements that can be safely assumed to lie within certain fixed tolerances. But a number of sources of systematic error in these experiments lead to inaccuracies in the data that are very hard to quantify; in effect, one must treat certain entries of the measured distance matrix as being arbitrarily “corrupted.”

The existence of arbitrary errors leads to an interesting sort of error-correction problem—how many corrupted entries in a distance matrix can be efficiently corrected to produce a consistent three-dimensional structure? For the case of an
n × n
matrix in which every entry is specified, we provide a randomized algorithm running in time
O(n log n)
that enumerates all structures consistent with at most (1/2-ε)n errors per row, with high probability. In the case of randomly located errors, we can correct errors of the same density in a sparse matrix-one in which only a β fraction of the entries in each row are given, for any constant βgt;0.
Human factors comparison of a procedural and a nonprocedural query language
Authors: Welty Charles , Stemple David W.
Published: July 2002

Two experiments testing the ability of subjects to write queries in two different query languages were run. The two languages, SQL and TABLET, differ primarily in their procedurality; both languages use the relational data model, and their Halstead levels are similar. Constructs in the languages which do not affect their procedurality are identical. The two languages were learned by the experimental subjects almost exclusively from manuals presenting the same examples and problems ordered identically for both languages. The results of the experiments show that subjects using the more procedural language wrote difficult queries better than subjects using the less procedural language. The results of the experiments are also used to compare corresponding constructs in the two languages and to recommend improvements for these constructs.
Some Results on Multicategory Pattern Recognition
Authors: Bledsoe W. W.
Published: July 2002

Some problems arising in multicategory (many pattern types) pattern recognition are treated mathematically, and formulas are derived which describe some inherent limitations associated therewith. The principal results concern the “dimensional” and “correlational” effects and their degradation of a multimeasurement recognition system.
A Procedure for Detecting Intersections of Three-Dimensional Objects
Authors: Comba Paul G.
Published: July 2002

As a step toward the solution of the placement problem in engineering design, a procedure has been developed for detecting intersections of convex regions in 3-space by means of a pseudocharacteristic function. The mathematical techniques underlying the procedure are discussed, and a system of programs embodying these techniques is described. As a special case a solution is given for the hidden-line problem in graphic display.
Characterization and Theoretical Comparison of Branch-and-Bound Algorithms for Permutation Problems
Authors: Kohler Walter H. , Steiglitz Kenneth
Published: July 2002

Branch-and-bound implicit enumeration algorithms for permutation problems (discrete optimization problems where the set of feasible solutions is the permutation group

S
n

) are characterized in terms of a sextuple (

B
p
S,E,D,L,U

), where (1)

B
p

is the branching rule for permutation problems, (2)
S
is the next node selection rule, (3)
E
is the set of node elimination rules, (4)
D
is the node dominance function, (5)
L
is the node lower-bound cost function, and (6)
U
is an upper-bound solution cost. A general algorithm based on this characterization is presented and the dependence of the computational requirements on the choice of algorithm parameters,
S, E, D, L,
and
U
is investigated theoretically. The results verify some intuitive notions but disprove others.
The Semantics of Predicate Logic as a Programming Language
Authors: Van Emden M. H. , Kowalski R. A.
Published: July 2002

Sentences in first-order predicate logic can be usefully interpreted as programs. In this paper the operational and fixpoint semantics of predicate logic programs are defined, and the connections with the proof theory and model theory of logic are investigated. It is concluded that operational semantics is a part of proof theory and that fixpoint semantics is a special case of model-theoretic semantics.
Locality of order-invariant first-order formulas
Authors: Grohe Martin , Schwentick Thomas
Published: July 2002

A query is
local
if the decision of whether a tuple in a structure satisfies this query only depends on a small neighborhood of the tuple. We prove that all queries expressible by
order-invariant
first-order formulas are local.
Optimal paths in graphs with stochastic or multidimensional weights
Authors: Loui Ronald Prescott
Published: July 2002

This paper explores computationally tractable formulations of stochastic and multidimensional optimal path problems, each as an extension of the shortest path problem. A single formulation encompassing both problems is considered, in which a utility function defines preference among candidate paths. The result is the ability to state explicit conditions for exact solutions using standard methods, and the applicability of well-understood approximation techniques.
Evolution and organizational information systems
Authors: King John Leslie , Kraemer Kenneth L.
Published: July 2002

Richard Nolan's stage model is the best known and most widely cited model of computing evolution in organizations. The model's development over a decade demonstrates its own evolution from a simple theory, based on the factoring of change states indicated by changes in computing budgets, to an elaborate account of the characteristics of six stages of computing growth. An analysis of the model's logical and empirical structure reveals a number of problems in its formulation that help to account for the fact that its principal tenets have not been independently validated. The model is shown to be an “evolutionistic” theory within the theories of evolution in the social sciences, focusing on assumed directions of growth and an implied end state toward which growth proceeds, and suffering from problems inherent in such theories. Further research based on an “evolutionary” view of computing growth is suggested as a means of improving theories of computing in organizations.
Region representation
Authors: Samet Hanan
Published: July 2002

An algorithm is presented for constructing a quadtree for a region given its boundary in the form of a chain code. Analysis of the algorithm reveals that its execution time is proportional to the product of the perimeter and the log of the diameter of the region.
Interference in multiprocessor computer systems with interleaved memory
Authors: Baskett Forest , Smith Alan Jay
Published: July 2002

This paper analyzes the memory interference caused by several processors simultaneously using several memory modules. Exact results are computed for a simple model of such a system. The limiting value is derived for the relative degree of memory interference as the system size increases. The model of the limiting behavior of the system yields approximate results for the simple model and also suggests that the results are valid for a much larger class of models, including those more nearly like real systems than the simple model. The assumptions and results of the simple model are tested against some measurements of program behavior and simulations of systems using memory references from real programs. The model results provide a good indication of the performance that should be expected from real systems of this type.
Symbolic execution and program testing
Authors: King James C.
Published: July 2002

This paper describes the symbolic execution of programs. Instead of supplying the normal inputs to a program (e.g. numbers) one supplies symbols representing arbitrary values. The execution proceeds as in a normal execution except that values may be symbolic formulas over the input symbols. The difficult, yet interesting issues arise during the symbolic execution of conditional branch type statements. A particular system called EFFIGY which provides symbolic execution for program testing and debugging is also described. It interpretively executes programs written in a simple PL/I style programming language. It includes many standard debugging features, the ability to manage and to prove things about symbolic expressions, a simple program testing manager, and a program verifier. A brief discussion of the relationship between symbolic execution and program proving is also included.
Algorithm 430 [H]: Immediate predominators in a directed graph
Authors: Purdom Paul W. , Moore Edward F.
Published: July 2002

We assume a directed graph whose nodes are labeled by integers between 1 and
n
. The arcs of this graph correspond to the flow of control between blocks of a computer program. The initial node of this graph (corresponding to the entry point of the program) is labeled by the integer 1. For optimizing the object code generated by a compiler, the relationship of immediate predominator has been used by Lowry and Medlock [3]. We say that node
i
predominates node
k
if every path from node 1 to node
k
passes through (i.e. both into and out of) node
i
. Node
j
is an immediate predominator of node
k
if node
j
predominates node
k
and if every other node
i
which predominates node
k
also predominates node
j
. It can easily be proved that if
k
≠ 1 and node
k
is reachable from node 1t hen node
k
has exactly one immediate predominator. In case
k
= 1, or node
k
is not reachable from node 1, the immediate predominator of node
k
is undefined, and the value 0 will be given by the procedure
PREDOMINATOR
.
Generating a canonical prefix encoding
Authors: Schwartz Eugene S. , Kallick Bruce
Published: July 2002

Computer programs for generating a minimum-redundancy exhaustive prefix encoding are described. One program generates a Huffman frequency tree, another determines the structure functions of an encoding, and a third program assigns codes.
Conversion of a power to a series of Chebyshev polynomials
Authors: Thacher Henry C.
Published: July 2002

Even slowly convergent power series can be rearranged as series in Chebyshev polynomials if appropriate sequence transformations are used in evaluating the coefficients. The method is illustrated by computing the coefficients for the expansion of the logarithm and dilogarithm.
A MATLAB differentiation matrix suite
Authors: Weideman J. A. , Reddy S. C.
Published: July 2002

A software suite consisting of 17 MATLAB functions for solving differential equations by the spectral collocation (i.e., pseudospectral) method is presented. It includes functions for computing derivatives of arbitrary order corresponding to Chebyshev, Hermite, Laguerre, Fourier, and sinc interpolants. Auxiliary functions are included for incorporating boundary conditions, performing interpolation using barycentric formulas, and computing roots of orthogonal polynomials. It is demonstrated how to use the package for solving eigenvalue, boundary value, and initial value problems arising in the fields of special functions, quantum mechanics, nonlinear waves, and hydrodynamic stability.
Clausal temporal resolution
Authors: Fisher Michael , Dixon Clare , Peim Martin
Published: July 2002

In this article, we examine how clausal resolution can be applied to a specific, but widely used, nonclassical logic, namely discrete linear temporal logic. Thus, we first define a normal form for temporal formulae and show how arbitrary temporal formulae can be translated into the normal form, while preserving satisfiability. We then introduce novel resolution rules that can be applied to formulae in this normal form, provide a range of examples, and examine the correctness and complexity of this approach. Finally, we describe related work and future developments concerning this work.
Algorithm 809: PREQN
Authors: Morales José Luis , Nocedal Jorge
Published: July 2002

PREQN is a package of Fortran 77 subroutins for automatically generating preconditioners for the conjugate gradient method. It is designed for solving a sequence of linear systems

A
i
x

=

b
i

,
i
= 1…,
t
, where the coefficient matrices

A
i

are symmetric and positive definite and vary slowly. Problems of this type arise, for example, in nonlinear optimization. The preconditioners are based on limited-memory quasi-Newton updating and are recommended for problems in which (i) the coefficient matrices are not explicitly known and only matrix-vector products of the form

A
i
v

can be computed; or (ii) the coefficient matrices are not sparse. PREQN is written so that a single call from a conjugate gradient routine performs the preconditioning operation and stores information needed for the generation of a new preconditioner.
Probabilistic temporal databases, I
Authors: Dekhtyar Alex , Ross Robert , Subrahmanian V. S.
Published: July 2002

Dyreson and Snodgrass have drawn attention to the fact that, in many temporal database applications, there is often uncertainty about the start time of events, the end time of events, and the duration of events. When the granularity of time is small (e.g., milliseconds), a statement such as “Packet
p
was shipped sometime during the first 5 days of January, 1998” leads to a massive amount of uncertainty (5×24×60×60×1000) possibilities. As noted in Zaniolo et al. [1997], past attempts to deal with uncertainty in databases have been restricted to relatively small amounts of uncertainty in attributes. Dyreson and Snodgrass have taken an important first step towards solving this problem.

In this article, we first introduce the syntax of Temporal-Probabilistic (TP) relations and then show how they can be converted to an explicit, significantly more space-consuming form, called Annotated Relations. We then present a
theoretical annotated temporal algebra
(TATA). Being explicit, TATA is convenient for specifying how the algebraic operations should behave, but is impractical to use because annotated relations are overwhelmingly large.

Next, we present a
temporal probabilistic algebra
(TPA). We show that our definition of the TP-algebra provides a correct implementation of TATA despite the fact that it operates on implicit, succinct TP-relations instead of overwhemingly large annotated relations. Finally, we report on timings for an implementation of the TP-Algebra built on top of ODBC.
Problems and some solutions in customization of natural language database front ends
Authors: Damerau Fred J.
Published: July 2002

This paper is concerned with some of the issues arising in the development of a domain-independent English interface to IBM SQL-based program products. The TQA system falls into the class of multilayered natural language processing systems. As a result, there is a large number of potential points at which customization to a particular database can be done. Of these, we discuss procedures that affect the reader, the lexicon, the lowest level of grammar rules, the semantic interpreter, and the output formatter. Our tests lead us to believe that the approach we are taking will make it possible for database administrators to generate robust English interfaces to particular databases without help from linguistic experts.
A data distortion by probability distribution
Authors: Liew Chong K. , Choi Uinam J. , Liew Chung J.
Published: July 2002

This paper introduces data distortion by probability distribution, a probability distortion that involves three steps. The first step is to identify the underlying density function of the original series and to estimate the parameters of this density function. The second step is to generate a series of data from the estimated density function. And the final step is to map and replace the generated series for the original one. Because it is replaced by the distorted data set, probability distortion guards the privacy of an individual belonging to the original data set. At the same time, the probability distorted series provides asymptotically the same statistical properties as those of the original series, since both are under the same distribution. Unlike conventional point distortion, probability distortion is difficult to compromise by repeated queries, and provides a maximum exposure for statistical analysis.
NPATH: a measure of execution path complexity and its applications
Authors: Nejmeh Brian A.
Published: July 2002

Software engineering is a discipline in search of objective measures for factors that contribute to software quality. NPATH, which counts the acyclic execution paths through a function, is an objective measure of software complexity related to the ease with which software can be comprehensively tested.
Color gamut mapping and the printing of digital color images
Authors: Stone Maureen C. , Cowan William B. , Beatty John C.
Published: July 2002

Principles and techniques useful for calibrated color reproduction are defined. These results are derived from a project to take digital images designed on a variety of different color monitors and accurately reproduce them in a journal using digital offset printing. Most of the images printed were reproduced without access to the image as viewed in its original form; the color specification was derived entirely from calorimetric specification. The techniques described here are not specific to offset printing and can be applied equally well to other digital color devices.

The reproduction system described is calibrated using CIE tristimulus values. An image is represented as a set of three-dimensional points, and the color output device as a three-dimensional solid surrounding the set of all reproducible colors for that device, called its
gamut
. The shapes of the monitor and the printer gamuts are very different, so it is necessary to transform the image points to fit into the destination gamut, a process we call
gamut mapping
. This paper describes the principles that control gamut mapping. Included also are some details on monitor and printer calibration, and a brief description of how digital halftone screens for offset printing are prepared.
TRBAC
Authors: Bertino Elisa , Bonatti Piero Andrea , Ferrari Elena
Published: July 2002

Role-based access control (RBAC) models are receiving increasing attention as a generalized approach to access control. Roles may be available to users at certain time periods, and unavailable at others. Moreover, there can be temporal dependencies among roles. To tackle such dynamic aspects, we introduce Temporal-RBAC (TRBAC), an extension of the RBAC model. TRBAC supports periodic role enabling and disabling---possibly with individual exceptions for particular users---and temporal dependencies among such actions, expressed by means of role triggers. Role trigger actions may be either immediately executed, or deferred by an explicitly specified amount of time. Enabling and disabling actions may be given a priority, which is used to solve conflicting actions. A formal semantics for the specification language is provided, and a polynomial safeness check is introduced to reject ambiguous or inconsistent specifications. Finally, a system implementing TRBAC on top of a conventional DBMS is presented.
Who is an open source software developer?
Authors: Dempsey Bert J. , Weiss Debra , Jones Paul , Greenberg Jane
Published: July 2002

Profiling a community of Linux developers.
The mutual exclusion problem
Authors: Lamport Leslie
Published: July 2002

A novel formal theory of concurrent systems that does not assume any atomic operations is introduced. The execution of a concurrent program is modeled as an abstract set of operation executions with two temporal ordering relations: “precedence” and “can causally affect”. A primitive interprocess communication mechanism is then defined. In Part II, the mutual exclusion is expressed precisely in terms of this model, and solutions using the communication mechanism are given.
Partial match retrieval of multidimensional data
Authors: Flajolet Philippe , Puech Claude
Published: July 2002

A precise analysis of partial match retrieval of multidimensional data is presented. The structures considered here are multidimensional search trees (
k
-d-trees) and digital tries (
k
-d-tries), as well as structures designed for efficient retrieval of information stored on external devices. The methods used include a detailed study of a differential system around a regular singular point in conjunction with suitable contour integration techniques for the analysis of
k
-d-trees, and properties of the Mellin integral transform for
k
-d-tries and extendible cell algorithms.
Guided tours and tabletops: tools for communicating in a hypertext environment
Authors: Trigg Randall H.
Published: July 2002

The author of a complex hypertext document is often faced with the problem of conveying the document's meaning to future readers through a shared computer environment. Two tools implemented in the NoteCards hypertext environment, guided tours and tabletops, allow authors to employ annotation, graphic layout, and ordered presentation when communicating to readers. This paper describes these tools and gives examples of their use. Issues of remote pointing arising from an application in legal argumentation are discussed as well as early work on the use of these tools to support sharing of hypertext strategies among NoteCards users.
Accuracy, integrity and security in computerized vote-tallying
Authors: Saltman R. G.
Published: July 2002

The following excerpts have been gleaned from a 130-page report of potential inaccuracies and fraud in computerized voting systems. Recent difficulties in automated vote-tallying, including specific legal cases, are detailed along with a summary of conclusions and recommendations.
Computerized performance monitoring systems: use and abuse
Authors: Irving R. H. , Higgins C. A. , Safayeni F. R.
Published: July 2002

An exploratory study of computerized performance monitoring and control systems reveals both positive and negative effects. Responses of 50 clerical workers from 2 organizations with computerized monitoring were compared to 94 individuals from 3 organizations in similar jobs without computerized monitoring. The results indicate that computerized monitoring is associated with perceived increases in office productivity, more accurate and complete assessment of workers' performance, and higher levels of organizational control. Respondents indicate that managers overemphasize the importance of quantity and underemphasize the importance of quality in evaluating employee performance. Workers perceive increased stress, lower levels of satisfaction, and a decrease in the quality of their relationships with peers and management as a consequence of computerized monitoring. The relevance of existing models of performance monitoring is examined in light of these findings.
DVI—a digital multimedia technology
Authors: Ripley G. David
Published: July 2002

A digital presentation technology that manages anything from text to full-motion video has the potential of expanding the usefulness of personal computers, while rendering them less intimidating.
Information retrieval using a hypertext-based help system
Authors: Campagnoni F. R. , Ehrlich Kate
Published: July 2002

Hypertext offers users a simple, flexible way to navigate through electronic information systems but at the potential risk of becoming lost in the network of interconnected pieces of information. A study was conducted on information retrieval using a commercial hypertext-based help system. It was found that the predominant search strategy was “browsing” (characterized by scanning tables of contents and paging through topics), rather than employing the indexes ("analytical search"). Although subjects did not get lost, individuals with better spatial visualization skills, as measured by a standardized test, were faster at retrieving information and returned to the top of the information hierarchy less often than those with poorer spatial visualization skills. These results support previous studies that have found a strong preference by users for browsing in hypertext systems and extend those findings to a new domain (help), a different type of user interface, and a different information architecture. In addition, the results demonstrate the importance of spatial visualization ability for efficient navigation and information retrieval in a hierarchical hypertext system.
The adaptable user interface
Authors: Kantorowitz Eliezer , Sudarsky Oded
Published: July 2002

A single adaptable user interface (AUI) which allows the user to switch between any number of different dialogue modes at any time—even in the middle of a command—can be useful to a variety of users who are neither beginners nor experts. It can also be used in applications where different dialogue modes are appropriate for the various parameters of a single command. An implemented user interface management system (UIMS) suggests the practicality of AUIs and their automatic generation.
Predicative programming Part I
Authors: Hehner Eric C. R.
Published: July 2002

Programs are given a new semantics with the merit that a specification written as a first-order predicate can be refined, step by step, to a program via the rules of Predicate Calculus. The semantics allows a free mixture of predicate and programming notations, and manipulation of programs.
Predicative programming Part II
Authors: Hehner Eric C. R.
Published: July 2002

Part I of this two-part paper presented a new semantics of programs. Each program is considered to be a predicate, in a restricted notation, that specifies the observable behavior of a computer executing the program. We considered a variety of notations, including assignment, composition (semicolon), deterministic choice
(if),
nondeterministic choice, definition (nonrecursive and recursive), and variable declaration. We did not consider any input or output notations, or concurrency; that is the subject of Part II. We assume the reader is familiar with Part I, so that we can build on ideas presented there.
Slowing down sorting networks to obtain faster sorting algorithms
Authors: Cole Richard
Published: July 2002

Megiddo introduced a technique for using a parallel algorithm for one problem to construct an efficient serial algorithm for a second problem. This paper provides a general method that trims a factor of
O
(log
n
) time (or more) for many applications of this technique.
An incremental constraint solver
Authors: Freeman-Benson Bjorn N. , Maloney John , Borning Alan
Published: July 2002

An incremental constraint solver, the DeltaBlue algorithm maintains an evolving solution to the constraint hierarchy as constraints are added and removed. DeltaBlue minimizes the cost of finding a new solution after each change by exploiting its knowledge of the last solution.
A variable order Runge-Kutta method for initial value problems with rapidly varying right-hand sides
Authors: Cash J. R. , Karp Alan H.
Published: July 2002

Explicit Runge-Kutta methods (RKMs) are among the most popular classes of formulas for the approximate numerical integration of nonstiff, initial value problems. However, high-order Runge-Kutta methods require more function evaluations per integration step than, for example, Adams methods used in PECE mode, and so, with RKMs, it is expecially important to avoid rejected steps. Steps are often rejected when certain derivatives of the solutions are very large for part of the region of integration. This corresponds, for example, to regions where the solution has a sharp front or, in the limit, some derivative of the solution is discontinuous. In these circumstances the assumption that the local truncation error is changing slowly is invalid, and so any step-choosing algorithm is likely to produce an unacceptable step. In this paper we derive a family of explicit Runge-Kutta formulas. Each formula is very efficient for problems with smooth solution as well as problems having rapidly varying solutions. Each member of this family consists of a fifty-order formula that contains imbedded formulas of all orders 1 through 4. By computing solutions at several different orders, it is possible to detect sharp fronts or discontinuities before all the function evaluations defining the full Runge-Kutta step have been computed. We can then either accpet a lower order solution or abort the step, depending on which course of action seems appropriate. The efficiency of the new algorithm is demonstrated on the DETEST test set as well as on some difficult test problems with sharp fronts or discontinuities.
Random numbers for simulation
Authors: L'Ecuyer Pierre
Published: July 2002

In the mind of the average computer user, the problem of generating uniform variates by computer has been solved long ago. After all, every computer :system offers one or more function(s) to do so. Many software products, like compilers, spreadsheets, statistical or numerical packages, etc. also offer their own. These functions supposedly return numbers that could be used, for all practical purposes, as if they were the values taken by independent random variables, with a uniform distribution between 0 and 1. Many people use them with faith and feel happy with the results. So, why bother?

Other (less naive) people do not feel happy with the results and with good reasons. Despite renewed crusades, blatantly bad generators still abound, especially on microcomputers [55, 69, 85, 90, 100]. Other generators widely used on medium-sized computers are perhaps not so spectacularly bad, but still fail some theoretical and/or empirical statistical tests, and/or generate easily detectable regular patterns [56, 65].

Fortunately, many applications appear quite robust to these defects. But with the rapid increase in desktop computing power, increasingly sophisticated simulation studies are being performed that require more and more “random” numbers and whose results are more sensitive to the quality of the underlying generator [28, 40, 65, 90]. Sometimes, using a not-so-good generator can give totally misleading results. Perhaps this happens rarely, but can be disastrous in some cases. For that reason, researchers are still actively investigating ways of building generators. The main goal is to design more robust generators without having to pay too much in terms of portability, flexibility, and efficiency. In the following sections, we give a quick overview of the ongoing research. We focus mainly on efficient and recently proposed techniques for generating uniform pseudorandom numbers. Stochastic simulations typically transform such numbers to generate variates according to more complex distributions [13, 25]. Here, “uniform pseudorandom” means that the numbers behave from the outside as if they were the values of i.i.d. random variables, uniformly distributed over some finite set of symbols. This set of symbols is often a set of integers of the form {0, . . . , m - 1} and the symbols are usually transformed by some function into values between 0 and 1, to approximate the U(0, 1) distribution. Other tutorial-like references on uniform variate generation include [13, 23, 52, 54, 65, 84, 89].
Computing the block triangular form of a sparse matrix
Authors: Pothen Alex , Fan Chin-Ju
Published: July 2002

We consider the problem of permuting the rows and columns of a rectangular or square, unsymmetric sparse matrix to compute its block triangular form. This block triangular form is based on a canonical decomposition of bipartite graphs induced by a maximum matching and was discovered by Dulmage and Mendelsohn. We describe implementations of algorithms to compute the block triangular form and provide computational results on sparse matrices from test collections. Several applications of the block triangular form are also included.
The hB-tree: a multiattribute indexing method with good guaranteed performance
Authors: Lomet David B. , Salzberg Betty
Published: July 2002

A new multiattribute index structure called the hB-tree is introduced. It is derived from the K-D-B-tree of Robinson [15] but has additional desirable properties. The hB-tree internode search and growth processes are precisely analogous to the corresponding processes in B-trees [1]. The intranode processes are unique. A k-d tree is used as the structure within nodes for very efficient searching. Node splitting requires that this k-d tree be split. This produces nodes which no longer represent brick-like regions in k-space, but that can be characterized as holey bricks, bricks in which subregions have been extracted. We present results that guarantee hB-tree users decent storage utilization, reasonable size index terms, and good search and insert performance. These results guarantee that the hB-tree copes well with arbitrary distributions of keys.
Programme to Practice: Gender and Feminism in Archaeology
Authors: Conkey Margaret W. , Gero Joan M.
Published: July 2002

In the past decade, archaeologists have given considerable attention to research on gender in the human past. In this review, we attempt to acknowledge much of this diverse and abundant work from an explicitly feminist perspective. We focus on reviewing a selection of approaches to gender that are anchored to specific theoretical standpoints. In addition, we highlight several approaches that challenge an archaeology of gender that does not explicitly engage with the implications of this topic for research, practice, and interpretation. From our perspective, we suggest the value of situating gender research within an explicitly feminist framework, and we draw attention to some of the important insights for archaeology from the wider field of feminist critiques of science. Last, we draw attention to the crucial implications for the practice of archaeology.
CONTEMPORARY TRANSFORMATIONS OF LOCAL LINGUISTIC COMMUNITIES
Authors: Silverstein M.
Published: July 2002

▪ Abstract  An emergent focus of linguistic anthropological research is discernible in the investigation of the causes and consequences of contact of local language communities with forces of the wider polities in which they have become incorporated. This focus can be sketched by surveying a number of its component conceptual approaches, such as anthropological linguistics, ethnography of communication, variationist sociolinguistics, and the sociology and politics of languages. Its consideration of language as a total cultural fact is outlined by reference to studies that differentially emphasize language structure, entextualization/contextualization of language, and language ideology.
The Origin of State Societies in South America
Authors: Stanish Charles
Published: July 2002

▪ Abstract  The earliest states developed in the central Andean highlands and along the central Pacific coast of western South America. The consensus in the archaeological literature is that state societies first developed in the central Andes in the early part of the first millennium C.E. A minority opinion holds that first-generation states developed as early as the late second millennium B.C.E. in the same area. The Andean region constitutes one of a few areas of first-generation state development in the world. This area therefore represents an important case study for the comparative analysis of state formation. This article outlines the arguments for state formation in South America, presents the evidence, analyzes the underlying assumptions about these arguments, and assesses the South American data in terms of contemporary anthropological theory of state evolution.
THE ORGANIZATION AND REGULATION OF PLANT GLYCOLYSIS
Authors: Plaxton William C.
Published: July 2002

▪ Abstract  This review discusses the organization and regulation of the glycolytic pathway in plants and compares and contrasts plant and nonplant glycolysis. Plant glycolysis exists both in the cytosol and plastid, and the parallel reactions are catalyzed by distinct nuclear-encoded isozymes. Cytosolic glycolysis is a complex network containing alternative enzymatic reactions. Two alternate cytosolic reactions enhance the pathway's ATP yield through the use of pyrophosphate in place of ATP. The cytosolic glycolytic network may provide an essential metabolic flexibility that facilitates plant development and acclimation to environmental stress. The regulation of plant glycolytic flux is assessed, with a focus on the fine control of enzymes involved in the metabolism of fructose-6-phosphate and phosphoenolpyruvate. Plant and nonplant glycolysis are regulated from the “bottom up” and “top down,” respectively. Research on tissue- and developmental-specific isozymes of plant glycolytic enzymes is summarized. Potential pitfalls associated with studies of glycolytic enzymes are considered. Some glycolytic enzymes may be multifunctional proteins involved in processes other than carbohydrate metabolism.
PHOSPHOENOLPYRUVATE CARBOXYLASE: A Ubiquitous, Highly Regulated Enzyme in Plants
Authors: Chollet Raymond , Vidal Jean , O'Leary Marion H.
Published: July 2002

▪ Abstract  Since plant phosphoenolpyruvate carboxylase (PEPC) was last reviewed in the Annual Review of Plant Physiology over a decade ago (O'Leary 1982), significant advances have been made in our knowledge of this oligomeric, cytosolic enzyme. This review highlights this exciting progress in plant PEPC research by focusing on the three major areas of recent investigation: the enzymology of the protein; its posttranslational regulation by reversible protein phosphorylation and opposing metabolite effectors; and the structure, expression, and molecular evolution of the nuclear PEPC genes. It is hoped that the next ten years will be equally enlightening, especially with respect to the three-dimensional structure of the plant enzyme, the molecular analysis of its highly regulated protein-Ser/Thr kinase, and the elucidation of its associated signal-transduction pathways in various plant cell types.
DNA METHYLATION IN PLANTS
Authors: Finnegan E. J. , Genger R. K. , Peacock W. J. , Dennis E. S.
Published: July 2002

▪ Abstract  Methylation of cytosine residues in DNA provides a mechanism of gene control. There are two classes of methyltransferase in Arabidopsis; one has a carboxy-terminal methyltransferase domain fused to an amino-terminal regulatory domain and is similar to mammalian methyltransferases. The second class apparently lacks an amino-terminal domain and is less well conserved. Methylcytosine can occur at any cytosine residue, but it is likely that clonal transmission of methylation patterns only occurs for cytosines in strand-symmetrical sequences CpG and CpNpG. In plants, as in mammals, DNA methylation has dual roles in defense against invading DNA and transposable elements and in gene regulation. Although originally reported as having no phenotypic consequence, reduced DNA methylation disrupts normal plant development.
THE AGE OF THE GALACTIC GLOBULAR CLUSTER SYSTEM
Authors: VandenBerg Don A. , Bolte Michael , Stetson Peter B.
Published: July 2002

▪ Abstract  A careful assessment of current uncertainties in stellar physics (opacities, nuclear reaction rates, equation of state effects, diffusion, rotation, and mass loss), in the chemistry of globular cluster (GC) stars, and in the cluster distance scale, suggests that the most metal-poor (presumably the oldest) of the Galaxy's GCs have ages near 15 Gyr. Ages below 12 Gyr or above 20 Gyr appear to be highly unlikely. If these ≈ 2 σ limits are increased by ∼ 1 Gyr to account for the formation time of the globulars, and if standard Friedmann cosmologies with the cosmological constant set to zero are assumed, then the GC constraint on the present age of the Universe (t0≥ 13 Gyr) implies that the Hubble constant H0≤ 51 km s−1Mpc−1if the density parameter Ω = 1 or ≤ 62 km s−1Mpc−1if Ω = 0.3.
SPHINGOLIPID FUNCTIONS INSACCHAROMYCES CEREVISIAE: Comparison to Mammals
Authors: Dickson Robert C.
Published: July 2002

Many roles for sphingolipids have been identified in mammals. Available data suggest that sphingolipids and their intermediates also have diverse roles in Saccharomyces cerevisiae. These roles include signal transduction during the heat stress response, regulation of calcium homeostasis or components in calcium-mediated signaling pathways, regulation of the cell cycle, and functions as components in trafficking of secretory vesicles from the endoplasmic reticulum to the Golgi apparatus and as the lipid moiety in many glycosylphosphatidylinositol-anchored proteins. S. cerevisiae is likely to be the first organism in which all genes involved in sphingolipid metabolism are identified. This information will provide an unprecedented opportunity to determine, for the first time in any organism, how sphingolipid synthesis is regulated. Through the use of both genetic and biochemical techniques, the identification of the complete array of processes regulated by sphingolipid signals is likely to be possible, as is the quantification of the physiological contribution of each.
ROLE OF SMALL G PROTEINS IN YEAST CELL POLARIZATION AND WALL BIOSYNTHESIS
Authors: Cabib Enrico , Drgonová Jana , Drgon Tomás
Published: July 2002

In the vegetative (mitotic) cycle and during sexual conjugation, yeast cells display polarized growth, giving rise to a bud or to a mating projection, respectively. In both cases one can distinguish three steps in these processes: choice of a growth site, organization of the growth site, and actual growth and morphogenesis. In all three steps, small GTP-binding proteins (G proteins) and their regulators play essential signaling functions. For the choice of a bud site, Bud1, a small G protein, Bud2, a negative regulator of Bud1, and Bud5, an activator, are all required. If any of them is defective, the cell loses its ability to select a proper bud position and buds randomly. In the organization of the bud site or of the site in which a mating projection appears, Cdc42, its activator Cdc24, and its negative regulators play a fundamental role. In the absence of Cdc42 or Cdc24, the actin cytoskeleton does not become organized and budding does not take place. Finally, another small G protein, Rho1, is required for activity of β(1 → 3)glucan synthase, the enzyme that catalyzes the synthesis of the major structural component of the yeast cell wall. In all of the above processes, G proteins can work as molecular switches because of their ability to shift between an active GTP-bound state and an inactive GDP-bound state.
Tetrahydropterin-Dependent Amino Acid Hydroxylases
Authors: Fitzpatrick Paul F.
Published: July 2002

▪ Abstract  Phenylalanine hydroxylase, tyrosine hydroxylase, and tryptophan hydroxylase constitute a small family of monooxygenases that utilize tetrahydropterins as substrates. When from eukaryotic sources, these enzymes are composed of a homologous catalytic domain to which are attached discrete N-terminal regulatory domains and short C-terminal tetramerization domains, whereas the bacterial enzymes lack the N-terminal and C-terminal domains. Each enzyme contains a single ferrous iron atom bound to two histidines and a glutamate. Recent mechanistic studies have begun to provide insights into the mechanisms of oxygen activation and hydroxylation. Although the hydroxylating intermediate in these enzymes has not been identified, the iron is likely to be involved. Reversible phosphorylation of serine residues in the regulatory domains affects the activities of all three enzymes. In addition, phenylalanine hydroxylase is allosterically regulated by its substrates, phenylalanine and tetrahydrobiopterin.
Chromosome Cohesion, Condensation, and Separation
Authors: Hirano Tatsuya
Published: July 2002

▪ Abstract  The faithful segregation of genetic information requires highly orchestrated changes of chromosome structure during the mitotic cell cycle. The linkage between duplicated sister DNAs is established during S phase and maintained throughout G2 phase (cohesion). In early mitosis, dramatic structural changes occur to produce metaphase chromosomes, each consisting of a pair of compacted sister chromatids (condensation). At anaphase onset, a signal is produced to disrupt the linkage between sister chromatids (separation), allowing them to be pulled apart to opposite poles of the cell. This review discusses our current understanding of the three stages of large-scale structural changes of chromosomes in eukaryotic cells. Recent genetic and biochemical studies have identified key components involved in these processes and started to uncover hitherto unexpected functional links between mitotic chromosome dynamics and other important chromosome functions.
Apoptosis Signaling
Authors: Strasser Andreas , O'Connor Liam , Dixit Vishva M.
Published: July 2002

▪ Abstract  Apoptosis, a physiological process for killing cells, is critical for the normal development and function of multicellular organisms. Abnormalities in cell death control can contribute to a variety of diseases, including cancer, autoimmunity, and degenerative disorders. Signaling for apoptosis occurs through multiple independent pathways that are initiated either from triggering events within the cell or from outside the cell, for instance, by ligation of death receptors. All apoptosis signaling pathways converge on a common machinery of cell destruction that is activated by a family of cysteine proteases (caspases) that cleave proteins at aspartate residues. Dismantling and removal of doomed cells is accomplished by proteolysis of vital cellular constituents, DNA degradation, and phagocytosis by neighboring cells. This article reviews current knowledge of apoptosis signaling, lists several pressing questions, and presents a novel model to explain the biochemical and functional interactions between components of the cell death regulatory machinery.
Regulation of Actin Filament Network Formation Through ARP2/3 Complex: Activation by a Diverse Array of Proteins
Authors: Higgs Henry N. , Pollard Thomas D.
Published: July 2002

▪ Abstract  Actin filament assembly and turnover drive many forms of cellular motility, particularly extension of the leading edge of locomoting cells and rocketing of pathogenic microorganisms through host cell cytoplasm. De novo nucleation of actin filaments appears to be required for these movements. A complex of seven proteins called Arp2/3 complex is the best characterized cellular initiator of actin filament nucleation. Arp2/3 complex is intrinsically inactive, relying on nucleation promoting factors for activation. WASp/Scar family proteins are prominent cellular nucleation promoting factors. They bring together an actin monomer and Arp2/3 complex in solution or on the side of an existing actin filament to initiate a new filament that grows in the barbed end direction. WASp and N-WASP are intrinsically autoinhibited, and their activity is regulated by Rho-family GTPases such as Cdc42, membrane polyphosphoinositides, WIP/verprolin, and SH3 domain proteins. These interactions provide a final common pathway for many signaling inputs to regulate actin polymerization. Microorganisms either activate Arp2/3 complex directly or usurp N-WASP to initiate actin polymerization.