bluuebunny/crossref_metadata_2025 huggingface dataset:
Optimal placement of high-probability randomly retrieved blocks on CLV optical discs
Authors: Ford Daniel Alexander , Christodoulakis Stavros
Published: July 2002

Optimal data placement on a CLV (Constant Linear Velocity) format optical discs has an objective the minimization of the expected access cost of data retrievals from the disc when the probabilities of access of data items may be different. The problem of optimal data placement for optical discs is both important and more difficult than the corresponding problem on magnetic discs. A good data placement on optical discs is more important because data sets on optical discs such as WORM and CD ROM cannot be modified or moved once they are placed on disc. Currently, even rewritable optical discs are best suited for applications that are archival in nature. The problem of optimal data placement on CLV format optical discs is more difficult, mainly because the useful storage space is not uniformly distributed across the disc surface (along the radius). This leads to a complicated positional performance trade-off not present for magnetic disks.

We present a model that encompasses all the important aspects of the placement problem on CLV format optical discs. The model takes into account the nonuniform distribution of useful storage, the dependency of the rotational delay on disc position, a parameterized seek cost function for optical discs, and the varying access probabilities of data items. We show that the optimal placement of high-probability blocks satisfies a unimodality property. Based on this observation, we solve the optimal placement problem. We then study the impact of the relative weights of the problem parameters and show that the optimal data placement may be very different from the optimal data placement on magnetic disks. We also validate our model and analysis and give an algorithm for computing the placement of disc sectors.
Integrating expert systems with group decision support systems
Authors: Aiken Milam W. , Liu Sheng Olivia R. , Vogel Douglas R.
Published: July 2002

Expert systems are powerful tools that serve as adjuncts to decision making and have found wide applicability in a wide variety of areas. Integrating expert systems with group decision support systems has the potential to enhance the quality and effeciency of group communication, negotiation, and collaborative work. This paper examines possible synergies between the two technologies and provides a survey of current partially-integrated systems. Finally, a prototype design of a highly-integrated system is described with directions for further research.
Integer forward differencing of cubic polynomials
Authors: Klassen R. Victor
Published: July 2002

Two incremental cubic interpolation algorithms are derived and analysed. Each is based on a known linear interpolation algorithm and modified for third order forward differencing. The tradeoff between overflow avoidance and loss of precision has made forward differencing a method which, although known to be fast, can be difficult to implement. It is shown that there is one particular family of curves which represents the worst case, in the sense that if a member of this family can be accurately drawn without overflow, then any curve which fits in the bounding box of that curve can be. From this the limitations in terms of step count and screen resolution are found for each of the two algorithms.
A new normal form for nested relations
Authors: Ozsoyoglu Z. Meral , Yuan Li-Yan
Published: July 2002

We consider nested relations whose schemes are structured as trees, called scheme trees, and introduce a normal form for such relations, called the nested normal form. Given a set of attributes
U
, and a set of multivalued dependencies (MVDs)
M
over these attributes, we present an algorithm to obtain a nested normal form decomposition of
U
with respect to
M
. Such a decomposition has several desirable properties, such as explicitly representing a set of full and embedded MVDs implied by
M
, and being a faithful and nonredundant representation of
U
. Moreover, if the given set of MVDs is conflict-free, then the nested normal form decomposition is also dependency-preserving. Finally, we show that if
M
is conflict-free, then the set of root-to-leaf paths of scheme trees in nested normal form decomposition is precisely the unique 4NF decomposition [9, 16] of
U
with respect to
M
.
A program integration algorithm that accommodates semantics-preserving transformations
Authors: Yang Wuu , Horwitz Susan , Reps Thomas
Published: July 2002

Given a program
Base
and two variants,
A
and
B
, each created by modifying separate copies of
Base
, the goal of program integration is to determine whether the modifications interfere, and if they do not, to create an integrated program that includes both sets of changes as well as the portions of
Base
preserved in both variants. Text-based integration techniques, such as the one used by the Unix

diff
3

utility, are obviously unsatisfactory because one has no guarantees about how the execution behavior of the integrated program relates to the behaviors of
Base
,
A
, and
B
. The first program-integration algorithm to provide such guarantees was developed by Horwitz et al.[13]. However, a limitation of that algorithm is that it incorporates no notion of semantics-preserving transformations. This limitation causes the algorithm to be overly conservative in its definition of interference. For example, if one variant changes the
way
a computation is performed (without changing the values computed) while the other variant adds code that uses the result of the computation, the algorithm would classify those changes as interfering. This paper describes a new integration algorithm that is able to accommodate semantics-preserving transformations.
Dynamic NURBS with geometric constraints for interactive sculpting
Authors: Terzopoulos Demetri , Qin Hong
Published: July 2002

