Search

This paper describes a simple, efficient algorithm to locate all occurrences of any of a finite number of keywords in a string of text. The algorithm consists of constructing a finite state pattern matching machine from the keywords and then using the pattern matching machine to process the text string in a single pass. Construction of the pattern matching machine takes time proportional to the sum of the lengths of the keywords. The number of state transitions made by the pattern matching machine in processing the text string is independent of the number of keywords. The algorithm has been used to Improve the speed of a library bibliographic search program by a factor of 5 to 10. [ABSTRACT FROM AUTHOR]

The article presents information about the events related to information technology. For the first time in many years, Association of Computing machinery will hold its annual conference on November 11-13, 1974 in San Diego. A conference on Medical Informatics will be held in Stockholm concurrently with IFIP 74. This conference sponsored by IFIP, is the first of its type on this subject. The 12th annual meeting of the Association for Computational Linguistics will be held on July 26-27 on the Amherst campus of the University of Massachusetts, concurrent with the summer meeting of the Linguistic Society of America. The IEEE 1974 International Symposium on Information Theory will be held at the University of Notre Dame, Indiana, during October 28-31.

This paper presents a new approach to the analysis of performance of the various key-to-address transformation methods. In this approach the keys in a file arc assumed to have been selected from the key space according to a certain probabilistic selection algorithm. All files with the same number of keys selected from this key space will be suitably weighted in accordance with the algorithm, and the average performance of the transformation methods on these files will be used as the potential of these methods. Using this analysis, methods with the same overall performance can be classified and key distributions partial to certain transformations can be identified. All this can be done analytically. The approach is applied to a group of transformation methods using files whose keys are selected randomly. [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]

Sussenguth suggests in a paper (1963) that a file should be organized as a doubly-chained tree structure if it is necessary both to search and to update frequently. Such a structure provides a compromise between the fast search/slow update characteristics of binary searching and the slow search/fast update characteristics of serial searching. His method, however, contains the limiting restriction that all terminal nodes lie on the same level of the tree. This paper considers the effect of relaxing this restriction. First, trees which have the property that a priori the filial set of each node is well defined are studied. It is proved that coding the nodes within each filial set with respect to the number of terminal nodes reachable from each is necessary and sufficient to guarantee minimum average search time. Then the more general case (that is, where the entire structure of the tree is changeable) is treated. A procedure is developed for constructing a tree with a minimum average search time. A simple closed expression for this minimum average search time is obtained as a function of the number of terminal nodes. The storage capacity required to implement the doubly-chained tree structure on a digital computer is also determined. Finally, the total cost of the structure, using Sussenguth's cost criterion, is computed. It is shown that significant improvements in both the average search time and the total cost can be obtained by relaxing Sussenguth's restriction that all terminal nodes lie on the same level of the tree. [ABSTRACT FROM AUTHOR]

Describes the storage program and data representation being used at the Rice University computer programming system. Storage allocation and organization; Simplicity of programmed addressing; Flexibility of data structures; Efficiency of memory utilization.

The article presents information about various events related to computer machinery. Changing Patterns in Information Retrieval will be the theme of the 10th Annual National Information Retrieval Colloquium on May 3-4, 1973, at the Independence Mall Holiday Inn, Philadelphia, Pennsylvania. The Sixth Annual Simulation Symposium will be held in Tampa, Florida, on March 7-9, 1973. The Symposium provides an excellent opportunity to hear about latest developments in the field of digital computer simulation as well as opportunity to meet informally with other active members of the simulation community. The Second Texas Conference on Computing Systems will be held in Austin on November 12-13, 1973. The conference is an annual forum for the presentation of state-of-the-art practice in computing systems and research results. The second annual Computer Communications Conference will be held on January 24-25, 1973, at California State University, San Jose. Theme of the conference is "Time-Sharing: Past, Present, and Future."

Presents several letters to the editor on issues related to computer languages. Comments on the usage of heavy sprinkling of capital letters in the computing literature; Discussion on the paper related to the statistical method used in the study of roundoff propagation in the solution of ordinary differential equations; View that vagueness of the terms "information retrieval," "cognitive processes," "artificial intelligence," etc., has led to too many conferences that have tried to span so wide a field that they have not been effective in any one area.

