This study examines the performance of concurrent algorithms for B-trees and linear hashing. B-trees are widely used as an access method for large, single key, database files, stored in lexicographic order on secondary storage devices. Linear hashing is a fast and reliable hash algorithm, suitable for accessing records stored unordered in buckets. This dissertation presents performance results on implementations of concurrent Bunk-tree and linear hashing algorithms, using lock-based, partitioned and distributed methods on the Sequent Symmetry shared memory multiprocessor system and on a network of distributed processors created with PVM (Parallel Virtual Machine) software. Initial experiments, which started with empty data structures, show good results for the partitioned implementations and lock-based linear hashing, but poor ones for lock-based Blink-trees. A subsequent test, which started with loaded data structures, shows similar results, but with much improved performances for locked Blink- trees. The data also highlighted the high cost of split operations, which reached up to 70% of the total insert time.

Generalized algebraic data types (GADTs) are a type system extension to algebraic data types that allows the type of an algebraic data value to vary with its shape. The GADT type system allows programmers to express detailed program properties as types (for example, that a function should return a list of the same length as its input), and a general-purpose type checker will automatically check those properties at compile time. Type inference for the GADT type system and the properties of the type system are both currently areas of active research. In this dissertation, I attack both problems simultaneously by exploiting the symbiosis between type system research and type inference research. Deficiencies of GADT type inference algorithms motivate research on specific aspects of the type system, and discoveries about the type system bring in new insights that lead to improved GADT type inference algorithms. The technical contributions of this dissertation are therefore twofold: in addition to new GADT type system properties (such as the prevalence of pointwise type information flow in GADT patterns, a generalized notion of existential types, and the effects of enforcing the GADT branch reachability requirement), I will also present a new GADT type inference algorithm that is significantly more powerful than existing algorithms. These contributions should help programmers use the GADT type system more effectively, and they should also enable language implementers to provide better support for the GADT type system.

No description available.

This thesis presents a data structure for the interactive editing of logic diagrams by means of a storage graphics terminal. It presents an overview of Computer-Aided Design of digital systems, and outlines the requirements of an interactive graphics system. The use of sequential list, hashing, binary tree, and linked list data structures are evaluated, and the data structure is formulated, which includes a combination of linked lists, binary trees, and sequential lists. An illustrative example is presented, along with recommendations for further study. / M.S.

This dissertation deals with the application of efficient data structures and hashing algorithms to the problems of textual information storage and retrieval. We have developed static and dynamic techniques for handling large dictionaries, inverted lists, and optimizations applied to ranking algorithms. We have carried out an experiment called REVTOLC that demonstrated the efficiency and applicability of our algorithms and data structures. Also, the REVTOLC experiment revealed the effectiveness and ease of use of advanced information retrieval methods, namely extended Boolean (p-norm), vector, and vector with probabilistic feedback methods. We have developed efficient static and dynamic data structures and linear algorithms to find a class of minimal perfect hash functions for the efficient implementation of dictionaries, inverted lists, and stop lists. Further, we have developed a linear algorithm that produces order preserving minimal perfect hash functions. These data structures and algorithms enable much faster indexing of textual data and faster retrieval of best match documents using advanced information retrieval methods. Finally, we summarize our research findings and some open problems that are worth further investigation. / Ph. D.

Computer representation of the continuous two-dimensional features on a map is complicated by the spatial properties not found in typical alphanumeric data. We have designed an entity-oriented relational system for representing the cartographic data, using the concept of spatial data structures. Each geographic entity such as a region, road, or city is represented by a set of relations describing its properties, its related entities, and all the relationships among them. The thesis presents the description of the first experimental cartographic information system based on these concepts to store and retrieve watershed data for a portion of the Wise county in the state of Virginia. The thesis describes the logical structure of the database, the physical structures in memory and on the dist, a guery language interpreter which is used to access the information in the database, and a memory management scheme to transfer the structures back and forth between memory and secondary device. / Master of Science

An interactive color graphics layout editor for VLSI has been implemented on the IBM PC. The software, PC-ICICLE, is written in Microsoft PASCAL and the 8086/88 Assembly Language under the DOS 2.0 environment. The basic hardware requirement is the standard configuration of the IBM PC with 256K bytes, and color graphics monitor and adapter. Without the need for any special hardware, PC-ICICLE makes layout editors more readily available to VLSI chip designers. PC-ICICLE has also been executed on the IBM PC-XT, IBM PC-AT, and Zenith's IBM compatible PC without any modifications. / Master of Science

In Chapter 2, several other relational database systems will be reviewed. The primary goal of each analysis will be to identify the logical and physical approaches to data representation, as well as the user interface. Chapters 3 and 4 identify the physical and logical structure of the experimental disk-resident spatial information system developed for this project. As will be seen, this experimental system combines features of existing relational databases with new approaches to represent and manipulate information in a database. The Query Language Interpreter will be presented in Chapter 5. Through the interpreter, a database user can issue a variety of commands to perform database operations, as well as create sophisticated program control structures. Chapters 6-8 discuss the security, integrity, and recovery aspects of the disk-resident system. During the development of this project, various implementation problems were encountered. These problems and solutions are presented in Chapter 9. Chapter 10 discusses the performance of the disk-resident system. Statistics are presented comparing how the database commands performed when run under a variety of test environments. Chapter 11 uses the results from earlier chapters to draw conclusions concerning the disk-resident system and presents some directions for future work. Following the bibliography are related appendices that illustrate the various types of files recognized by the query language interpreter. / Master of Science

In this thesis we describe a spatial information system. A spatial data structure is used as the building block of the system. Prototypes, a high level query language and an associated retrieval scheme particularly designed for the hierarchical and relational spatial data structure are discussed. / M.S.

The B-tree is a one of the more popular methods in use today for indexes and inverted files in database management systems. The traditional implementation of a Bâ tree uses many pointers (more than one per key), which can directly affect the performance of the B-tree. A general method of file organization and access (called Dynanic Address Computation) has been described by Cook that can be used to implement B-trees using no pointers. A minimal amount of storage (in addition to the keys) is required. An implementation of Dynamic Address Computation and a B-tree management package is described. Analytical performance measures are derived in an attempt to understand the performance characteristics of the B-tree. It is shown that the additional costs associated with Dynamic Address Computation result in an implementation that is competitive with traditional implementations only for small applications. For very large B-trees, additional work is required to make the performance acceptable. Some examples of possible modifications are discussed. / Master of Science