This article develops a dynamic generalization of the nonuniform rational B-spline (NURBS) model. NURBS have become a defacto standard in commercial modeling systems because of their power to represent free-form shapes as well as common analytic shapes. To date, however, they have been viewed as purely geometric primitives that require the user to manually adjust multiple control points and associated weights in order to design shapes. Dynamic NURBS, or D-NURBS, are physics-based models that incorporate mass distributions, internal deformation energies, and other physical quantities into the popular NURBS geometric substrate. Using D-NURBS, a modeler can interactively sculpt curves and surfaces and design complex shapes to required specifications not only in the traditional indirect fashion, by adjusting control points and weights, but also through direct physical manipulation, by applying simulated forces and local and global shape constraints. D-NURBS move and deform in a physically intuitive manner in response to the user's direct manipulations. Their dynamic behavior results from the numerical integration of a set of nonlinear differential equations that automatically evolve the control points and weights in response to the applied forces and constraints. To derive these equations, we employ Lagrangian mechanics and a finite-element-like discretization. Our approach supports the trimming of D-NURBS surfaces using D-NURBS curves. We demonstrate D-NURBS models and constraints in applications including the rounding of solids, optimal surface fitting to unstructured data, surface design from cross sections, and free-form deformation. We also introduce a new technique for 2D shape metamorphosis using constrained D-NURBS surfaces.
A speech-act-based negotiation protocol
Authors: Chang Man Kit , Woo Carson C.
Published: July 2002

Existing negotiation protocols used in Distributed Artificial Intelligence (DAI) systems rarely take into account the results from negotiation research. We propose a negotiation protocol, SANP (Speech-Act-based Negotiation Protocol), which is based on Ballmer and Brennenstuhl's speech act classification and on negotiation analysis literature. The protocol is implemented as a domain-independent system using Strudel, which is an electronic mail toolkit. A small study tested the potential use of the protocol. Although a number of limitations were found in the study, the protocol appears to have potential in domains without these limitations, and it can serve as a building block to design more general negotiation protocols.
Program integration for languages with procedure calls
Authors: Binkley David , Horwitz Susan , Reps Thomas
Published: July 2002

Given a program Base and two variants, A and B, each created by modifying separate copies of Base, the goal of program integration is to determine whether the modifications interfere, and if they do not, to create an integrated program that incorporates both sets of changes as well as the portions of Base preserved in both variants. Text-based integration techniques, such as the one used by the Unix
diff3
utility, are obviously unsatisfactory because one has no guarantees about how the execution behavior of the integrated program relates to the behaviors of Base, A, and B. The first program integration algorithm to provide such guarantees was developed by Horwitz, Prins, and Reps. However, a limitation of that algorithm is that it only applied to programs written in a restricted language—in particular, the algorithm does not handle programs with procedures. This article describes a generalization of the Horwitz-Prins-Reps algorithm that handles programs that consist of multiple (and possibly mutually recursive) procedures.

We show that two straightforward generalizations of the Horwitz-Prins-Reps algorithm yield unsatisfactory results. The key issue in developing a satisfactory algorithm is how to take into account different calling contexts when determining what has changed in the variants A and B. Our solution to this problem involves identifying two different kinds of affected components of A and B: those affected regardless of how the procedure is called, and those affected by a changed or new calling context. The algorithm makes use of interprocedural program slicing to identify these components, as well as components in Base, A, and B with the same behavior.
Algorithm 750: CDT
Authors: Carpaneto G. , Dell'Amico M. , Toth P.
Published: July 2002

The Fortran code CDT, implementing an algorithm for the
asymmetric traveling salesman problem
, is presented. The method is based on the
Assignment Problem relaxation
and on a
subtour elimination branching scheme
. The effectiveness of the implementation derives from reduction procedures and parametric solution of the relaxed problems associated with the nodes of the branch-decision tree.
Software pipelining
Authors: Allan Vicki H. , Jones Reese B. , Lee Randall M. , Allan Stephen J.
Published: July 2002

Utilizing parallelism at the instruction level is an important way to improve performance. Because the time spent in loop execution dominates total execution time, a large body of optimizations focuses on decreasing the time to execute each iteration. Software pipelining is a technique that reforms the loop so that a faster execution rate is realized. Iterations are executed in overlapped fashion to increase parallelism.

Let {
ABC
}

n

represent a loop containing operations
A, B, C
that is executed
n
times. Although the operations of a single iteration can be parallelized, more parallelism may be achieved if the entire loop is considered rather than a single iteration. The software pipelining transformation utilizes the fact that a loop {
ABC
}

n

is equivalent to
A
{
BCA
}

n
−1

BC
. Although the operations contained in the loop do not change, the operations are from different iterations of the original loop.

Various algorithms for software pipelining exist. A comparison of the alternative methods for software pipelining is presented. The relationships between the methods are explored and possibilities for improvement highlighted.
Applying ethics to information technology issues
Authors: Mason Richard O.
Published: July 2002

