Distributed Grid resource discovery (ReD) systems lack the ability to adapt efficiently to an increase in the number of attributes. The main contribution of this paper is a fast and scalable ReD mechanism, dubbed FaSReD, which composes a resource key via bit string encoding. We establish close-to-optimal FaSReD and a lower bound on the mean number of search hops under FaSReD. Through extensive simulation, our ReD is demonstrated to accommodate effectively an increase in the number of attributes with respect to such performance metrics as overlay hops, total messages, mean query response time, and throughput. FaSReD is further shown to outperform the leading prior distributed ReD range query schemes.