The authors present parallel processing of database joins in a hypercube system based on a dynamic and order-preserving data partitioning storage organization referred to as DYOP. A DYOP file system corresponds to a grid-based file organization. A grid-based file is any file organization where the n-field (attribute) records of a file are represented as points in an n-dimensional space. Such a hyperspace is divided into a set of hyperrectangles, each of which corresponds to a disk block. In DYOP, values along each attribute are stored in an order-preserving fashion. As the file grows, its partitions are split along a dimension (attribute) by preserving the order of values. As the file growth continues, further splits are performed in such a way that each split occurs along a different attribute in a cyclic fashion. There have been two previous studies in implementing a database join operation on hypercubes. A performance comparison of these studies is presented.>

A new algorithm for document clustering is introduced. The base concept of the algorithm, the cover coefficient (CC) concept, provides a means of estimating the number of clusters within a document database and related indexing and clustering analytically. The CC concept is used also to identify the cluster seeds and to form clusters with these seeds. It is shown that the complexity of the clustering process is very low. The retrieval experiments show that the information-retrieval effectiveness of the algorithm is compatible with a very demanding complete linkage clustering method that is known to have good retrieval performance. The experiments also show that the algorithm is 15.1 to 63.5 (with an average of 47.5) percent better than four other clustering algorithms in cluster-based information retrieval. The experiments have validated the indexing-clustering relationships and the complexity of the algorithm and have shown improvements in retrieval effectiveness. In the experiments two document databases are used: TODS214 and INSPEC. The latter is a common database with 12,684 documents.

Partitioning by clustering of very large databases is a necessity to reduce the space/time complexity of retrieval operations. However, the contemporary and modern retrieval environments demand dynamic maintenance of clusters. A new cluster maintenance strategy is proposed and its similarity/stability characteristics, cost analysis, and retrieval behavior in comparison with unclustered and completely reclustered database environments have been examined by means of a series of experiments.

Indexing in information retrieval (IR) is used to obtain a suitable vocabulary of index terms and optimum assignment of these terms to documents for increasing the effectiveness and efficiency of an IR system. The concept of term discrimination value (TDV) is one of the criteria used for index-term selection. In this article a new concept called the cover coefficient (CC) will be used in computing TDVs. After a brief introduction to the theory of indexing and the CC concept, an efficient way of computing TDVs by use of the CC concept, index-term selection, and weight modification are discussed. It is also shown that the computational cost of the CC approach in the calculation of TDVs is favorably comparable to the cost of a different approach that uses similarity coefficients. Furthermore, the TDVs obtained by the CC approach are consistent with those of the latter approach. © 1987 John Wiley & Sons, Inc.

In this article we present an interactive automatic document indexing software together with various index tuning/optimization strategies. After stems are generated from the raw text, the initial index vocabulary is narrowed down and tuned with the use of indexing versus clustering theory relationships. The narrowed down vocabulary is further optimized with the inclusion of term phrases and virtual terms corresponding to high and low frequency terms respectively. The results of performance experimentation which proved significant improvements of index vocabulary optimization are presented. The exploitation of the term discrimination value concept in index and retrieval system tuning and optimization is discussed.

Document clustering has several unresolved problems. Among them are high time and space complexity, difficulty of determining similarity thresholds, order dependence, nonuniform document distribution in clusters, and arbitrariness in determination of various cluster intiators. To overcome these problems to some degree, the cover coefficient based clustering methodology has been introduced. The concepts used in this methodology have created certain new concepts, relationships, and measures such as the effect of indexing on clustering, an optimal vocabulary generation for indexing, and a new matching function. These new concepts are discussed. The result of performance experiments that show the effectiveness of the clustering methodology and the matching function are also included. In these experiments, it has been also observed that the majority of the documents obtained in a search are concentrated in a few clusters containing a low percentage of documents of the database.

Abstract The similarity and stability analysis of the two partitioning type clustering algorithms, which appeared in this journal recently, are presented with respect to two different metrics. This article also includes other aspects of the algorithms, such as the number and size of the clusters generated, the similarity between the members of a cluster and the corresponding centroid, and other relevant details. In the experiments, a document collection consisting of the titles, abstracts, and keywords of 167 ACM TODS publications was used.

Abstract In this article, two partitioning type clustering algorithms are presented. Both algorithms use the same method for selecting cluster seeds; however, assignment of documents to the seeds is different. The first algorithm uses a new concept called “cover coefficient,” and it is a single‐pass algorithm. The second one uses a conventional measure for document assignment to the cluster seeds and is a multipass algorithm. The concept of clustering, a model for seed oriented partitioning, the new centroid generation approach, and an illustration for both algorithms are also presented in the article.

In this paper, a new clustering algorithm has been described. The algorithm proposed determines both the number of clusters in a collection, and the number of elements in each cluster before beginning the final clustering process. The complexity assessment of the algorithm and the implementation issues are also emphasized.

The design and implementation of a generalized database management system based on the RAP database machine is described. The GDBMS architecture, while is similar to the ANSI/SPARC view, has differences in the interpretation of its physical levels. The E/R model is chosen as the Meta Data Model (Conceptual Schema) which generates external model interfaces consisting of the relational, network, and hierarchical models. The SEQUEL, LSL, MRI --- like languages are supported at these interfaces. Structural and operational transformations from the external interfaces into the corresponding constructs of the RAP database machine have been implemented. The RAP DBMS assembler is found to be an efficient facility for language translation and in realizing common operational transformations. It performs these transformations in a way that preserves database consistency.

RAP—a Relational Associative Processor—is a back-end or peripheral device to augment a general purpose computer for implementing a database management system (DBMS) Its architecture is based on the fact that database operations are inherently set-oriented and that data base addressing is best accomplished through associative reference to achieve high data independence. RAP utilizes these characteristics by combining the features of associative and array processors. Previous publications on RAP have dealt separately with the details of the first version of its architecture [1]-[4] language interface [5],[6] and performance evaluation [7]-[9]. This paper provides details on a recently evolved, faster, and more flexible architecture for RAP called RAP. 2 [17].

RAP - a Relational Associative Processor - is a back-end or peripheral device to augment a general purpose computer for implementing a data base management system (DBMS). Its architecture is based on the fact that data base operations are inherently set-oriented and that data base addressing is best accomplished through associative reference to achieve high data independence. RAP utilizes these characteristics by combining the features of associative and array processors. Previous publications on RAP have dealt separately with the details of the first version of its architecture [1,2,3,4] language interface [5,6] and performance evaluation [7,8,9,]. This paper provides details on a recently evolved, faster, and more flexible architecture for RAP.

RAP (Relational Associative Processor) is a “back-end” database processor that is intended to take over much of the effort of database management in a computer system. In order to enhance RAP's performance its design includes mechanisms for permitting features analogous to multiprogramming and virtual memory as in general purpose computer systems. It is the purpose of this paper to present the detailed design of these mechanisms, along with some analysis that supports their value. Specifically, (1) the response time provided by RAP under several scheduling disciplines involving priority by class is analyzed, (2) the cost effectiveness of the additional hardware in RAP necessary to support multiprogramming is assessed, and (3) a detailed design of the RAP virtual memory system and its monitor is presented.

An associative processor called RAP has been designed to provide hardware support for the use and manipulation of databases. RAP is particularly suited for supporting relational databases. In this paper, the relational operations provided by the RAP hardware are described, and a representative approach to providing the same relational operations with conventional software and hardware is devised. Analytic models are constructed for RAP and the conventional system. The execution times of several of the operations are shown to be vastly improved with RAP for large relations.