Search

Using direct access computer files of bibliographic information, an attempt is made to overcome one of the problems often associated with information retrieval, namely, the maintenance and use of large dictionaries, the greater part of which is used only infrequently. A novel method is presented, which maps the hyperbolic frequency distribution of text characteristics onto a rectangular distribution. This is more suited to implementation on storage devices. This method treats text as a string of characters rather than words bounded by spaces, and chooses subsets of strings such that their frequencies of occurrence are more even than those of word types. The members of this subset are then used as index keys for retrieval. The rectangular distribution of key frequencies results in a much simplified file organization and promises considerable cost advantages. [ABSTRACT FROM AUTHOR]

The high cost of page accessing implies a need for for more careful data organization in a paged memory than is typical of most inverted file and similar approaches to multi-key retrieval. This article analyses that cost and proposes a method called multiple key hashing which attempts to minimize it, Since this approach is not always preferable to inversion, a combined method is described. The exact specifications of this combination for a file with given data and traffic characteristics is formulated as a mathematical program. The proposed heuristic solution to this program can often improve on a simple inversion technique by a factor of 2 or 3. [ABSTRACT FROM AUTHOR]

A data definition language is a declarative computer language for specifying data structures. Most data definition languages concentrate on the declaration of logical data structures with little concern for how these structures are physically realized on a computer system. However, the need for data definition languages which describe both the logical and physical aspects of data is increasingly apparent. Such languages will be a key element in the translation of data between computer systems, as well as in advanced data management systems and distributed data bases. This paper reviews past work in the data definition language for describing both logical and physical aspects of data. Applications of these "generalized" data definition languages are also discussed. [ABSTRACT FROM AUTHOR]

Presents a model and a programmed system to estimate total storage costs and average access time of various file organizations, given a specific database, query characterization and device-related specifications. Factors that affect the performance of file organization; Importance of proper file structure and evaluation.

When the space allocation for a hash-coded table is altered, the table entries must be rescattered over the new space. A technique for accomplishing this rescattering is presented. The technique is independent of both the length of the table and the hashing function used, and can he utilized in conjunction with a linear reallocation of the table being rescattered. Moreover, it can be used to eliminate previously flagged deletions from any hash-coded table, or to change from one hashing method to another. The efficiency of the technique is discussed and theoretical statistics are given. [ABSTRACT FROM AUTHOR]

The paper describes a scheme for symbolic manipulation of index expressions which arise as a by-product of the symbolic manipulation of expressions in the matrix calculi described by the authors in a previous paper. This scheme attempts program optimization by transforming the original algorithm rather than the machine code. The goal is to automatically generate code for handling the tedious address calculations necessitated by complicated data structures. The paper is therefore preoccupied with "indexing by position." The relationship of "indexing by name" and "indexing by position" is discussed. [ABSTRACT FROM AUTHOR]

The consecutive retrieval property is an important relation between a query set and record set. Its existence enables the design of an information retrieval system with a minimal search time and no redundant storage. Some important theorems on the consecutive retrieval property are proved in this paper. Conditions under which the consecutive retrieval property exists and remain invariant have been established. An outline for designing an information retrieval system based on the consecutive retrieval property is also discussed. [ABSTRACT FROM AUTHOR]

List processing systems should be designed to facilitate production of large programs to manipulate large complex symbolic data stores. This paper presents an overview of a number of system features which the author feels are important to improve the productivity of programmers working in such domains. A systems view is taken, rather than focusing just on language features, since algorithms must be not only coded in a language form, but debugged, modified, made efficient, and run on data Because of this general framework, the requirements specified are applicable to the design of advanced programming systems for a wide range of applications Three aspects of programming systems are highlighted good interactive facilities, programmable control structures, and sophisticated data communication mechanisms Interactive features are described to facilitate program composition, entry, testing, debugging, editing, optimization, and packaging. Implementation of a generalized environment structure model specified would allow programming of various control regimes including multi processes, coroutines and backtracking. Alternative methods of procedure invocation required include invocation by pattern and by monitoring condition. The need for extended data forms, storage management, and extensibility are stressed, as is the duality of data retrieval and function evaluation. Syntax directed input and output of data would facilitate use of complex data stores. [ABSTRACT FROM AUTHOR]

