Using Dynamic Sets to Speed Search in World Wide
Information Systems
David C. Steere
Abstract
Search on wide area distributed systems is plagued by the high latencies
inherent in remote access. A solution is to prefetch information before
it is requested by the searcher to hide latency. But this raises the problem
of knowing what to prefetch, since fetching data that will not be used
can actually hurt performance. This paper proposes extending the Unix file
model to support dynamic sets, short-lived and unordered collections
of objects created by searchers to hold the results of queries. An object's
membership in a set is a hint of future access, informing the system
that prefetching that object can improve performance. An additional benefit
of using set membership as the hint is that it allows the system to determine
the order in which objects are returned to the searcher, further increasing
the opportunity for performance improvement. This paper presents the design
of SETS, a system extension to Unix to provide dynamic sets. A performance
evaluation of SETS shows dynamic sets offer substantial opportunity to
reduce the aggregate latency to fetch a group of objects. Experiments on
existing world wide information systems show as much as a factor of 8 performance
improvement from using sets.