Artificial Intelligence and Machine Learning
Advertisement
The measurement of user information satisfaction
This paper critically reviews measures of user information satisfaction and selects one for replication and extension. A survey of production managers is used to provide additional support for the instrument, eliminate scales that are psychometrically unsound, and develop a standard short form for use when only an overall assessment of information satisfaction is required and survey time is limited.
A quadtree medial axis transform
As printed
Quadtree skeletons are exact representations of the image and
are used because they are observed to yield space efficiently and a
decreased sensitivity to shifts in contrast with the quadtree. The
QMAT can be used as the underlying representation when solving most
problems that can be solved by using a quadtree. An algorithm is
presented for the computation of the QMAT of a given quadtree by
only examining each BLACK node's adjacent and abutting
neighbors.
Corrected Abstract (published as corrigendum in CACM 27, 2
(February 1984) p. 151)
The skeletal and medial axis transform concepts used in
traditional image processing representations are adapted to the
quadtree representation. The result is the definition of of a new
data structure termed the Quadtree Medial Axis Transform (QMAT). A
QMAT results in a partition of the image into a set of nondisjoint
squares having sides whose lengths are sums of powers of 2 rather
than, as is the case with quadtrees, a set of disjoint squares
having sides of lengths which are powers of 2. The motivation is
not to study skeletons for the usual purpose of obtainings
approximations of the image. Instead, quadtree skeletons are exact
representations of the image and are used because they are observed
to yield space efficiency and a decreased sensitvity to shifts in
contrast with the quadtree. The QMAT can be used as the underlying
representation when solving most problems that can be solved by
using a quadtree. An algorithm is presented for the computation of
the QMAT of a given quadtree by only examining each BLACK node's
adjacent and abutting neighbors. Analysis of the algorithm reveals
an average execution time proportional to the complexity of the
image, i.e., the number of BLACK blocks.
The fifth generation project — a trip report
As part of Japan's effort to become a leader in the computer industry, the Institute for New Generation Computer Technology has launched a revolutionary ten-year plan for the development of large computer systems which will be applicable to knowledge information processing systems. These Fifth Generation computers will be built around the concepts of logic programming. In order to refute the accusation that Japan exploits knowledge from abroad without contributing any of its own, this project will stimulate original research and will make its results available to the international research community.
A correction to Brelaz’s modification of Brown’s coloring algorithm
Brelaz's modification of Brown's exact coloring algorithm contains two errors as demonstrated in two examples. A correct version of the algorithm and a proof of the exactness are given. Finally, Brown's look-ahead rule is built into this algorithm.
Precision averaging for real-time analysis
An analysis of the computation of the arithmetic mean using only single-precision fixed-point arithmetic is presented. This is done to ease the timing constraints common to many on-line applications. Others have introduced several averaging algorithms in floating-point arithmetic for use in inferential statistics. In this paper, these algorithms are evaluated with respect to their feasibility as fixed-point methods in the context of real-time analysis. Modifications of these algorithms are presented, and previously unpublished ones are introduced in the interest of avoiding overflow (necessary) and minimizing truncation errors (highly desirable). All algorithms presented are tested for speed and accuracy on several sets of data, including their own “worst case.” The applicability of each algorithm is discussed with respect to some of the basic functions that real-time programs must perform.
Natural command names and initial learning: a study of text-editing terms
In the first of two studies of “naturalness” in command names, computer-naive typists composed instructions to “someone else” for correcting a sample text. There was great variety in their task-descriptive lexicon and a lack of correspondence between both their vocabulary and their underlying conceptions of the editing operations and those of some computerized text editors. In the second study, computer-naive typists spent two hours learning minimal text-editing systems that varied in several ways. Lexical naturalness (frequency of use in Study 1) made little difference in their performance. By contrast, having different, rather than the same names for operations requiring different syntax greatly reduced difficulty. It is concluded that the design of user-compatible commands involves deeper issues than are captured by the slogan “naturalness.” However, there are limitations to our observations. Only initial learning of a small set of commands was at issue and generalizations to other situations will require further testing.
A hierarchical data structure for multidimensional digital images
A tree data structure for representing multidimensional digital binary images is described. The method is based on recursive subdivision of the d-dimensional space into 2d hyperoctants. An algorithm for constructing the tree of a d-dimensional binary image from the trees of its (d - 1 )-dimensional cross sections is given. The computational advantages of the data structure and the algorithm are demonstrated both theoretically and in application to a three-dimensional reconstruction of a human brain.
Pracniques: coordinated text and tranperiences
An economical method of producing both hard copy and projection forms of text, without duplication of effort.
A real-time garbage collector based on the lifetimes of objects
In previous heap storage systems, the cost of creating objects and garbage collection is independent of the lifetime of the object. Since objects with short lifetimes account for a large portion of storage use, it is worth optimizing a garbage collector to reclaim storage for these objects more quickly. The garbage collector should spend proportionately less effort reclaiming objects with longer lifetimes. We present a garbage collection algorithm that (1) makes storage for short-lived objects cheaper than storage for long-lived objects, (2) that operates in real time—object creation and access times are bounded, (3) increases locality of reference, for better virtual memory performance, (4) works well with multiple processors and a large address space.
DOCUMENTS: an interactive online solution to four documentation problems
An adequate delivery system for user documentation addresses the problems of easy access, versatile publication, convenient administration, and good document quality. At the National Magnetic Fusion Energy Computer Center the DOCUMENT program helps solve these problems by providing a high level of service through strategies that can readily be exported to other contexts. Dividing machine-readable documents into keyword windows permits fully online, subject-oriented access to all passages. An adaptive, three-tier user interface extends flexible viewing control to novices and experts alike. DOCUMENT also supports online subject, title, and date catalogs, and provides on-demand output of hardcopy and microfiche. Several other document delivery systems are compared with DOCUMENT, and all have more rigid human interfaces, more structural display units for text, or more cumbersome output options.
Composing letters with a simulated listening typewriter
With a listening typewriter, what an author says would be automatically recognized and displayed in front of him or her. However, speech recognition is not yet advanced enough to provide people with a reliable listening typewriter. An aim of our experiments was to determine if an imperfect listening typewriter would be useful for composing letters. Participants dictated letters, either in isolated words or in consecutive word speech. They did this with simulations of listening typewriters that recognized either a limited vocabulary (1000 or 5000 words)or an unlimited vocabulary. Results suggest that some versions, even upon first using them, could be at least as good as traditional methods of handwriting and dictating. Isolated word speech with large vocabularies may provide the basis for a useful listening typewriter.
Design rules based on analyses of human error
By analyzing the classes of errors that people make with systems, it is possible to develop principles of system design that minimize both the occurrence of error and the effects. This paper demonstrates some of these principles through the analysis of one class of errors: slips of action. Slips are defined to be situations in which the user's intention was proper, but the results did not conform to that intention. Many properties of existing systems are conducive to slips; from the classification of these errors, some procedures to minimize the occurrence of slips are developed.
The evaluation of text editors: methodology and empirical results.
This paper presents a methodology for evaluating text editors on several dimensions: the time it takes experts to perform basic editing tasks, the time experts spend making and correcting errors, the rate at which novices learn to perform basic editing tasks, and the functionality of editors over more complex tasks. Time, errors, and learning are measured experimentally; functionality is measured analytically; time is also calculated analytically. The methodology has thus far been used to evaluate nine diverse text editors, producing an initial database of performance results. The database is used to tell us not only about the editors but also about the users—the magnitude of individual differences and the factors affecting novice learning.
Speeding up an overrelaxation method of division in Radix-2n machine
For normalized floating point division, digital computers can take advantage of a division process that uses an iterative multiplying operation instead of repeated subtractions. An improvement of this division process by using accelerating constants in the overrelaxation has previously been proposed. Multiplication by a chosen accelerating constant accelerates the process of generating accurate digits of a quotient in division. We propose a further improvement by generalizing the accelerating constants in the overrelaxation method. Two benefits resulting from this improvement promise to yield faster division in digital computers.
A tree convolution algorithm for the solution of queueing networks
A new algorithm called the tree convolution algorithm, for the computation of normalization constants and performance measures of product-form queueing networks, is presented. Compared to existing algorithms, the algorithm is very efficient in the solution of networks with many service centers and many sparse routing chains. (A network is said to have sparse routing chains if the chains visit, on the average, only a small fraction of all centers in the network.) In such a network, substantial time and space savings can be achieved by exploiting the network's routing information. The time and space reductions are made possible by two features of the algorithm: (1) the sequence of array convolutions to compute a normalization constant is determined according to the traversal of a tree; (2) the convolutions are performed between arrays that are smaller than arrays used by existing algorithms. The routing information of a given network is used to configure the tree to reduce the algorithm's time and space requirements; some effective heuristics for optimization are described. An exact solution of a communication network model with 64 queues and 32 routing chains is illustrated.
On the modeling of parallel access to shared data
A model is constructed of a database that can be accessed and modified concurrently by a number of users, and an approximate solution is presented. The resource allocation policies considered involve dynamic acquisition of entities and locking; deadlock is avoided by limiting the number of consecutive attempts to acquire a particular entity. The accuracy of the approximation is evaluated by simulations. Several generalizations aimed at improving the practicality of the model are described.
The computational metaphor and quantum physics
Concurrent computational systems, viewed as sets of cooperating processes, are shown to have close analogies in the world of quantum physics. In particular, analogies exist between processes and particles, between a process' state and a particle's mass, between a process'state changes and a particle's velocity, and between interprocess communications and particle interactions. This view allows the application in the computational world of special relativity theory, the uncertainty principle, the law of conservation of momentum, and many of particle physics' fundamental results. This paper describes the basic analogy and some fundamental results. It is the authors' belief that new insights into a computational processes will be gained as the analogy is developed and vice versa. It is conceivable that established results of the computational sciences may contribute to a new understanding of some of the problems of physics. Other process-oriented sciences, such as biology, economics, and psychology, could also benefit from such development.
An effective way to represent quadtrees
A quadtree may be represented without pointers by encoding each black node with a quaternary integer whose digits reflect successive quadrant subdivisions. We refer to the sorted array of black nodes as the “linear quadtree” and show that it introduces a saving of at least 66 percent of the computer storage required by regular quadtrees. Some algorithms using linear quadtrees are presented, namely, (i) encoding a pixel from a 2n × 2>n array (or screen) into its quaternary code; (ii) finding adjacent nodes; (iii) determining the color of a node; (iv) superposing two images. It is shown that algorithms (i)-(iii) can be executed in logarithmic time, while superposition can be carried out in linear time with respect to the total number of black nodes. The paper also shows that the dynamic capability of a quadtree can be effectively simulated.
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 InvolvedCommunications 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