在过去几年中，通过询问成对同类查询来恢复一组 $n$ 个点的潜在 $k$-聚类引起了广泛关注。给定查询 $S \subset U$，且 $|S|=2$，如果这两个点在同一聚类中，oracle 返回 "yes"，否则返回 "no"。对于自适应算法，查询复杂度已知为 $\Theta(nk)$，而非自适应算法则极为有限：即使对于 $k=3$，这样的算法也需要 $\Theta(n^2)$ 次查询，匹配了简单的上界。
然而，非自适应性是极其可取的，因为它允许并行查询。为了突破非自适应查询的二次瓶颈，我们研究了这个问题的自然推广——对于 $|S|$ 大于 $2$ 的子集查询，其中 oracle 返回与 $S$ 相交的聚类数量。
之前的研究获得了一个 $O(n)$ 查询的自适应算法，但非自适应算法的领域仍然完全未知。本文提出了第一个用于子集查询的非自适应聚类算法。我们的主要结果是一个非自适应算法，需进行 $O(n \times \log k \times (\log k + \log \log n)^2)$ 次查询，当 $k$ 为常数时，查询复杂度改善为 $O(n \times \log \log n)$。
除了非自适应性，我们还考虑了一些实用因素，例如对查询大小的限制 $s$。我们展示了 $\Theta(\max(n^2/s^2,n))$ 次查询是必要的，并获得了对于任何 $s \leq \sqrt{n}$ 的算法，使查询次数为 $\tilde{O}(n^2 k/s^2)$，对于任何 $s \leq n$ 的算法，使查询次数为 $\tilde{O}(n^2/s)$。最后，当聚类大致平衡且允许算法进行两轮自适应时，我们获得了改进的上界。
博主点评： 本文提出的非自适应聚类算法在理论上具有重要意义，尤其是在并行处理和查询效率方面。通过对查询复杂度的显著降低，推动了聚类算法的发展，同时也为实际应用提供了新的思路。尽管仍有改进空间，但其成果无疑为该领域的研究奠定了基础。