The articles in this special section express a common theme; the use of information technology in society is creating a rather unique set of ethical issues that requires the making of new moral choices on the part of society and has spawned special implications for its members. Technology itself is not the only, nor necessarily the most responsible, cause of these issues. All ethical questions arise initially out of human agency. Technology, due to its capability to augment mental and physical powers of human beings, does stand in the role of a coconspirator. The hire of power-enhancing capabilities makes technology an inducer of sorts, a necessary but not sufficient underpinning to many of the ethical issues we face today.
Synchronizing clocks in the presence of faults
Authors: Lamport Leslie , Melliar-Smith P. M.
Published: July 2002

Algorithms are described for maintaining clock synchrony in a distributed multiprocess system where each process has its own clock. These algorithms work in the presence of arbitrary clock or process failures, including “two-faced clocks” that present different values to different processes. Two of the algorithms require that fewer than one-third of the processes be faulty. A third algorithm works if fewer than half the processes are faulty, but requires digital signatures.
Reduced instruction set computers
Authors: Patterson David A.
Published: July 2002

Reduced instruction set computers aim for both simplicity in hardware and synergy between architectures and compilers. Optimizing compilers are used to compile programming languages down to instructions that are as unencumbered as microinstructions in a large virtual address space, and to make the instruction cycle time as fast as possible.
Algorithm 772
Authors: Renka Robert J.
Published: July 2002

STRIPACK is a Fortran 77 software package that employs an incremental algorithm to construct a Delaunay triangulation and, optionally, a Voronoi diagram of a set of points (nodes) on the surface of the unit sphere. The triangulation covers the convex hull of the nodes, which need not be the entire surface, while the Voronoi diagram covers the entire surface. The package provides a wide range of capabilities including an efficient means of updating the triangulation with nodal additions or deletions. For
N
nodes, the storage requirement for the triangulation is 13
N
integer storage locations in addition to 3
N
nodal corrdinates. Using an off-line algorithm and work space of size 3
N
, the triangulation can be constructed with time complexity
O(NlogN)
.
Worst-case optimal hidden-surface removal
Authors: McKenna Michael
Published: July 2002

An O(
n
2
) hidden-surface removal algorithm is shown. This is an improvement over the previous best worst-case performance of O(
n
2
log
n
). It has been established that the hidden-line and hidden-surface problems have an Ω(
n
2
) worst-case lower bound, so the algorithm is optimal. However, the algorithm is not output-size sensitive. Two corollaries to the result are (1) hidden-lines can be removed in optimal O(
n
2
) time, and (2) the portion of a 3-D polyhedron visible from a given interior point is constructible in optimal O(
n
2
) time.
Dataflow machine architecture
Authors: Veen Arthur H.
Published: July 2002

Dataflow machines are programmable computers of which the hardware is optimized for fine-grain data-driven parallel computation. The principles and complications of data-driven execution are explained, as well as the advantages and costs of fine-grain parallelism. A general model for a dataflow machine is presented and the major design options are discussed.

Most dataflow machines described in the literature are surveyed on the basis of this model and its associated technology. For general-purpose computing the most promising dataflow machines are those that employ packet-switching communication and support general recursion. Such a recursion mechanism requires an extremely fast mechanism to map a sparsely occupied virtual space to a physical space of realistic size. No solution has yet proved fully satisfactory.

A working prototype of one processing element is described in detail. On the basis of experience with this prototype, some of the objections raised against the dataflow approach are discussed. It appears that the overhead due to fine-grain parallelism can be made acceptable by sophisticated compiling and employing special hardware for the storage of data structures. Many computing-intensive programs show sufficient parallelism. In fact, a major problem is to restrain parallelism when machine resources tend to get overloaded. Another issue that requires further investigation is the distribution of computation and data structures over the processing elements.
Supporting valid-time indeterminacy
Authors: Dyreson Curtis E. , Snodgrass Richard Thomas
Published: July 2002

In
valid-time indeterminacy
it is known that an event stored in a database did in fact occur, but it is not known exactly
when
. In this paper we extend the SQL data model and query language to support valid-time indeterminacy. We represent the occurrence time of an event with a set of possible instants, delimiting when the event might have occurred, and a probability distribution over that set. We also describe query language constructs to retrieve information in the presence of indeterminacy. These constructs enable users to specify their
credibility
in the underlying data and their
plausibility
in the relationships among that data. A denotational semantics for SQL's select statement with optional credibility and plausibility constructs is given. We show that this semantics is
reliable,
in that it never produces incorrect information, is
maximal,
in that if it were extended to be more informative, the results may not be reliable, and
reduces
to the previous semantics when there is no indeterminacy. Although the extended data model and query language provide needed modeling capabilities, these extensions appear initially to carry a significant execution cost. A contribution of this paper is to demonstrate that our approach is useful and practical. An efficient representation of valid-time indeterminacy and efficient query processing algorithms are provided. The cost of support for indeterminacy is empirically measured, and is shown to be modest. Finally, we show that the approach is general, by applying it to the temporal query language constructs being proposed for SQL3.
Complete inverted files for efficient text retrieval and analysis
Authors: Blumer A. , Blumer J. , Haussler D. , McConnell R. , Ehrenfeucht A.
Published: July 2002

