Divide, Predict, Conquer: Adaptive Internet-wide Service Discovery with Limited Seeds

To address the challenge of severe reliance on massive prior knowledge (seeds) and low efficiency in Internet-wide service discovery, this project proposes SPADE, an efficient prediction and discovery method featuring adaptivity and divide-and-conquer. This method first acquires a limited number of high-value seeds from target hosts through a multi-level adaptive sampling strategy. Subsequently, drawing on data mining concepts, it progressively extracts two-layer service deployment features using a divide-and-conquer strategy and executes multi-layer predictions in stages. Experiments show that SPADE achieves over 94% Top-1 hit rate and coverage while consuming only 0.15%-1% of the seed volume required by existing state-of-the-art methods. Furthermore, the method accelerates the discovery speed by 219 to 805 times, completing an Internet-wide prediction covering hundreds of millions of hosts within 7 minutes.

Recommended citation: Daguo Cheng, Zedong Jia, Ying Liu, Lin He, Le Gai, et al. "Divide, Predict, Conquer: Adaptive Internet-wide Service Discovery with Limited Seeds." INFOCOM 2026.