This paper studies the properties of a new class of file organizations (CRWR) where records relevant to every query are stored in consecutive storage locations but the organizations contain redundancy. Some theorems which provide tools for reducing redundancy in CRWR organizations have been also developed. Redundancies obtained by the application of these theorems are compared with that of query-inverted file organizations. Some CRWR organizations with minimum redundancy have also been developed for queries which specify sets of keys. [ABSTRACT FROM AUTHOR]

The article focuses on the paper "Variable Length Tree Structures Having Minimum Average Search Time," by Y.N. Patt in the February 1969 issue of the periodical "Communications of the ACM." In this paper, the tree structures obtained are not actually optimal with respect to the two-dimensional chaining. This points out that the result can be described as "optimal" only under the constraint--which Patt implicitly assumes--that no key be allowed to prefix another. Since the jump to the terminal symbol * always adds a unit time to the search for a particular item, it seems as if one should be able to ignore the terminal symbols in constructing an optimal tree. Thus the result obtained by Patt cannot be accurately described as "optimal"; rather it is optimal subject to the constraint that no key be allowed to prefix another; otherwise, as shown above, it is possible to further decrease expected search time.

The article discusses the latest developments related to the Association for Computing Machinery (ACM). An interdepartmental Federal Government panel or task force has been organized by Burton W. Adkinson of the National Science Foundation's Office of Science Information Service to look into the scientific information activities of the U.S. The ACM Southeast region will offer prize for the best paper presented by an undergraduate at the national conference which is going to be held on August 24-26, 1965.

Because of the problems created by the explosion of papers in the mathematical sciences and the drawbacks that this places on research, it is suggested that a tree of all mathematical results and terminology be maintained in a multiterminal computer system. Users of the system can store in the computer an updated file of their current knowledge, and on selecting a paper to read, they can obtain from the computer the minimum subtree of theorems required to bring them from what they already know to the background knowledge which the paper assumes. Under certain conditions, means are also provided for the contribution of useful comments by the readers of a work and for interaction between commentators and with the author. This paper describes how the system can be organized and the role required of readers, writers, and commentators. [ABSTRACT FROM AUTHOR]

In certain data base organization schemes the cost per access may increase due to structural inefficiencies caused by updates. By reorganizing the data base the cost per access may be reduced. However, the high cost of a reorganization prohibits frequent reorganizations. This paper examines strategies for selecting the optimum reorganization points. [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]

CODAS, a Customer Oriented Data System, is a user-oriented data retrieval and display system. The command language of the system provides the user with an easy means for specifying data retrieval and display requests. Data is displayed as tables and graphs produced in a format ready for publication. In this paper the statements of the request language and the general system design are described. [ABSTRACT FROM AUTHOR]

The article presents a paper dealing with doubly-chained trees structures, designed to retrieve information for a given key value. The search mechanism of the structure may be described as follows: each level of the tree corresponds to a character position of the key. Initially the first character of the request key is compared with the nodes on the first level of the tree from left to right. When a node is found which matches exactly (no ordering is implied), the nodes emanating from it (its filial set) are then compared to the second character of the request key, also from left to right. The search continues through the appropriate filial sets on each level until the entire key has been matched. When implemented, each node consists of a character value and two chaining links: one to the node to its right on the same level in the tree (the next node to be tested if a match is not found) and the other to the first node in its filial set (next if a match does occur). It is assumed that the designer of the tree has the freedom to assign keys to elements, and that the number of available characters is unlimited, but that no key may prefix another. Specifically, the doubly-chained tree which is optimal will come from the extended class of binary trees in which any node without a left-hand son may contain an element.

In a paper in the November 1970 Communications of the ACM, V.Y. Lum introduced a technique of file indexing named combined indices. This technique permitted decreased retrieval time at the cost of increased storage space. This paper examines combined indices under conditions of file usage with different fractions of retrieval and update. Tradeoff curves are developed to show minimal cost of file usage by grouping various partially combined indices. [ABSTRACT FROM AUTHOR]