Given a finite set of texts
S
= {
w
1, … ,

w
k

} over some fixed finite alphabet Σ, a complete inverted file for
S
is an abstract data type that provides the functions
find
(
w
), which returns the longest prefix of
w
that occurs (as a subword of a word) in
S
;
freq
(
w
), which returns the number of times
w
occurs in
S
; and
locations
(
w
), which returns the set of positions where
w
occurs in
S
. A data structure that implements a complete inverted file for
S
that occupies linear space and can be built in linear time, using the uniform-cost RAM model, is given. Using this data structure, the time for each of the above query functions is optimal. To accomplish this, techniques from the theory of finite automata and the work on suffix trees are used to build a deterministic finite automaton that recognizes the set of all subwords of the set
S
. This automaton is then annotated with additional information and compacted to facilitate the desired query functions. The result is a data structure that is smaller and more flexible than the suffix tree.
Algorithm 784: GEMM-based level 3 BLAS
Authors: Kågström Bo , van Loan Charles
Published: July 2002

This companion article discusses portability and optimization issues of the GEMM-based level 3 BLAS model implementations and the performance evaluation benchmark. All software comes in all four data types (single- and double-precision, real and complex) and are designed to be easy to implement and use on different platforms. Each of the GEMM-based routines has a few machine-dependent parameters that specify internal block sizes, cache characteristics, and branch points for alternative code sections. These parameters provide means for adjustment to the characteristics of a memory hierarchy.
A language facility for designing database-intensive applications
Authors: Mylopoulos John , Bernstein Philip A. , Wong Harry K. T.
Published: July 2002

TAXIS, a language for the design of interactive information systems (e.g., credit card verification, student-course registration, and airline reservations) is described. TAXIS offers (relational) database management facilities, a means of specifying semantic integrity constraints, and an exception-handling mechanism, integrated into a single language through the concepts of
class, property
, and the
IS-A
(generalization)
relationship
. A description of the main constructs of TAXIS is included and their usefulness illustrated with examples.
Index Register Allocation
Authors: Horwitz L. P. , Karp R. M. , Miller R. E. , Winograd S.
Published: July 2002

A procedure for index register allocation is described. The rules of this procedure are shown to yield an optimal allocation for “straight line” programs.
Pseudo-Runge-Kutta Methods Involving Two Points
Authors: Byrne George D. , Lambert Robert J.
Published: July 2002

A third order two step method and a fourth order two step method for the numerical solution of the vector initial value problem
dy
÷
dx
=F(y), y(
a
) = n can be defined by making evaluations of F similar to those found in a classical Runge-Kutta formula. These two step methods are different from classical Runge-Kutta methods in that evaluations of F made at the previous point are used along with those made at the current point in order to obtain the solution at the next point. If the stepsize is fixed, this use of previous computations makes it possible to obtain the solution at the next point by evaluating F two or three times for the third or fourth order method, respectively.

These methods are consistent with the initial value problem and are shown to be convergent with its unique solution under certain restrictions. The local truncation error terms are given. Finally, a few numerical results are presented.
Semi-Automated Mathematics
Authors: Guard J. R. , Oglesby F. C. , Bennett J. H. , Settle L. G.
Published: July 2002

The fifth in a series of experiments in semi-automated mathematics is described. These experiments culminated in large complex computer programs which allow a mathematician to prove mathematical theorems on an man/machine basis. SAM V, the fifth program, is oriented primarily toward the development of efficient automatic techniques for handling some of the more basic processes of mathematical deduction, and toward the realization of efficient real-time interaction between man and machine through the use of cathode-ray tube displays. SAM V's most notable success is the solution of an open problem in lattice theory.
IFO: a formal semantic database model
Authors: Abiteboul Serge , Hull Richard
Published: July 2002

A new, formally defined database model is introduced that combines fundamental principles of “semantic” database modeling in a coherent fashion. Using a graph-based formalism, the IFO model provides mechanisms for representing structured objects, and functional and ISA relationships between them. A number of fundamental results concerning semantic data modeling are obtained in the context of the IFO model. Notably, the types of object structure that can arise as a result of multiple uses of ISA relationships and object construction are described. Also, a natural, formal definition of update propagation is given, and it is shown that (under certain conditions) a correct update always exists.
Amortized analyses of self-organizing sequential search heuristics
Authors: Bentley Jon L. , McGeoch Catherine C.
Published: July 2002

