Data sources, storage, computing resources and services are entities on Grids that require mechanisms for publication and lookup. A discovery service relies on efficient lookup to locate these objects from names or attributes. And on large-scale grids, these should be scalable and be able to support range queries and multicriteria searching. Trie-based approaches like the PHT and DPT, enable sophisticated queries while providing resilience to failures. In this paper, we propose a more efficient variant of the DPT called the Dynamic Prefix Graph (DPG). And we introduce an encoding scheme that allows DPGs to support both string partial matching and numerical range queries. A distributed algorithm for dynamic construction of DPGs is presented. We conduct simulation studies with the DPG under various data sets. And results demonstrate a reduction of up to 30% in logical hops when lookups are performed under DPGs compared to DPTs.