Xref: utzoo uw.talks:6 uw.cs.grad:7
Path: utzoo!utgpu!watmath!maytag!water!uthoene
From: uthoene@water.waterloo.edu (U.Thoene)
Newsgroups: uw.talks,uw.cs.grad
Subject: Computer Science Data Structuring Seminar
Keywords: Ron McFadyen, CS Grad Student  3:30 DC1331  Nov.17/89
Message-ID: <2591@water.waterloo.edu>
Date: 16 Aug 89 17:54:31 GMT
Distribution: uw
Organization: U of Waterloo, Ontario
Lines: 41




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.