As the domain name system (DNS) plays a critical role in malicious services and number of networks, especially small enterprise networks and home networks that are generally and poorly managed, grows rapidly, it is highly desired to outsource the malicious domain detection service to a third-party system that can aggregate information from multiple vantage points to perform detection. To this end, we propose DNSRadar, a system that explores the coexistence of domain cache-footprints distributed in all networks that participate in the outsourcing service. Bootstrapping from a list of prelabeled malicious domains, DNSRadar leverages link analysis techniques to infer maliciousness likelihood of unknown domains based on coexistence information. As DNSRadar only uses the existence of an unknown domain in a network for detection, privacy concerns have been drastically reduced. Both MapReduce and lightweight matrix analysis techniques are employed to implement DNSRadar, making scalability as a built-in feature. Taking advantage of a large number of open recursive DNS servers, we have performed extensive evaluation at scale. Experimental results have demonstrated that DNSRadar can efficiently detect ∼90% malicious domains given a low false positive rate of 1%. Of all these detected malicious domains, ∼30% are on average 6 days earlier than public DNS reputation services, indicating DNSRadar's great early detection capability.