This article presents news developments related to activities of Association for Computing Machinery (ACM), as of June 1, 1966. All ACM members as of June 30, 1966 will automatically become full, professional, voting Members when the new membership qualifications of ACM go into effect on July 1st. To be eligible a candidate must have bachelor's degree or equivalent level of education from an accredited educational institution, or at least four years of full-time experience in the arts and sciences of information processing. In another development, Bill Eichelberger and his committee on Copyrighting and Patenting of Computer Programs have been active writing letters expressing concern that the new copyright bill now in the U.S. Congress Committee is unduly restrictive of the use of computers in information retrieval. The services of the ACM committee in providing technical information on the subject have been offered to the House Subcommittee preparing the bill. The bill, H.R. 4347, was introduced last year to the First Session of the 89th Congress, and is being considered in the Second Session.

Typical report generators allow the production of standard forms when tabulating a magnetic tape file; the extraction of nonstandard sets of information, with suitable annotation, involves troublesome forms design. A method of information extraction, involving the calculation of suitable FORTRAN FORMAT statements, which combats this problem, is described. [ABSTRACT FROM AUTHOR]

The article presents information on informal publications received by SIG members. Some of the publications are: "Architecture of Computer Systems," "Computers and the Physically Handicapped," "Computers and Society," "Data Communication," "Design Automation," "Information Retrieval," and "Minicomputer."

The article presents information on upcoming conferences related to the computer industry in the U.S. The Third Annual National Colloquium on Information Retrieval will be held on May 12-13, 1966 at the University of Pennsylvania in Philadelphia. Theme of the Colloquium is "Information Retrieval (IR)--A Critical View." The program offers a series of distinguished speakers active in many aspects of the IR field. Keynote speaker for the colloquium is U.S. Congressman William S. Moorehead, who was a sponsor of the joint resolution to establish the President's Advisory Staff on Scientific Information Management. The Annual Spring Symposium of the Digital Equipment Computer Users Society will be held on May 23-25, 1966 at the Hotel Somerset in Boston. Chairman for the meeting is Donald A. Molony of Rutgers University in New Jersey. The program will concern Digital's line of Programmed Data Processors, their peripheral equipment, and LINC. Emphasis will be given to unusual applications. Symposium on Prospects for Simulation and Simulators of Dynamics, sponsored by the Air Force Office of Scientific Research and Westinghouse, will be held at Westinghouse Defense and Space Center, Baltimore, Maryland on September 26-27, 1966.

The article presents the schedule and other information of certain upcoming events related to computing machinery. The second annual national colloquium on information retrieval will be held on April 23-24, 1965 at the University of Pennsylvania in Philadelphia. It will have as its conference theme: "Toward a National Information System." The colloquium will be cosponsored by the Association for Computing Machinery Special Interest Group on Information Retrieval and the Delaware Valley Chapters of the American Documentation Institute and by The Moore School of Electrical Engineering, University of Pennsylvania. Advances in Bio-Medical Applications is the title of a computer conference to be held on June 3-5, 1965 at the Waldorf Astoria Hotel in New York. The conference will be sponsored by the New York Academy of Sciences and Association for Computing Machinery's (ACM's) BIO group, the Bio-Medical Information Processing Organization. ACM annual southeast regional conference will be held 10-12 June at the Palm Beach Towers in Palm Beach, Florida.

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]

Examines the fixed and dynamic storage partitioning procedures for use in multiprogramming systems. Mathematical model of the storage requirement of programs; Comparison between dynamic and fixed storage partitioning on storage utilization and operating efficiency.

An affirmative partial answer is provided to the question of whether it is possible to program parallel-processor computing systems to efficiently decrease execution time for useful problems. Parallel-processor systems ore multiprocessor systems in which several of the processors con simultaneously execute separate tasks of o single job, thus cooperating to decrease the solution time of a computational problem. The processors have independent instruction counters, meaning that each processor executes its own task program relatively independently of the other processors. Communication between cooperating processors is by means of data in storage shared by oil processors. A program for the determination of the distribution of current in an electrical network was written for a parallel-processor computing system, and execution of this program was simulated. The data gathered from simulation runs demonstrate the efficient solution of this problem, typical of a large class of important problems. It is shown that, with proper programming, solution time when Np processors are applied approaches 1/Np times the solution time for a single processor, while improper programming con actually lead to an increase of solution time with the number of processors. Storage interference and other measures of performance are discussed. Stability of the method of solution was also investigated. [ABSTRACT FROM AUTHOR]

