An algorithm for record clustering is presented. It is capable of detecting sudden changes in users' access patterns and then suggesting an appropriate assignment of records to blocks. It is conceptually simple, highly intuitive, does not need to classify queries into types, and avoids collecting individual query statistics. Experimental results indicate that it converges rapidly; its performance is about 50 percent better than that of the total sort method, and about 100 percent better than that of randomly assigning records to blocks.

In this paper, we study the allocation of files in a star network. Unlike previous algorithms which assume that files are independently accessed and independently assigned, the interaction of files during the processing of queries is directly incorporated into our cost model. We present an adaptive algorithm, which is much faster than existing algorithms on file allocation, obtains solutions which are on the average only 0.1 percent away from the optimal solutions, and possesses many desirable properties such as the satisfaction of some necessary and sufficient conditions for file allocation.

The relative placement of records in a database has a significant impact on the overall system performance. In this paper we study three related assignment problems. They are (1) the assignment of records to devices so as to minimize the expected completion time and to maximize the expected utilization of the devices, (2) the assignment of records to pages or blocks in secondary memory so as to minimize the number of blocks to be accessed, and (3) the analysis of the performance of a hashing scheme under the assumption that the record-to-bucket probability varies from one bucket to another. The solutions to these problems are obtained by studying an occupancy problem. In each case, an optimal solution is obtained.

In mformaUon retrieval indexing is the task consisting of the assignment to stored records and mcommg mformatton requests of content ~dent~fiers capable of representing record or query content If the mdexmg is performed automatically and the records are wntten documents, an mmal set of index terms might be chosen by taking words extracted from document roles or abstracts, this mmal term assignment might then be improved by addmg related terms chosen from a thesaurus, by deletmg extraneous or marginal terms, and by replacing smgle terms by term combmaaons and phrases.In the present study formal proofs are given of the retrieval effectiveness under well-defined condmons of mdexmg policies based on the use of single terms, term additions and deletions, and term combmaaons or phrases.

The importance of the estimation of the number of desired records for a given query is outlined. Two algorithms for the estimation in the “closest neighbors problem” are presented. The numbers of operations of the algorithms are Ο ( ml 2 ) and Ο ( ml ), where m is the number of clusters and l is the “length” of the query.

This paper investigates the problem of locating a set of “boundary points” of a large number of records. Conceptually, the boundary points partition the records into subsets of roughly the same number of elements, such that the key values of the records in one subset are all smaller or all larger than those of the records in another subset. We guess the locations of the boundary points by linear interpolation and check their accuracy by reading the key values of the records on one pass. This process is repeated until all boundary points are determined. Clearly, this problem can also be solved by performing an external tape sort. Both analytical and empirical results indicate that the number of passes required is small in comparison with that in an external tape sort. This kind of record partitioning may be of interest in setting up a statistical database system.