uthoene@water.waterloo.edu (U.Thoene) (08/17/89)
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
DATA STRUCTURING SEMINAR
- Thursday, August 17, 1989
Mr. Ron McFadyen, Graduate Student, will speak on
``Estimating Cluster Accesses in Random Allocations''.
TIME: 3:30 PM
ROOM: DC1331 ICR Board Room
ABSTRACT
We consider the costs of answering queries when records
have been randomly allocated to the pages of a file.
Answering a query entails the retrieval of those pages,
the response set, containig the required records.
Previous work has used the number of pages retrieved as
a measure of the cost of processing a query. Counting
pages does not take into account any reduction in cost
that accrues when contiguous pages are transmitted from
disk to memory. We view a response set as a collection
of clusters, where a cluster is a set of contiguous
pages, and incorporate both cluster accesses (seeks)
and page transmission into our cost function,. Our
results include a measure of the clustering present in
random organizations and give a baseline for measuring
the performance of other organizations.