Though resource discovery is a fundamental requirement in collaborative peer-to-peer, grid, and cloud computing, very little is known about resource/query characteristics and their impact on resource discovery. Fundamental design choices for distributed resource advertising and querying are evaluated in the context of existing practical systems. First, a generic model for cost of resource discovery is presented. Second, multi-attribute resource and query characteristics from Planet-Lab and SETI@home are presented. We observe that attributes of both resources and queries are highly skewed, correlated, queries are less specific, and Generalized Pareto distribution is suitable for capturing the distribution of most dynamic attributes and their rate of change. Based on these observations, different design choices are evaluated for resource discovery in terms of their cost of advertising/querying, latency, load balancing, and routing table size. The findings indicate that superpeer-based architectures have the potential to support large-scale resource aggregation as they simultaneously balance the cost and load.