Experiments designed to evaluate the capabilities of mechanized information retrieval systems, with emphasis on interactive (man-machine) language and on some of the mechanical and psychological limitations in their design, were conducted at the Moore School Information Systems Laboratory The bask assumption of the research is that an information retrieval system that provides for man-machine dialogue cat a remote inquiry terminal should provide a searcher with many of the tools Which would be available to him were he actually performing his search at a library or repository of documents. Factors involved in evaluation of such a system include ease of use, learning time, and effectiveness of actual retrieval. Three experiments and the conclusions resulting from them are detailed. [ABSTRACT FROM AUTHOR]

Presents a drum scheme in storing and retrieving information. Purpose of the scheme; Consideration of drum as the most rapid means for storing and retrieving information; Illustration of the Eschenbach drum scheme.

The article offers news briefs related to the Association for Computing Machinery (ACM). ACM chapters disclosed their new set of officers for 1965 to 1966 term. Various chapters focused on discussions involving programming languages in chapter meetings. The 4th ACM Southeastern Regional Meeting works on issues concerning information retrieval, statistical analysis of stocks, and airline reservation systems.

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.

Comments on articles published in earlier issues of the journal "Communications of the ACM." Discussion on techniques used in automatic segmentation of cyclic program structures;Focus on diverse techniques to assure the integrity of a data base;Information on algorithms to be followed by primitives in order to maximize the amount of parallel activity in a data base.

The article presents a list of forthcoming events related to information science, to be held across the world. Some of the events included in the list are: "Second International Conference of Women Engineers and Scientists," to be held on July 1-9, 1967 in Cambridge, England; "Sixth Symposium on Mathematical Programming," to be held during August 14-18, 1969 in Princeton New Jersey; "ACM Symposium on Interactive Systems for Experimental Applied Mathematics," to be held on August 26-28, 1967 in Washington D.C. etc.

Presents a technique for compression and storage of computer data. Efficiency of the system; Involvement of special handling of leading and trailing blanks; Encoding of other symbols in groups of fixed size as unique fixed point numbers.

This article analyzes the best-match problem in document retrieval. One major problem encountered in clustering for the purpose of reducing search time is the selection of an appropriate cluster representative. These representatives are to somehow characterize the cluster and discriminate it from other clusters, so that a search may be able to find the nearest cluster by comparing each cluster representative with the incoming query. Two different approaches to the selection of a typical member are possible. One is through the definition of typicality. A cluster representative should be such that an incoming query will be diagnosed into the cluster containing the documents relevant to the query. Unfortunately, as it stands this is of very little help in choosing the cluster representative since the relevant documents are normally not known in advance. However, it is reasonable to suppose that a query identical to a document, that is, a document treated as a query, should retrieve that document. Experiments with this kind of cluster representative have been reported elsewhere.

The article discusses the retrieval times for a packed direct access inverted file. In a packed list file, the bucket which contains the first element of list "j" will have its first positions occupied by lists j-1, j- 2. For any practical file, when j is not a small integer, it behaves as a random variable uniformly distributed between 0 and C. In other words, the start of a list is independent of bucket boundaries.

The article presents a list of events related to computer programming. From December 2-4, 1968 there will be "Second Conference on the Applications of Simulation." The "Fifth Workshop on Computer Applications in the Earth Sciences" will be conducted from December 11-13, 1968. "Purdue University Centennial Year Symposium on Information Processing" will be held from April 28-30, 1969. The "Sixth Annual National Information Retrieval Colloquium" will be held in May 1969 and the "6th Annual Design Automation Workshop" will be held from June 8-12, 1969.

This article presents information about meetings related to the computer science. Some of them are as follows: The Winter Convention on Aerospace and Electronics Systems will be held at Baltimore Hotel, Los Angeles, California during February 11-13, 1969. The 4th International Exhibition of Industrial Electronics will be held in Basel, Switzerland during March 4-8. The Conference on Semiconductor Device Research will be held in Munich, Germany during March 24-27. The International Conference on Remote Data Processing will be held in Paris, France during March 24-28. The Seventh Annual Symposium on Biomathematics and Computer Sciences in the Life Sciences at University of Texas, Houston during March 26-28. The 16th International TIMS Meeting will held at Hotel Commodore, New York City during March 26-29. The 9th Annual Computing Conference will be held in Florida State University, Tallahassee during March 27-29. The Sixth Annual National Information Retrieval Colloquium will be held in Philadelphia in May.