The performance of sequential search can be enhanced by the use of heuristics that move elements closer to the front of the list as they are found. Previous analyses have characterized the performance of such heuristics probabilistically. In this article, we use amortization to analyze the heuristics in a worst-case sense; the relative merit of the heuristics in this analysis is different in the probabilistic analyses. Experiments show that the behavior of the heuristics on real data is more closely described by the amortized analyses than by the probabilistic analyses.
A foundation for representing and querying moving objects
Authors: Güting Ralf Hartmut , Böhlen Michael H. , Erwig Martin , Jensen Christian S. , Lorentzos Nikos A. , Schneider Markus , Vazirgiannis Michalis
Published: July 2002

Spatio-temporal databases deal with geometries changing over time. The goal of our work is to provide a DBMS data model and query language capable of handling such time-dependent geometries, including those changing continuously that describe
moving objects
. Two fundamental abstractions are
moving point
and
moving region
, describing objects for which only the time-dependent position, or position and extent, respectively, are of interest. We propose to present such time-dependent geometries as attribute data types with suitable operations, that is, to provide an abstract data type extension to a DBMS data model and query language. This paper presents a design of such a system of abstract data types. It turns out that besides the main types of interest, moving point and moving region, a relatively large number of auxiliary data types are needed. For example, one needs a line type to represent the projection of a moving point into the plane, or a “moving real” to represent the time-dependent distance of two points. It then becomes crucial to achieve (i) orthogonality in the design of the system, i.e., type constructors can be applied unifomly; (ii) genericity and consistency of operations, i.e., operations range over as many types as possible and behave consistently; and (iii) closure and consistency between structure and operations of nontemporal and related temporal types. Satisfying these goal leads to a simple and expressive system of abstract data types that may be integrated into a query language to yield a powerful language for querying spatio-temporal data, including moving objects. The paper formally defines the types and operations, offers detailed insight into the considerations that went into the design, and exemplifies the use of the abstract data types using SQL. The paper offers a precise and conceptually clean foundation for implementing a spatio-temporal DBMS extension.
On the sorting-complexity of suffix tree construction
Authors: Farach-Colton Martin , Ferragina Paolo , Muthukrishnan S.
Published: July 2002

The suffix tree of a string is the fundamental data structure of combinatorial pattern matching. We present a recursive technique for building suffix trees that yields optimal algorithms in different computational models. Sorting is an inherent bottleneck in building suffix trees and our algorithms match the sorting lower bound. Specifically, we present the following results. (1) Weiner [1973], who introduced the data structure, gave an optimal
0
(
n
)-time algorithm for building the suffix tree of an
n
-character string drawn from a constant-size alphabet. In the comparison model, there is a trivial Ο(
n
log
n
)-time lower bound based on sorting, and Weiner's algorithm matches this bound. For integer alphabets, the fastest known algorithm is the
O
(
n
log
n
)time comparison-based algorithm, but no super-linear lower bound is known. Closing this gap is the main open question in stringology. We settle this open problem by giving a linear time reduction to sorting for building suffix trees. Since sorting is a lower-bound for building suffix trees, this algorithm is time-optimal in every alphabet mode. In particular, for an alphabet consisting of integers in a polynomial range we get the first known linear-time algorithm. (2) All previously known algorithms for building suffix trees exhibit a marked absence of locality of reference, and thus they tend to elicit many page faults (I/Os) when indexing very long strings. They are therefore unsuitable for building suffix trees in secondary storage devices, where I/Os dominate the overall computational cost. We give a linear-I/O reduction to sorting for suffix tree construction. Since sorting is a trivial I/O-lower bound for building suffix trees, our algorithm is I/O-optimal.
Implementing Clenshaw-Curtis quadrature, II computing the cosine transformation
Authors: Gentleman W. Morven
Published: July 2002

In a companion paper to this, “I Methodology and Experiences,” the automatic Clenshaw-Curtis quadrature scheme was described and how each quadrature formula used in the scheme requires a cosine transformation of the integrand values was shown. The high cost of these cosine transformations has been a serious drawback in using Clenshaw-Curtis quadrature. Two other problems related to the cosine transformation have also been troublesome. First, the conventional computation of the cosine transformation by recurrence relation is numerically unstable, particularly at the low frequencies which have the largest effect upon the integral. Second, in case the automatic scheme should require refinement of the sampling, storage is required to save the integrand values after the cosine transformation is computed.

This second part of the paper shows how the cosine transformation can be computed by a modification of the fast Fourier transform and all three problems overcome. The modification is also applicable in other circumstances requiring cosine or sine transformations, such as polynomial interpolation through the Chebyshev points.
A practical tool kit for making portable compilers
Authors: Tanenbaum Andrew S. , van Staveren Hans , Keizer E. G. , Stevenson Johan W.
Published: July 2002