Data base management systems have grown rapidly in their power and complexity over the 15-year history of data processing on commercially available computers. The original concepts have split, and new terms have been adopted to name and refer to these concepts. The Data Structure Diagram graphic technique is used to illustrate the splitting of the concepts and the structural relations which exist between these concepts at each point in the evolution. [ABSTRACT FROM AUTHOR]

The Index Sequential Access Method (ISAM) is one of the most important file management systems used with moveable head disk devices. This study investigates the use of an unconventional method of treating overflow records. The method is to use hashing techniques to allocate space for such records. If certain conditions are satisfied, this is superior to the conventional ISAM method of chaining the overflow records via linked list techniques. These conditions are: long overflow chains with significant overflow; lack of tight disk space constraints; record keys which are small compared to the total record size; and significant use of the file in the index as opposed to the sequential mode. Using hashed overflow, the time to locate a record is dependent not on the total volume of overflow records as in conventional ISAM, but on the percentage use of space dedicated to overflow records. [ABSTRACT FROM AUTHOR]

Proposes a new file structure for attribute based retrieval. Functions of the structure that allows queries involving arbitrary Boolean functions of the attribute-value pairs; Strategies for processing without taking intersections of lists.

The utilization of storage is studied in a two-level memory hierarchy. The first storage level, which is the fast store, is divided into a number of storage areas. When an entry is to be filed in the hierarchy, a hashing algorithm will attempt to place the entry into one of these areas. If this particular area is full, then the entry will be placed into the slower second-level store, even though other areas in the first-level store may have space available. Given that N entries have been filed in the entire hierarchy, an expression is derived for the expected number of entries filed in the first-level store. This expression gives a measure of how effectively the first-level store is being used. By means of examples, storage utilization is then studied as a function of the hashing algorithm, the number of storage areas into which the first-level store is divided and the total size of the first-level store. [ABSTRACT FROM AUTHOR]

Describes a file organizing scheme designed to replace the use of the popular secondary index filing scheme. Retrieval of keys satisfying any input query derived from a subset of fields by a single access to an index file; Advantages of the method over conventional index filing.

In this paper trade-offs among certain computational factors in hash coding are analyzed. The paradigm problem considered is that of testing a series of messages one-by-one for membership in a given set of messages. Two new hash-coding methods are examined and compared with a particular conventional hash-coding method. The computational factors considered are the size of the hash area (space), the time required to identify a message as a nonmember of the given set (reject time), and an allowable error frequency. The new methods are intended to reduce the amount of space required to contain the hash-coded information from that associated with conventional methods. The reduction in space is accomplished by exploiting the possibility that a small fraction of errors of commission may be tolerable in some applications, in particular, applications in which a large amount of data is involved and a core resident hash area is consequently not feasible using conventional methods. in such applications, it is envisaged that overall performance could be improved by using a smaller core resident hash area in conjunction with the new methods and, when necessary, by using some secondary and perhaps time-consuming test to "catch" the small fraction of errors associated with the new methods. An example is discussed which illustrates possible areas of application for the new methods. Analysis of the paradigm problem demonstrates that allowing a small number of test messages to be falsely identified as members of the given set will permit a much smaller hash area to be used without increasing reject time. [ABSTRACT FROM AUTHOR]

A practical PL/1 program is described which can assist comparative linguists to determine the regular sound correspondences between genetically related languages. The investigator must arrange data for input by aligning pairs of suspected cognates. The program tabulates the correspondences, and uses list processing techniques to sort and count them. Each pair of words is then assigned a relative value that is a function of the total frequency in the data of each correspondence found in that pair of words. The output is a list of all correspondence types with their frequency of occurrence in the data, and a separate listing of each correspondence with all words pairs showing that correspondence (unless their relative value is below an arbitrarily chosen cutoff point). The article explains the usefulness, as well as the limitations, of the program, and illustrates its use with a small portion of hypothetical data. [ABSTRACT FROM AUTHOR]

