July 1984 - Vol. 27 No. 7

July 1984 issue cover image

Features

Research and Advances

The TWA reservation system

Where can you find a solid, forthright overview of the computer systems and management behind airline reservations? NASA's space shuttle? Or any of the multitude of other large computer systems that support important projects or national activities? It's hard, sometimes impossible: partly because the people who worked on such systems often do not have the time to write about their experiences: and partly because many professional journalists who interview these people do not have the technical background to ferret out answers to the fundamental design questions addressed in these systems.
Research and Advances

Audit trail compaction for database recovery

Total elapsed recovery time from disk-based database corruption can be shortened by reprocessing the audit trail off-line and thereby avoiding excessive resource utilization penalties. Using a bit map, the audit trail is compacted by eliminating irrelevant or superseded records. The compacted trail is then partitioned, and the partitions are processed in parallel.
Research and Advances

A null-object detection algorithm for constructive solid geometry

Constructive solid geometry (CSG) is the primary scheme used for representing solid objects in many contemporary solid modeling systems. A CSG representation is a binary tree whose nonterminal nodes represent Boolean operations and whose terminal nodes represent primitive solids. This paper deals with algorithms that operate directly on CSG representations to solve two computationally difficult geometric problems—null-object detection (NOD) and same-object detection (SOD). The paper also shows that CSG trees representing null objects may be reduced to null trees through the use of a new concept called primitive redundancy, and that, on average, tree reduction can be done efficiently by a new technique called spatial localization. Primitive redundancy and spatial localization enable a single complex instance of NOD to be converted into a number of simpler subproblems and lead to more efficient algorithms than those previously known.
Research and Advances

Efficient algorithms to globally balance a binary search tree

A binary search tree can be globally balanced by readjustment of pointers or with a sorting process in O(n) time, n being the total number of nodes. This paper presents three global balancing algorithms, one of which uses folding with the other two adopting parallel procedures. These algorithms show improvement in time efficiency over some sequential algorithms [1, 2, 7] when applied to large binary search trees. A comparison of various algorithms is presented.
Research and Advances

Faster methods for random sampling

Several new methods are presented for selecting n records at random without replacement from a file containing N records. Each algorithm selects the records for the sample in a sequential manner—in the same order the records appear in the file. The algorithms are online in that the records for the sample are selected iteratively with no preprocessing. The algorithms require a constant amount of space and are short and easy to implement. The main result of this paper is the design and analysis of Algorithm D, which does the sampling in O(n) time, on the average; roughly n uniform random variates are generated, and approximately n exponentiation operations (of the form ab, for real numbers a and b) are performed during the sampling. This solves an open problem in the literature. CPU timings on a large mainframe computer indicate that Algorithm D is significantly faster than the sampling algorithms in use today.

Recent Issues

  1. October 2024 CACM cover
    October 2024 Vol. 67 No. 10
  2. September 2024 CACM cover
    September 2024 Vol. 67 No. 9
  3. August 2024 CACM cover
    August 2024 Vol. 67 No. 8
  4. July 2024 CACM cover
    July 2024 Vol. 67 No. 7