Search
Join ACM

Artificial Intelligence and Machine Learning

Advertisement

Research and Advances Nov 1 1988

The number of buffers required for sequential processing of a disk file

The number of buffers required for sequential processing of disk files is investigated with the assumption that there is a single user served by two processors: one reads blocks from the disk into buffers in main memory, while the other processor processes the buffers. If processing is faster than reading, then two buffers suffice. However, if processing is slower, using only two buffers does not guarantee minimum completion time. The minimal required number of buffers is calculated in this article.
and
Research and Advances Nov 1 1988

Efficient table-free sampling methods for the exponential, Cauchy, and normal distributions

Three algorithms for sampling from exponential, Cauchy and normal distributions are developed. They are based on the "exact approximation" method, and their expected numbers of consumed uniform deviates are less than 1.04 per sample from the target distributions. The algorithms are simple and easily implemented in any desired precision. They require no space for long tables of auxiliary vectors, merely a few constants are needed. Nevertheless, their speed compares well with the performance of much more complex and table-aided sampling procedures.
and
Research and Advances Oct 1 1988

Calendar queues: a fast 0(1) priority queue implementation for the simulation event set problem

A new priority queue implementation for the future event set problem is described in this article. The new implementation is shown experimentally to be O(1) in queue size for the priority increment distributions recently considered by Jones in his review article. It displays hold times three times shorter than splay trees for a queue size of 10,000 events. The new implementation, called a calendar queue, is a very simple structure of the multiple list variety using a novel solution to the overflow problem.
Research and Advances Oct 1 1988

A subset coloring algorithm and its applications to computer graphics

We consider the following problem: we are given a diagram made up of intersecting circles, where each region is colored either black or white. We wish to display this diagram on a bitmap device, where we are allowed to (i) paint a given circle white and (ii) invert the colors within a given circle, changing white to black and vice versa. (These operations are frequently provided in graphics hardware or software.) We ask: using only these paint and invert operations, is it possible to draw the diagram? A generalization of this problem leads to an analogous coloring problem on a subset of the power set of n elements. We give a polynomial-time algorithm that answers the question above, and produces a "short" sequence of instructions to draw the diagram, if one exists. A simple modification of the algorithm permits us to handle the case where there are more colors than just black and white, and the colors are represented by bit strings. This corresponds to the conventions frequently used with color raster devices.
, , and
Research and Advances Jul 1 1988

HAM: a general purpose hypertext abstract machine

The HAM is a transaction-based server for a hyper text storage system. The server is designed to handle multiple users in a networked environment. The storage system consists of a collection of contexts, nodes, links, and attributes that make up a hypertext graph. The versatility of the HAM can be illustrated by showing how Guide buttons, intermedia webs, and NoteCard FileBoxes can be implemented using its storage model.
, , and
Research and Advances Jul 1 1988

Abstraction mechanisms in hypertext

Abstraction is the means by which information can be stored and retrieved from an information structure at different levels of detail and from different perspectives. As such, abstraction mechanisms in hypertext are interesting to evaluate from a theoretical perspective as they become various first-order logic formulae.
and
Research and Advances Jul 1 1988

Reflections on NoteCards: seven issues for the next generation of hypermedia systems

NoteCards, developed by a team at Xerox PARC, was designed to support the task of transforming a chaotic collection of unrelated thoughts into an integrated, orderly interpretation of ideas and their interconnections. This article presents NoteCards as a foil against which to explore some of the major limitations of the current generation of hypermedia systems, and characterizes the issues that must be addressed in designing the next generation systems.
and
Research and Advances Jun 1 1988

Graphics and managerial decision making: research-based guidelines

Graphical charts are generally thought to be a superior reporting technique compared to more traditional tabular representations in organizational decision making. The experimental literature, however, demonstrates only partial support for this hypothesis. To identify the characteristics of the situations that have been shown to benefit from the use of graphics, existing studies are reviewed in terms of the type of task used, the format employed, and the user experience. The examination of the literature reveals a set of empirically based—though preliminary—guidelines as to when and how to use business graphics.
and
Research and Advances Jun 1 1988

The equivalence of the subregion representation and the wall representation for a certain class of rectangular dissections

A rectangular dissection is a partition of a rectangular space R info n ≱ 1 disjoint rectangles {r1, r2, . . ., rn. Two classes of dissections that are of particular interest in floor-space design and very-large-scale integration (VLSI) space partitioning are called T-plans and T*-plans, where the T*-plans form a subclass of the T-plans. We consider here the subregion tree representation t(D) of a T*-plan D, which describes the successive partitioning operations by which the dissection D is derived. There are four types of partitioning operations in a T*-plan: (1) the horizontal partitioning; (2) the vertical partitioning; (3) the left-spiral partitioning; and (4) the right-spiral partitioning. We show that for a T*-plan the subregion representation and the wall representation are equivalent in the sense that one can be obtained from the other in a unique fashion. The importance of this equivalence property lies in that while the two representations allow different types of design constraints to be represented in a more natural way, these constraints may be converted to the same representation for a more efficient solution of the design problem.
Research and Advances May 1 1988

An experimental evaluation of the impact of data display format on recall performance

Recall, while an important topic in the study of learning and memory, has received relatively little attention as a dependent variable in studies that investigate alternative formats for presenting information. This paper describes two experiments, performed back to back, that examined the relationship between data display format and recall performance across different task categories. The results of Experiment 1 were reaffirmed by Experiment 2 and collectively suggest that a graphical presentation enhances recall when the task possesses a spatial orientation while the recall of specific facts is indifferent to data display format.
and
Research and Advances May 1 1988

On visual formalisms

The higraph, a general kind of diagramming object, forms a visual formalism of topological nature. Higraphs are suited for a wide array of applications to databases, knowledge representation, and, most notably, the behavioral specification of complex concurrent systems using the higraph-based language of statecharts.
Research and Advances Apr 1 1988

Undebuggability and cognitive science

A resource-realistic perspective suggests some indispensable features for a computer program that approximates all human mentality. The mind's program would differ fundamentally more from familiar types of software. These features seem to exclude reasonably establishing that a program correctly and completely models the mind.

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved

Communications of the ACM (CACM) is now a fully Open Access publication.

By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.

Learn More