The Peer-to-Peer (P2P) service model is being intensely explored for creating scalable and robust designs for decentralized Internet-scale applications. A lookup service for finding resources within a P2P network is one of the key services in the model. Lookup queries in P2P applications can be precise queries based on resource identifiers or imprecise ones involving keywords or attributes associated with resources. Some recent P2P designs have tried to leverage the efficient key-based routing mechanism of structured P2P systems for efficient lookups. These systems support precise queries directly and efficiently. To support imprecise queries, they create an index that maps keywords or attributes to keys used for structured routing and is attribute-partitioned across peers, that is, the index entry for a given attribute is stored at the peer addressed by its key. This approach has certain drawbacks. First, maintaining these index partitions in the presence of network churn is expensive. Second, popular keywords/attributes may get mapped to low capacity peers that cannot cope with the load. Third, the queries that require intersection of large indices to be computed, can be quite expensive to resolve.