Browsing by Author "Gopalakrishnan, Vijay"
Now showing 1 - 4 of 4
Results Per Page
Sort Options
Item Adaptive Replication in Peer-to-Peer Systems(2003-08-01) Gopalakrishnan, Vijay; Silaghi, Bujor; Bhattacharjee, Bobby; Keleher, PeteRecent work on peer-to-peer systems has demonstrated the ability to deliver low latencies and good load balance when demand for data items is relatively uniform. We describe a lightweight, adaptive, and system-neutral replication protocol, LAR, that delivers low latencies and good load balance even when demand is heavily skewed. Simulation of LAR in combination with both the Chord and TerraDir systems shows that LAR quickly adapts to non-uniformity in both the underlying system topology and in the input stream. Further, we demonstrate better performance than functionally similar application-layer protocols, using an order of magnitude less network bandwidth. (UMIACS-TR-2003-83)Item Efficient Peer-to-Peer Namespace Searches(2004-04-19) Gopalakrishnan, Vijay; Bhattacharjee, Bobby; Chawathe, Sudarshan; Keleher, PeteIn this paper we describe new methods for efficient and exact search (keyword and full-text) in distributed namespaces. Our methods can be used in conjunction with existing distributed lookup schemes, such as Distributed Hash Tables, and distributed directories. We describe how indexes for implementing distributed searches can be efficiently created, located, and stored. We describe techniques for creating approximate indexes that can be used to bound the space requirement at individual hosts; such techniques are particularly useful for full-text searches that may require a very large number of individual indexes to be created and maintained. Our methods use a new distributed data structure called the view tree. View trees can be used to efficiently cache and locate results from prior queries. We describe how view trees are created, and maintained. We present experimental results, using large namespaces and realistic data, showing that the techniques introduced in this paper can reduce search overheads (both network and processing costs) by more than an order of magnitude. (UMIACS-TR-2004-13)Item Ranking Search Results in Peer-to-Peer Systems(2006-01) Gopalakrishnan, Vijay; Morselli, Ruggero; Bhattacharjee, Bobby; Keleher, Peter; Srinivasan, AravindP2P deployments are a natural infrastructure for building distributed search networks. Proposed systems support locating and retrieving all results, but lack the information necessary to rank them. Users, however, are primarily interested in the most relevant, and not all possible results. Using random sampling, we extend a class of well-known information retrieval ranking algorithms such that they can be applied in this distributed setting. We analyze the overhead of our approach, and quantify exactly how our system scales with increasing number of documents, system size, document to node mapping (uniform versus non-uniform), and types of queries (rare versus popular terms). Our analysis and simulations show that a) these extensions are efficient, and can scale with little overhead to large systems, and b) the accuracy of the results obtained using distributed ranking is comparable to a centralized implementation.Item System support for keyword-based search in structured Peer-to-Peer systems(2006-08-07) Gopalakrishnan, Vijay; Bhattacharjee, Bobby; Keleher, Pete; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)In this dissertation, we present protocols for building a distributed search infrastructure over structured Peer-to-Peer systems. Unlike existing search engines which consist of large server farms managed by a centralized authority, our approach makes use of a distributed set of end-hosts built out of commodity hardware. These end-hosts cooperatively construct and maintain the search infrastructure. The main challenges with distributing such a system include node failures, churn, and data migration. Localities inherent in query patterns also cause load imbalances and hot spots that severely impair performance. Users of search systems want their results returned quickly, and in ranked order. Our main contribution is to show that a scalable, robust, and distributed search infrastructure can be built over existing Peer-to-Peer systems through the use of techniques that address these problems. We present a decentralized scheme for ranking search results without prohibitive network or storage overhead. We show that caching allows for efficient query evaluation and present a distributed data structure, called the View Tree, that enables efficient storage, and retrieval of cached results. We also present a lightweight adaptive replication protocol, called LAR that can adapt to different kinds of query streams and is extremely effective at eliminating hotspots. Finally, we present techniques for storing indexes reliably. Our approach is to use an adaptive partitioning protocol to store large indexes and employ efficient redundancy techniques to handle failures. Through detailed analysis and experiments we show that our techniques are efficient and scalable, and that they make distributed search feasible.