In this paper, we address the problem of self-adaptation in internet-scale service-oriented systems. Services need to adapt by selecting the best neighboring services solely based on local, limited information. In such complex systems, the global significance of the various selection parameters dynamically changes. We introduce a novel metric measuring the distribution and potential impact of service properties affecting such selection parameters. We further present a formalism identifying the most significant properties based on aggregated service interaction data. We ultimately provide a ranking algorithm exploiting these dynamic interaction characteristics. Experimental evaluation demonstrates scalability and adaptiveness of our approach.