September 1982 - Vol. 25 No. 9
Features
Designing a Bloom filter for differential file access
The use of a differential file for a database update can yield integrity and performance benefits, but it can also present problems in providing current data to subsequent accessing transactions. A mechanism known as a Bloom filter can solve these problems by preventing most unnecessary searches of the differential file. Here, the design process for a Bloom filter for an on-line student database is described, and it is shown that a very effective filter can be constructed with a modest expenditure of system resources.
File archival techniques using data compression
The performance of most small computer systems is determined, to a large extent, by the characteristics of their mass storage devices. Data compression can expand the storage capacity of such devices and also slightly increase their speed. Here, a summary of one method of data compression using Huffman variable length coding is presented, along with statistics of effectiveness for various file types and practical techniques for integrating such methods into a small computer system.
Designing computer system messages
tive computer systems and studies of their users, we have become increasingly aware of the importance of system messages. Novice users are unimpressed with CPU speeds, disk storage capabilities, or elegant file structures. For them, the system appears only in the form of the messages on their screens or printers. So when novices encounter violent messages such as “FATAL ERROR, RUN ABORTED”, vague phases like “ILLEGAL CMD”, or obscure codes such as “OC7” or “IEH2191”, they are understandably shaken, confused, dismayed, and discouraged from continuing. The negative image that computer systems sometimes generate is, we believe, largely due to the difficulties users experience when they make mistakes or are unsure about what to do next.
U.S. computer export control policies: value conflicts and policy choices
The formulation of a balanced and effective export control policy for computer products and know-how has been an important and difficult task for both the U.S. Government and the computing community. External pressures force national security concerns to conflict with the values and interests of private enterprise and academic freedom. This paper has two primary objectives: the first is to present the computing community with a reasonably equitable and detailed perspective on this important public policy problem; the second is to present and analyze a range of policy choices.
This paper describes the design and implementation of a program testing assistant which aids a programmer in the definition, execution, and modification of test cases during incremental program development. The testing assistant helps in the interactive definition of test cases and executes them automatically when appropriate. It modifies test cases to preserve their usefulness when the program they test undergoes certain types of design changes. The testing assistant acts as a fully integrated part of the programming environment and cooperates with existing programming tools such as a display editor, compiler, interpreter, and debugger.
The volume, moments of inertia, and similar properties of solids are defined by triple (volumetric) integrals over subsets of three-dimensional Euclidean space. The automatic computation of such integral properties for geometrically complex solids is important in CAD/CAM, robotics, and other fields and raises interesting mathematical and computational problems that have received little attention from numerical analysts and computer scientists. This paper summarizes the known methods for calculating integral properties of solids that may be geometrically complex and identifies some significant gaps in our current knowledge.
This paper discusses a family of algorithms for computing the volume, moments of inertia, and other integral properties of geometrically complex solids, e.g. typical mechanical parts. The algorithms produce approximate decompositions of solids into cuboid cells whose integral properties are easy to compute.
The paper focuses on versions of the algorithms which operate on solids represented by Constructive Solid Geometry (CSG), i.e., as set-theoretical combinations of primitive solid “building blocks.” Two known algorithms are summarized and a new algorithm is presented. The efficiencies and accuracies of the three algorithms are analyzed theoretically and compared experimentally.
The new algorithm uses recursive subdivision to convert CSG representations of complex solids into approximate cellular decompositions based on variably sized blocks. Experimental data show that the new algorithm is efficient and has predictable accuracy. It also has other potential applications, e.g., in producing approximate octree representations of complex solids and in robot navigation.
Letters to the editor: A protection model and its implementation in a dataflow system
A protection model is presented for a general purpose computing system based on tags attached as seals and signatures to values exchanged among processes. A tag attached to a value as a seal does not prevent that value from being propagated to any place within the system; rather, it guarantees that the value and any information derived from it cannot leave the system unless a matching tag is presented. A tag attached to a value as a signature is used by a process to verify the origin of the received data. Solutions to problems from the areas of interprocess communication and proprietary services are given.
Efficient parallel algorithms for some graph problems
We study parallel algorithms for a number of graph problems, using the Single Instruction Stream-Multiple Data Stream model. We assume that the processors have access to a common memory and that no memory or data alignment time penalties are incurred. We derive a general time bound for a parallel algorithm that uses K processors for finding the connected components of an undirected graph. In particular, an O(log2 n) time bound can be achieved using only K = n⌈n/log2 n⌉ processors. This result is optimal in the sense that the speedup ratio is linear with the number of processors used. The algorithm can also be modified to solve a whole class of graph problems with the same time bound and fewer processors than previous parallel methods.