GEDAN KEN is an experimental programming language with the following characteristics. (1) Any value which is permitted in some context of the language is permissible in any other meaningful context. In particular, functions and labels are permissible results of functions and values of variables. (2) Assignment and indirect addressing are formalized by introducing values, called references, which in turn possess other values. The assignment operation always affects the relation between some reference and its value. (3) All compound data structures are treated as functions. (4) Type declarations are not permitted. The functional approach to data structures and the use of references insure that any process which accepts some data structure will accept any logically equivalent structure, regards less of its internal representation. More generally, any data structure may be implicit; i.e. it may be specified by giving an arbitrary algorithm for computing or accessing its components. The existence of label variables permits the construction of co-routines, quasi-parallel processes, and other unorthodox control mechanisms. A variety of programming examples illustrates the generality of the language. Limitations and possible extensions are discussed briefly. [ABSTRACT FROM AUTHOR]

A generalized file structure is provided by which the concepts of keyword, index, record, file, directory, file structure, directory decoding, and record retrieval are defined and from which some of the frequently used file structures such as inverted files, index-sequential files, and multilist files are derived. Two algorithms which retrieve records from the generalized file structure are presented. [ABSTRACT FROM AUTHOR]

A syntactic parser is described for hierarchical concatenation patterns that are presented to the analyzer in the form of linear strings. Particular emphasis is given to the system of "significant addresses" by means of which processing times for large-wale matching procedures can be substantially reduced. The description makes frequent use of examples taken from the fully operational implementation of the parser in an experimental English sentence analyzer. By structuring an area of the computer's central core storage in such a way that the individual locations of bytes and bits come to represent the data involved in the matching procedure, the shifting of information is reduced to a minimum, and the searching of lists is eliminated altogether. The matches are traced by means of binary masks and the state of single bits determines the operational flow of the procedure. The method could be implemented with any interpretive grammar, provided it can be expressed by the functional classification of the items composing the input hierarchical structures. [ABSTRACT FROM AUTHOR]

ASP is a general purpose Associative Data Structure Package in which an arbitrary number of data items and an arbitrary number of the relationships between these data items may be represented. A special picture language is described which has proved very useful for drawing ASP structures on paper. ASP structures are built and manipulated by means of a series of macro coils, which are outlined in the Appendix. Emphasis is on the philosophy of the system rather than a particular implementation, though sufficient information is included to enable the reader to produce his own implementation of ASP. [ABSTRACT FROM AUTHOR]

Reduction in the size of decision tables can be accomplished by several techniques. The techniques considered in this paper are on the parsing of decision tables with regard to horizontal and vertical data structures, job identity, hardware and job priorities, and context relationships. Such parsing rests upon some conventions for the linkage of decision tables. [ABSTRACT FROM AUTHOR]

A method for returning registers to the free list is an essential part of any list processing system. In this paper, past solutions of the recovery problem are reviewed and compared. A new algorithm is presented which offers significant advantages of speed and storage utilization. The routine for implementing this algorithm can be written in the list language with which it is to be used, thus insuring a degree of machine independence. Finally, the application of the algorithm to a number of different list structures appearing in the literature is indicated. [ABSTRACT FROM AUTHOR]

The internal organization of string processing systems is discussed. Six techniques for data structures are presented and evaluated on the basis of; (1) creation of strings; (2) examination of strings; and (3) alteration of strings. Speed of operation, storage requirements, effect on paging, and programmer convenience are also considered. One of the techniques, single-word linked blocks, is used in an example demonstrating an implementation of a SNOBOL string processing language on an IBM System 360. [ABSTRACT FROM AUTHOR]