The Amsterdam Compiler Kit is an integrated collection of programs designed to simplify the task of producing portable (cross) compilers and interpreters. For each language to be compiled, a program (called a front end) must be written to translate the source program into a common intermediate code. This intermediate code can be optimized and then either directly interpreted or translated to the assembly language of the desired target machine. The paper describes the various pieces of the tool kit in some detail, as well as discussing the overall strategy.
Estimating file access time of floppy disks
Authors: Pechura M. A. , Schoeffler J. D.
Published: July 2002

Small computers often use floppy disks for storage. Since such disks are significantly slower than hard disks, the response time of a given application program is due predominantly to the time required to access data in files. Access time is dependent on three factors: hardware (disk drive and interface), the operating system in use, and the patterns of file access of application programs. A simple-to-use method of predicting access times with good accuracy is presented. The method makes use of simple calibration experiments that provide information related to the hardware and operating system characteristics of the system in use. This is combined with patterns of file access information for a given application program to predict access time for that program. Actual examples for several small computer systems are presented.
Updating mean and variance estimates
Authors: West D. H. D.
Published: July 2002

A method of improved efficiency is given for updating the mean and variance of weighted sampled data when an additional data value is included in the set. Evidence is presented that the method is stable and at least as accurate as the best existing updating method.
Optimal surface reconstruction from planar contours
Authors: Fuchs H. , Kedem Z. M. , Uselton S. P.
Published: July 2002

In many scientific and technical endeavors, a three-dimensional solid must be reconstructed from serial sections, either to aid in the comprehension of the object's structure or to facilitate its automatic manipulation and analysis. This paper presents a general solution to the problem of constructing a surface over a set of cross-sectional contours. This surface, to be composed of triangular tiles, is constructed by separately determining an optimal surface between each pair of consecutive contours. Determining such a surface is reduced to the problem of finding certain minimum cost cycles in a directed toroidal graph. A new fast algorithm for finding such cycles is utilized. Also developed is a closed-form expression, in terms of the number of contour points, for an upper bound on the number of operations required to execute the algorithm. An illustrated example which involves the construction of a minimum area surface describing a human head is included.
An ALGOL-based associative language
Authors: Feldman Jerome A. , Rovner Paul D.
Published: July 2002

A high level programming language for large, complex associative structures has been designed and implemented. The underlying data structure has been implemented using a hash-coding technique. The discussion includes a comparison with other work and examples of applications of the language.
An information-theoretic approach to automatic query expansion
Authors: Carpineto Claudio , de Mori Renato , Romano Giovanni , Bigi Brigitte
Published: July 2002

Techniques for automatic query expansion from top retrieved documents have shown promise for improving retrieval effectiveness on large collections; however, they often rely on an empirical ground, and there is a shortage of cross-system comparisons. Using ideas from Information Theory, we present a computationally simple and theoretically justified method for assigning scores to candidate expansion terms. Such scores are used to select and weight expansion terms within Rocchio's framework for query reweigthing. We compare ranking with information-theoretic query expansion versus ranking with other query expansion techniques, showing that the former achieves better retrieval effectiveness on several performance measures. We also discuss the effect on retrieval effectiveness of the main parameters involved in automatic query expansion, such as data sparseness, query difficulty, number of selected documents, and number of selected terms, pointing out interesting relationships.
MSO definable string transductions and two-way finite-state transducers
Authors: Engelfriet Joost , Hoogeboom Hendrik Jan
Published: July 2002

We extend a classic result of Büchi, Elgot, and Trakhtenbrot: MSO definable string transductions i.e., string-to-string functions that are definable by an interpretation using monadic second-order (MSO) logic, are exactly those realized by deterministic two-way finite-state transducers, i.e., finite-state automata with a two-way input tape and a one-way output tape. Consequently, the equivalence of two mso definable string transductions is decidable. In the nondeterministic case however, MSO definable string tranductions, i.e., binary relations on strings that are mso definable by an interpretation with parameters, are incomparable to those realized by nondeterministic two-way finite-state transducers. This is a motivation to look for another machine model, and we show that both classes of MSO definable string transductions are characterized in terms of Hennie machines, i.e., two-way finite-state transducers that are allowed to rewrite their input tape, but may visit each position of their input only a bounded number of times.
Simplifying fault-tolerance
Authors: Bazzi Rida A. , Neiger Gil
Published: July 2002

The difficulty of designing fault-tolerant distributed algorithms incr eases with the severity of failures that an algorithm must tolerate, especially for systems with synchronous message passing. This paper considers methods that automatically translate algorithms tolerant of simple crash failures into ones tolerant of more severe failures. These translations simplify the design task by allowing algorithm designers to assume that processors fail only by stopping. Such translations can be quantified by two measures:
fault-tolerance
, which is a measure of how many processors must remain correct for the translation to be correct, and
round-complexity
, which is a measure of how the translation increases the running time of an algorithm. Understanding these translations and their limitations with respect to these measures can provide insight into the relative impact of different models of faculty behavior on the ability to provide fault-tolerant applications for systems with synchronous message passing.

