We study the power of uniform sampling for k-Median in various metric spaces. We relate the query complexity for approximating k-Median, to a key parameter of the dataset, called the balancedness β∈ (0, 1] (with 1 being perfectly balanced). We show that any algorithm must make Ω(1 / β) queries to the point set in order to achieve O(1)-approximation for k-Median. This particularly implies existing constructions of coresets, a popular data reduction technique, cannot be query-efficient. On the oth…