A mapping from block diagrams of digital circuits to list structures is described, together with a list processing program written for the Control Data 3600 which uses this mopping to automatically carry out circuit analysis. [ABSTRACT FROM AUTHOR]

Some basic facts about certain data structures are reviewed and an efficient algorithm is presented for constructing storage mapping function for n structure from the structure's definition. [ABSTRACT FROM AUTHOR]

Automatic information retrieval programs require the manipulation of a variety of different data structures, including linear text, sparse matrices, and tree or list structures. The main data manipulations to be performed in automatic information systems are first briefly reviewed. A variety of data representations which have been used to describe structured information are then examined, and the characteristics of various processing languages are outlined in the light of the procedures requiring implementation. Advantages and disadvantages of these programming languages for the retrieval application are examined, and suggestions are made for the design of programming facilities to aid in information retrieval. [ABSTRACT FROM AUTHOR]

An experimental system that uses LISP to make a conceptual dictionary is described. The dictionary associates with each English word the syntactic information, definitional material, and references to the contexts in which it has been used to define other words. Such relations as class inclusion, possession, and active or passive actions are used as definitional material. The resulting structure serves as a powerful vehicle for research on the logic of question answering. Examples of methods of inputting information and answering simple English questions are given. An important conclusion is that, although LISP and other list processing languages ore ideally suited for producing complex associative structures, they are inadequate vehicles for language processing on any large scale—at least until they can use auxiliary memory as continuous extension of core memory. [ABSTRACT FROM AUTHOR]

A technique is described for implementing the test which determines if one string is a substring of another. When there is tow probability that the test will be satisfied, it is shown how the operation can be speeded up considerably if it is preceded by a test on appropriately chosen hash codes of the strings. [ABSTRACT FROM AUTHOR]

A quadratic residue search method has previously been suggested to avoid the clustering usually encountered when hash address collisions occur and linear search methods are used. The search size, because of the property of quadratic residues, is limited to one half of the storage table. It is shown that for some classes of prime numbers the complement of the set of quadratic residues can easily be determined and hence the entire table of size p, where p is that prime number, can be searched. [ABSTRACT FROM AUTHOR]

Secondary clustering as a cause of hash code inefficiency is discussed, and a new hashing method based on its elimination is presented. Comparisons with previous methods are made both analytically and empirically. [ABSTRACT FROM AUTHOR]

The article discusses when to chain overflow items within a direct-access table. For this, it is assumed that a certain number of entries have been made in a chained hash table. This same number of entries will require less space in an open table, the amount of storage saved being the amount of storage that was used for linking entries.

The article focuses on key-to-address transformation techniques and the results of a performance study on large existing formatted files. The experimental results comparing six commonly used key-to-address transformation techniques were presented by the researchers. One transformation in the study referred to as "generalized radix transformation method" is an elaborate technique based on radix transformation. This method of transformation consists of a radix transformation algorithm as well as hardware implementation to carry out the steps of this transformation in an efficient manner. The intricacy of the generalized radix transformation method has motivated researchers to conduct further studies of the technique. The additional results are presented after a brief description of the basic algorithm used in this generalized radix transformation method. Additional experiments on the files showed that the distribution of the keys was particularly sensitive to the arbitrary selection of an 8-bit grouping.

The article provides an analysis of key-to-address transformation techniques and the results of a performance study on large existing formatted files. The experimental results comparing six commonly used key-to-address transformation techniques were presented by the researchers. One transformation in the study referred to as "generalized radix transformation method" is an elaborate technique based on radix transformation. This method of transformation consists of a radix transformation algorithm as well as hardware implementation to carry out the steps of this transformation in an efficient manner. The intricacy of the generalized radix transformation method has motivated researchers to conduct further studies of the technique. The additional results are presented after a brief description of the basic algorithm used in this generalized radix transformation method. Additional experiments on the files showed that the distribution of the keys was particularly sensitive to the arbitrary selection of an 8-bit grouping.

