Many large-scale utility computing infrastructures comprise heterogeneous hardware and software resources. This raises the need for scalable resource selection services that identify resources that match application requirements. Such a service must provide an efficient lookup in spite of changing resource attributes such as disk size, changing application requirements such as installed software libraries, and changing system composition as resources join or leave. We present a fully decentralized, self-managing Resource Selection Service (RSS) algorithm by which resources autonomously select themselves when their attributes match a query. An application specifies what it expects from a resource by means of a conjunction of (attribute,value-range) pairs, which are matched against the attribute values of resources. The set of search attributes can also be updated online to reflect new requirements. We show that our solution scales in the number of resources and in the number of attributes, while being relatively insensitive to churn and other membership changes like node failures. Our RSS continuously self-adapts its routing structure in response to variations in the distribution of node attributes and queries. We show that this autonomous optimization maintains performance and availability in a long-lived service even when the set of application requirements used to select resources changes.