Assessing similarity of policies is crucial in a variety of scenarios, such as finding the cloud service providers which satisfy users' privacy concerns, or finding collaborators which have matching security and privacy settings. Existing approaches to policy similarity analysis are mainly based on logical reasoning and Boolean function comparison. Such approaches are computationally expensive and do not scale well for large heterogeneous distributed environments (like the cloud). In this paper, we propose a policy similarity measure as a lightweight ranking approach to help one party quickly locate parties with potentially similar policies. In particular, given a policy P, the similarity measure assigns a ranking (similarity score) to each policy compared with P. We formally define the measure by taking into account various factors and prove several important properties of the measure. Our extensive experimental study demonstrates the efficiency and practical value of our approach. © 1989-2012 IEEE.