Ashish Gupta Peter Dinda Fabian Bustamante {ashish,pdinda,fabianb }@cs.northwestern.edu Department of Computer Science, Northwestern University 1. INTRODUCTION Distributed hash tables (DHTs) are a distributed, peer-to- peer analogue of hash indices in database systems. Given a key, a DHT returns a pointer to the associated object. DHTs have also be extended to support “keyword” queries [5, 2](object identified by multiple keys). Fundamentally, how- ever, these approaches all return a undirected sample of the full result set. Unfortunately, most applications are inter-ested in the most popular members of the result set. In other words, if all the objects in the result set were to be ranked in descending order of the number of accesses to the objectin a given time interval, the application’s interest decreasesthe further down the ranked list it goes. We are developing distributed popularity indices (DPIs). Suppose a DHT supports two query primitives. The firstsimply finds an object given a key: Lookup :k→d while the second provides keyword queries: Query :{w 1,w2,…}→{ k1,k2,…} where the wiare keywords and the kiare the keys of the objects that have all of those keywords associated with them.A DPI supports queries of the form LookupPop :k→(d, p) where pis the popularity of the object associated with key k, and the conjunctive query QueryPop :({w 1,w2,…},n)→{k1,k2,…,k n} which is similar to Query except that the keys of the nmost popular objects are returned. As with a DHT, a DPI alsomust support Insert ,Update ,a n d Delete primitives. There is an additional primitive Visit:(k,w 1,w2,… ,v )→. that indicates that object associated with k(and its associ- ated keywords wi) has been visited vtimes. While the DPI is a distributed structure that we either generate on the fly in response to query or maintain persis-tently within a DHT, copies of at least portions of it can be cached locally on the client. Gupta is a Ph.D. student. Dinda and Bustamante are fac- ulty. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee. Copyright 200X ACM X-XXXXX-XX-X/XX/XX … $5.00.Applications Beyond the obvious application in peer-to-peer file sharing communities, DPIs have many uses. Consider replication. Suppose that the system replicates popular objects up to z times by using zdifferent hash functions. A client would merely issue a LookupPop to determine how many of the hash functions can be used for a particular key, providing a simple decoupling. Consider web search. Arguably, link structures, as used in PageRank, and aggregated bookmarks as in social book- marking, are proxies for the extent to which a page has beenvisited. Web clients could push Visits into the DPI as pages were visited. A QueryPop would then be able to extract the topnmost visited pages associated with a set of keywords. If the DPI automatically reduced accumulated popularityof objects over time by an exponential response with some time constant, we would know what pages were significant in the context of some set of keywords for a window of timeending in the present: a zeitgeist query. 2. EXPLOITING REVERSIBLE SKETCHES A k-ary sketch [3] is a variant of a Bloom filter [4] that captures popularity in a highly condensed form. A key is inserted into a Bloom filter by updating mhash tables of sizes/m, each fronted with a different uniform hash func- tion. Each bucket contains a bit and the update is a bit-or of each bucket determined by the key with one. In a sketch, the buckets contain integers and the update involves incre-menting the buckets determined by the key. A Bloom fil- ter provides a constant size representation of a potentially very large set of keys, with the caveat that it is imperfect—spurious keys may also be included. Similarly, a sketch is aconstant size, but imperfect representation of an ideal pop- ularity index that would map from key to number of visits. A key may appear more popular than it really is, but thisnoise affects unpopular keys much more than popular ones. A sketch, when queried with a key, provides an estimate of the number of updates (visits) to that key whose accuracyincreases with the number of visits. Surprisingly, given that sketches are based on hashes, there exists a reverse-hashing formulation that is reversible for popular keys, meaning that it is possible to determine the most visited keys from the sketch, as well as the number of updates to them, without knowing the keys in advance [6].Our Visit maps to a sketch update, while the popularity p from LookupPop is determined by using a sketch S allin the forward direction. Sallis computed over all keys. QueryPop is implemented using the per-keyword sketches Sw1,Sw2,… in the reverse direction and aggregating the results. We can generate DPIs for use for individual queries, and DPIs that persist. We refer to these approaches as query-driven and update-driven indices. 3. QUERY-DRIVEN INDICES Query-driven indices are computed and aggregated on the fly in response to LookupPop sa n d QueryPop s. For LookupPop , the client simply finds the node associated with kand asks it for the popularity of k, which the node stores as a simple counter associated with the object. Visitsimply increments this counter. ForQueryPop , we use a DHT that provides keyword search, such as Magnolia [2, 1] or others [5]. We use Query to deter- mine the set of keys of interest, and then contact each nodeassociated with these keys. Each node constructs a sketch that reflects the counters associated with the matching keys it holds. We then sum all of these sketches and deliver themto the client. Notice that sketch summation is associative (indeed commutative), and so we can use a reduction tree to do this in log time. Recall also that the sketches are offixed size. The client receives the summed sketch, which it reverses to determine the nmost popular keys. The final and intermediate sketches in the reduction tree could be cached in the DHT, associated with the keywordsused and a special “ sketch” keyword, and a timeout. In the common case, even the reduction tree could be avoided for most queries. 4. UPDATE-DRIVEN INDICES Update-driven indices have long-term persistence and make the workload involved with the popularity query indepen- dent of the workload for fetching objects. The key idea is that we distribute each of Sall,Sw1,Sw2,…using the DHT. We place the bucket ( i, j)o fs k e t c h S∗into the DHT using the key “ sketch *ij”. Visit is now more complex as it needs ultimately to up- date a bucket (actually mbuckets in parallel) that could be anywhere in the DHT. However, notice that Visit,w h i c h simply increments the bucket, is an associative and commu- tative operation. Thus, when a node sees two Visitsb e i n g routed through it, it can simply sum their varguments and emit a single Visit. Furthermore, if we permit the propaga- tion of Visits to be delayed (by giving each a deadline for when it must reach its bucket), the number of Visitst h a t we aggregate as we route them increases quickly. LookupPop is straightforward—the client merely needs to query for the sbuckets of Salland then estimate the popu- larity from the reconstructed sketch. Of course, that sketch could also be cached locally and/or in the DHT. QueryPop is a complex operation in an update-driven in- dex. The initial step is to reconstruct the sketches {Sw:w∈ querykeywords }. Unfortunately, it is not the case that if we sum these sketches we have the sketch that would have arisenif we had been managing a sketch for the query’s conjunc- tion of keywords. The most popular object for ( w 1,w2)m a y be very unpopular for w1andw2individually. It remains to be seen whether this loss of information is significant in practice for common workloads. We expect that a better way to answer the QueryPop query is to compute correlations of tracks (sequences of hash buckets) through pairs of sketches. The most highly corre- lated tracks (highest covariance) are most likely associatedwith the keys that are most popular for the combination of keywords. However, naively, m×s/msketches would re- sult in ( s/m) mtracks to be considered. We are working on dynamic programming approaches to this problem.1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16Positive shift Negative shift scale 20 positions Figure 1: Accuracy of k-ary sketches for Zipf-distributed objects. 5. EXPERIMENTS The effectiveness of our distributed popularity indices de- pends on the degree to which we can tolerate low accuracy, low precision answers for unpopular objects. Popularitymust be strongly skewed so that the top nobjects in terms ofVisits correspond to a large proportion of the visits even ifnis small. The popularity of documents and keywords tends to follow Zipf’s rule, which is a rank power law, meaning that the pro- portion of the total visits in the system captured by the ith ranked document, is ∝1/i α. Given such a distribution over keywords, how well do the top ndocuments recovered using reversible sketches capture the actual top ndocuments? Figure 1 shows the results of a simple experiment to ad- dress this question. Here, we inserted over 20 million keys with their popularity assigned according the Zipf distribu- tion with α=1.0. The most popular object was visited ∼10000 times. Reverse-hashing algorithms were used to re- cover the top 20 keys from the sketch and then compared to ground truth. The figure shows the reported shift in rank ofthe top 20 keys. Clearly, the shifts are very small except for the 4th ranked item. The three keys that were not really in the top 20 were in the top 30. The upshot of Figure 1 is that given keywords with a Zipf popularity rank distribution, a small sized sketch is quite capable of recovering the top nmost popular keys with little error. This bodes well for the distributed popularity indicesthat we have described here. 6. REFERENCES [1]Gupta, A., Sanghi, M., Dinda, P., and Bustamante, F. Magnolia: A novel dht architecture for keyword-based searching. Technical Report, Northwestern University (May 2005). [2]Gupta, A., Sanghi, M., Dinda, P., and Bustamante, F. Magnolia: A novel dht architecture for keyword-basedsearching (poster). NSDI 2005 (May 2005). [3]Krishnamurthy, B., Sen, S., Zhang, Y., and Chen, Y. Sketch-based change detection: Methods, evaluation, and applications. In P r o c .o fA C MS I G C O M MI M C (2003). [4]Mitzenmacher, M. Compressed bloom filters. IEEE/ACM Transactions on Networking 10 , 5 (Oct. 2002), 604–612. [5]Reynolds, P., and Vahdat, A. Efficient peer-to-peer keyword searching. In Middleware (2003), pp. 21–40. [6]Schweller, R., Gupta, A., Parsons, E., and Chen, Y. Reverse hashing for sketch-based one-pass change detection for high-speed networks. In ACM SIGCOMM IMC (2004).