Search

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]

Mesa is a highly scalable analytic data warehousing system that stores critical measurement data related to Google's Internet advertising business. Mesa is designed to satisfy a complex and challenging set of user and systems requirements, including near real-time data ingestion and retrieval, as well as high availability, reliability, fault tolerance, and scalability for large data and query volumes. Specifically, Mesa handles petabytes of data, processes millions of row updates per second, and serves billions of queries that fetch trillions of rows per day. Mesa is geo-replicated across multiple datacenters and provides consistent and repeatable query answers at low latency, even when an entire datacenter fails. This paper presents the Mesa system and reports the performance and scale that it achieves. [ABSTRACT FROM AUTHOR]

Presents information on several forthcoming events related to the computing machinery industry. The Second National Association for Computing Machinery (ACM) Student Programming Championship Contest in connection with the 1978 ACM Computer Science Conference February 21-23, in Detroit; The First Annual SIGIR Conference from May 11-12, 1978, at the Holiday Inn Downtown, Rochester, New York; The Fourth International Conference on Very Large Data Bases, to be held in Berlin September 13-15, 1978, scheduled to coincide with the International Congress of Data Processing.

This article presents information on a digital library project called the Chemistry Online Retrieval Experiment (CORE). The CORE project is an electronic library of primary journal articles in chemistry published by the American Chemical Society. Unlike many digital library projects, CORE includes both a scanned image and a marked-up American Standard Code for Information Interchange version for each page of the publisher's database. Each page image was stored as a 300dpi bitonal image for printing and 100dpi greyscale for screen display. The author stressed that managing a 80 gigabytes of data from a single publisher, in one format and in one subject area should not be underestimated. Complex scientific material presents substantial problems for representation and display, especially when the material is being converted from previously published information. According to preliminary user studies, CORE users search more effectively with computers that with paper indexes; read and absorb content as effectively with computer displays as on paper; wish to organize their own display screen, forcing the interface designers to yield control of the exact placement of interface elements; have a wide range of experience and expertise in online information systems; and make extensive use of thumbnail-sized versions of the figures in the articles of browsing.

System R, an experimental database system, was constructed to demonstrate that the usability advantages of the relational data model can be realized in a system with the complete function and high performance required for everyday production use. This paper describes the three principal phases of the System R project and discusses some of the lessons learned from System R about the design of relational systems and database systems in general. [ABSTRACT FROM AUTHOR]

This paper describes a method for the organization and retrieval of attribute based information systems, using the normal multiplication table as a directory for the information system. Algorithms for the organization and retrieval of information are described. This method is particularly suitable for queries requesting a group of information items, all of which possess a particular set of attributes (and possibly some other attributes as well). Several examples are given; the results with respect to the number of disk accesses and disk space are compared to other common approaches. Algorithms evaluating the appropriateness of the above approach to a given information system are described. For a certain class of information systems, the normal multiplication table method yields far more rapid retrieval with a more economical space requirement than conventional systems. Moreover this method incorporates an improved modification of the inverted file technique. [ABSTRACT FROM AUTHOR]

The article presents information on an approach to optimal design of storage parameters in databases. The aim of the application of the said approach is to classify the critical factor in each definite application as being either the number of accesses or the storage volume. According to the author, the time-honored problem of the exchange between storage volume and response-time performance arises in many applications and in many disguises. The author stated that the actual location of the equilibrium depends on the conditions of the definite problem. The storage and organization policy is determined by a set of parameters such as number of records per block, length of record. The author further stated that a common way of creating the compound criterion is to bring the two non commensurate terms by introducing an appropriate weight that measures the importance of the number of accesses relative to the storage volume. A decision maker should be asked to state the largest value of the factor he is willing to tolerate in his system, once the critical factor has been identified.

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]

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 focuses on reexamination of organizational memory. After nearly 10 years of research, organizational memory (OM) has become overworked and confused. Burdened by a practical wish to reuse organizational experience, researchers have often ignored critical functions of an organization's memory in order to focus on only a few methods for augmenting memory. In this article, authors investigate where memory exists currently within an organizational setting, rather than focusing on potential technical enhancements. In order to accomplish this OM is studied within a telephone help line that answers human-resource questions at a well-established Silicon Valley company. This problem is approached using distributed cognition theory. Authors begin with a synopsis of the OM literature and the need for empirically based analyses of OM. The OM Literature holds many varying and occasionally competing, definitions. Intuitively, organizations should be able to retrieve traces of their past activities, but the form of this memory is unclear in research literature. A field study was conducted, which took place over a period of 18 months. A variety of data collection methods were Tracking system in which agents record the content of their phone interactions.

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]

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.