This paper considers translations fr om crash failures to each of the following types of more severe failures: omission to send messages; omission to send and receive messages; and totally arbitrary behavior. It shows that previously developed translaions to send-omission failures are optimal with respect to both fault-tolerance and round-complexity. It exhibits a hierarchy of translations to general (send/receive) omission failures that improves upon the fault-tolerance of previously developed translations. These translations are optimal in that they cannot be improved with respect to one measure without negatively affecting the other; that is, the hierarchy of translations is matched by corresponding hierarchy of impossibility results. The paper also gives a hierarchy of translations to arbitrary failures that improves upon the round-complexity of previously developed translations. These translations are near-optimal;
A framework for constructing features and models for intrusion detection systems
Authors: Lee Wenke , Stolfo Salvatore J.
Published: July 2002

Intrusion detection (ID) is an important component of infrastructure protection mechanisms. Intrusion detection systems (IDSs) need to be accurate, adaptive, and extensible. Given these requirements and the complexities of today's network environments, we need a more systematic and automated IDS development process rather that the pure knowledge encoding and engineering approaches. This article describes a novel framework, MADAM ID, for Mining Audit Data for Automated Models for Instrusion Detection. This framework uses data mining algorithms to compute activity patterns from system audit data and extracts predictive features from the patterns. It then applies machine learning algorithms to the audit records taht are processed according to the feature definitions to generate intrusion detection rules. Results from the 1998 DARPA Intrusion Detection Evaluation showed that our ID model was one of the best performing of all the participating systems. We also briefly discuss our experience in converting the detection models produced by off-line data mining programs to real-time modules of existing IDSs.
Incremental linear interpolation
Authors: Field Dan
Published: July 2002

Two incremental linear interpolation algorithms are derived and analyzed for speed and accuracy. The first is a version of a “simple” digital differential analyzer (DDA) employing fixed-point arithmetic, whereas the second is a new algorithm that uses only integral arithmetic and is a generalization of Bresenham's line-drawing algorithm. The new algorithm is shown to achieve perfect accuracy and, depending on the underlying processor, may be faster than the fixed-point algorithm.
A mechanical proof of the Church-Rosser theorem
Authors: Shankar N.
Published: July 2002

The Church-Rosser theorem is a celebrated metamathematical result on the lambda calculus. We describe a formalization and proof of the Church-Rosser theorem that was carried out with the Boyer-Moore theorem prover. The proof presented in this paper is based on that of Tait and Martin-Löf. The mechanical proof illustrates the effective use of the Boyer-Moore theorem prover in proof checking difficult metamathematical proofs.
Past and future emergency response information systems
Authors: Turoff Murray
Published: July 2002

Past and future objectives remain the same in crises, providing relevant communities collaborative knowledge systems to exchange information.
A node-addition model for symbolic factorization
Authors: Law Kincho H. , Fenives Steven J.
Published: July 2002

A symbolic node-addition model for matrix factorization of symmetric positive definite matrices is described. In this model, the nodes are added onto the filled graph one at a time. The advantage of the node-addition model is its simplicity and flexibility. The model can be immediately incorporated into finite element analysis programs. The model can also be extended to determine modification patterns in the matrix factors due to changes in the original matrix. For a given matrix
K
(=

LDL
t

), the time complexity of the algorithm for constructing the structure of the lower triangular matrix factor
L
is
O
(η(
L
)) where η(
L
) is the number of nonzero entries in
L
.
BAROQUE: a browser for relational databases
Authors: Motro Amihai
Published: July 2002

The standard, most efficient method to retrieve information from databases can be described as systematic retrieval: The needs of the user are described in a formal query, and the database management system retrieves the data promptly. There are several situations, however, in which systematic retrieval is difficult or even impossible. In such situations exploratory search (browsing) is a helpful alternative. This paper describes a new user interface, called BAROQUE, that implements exploratory searches in relational databases. BAROQUE requires few formal skills from its users. It does not assume knowledge of the principles of the relational data model or familiarity with the organization of the particular database being accessed. It is especially helpful when retrieval targets are vague or cannot be specified satisfactorily. BAROQUE establishes a view of the relational database that resembles a semantic network, and provides several intuitive functions for scanning it. The network integrates both schema and data, and supports access by value. BAROQUE can be implemented on top of any basic relational database management system but can be modified to take advantage of additional capabilities and enhancements often present in relational systems.
Sparse matrix test problems
Authors: Duff I. S. , Grimes Roger G. , Lewis John G.
Published: July 2002