The article focuses on the work of researcher H.L. Morgan related to a new form of interrupt which he proposes to use to control the execution of a program, in his case a file management system called data processing language. Simply stated, he has attached to every subroutine a Boolean expression which, if true, would cause that subroutine to be executed. Since his implementation is via software, a relatively time-consuming check must be made whenever some condition in the program changes. The implementation is described in terms of an IBM 360 environment, but is certainly not limited to it. Essentially the implementation involves the addition of a small associate memory to the CPU which is 12N bytes long. Each entry is 12 bytes wide, and the number of entries is up to the designer of the computer. The utility of this small associative memory is shown under a wide selection of applications. It is by no means definitive in its description. Its only goal is to show the desirability of implementing such a check at the hardware level.

Comments on a unified or generalized language for file organization and manipulation. Ideas from which disk file languages were developed; Applicability of language on magnetic tape files; Description of the general electric hanford system; Functions involved in access to a record.

The following are identified as major components of every programming language: (1) the elementary program statement, (2) mechanisms for linking elementary statements together, (3) the means by which program can obtain data inputs. Several alternative forms of each of these components ore described, compared and evaluated. Many examples, frequently from list processing languages, illustrate the forms described. Elementary program statements usually take the form of commands, requirements, or implicit specifications. A command is an imperative statement that commands the action to be taken. A requirement describes the effect to be achieved without saying anything about the actions to be taken. An implicit specification is similar to a requirement, but the programmer must understand what actions will be taken to achieve the desired effect. Subroutines may be entered explicitly, by execute coil, or by Function composition. Explicitly called subroutines generally require special linkage conventions. An execute subroutine call is syntactically indistinguishable from a basic instruction of the programming language. Function composition is convenient alternative to the explicit call. The three principal ways of getting inputs for routines are (1) by referring to the data itself, (2) by referring to the data by a "name", and {3) by referring to it implicitly by means of variables or functions. Names are useful entry points into permanent data structures, but can be error-causing distractions in other contexts. The author discusses advantages, disadvantages, and factors influencing the choice of a form of component for language. He concludes by suggesting the evolution of programming languages toward one which will permit all the most convenient ways of structuring programs, organizing Systems, and referencing data. [ABSTRACT FROM AUTHOR]

Describes some FORTRAN subroutines to facilitate handling of tape files. Symbolic naming of information files; Tape manipulation.

This article reports on the proceedings of an Association for Computing Machinery (ACM)'s SIGFIDET Workshop on Data Description, Access and Control which was convened in Ann Arbor, Michigan, during May 1-3, 1974. The convention featured a debate on the differences and similarities between the data structure set model and the relational model for data management systems. Educators C. W. Bachman and E. F. Codd were the two principals in the debate who were joined by E. Sibley and J. Lucking, on the one side, and V. K. Whitney and D. Tsichritzis, on the other. The moderator was R. Rustin. The discussion ranged over most of the relevant issues and topics, except possibly one posed by the moderator beforehand, that is, "Do databases eat their young?" Bachman took the position that the two points of view are perhaps two sides of the same coin, and that which is more natural depends on stylistic preferences. Other sessions on several related subjects featured contributed papers.

The article examines the quadratic search for hash tables of size pn. It has previously been claimed that the quadratic hash table search method of researcher W.D. Maurer cannot usefully be applied to tables of size 2n.This is not so; the method can in fact be applied to tables of size pn for any prime p. It is shown in the article that rather simple conditions on the conditions suffice to guarantee that all table locations will be examined once and only once.

Presents a critique of Robert P. Brent's presentation of a modification to the linear quotient algorithm sharing the common misconception that dynamic chaining requires larger table entries because of the space required for link fields, and Brents response. Effect of deletions on the speed of searches; Preferable method for applications where most entries are looked up several times and deletions are rare.

A method is discussed by which, after a system malfunction, the contents of disk files can be restored to their status at the time of the failure. [ABSTRACT FROM AUTHOR]