Relative fitness is a new approach to modeling the performance of storage devices (e.g., disks and RAID arrays). In contrast to a conventional model, which predicts the performance of an application's I/O on a given device, a relative fitness model predicts performance differences between devices. The result is significantly more accurate predictions. [ABSTRACT FROM AUTHOR]

The article discusses efforts to integrate database systems (DB) and information retrieval (IR) methods in order to address emerging applications related to the increased amounts and diversity of digital information. One goal of such efforts is to create an automatically built and maintained comprehensive knowledge base of facts derived from scientific literature and encyclopedic sources. Other topics include facts represented in terms of typed entities and relationships and expressive queries that return results with precision.

The article discusses the Semantic Web, examining the shortcomings of the hypertext paradigm that is behind the simplicity of Web searches and its distributed hypertext and link navigation. Content has become increasingly difficult to find via the search and browse method, the article states. Topics include the capabilities of Web query engines, the integration of information from multiple sources, and locating and integrating information without human intervention. Also discussed is creating suitable ontologies and dealing with the variable quality of Web content.

By typing requests in English, casual users will be able to obtain explicit answers from a large relational database of aircraft flight and maintenance data using a system called PLANES. The design and implementation of this system is described and illustrated with detailed examples of the operation of system components and examples of overall system operation. The language processing portion of the system uses a number of augmented transition networks, each of which matches phrases with a specific meaning, along with context registers (history keepers) and concept case frames; these are used for judging meaningfulness of questions, generating dialogue for clarifying partially understood questions, and resolving ellipsis and pronoun reference problems. Other system components construct a formal query for the relational database, and optimize the order of searching relations. Methods are discussed for handling vague or complex questions and for providing browsing ability. Also included are discussions of important issues in programming natural language systems for limited domains, and the relationship of this system to others. [ABSTRACT FROM AUTHOR]

The performance of information retrieval systems can be evaluated in a number of different ways. Much of the published evaluation work is based on measuring the retrieval performance of an average user query. Unfortunately, formal proofs are difficult to construct for the average case. In the present study, retrieval evaluation is based on optimizing the performance of a specific user query. The concept of query term accuracy is introduced as the probability of occurrence of a query term in the documents relevant to that query. By relating term accuracy to the frequency of occurrence of the term in the documents of a collection it is possible to give formal proofs of the effectiveness with respect to a given user query of a number of automatic indexing systems that have been used successfully in experimental situations. Among these are inverse document frequency weighting, thesaurus construction, and phrase generation. [ABSTRACT FROM AUTHOR]

Clustering in the key set is decreased by smoothing the key-to-address transformation, and by adding shadow buckets to an open chaining file. The keys are pre-hashed before the address division, to remove the effect of sequential properties In the key set. Shadow buckets in the key search sequence reduce the effect of nonuniformity in file loading, and decrease the number of maximum probes needed to locate a record. The combined effects of these techniques lead to improved file performance for secondary storage devices, as shown by empirical studies. [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.

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]

Focuses on the secondary key retrieval method, which involves the preparation of secondary storage lists from primary data records. Satisfaction of search requests by logical operations on appropriate lists; Production of a complete set of addresses of primary records relevant to the request.

Comments on an optimal evaluation of Boolean expressions in an online Query systems. Information that the operands of the Boolean functions can be evaluated in any order because of the commutativity and associativity of the operators; Claim that the large files often consist of partitioned records, with the most frequently referenced attributes in the primary portion and the remainder in one or more secondary records chained to the primary; View that a Boolean expression will depend upon attributes in both the primary and secondary portions of the record; Description of describes an algorithm for optimal evaluation of Boolean expression queries for sequential databases.

The article discusses another article in the issue which presents the results of research in the area of error-correcting codes built on Reed-Solomon codes. Error-correcting codes are tools used to compensate for interference in communication, the author states, as well as being essential for accuracy in digital data storage.