Search
Join ACM

Artificial Intelligence and Machine Learning

Advertisement

Research and Advances

Reduced instruction set computers

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.
Research and Advances

The cosmic cube

Sixty-four small computers are connected by a network of point-to-point communication channels in the plan of a binary 6-cube. This “Cosmic Cube” computer is a hardware simulation of a future VLSI implementation that will consist of single-chip nodes. The machine offers high degrees of concurrency in applications and suggests that future machines with thousands of nodes are both feasible and attractive.
Research and Advances

The weighted median filter

The median filter is well-known [1, 2]. However, if a user wishes to predefine a set of feature types to remove or retain, the median filter does not necessarily satisfy the requirements. A more general filter, called the Weighted Median Filter, of which the median filter is a special case, is described. It enables filters to be designed with a wide variety of properties. Particular cases of filter requirements are discussed and the corresponding filters are derived. The notion of a minimal weighted median filter, of a subclass that act identically, is introduced and discussed. The question of finding the number of distinct ways a class of filters can act is considered and solved for some classes.
Opinion

From Washington

We are entering a new era in very high performance computing that will be dominated by parallel architectured systems. It is critical for the United States to maintain its leadership as this new era, with its broadened applications, evolves over the next decade. Toward this end the National Science Foundation sponsored a workshop in November 1983 to focus the collective strength of universities, industry, and government on projects for development of knowledge-intensive industries.
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

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.
and
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.
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.
and
Research and Advances

Talking to UNIX in English: an overview of UC

UC is a natural language help facility which advises users in using the UNIX operating system. Users can query UC about how to do things, command names and formats, online definitions of UNIX or general operating systems terminology, and debugging problems in using commands. UC is comprised of the following components: a language analyzer and generator, a context and memory model, an experimental common-sense planner, highly extensible knowledge bases on both the UNIX domain and the English language, a goal analysis component, and a system for acquisition of new knowledge through instruction in English. The language interface of UC is based on a “phrasal analysis” approach which integrates semantic, grammatical and other types of information. In addition, it includes capabilities for ellipsis resolution and reference disambiguation.
, , and
Opinion

Programming pearls: graphic output

In previous columns we've studied the innards of programs. In this column we'll take a broader view of the programmer's task and consider the kind of output a program should produce. We'll focus on a single problem: once a system has produced detailed output, how can it summarize the trends in the mountain of data? The answer to that question depends heavily on both the data and the taste of the reader; paragraphs of text and tables of numbers often provide fine summaries. This column, however, will concetrate on graphical representations of data, which allow the powerful human vision system to understand data. A decade ago programmers could offer the excuse that they were limited to crude line printer graphics, but technology has changed that. Many large installations now have laser printers, and graphics printers for home computers sell for a few hundred dollars. This column is about ways that programmers can use the technology to deliver more useful (and more graphic) output.
Research and Advances

Anomalies in parallel branch-and-bound algorithms

We consider the effects of parallelizing branch-and-bound algorithms by expanding several live nodes simultaneously. It is shown that it is quite possible for a parallel branch-and-bound algorithm using n2 processors to take more time than one using n1 processors, even though n1 < n2. Furthermore, it is also possible to achieve speed-ups that are in excess of the ratio n2/n1. Experimental results with the 0/1-Knapsack and Traveling Salesman problems are also presented.
and
Research and Advances

Computer matching: should it be banned?

Since discovering the technique of computer matching several years ago, government managers have been invoking this computer tool in the attempt to root out waste and fraud in their programs. Is computer matching an indispensable tool for government administrators? Or a trampling on individual rights? In the following articles, two experts debate the pros and cons.

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