Stanford InfoLab Publication Server

Partial Lookup Services (Extended Version)

Sun, Qixiang and Garcia-Molina, Hector (2002) Partial Lookup Services (Extended Version). Technical Report. Stanford.




Lookup services are used in many Internet applications to translate a key (e.g., a file name) into an associated set of entries (e.g., the location of file copies). The key lookups can often be satisfied by returning just a few entries instead of the entire set. However, current implementations of lookup services do not take advantage of this usage pattern. In this paper, we formalize the notion of a partial lookup service that explicitly supports returning a subset of the entries per lookup. We present four schemes for building a partial lookup service, and propose various metrics for evaluating the schemes. We show that a partial lookup service may have significant advantages over conventional ones in terms of space usage, fairness, fault tolerance, and other factors.

Item Type:Techreport (Technical Report)
ID Code:531
Deposited By:Import Account
Deposited On:24 Feb 2002 16:00
Last Modified:25 Dec 2008 10:09

Download statistics

Repository Staff Only: item control page