Sign In

Communications of the ACM

3,291 - 3,300 of 3,299 for bentley

Partial-match queries and file designs

Tnis paper is concernd with information retrieval based upon secondary keys; that is, keys which cannot in general uniquely identify a record, but can indicate certain attributes of the associated record. Partial-match retrieval deals with accessing and reading those records of a data base which match the user's query albeit the query is only partially specified. For example, suppose that 'the data base consists of the binary words 1010, 1110, 0011, 1101, 0010, 1111. The response to query 1**0 where * is a don't know symbol is the set of records with keys 1010 or 1110 while the response to query 1101 is the set of records with key 1101.


The digital simulation of river plankton population dynamics

This paper deals with the development of a mathematical model for and the digital simulation in Fortran IV of phytoplankton and zooplankton population densities in a river using previously developed rate expressions. In order to study the relationships between the ecological mechanisms involved, the simulation parameters were varied illustrating the response of the ecosystem to different conditions, including those corresponding to certain types of chemical and thermal pollution. As an investigation of the accuracy of the simulation methods, a simulation of the actual population dynamics of Asterionella in the Columbia River was made based on approximations of conditions in that river. Although not totally accurate, the simulation was found to predict the general annual pattern of plankton growth fairly well and, specifically, revealed the importance of the annual velocity cycle in determining such patterns. In addition, the study demonstrates the usefulness of digital simulations in the examinations of certain aquatic ecosystems, as well as in environmental planning involving such examinations.


Multidimensional binary search trees used for associative searching

This paper develops the multidimensional binary search tree (or k-d tree, where k is the dimensionality of the search space) as a data structure for storage of information to be retrieved by associative searches. The k-d tree is defined and examples are given. It is shown to be quite efficient in its storage requirements. A significant advantage of this structure is that a single data structure can handle many types of queries very efficiently. Various utility algorithms are developed; their proven average running times in an n record file are: insertion, O(log n); deletion of the root, O(n(k-1)/k); deletion of a random node, O(log n); and optimization (guarantees logarithmic performance of searches), O(n log n). Search algorithms are given for partial match queries with t keys specified [proven maximum running time of O(n(k-t)/k)] and for nearest neighbor queries [empirically observed average running time of O(log n).] These performances far surpass the best currently known algorithms for these tasks. An algorithm is presented to handle any general intersection query. The main focus of this paper is theoretical. It is felt, however, that k-d trees could be quite useful in many applications, and examples of potential uses are given.


Alternating semantic evaluator

In order to make the use of attribute grammars practical in (automatic) compiler generation, restricted attribute grammars are introduced. A membership test is given which determines whether a given attribute grammar satisfies the required restrictions. The major advantage of the restricted attribute grammars is that they are non-circular. The given membership test can be embedded in a compiler writing system which accepts an attribute grammar as input and outputs a compiler for the associated language provided the grammar meets the restrictions. The technique is also applicable to translation grammars of [15]. It is assumed that the reader is familiar with context free grammars but not necessarily with attribute grammars.


Design of an aerospace computer for direct HOL execution

This paper presents an overview of a study, performed during 1971 and 1972, to design a computer architecture capable of executing a higher-order aerospace programming language directly—without the aid of a compiler or interpreter. The prime motivation for developing such a machine is to reduce system costs, for while hardware logic is becoming much cheaper, software is consuming a greater proportion of total system costs. A tremendous potential savings can be obtained by designing computer hardware that is oriented to aiding the programmer rather than to simplifying the computer designer's job. In this three-phase study, the first phase, preliminary to the actual design, analyzed direct execution tradeoffs for a number of languages. The languages examined were FORTRAN, ALGOL, PL/I, APL, JOVIAL, and SPL. In the second phase, the functional design was produced for a direct-execution system for a subset of Space Programming Language (SPL)/Mark IV. In the third phase, the performance of that system was evaluated by comparing it to a conventional architecture. The study successfully demonstrated that a higher-order aerospace language computer is feasible and efficient.


PL/I in the computer science curriculum

Two questions perpetually arising within Computer Science Departments are (1) whether or not the programming languages stressed in the academic programs are appropriate and (2) whether the correct emphasis is being placed on one language as opposed to another. In particular, one always wonders if any emerging and promising language is receiving enough attention. Attempts at answering such questions seem to provide quite suitable vehicles for student involvement in curriculum development and so recently at New Mexico State University a combined faculty-graduate student study was made for one important appropriate language, PL/I.