We describe the Harwell-Boeing sparse matrix collection, a set of standard test matrices for sparse matrix problems. Our test set comprises problems in linear systems, least squares, and eigenvalue calculations from a wide variety of scientific and engineering disciplines. The problems range from small matrices, used as counter-examples to hypotheses in sparse matrix research, to large test cases arising in large-scale computation. We offer the collection to other researchers as a standard benchmark for comparative studies of algorithms. The procedures for obtaining and using the test collection are discussed. We also describe the guidelines for contributing further test problems to the collection.
Boolean operations of 2-manifolds through vertex neighborhood classification
Authors: Mäntylä Martti
Published: July 2002

A topologically complete set operations algorithm for planar polyhedral Z-manifold objects is described; that is, under the assumption that all numerical tests required can be correctly evaluated, the algorithm is capable of solving all “special cases."

The central component of the algorithm is a module here called the
vertex neighborhood classifier
. By virtue of the classifier, the various special cases can be reduced into a collection of classification problems involving a pair of coincident vertices. The classifier works by means of decision rules that guarantee the topological consistency and regularity of the resulting polyhedron. If the result is not a 2-manifold, a relaxed polyhedron will be produced.
Electing a leader in a synchronous ring
Authors: Frederickson Greg N. , Lynch Nancy A.
Published: July 2002

The problem of electing a leader in a synchronous ring ofnprocessors is considered. Both positive and negative results are obtained. On the one hand, if processor IDS are chosen from some countable set, then there is an algorithm that uses onlyO(n) messages in the worst case. On the other hand, any algorithm that is restricted to use only comparisons of IDs requires Ω(nlogn) messages in the worst case. Alternatively, if the number of rounds is required to be bounded by sometin the worst case, and IDs are chosen from any set having at least ƒ(n, t) elements, for a certain very fast-growing function ƒ, then any algorithm requires Ω(nlogn) messages in the worst case.
Blending algebraic surfaces
Authors: Warren J.
Published: July 2002

A new definition of geometric continuity for implicitly defined surfaces is introduced. Under this definition, it is shown that algebraic
blending
surfaces (surfaces that smoothly join two or more surfaces) have a very specific form. In particular, any polynomial whose zero set blends the zero sets of several other polynomials is always expressible as a simple combination of these polynomials. Using this result, new methods for blending several algebraic surfaces simultaneously are derived.
Computation of the axial view of a set of isothetic parallelepipeds
Authors: Preparata Franco P. , Vitter Jeffrey S. , Yvinec Mariette
Published: July 2002

We present a new technique to display a scene of three-dimensional isothetic parallelepipeds (3D-rectangles), viewed from infinity along one of the coordinate axes (axial view). In this situation, there always exists a topological sorting of the 3D-rectangles based on the relation of occlusion (a dominance relation). The arising total order is used to generate the axial view, where the two-dimensional view of each 3D-rectangle is incrementally added, starting from the closest 3D-rectangle. The proposedscene-sensitivealgorithm runs in timeO(Nlog2N+dlogN), whereNis the number of 3D-rectangles anddis the number of edges of the display. This improves over the previously best known technique based on the same approach.
FLUORESCENCE MICROSCOPY OF LIVING PLANT CELLS
Authors: Gilroy Simon
Published: July 2002

▪ Abstract  Since its inception, light microscopy has shown the elegance and subtlety with which function is expressed in the form of the cells, tissues, and organs of the plant. Recently, light microscopy has seen a resurgence in use fueled by advances in microscope design and computer-based image analysis. The structural resolution afforded by static, fixed samples is being increasingly supplemented by approaches using fluorescent analogs and selective fluorescent indicators, which visualize the dynamic processes in living, functioning cells. This review describes some of these approaches and discusses how they are taking us a step closer to viewing the intricate complexity with which plants organize and regulate their functions down to the subcellular level.
(TRANS)GENE SILENCING IN PLANTS: How Many Mechanisms?
Authors: Fagard M. , Vaucheret H.
Published: July 2002

▪ Abstract  Epigenetic silencing of transgenes and endogenous genes can occur at the transcriptional level (TGS) or at the posttranscriptional level (PTGS). Because they can be induced by transgenes and viruses, TGS and PTGS probably reflect alternative (although not exclusive) responses to two important stress factors that the plant's genome has to face: the stable integration of additional DNA into chromosomes and the extrachromosomal replication of a viral genome. TGS, which results from the impairment of transcription initiation through methylation and/or chromatin condensation, could derive from the mechanisms by which transposed copies of mobile elements and T-DNA insertions are tamed. PTGS, which results from the degradation of mRNA when aberrant sense, antisense, or double-stranded forms of RNA are produced, could derive from the process of recovery by which cells eliminate pathogens (RNA viruses) or their undesirable products (RNA encoded by DNA viruses). Mechanisms involving DNA-DNA, DNA-RNA, or RNA-RNA interactions are discussed to explain the various pathways for triggering (trans)gene silencing in plants.