Presents a technique which allows a class of solid objects to be synthesized and stored using a computer. Computational geometry; Computer-aided design; Graphics; Machined components; Polyhedra; Shape synthesis; Three-dimensional modeling.

A model of natural language generation based on an underlying language-free representation of meaning is described. A program based on this model is able to produce sentence paraphrases which demonstrate understanding with respect to a given context. This generator operates in conjunction with a natural language analyzer and a combined memory and inference model. in generating sentences from meaning structures, the program employs both the information retrieval and deduction capabilities of the memory model. The model encompasses several diverse classes of linguistic knowledge, which include: (1) executable tests of conceptual properties stored in discrimination nets; (2) information relating conceptual to syntactic roles, stored in a word-sense dictionary, and (3) surface grammatical knowledge, stored in a formal grammar. [ABSTRACT FROM AUTHOR]

It is proposed that the data base management function be placed on a dedicated back-end computer which accepts commands (in a relatively high level language such as the CODASYL Data Base Task Group, April 1971 Report) from a host computer, accesses the data base on secondary storage, and returns results. The advantages of such a configuration are discussed An experimental implementation, called the experimental Data Management System, XDMS, is described and certain conclusions about the back-end approach are drawn from this implementation. [ABSTRACT FROM AUTHOR]

Details a user authentication scheme not requiring secrecy in the computer. Disadvantages of the password table system; Basis of the scheme; Mechanism of the scheme.

Examines a method for calculating the correction of regular computer languages. Requirements for the calculation; Application of method in information retrieval, artificial intelligence and spelling correction systems; Definition of a set of edit operations.

Examines the effect of iterating the improvement procedure in information retrieval process. Applications of the improvement factor; Indexing and classification of information.

Generalizes the concept of AVL trees by permitting the imbalance at nodes of the tree to take on values larger than one while still not permitting unrestricted growth. Five aspects of the generalized AVL trees; Retrieval time possible under a constraint; Method of constructing AVL trees.

Since the logical structure of a data base can be represented by a tree or graph, it is quite natural for us to view the process of designing a data base as that of constructing a tree or a graph. A general method for constructing such a tree or graph is provided. There are three important elements in this general construction method; namely, a set of binary relations, an algorithm for constructing subsets of a set, and an algorithm for selecting an element from the given set of objects. The use of different relations and algorithms results in different information structures, as list, tree, ring, etc. Thus the problem of information organization and storage is reduced to that of defining relations and formulating algorithms under a given set of constraints. The results presented may be valuable to designers as useful design concepts, and may serve as a basis for developing a formal theory on the subject. [ABSTRACT FROM AUTHOR]

Discusses the employment of a probabilistic analysis in determining the effect of hierarchical storage organizations on information retrieval operations. Mismatch between the speeds of primary storage and secondary storage; Optimization of memory hierarchies under a set of assumptions suitable for program segmentation and swapping.

Describes a method for entering and retrieving information in a hash table. Use of scatter storage techniques; Reduction in the number of probes required for subsequent lookups; Comparison of the efficiency of different algorithms.

The current role of computers in automatic document processing is briefly outlined, and some reasons are given why the early promise of library automation and of the mechanization of documentation processes has not been fulfilled. A new dynamic document environment is then outlined in which clustered files are searched and information Is retrieved following an interactive user-controlled search process. Methods are described for an automatic query modification based on user needs, and for a continuous reorganization of the stored information as a function of earlier file processing and of normal collection growth. The proposed procedures provide powerful tools for information retrieval and for the control of dynamic library collections in which new items are continually added and old ones are retired. [ABSTRACT FROM AUTHOR]

An algorithm is displayed which yields the merge orders such that the total read time, defined to be the sum of seek time plus data-transfer time, is minimized for a sort using mass storage. The analysis is parameterized in terms of the ratio of seek time to the time it takes to fill available core with records, and the file size in units of core lengths; and thus it can be applied to any conventional CPU mass storage combination. An explicit formula for total read time is derived, in terms of the parameters, which correlates very well with the total read time calculated using the optimum merge orders yielded by the algorithm. The formula involves the roots of a simple transcendental equation. A short table of these roots is included. Numerical results are graphically displayed for a wide range of the parameters. It is found that the normalized read time for optimum merging on a given hardware configuration is proportional to the file length times the logarithm of the file length. [ABSTRACT FROM AUTHOR]