2024/09/17 by Black, Hadley, Euiwoong Lee, Lee, Euiwoong +4 · 3 citations
Computer Science · #Data Mining Algorithms and Applications #Data Management and Algorithms #Advanced Clustering Algorithms Research
paper · pdf · doi:10.48550/arxiv.2409.10908
Recovering the underlying k-clustering of a set U of n points by asking pair-wise same-cluster queries has garnered significant interest in the past few years. Given a query S ⊂ U, |S|=2, the oracle returns "yes" if the points are in the same cluster and "no" otherwise. For adaptive algorithms, the query complexity is known to be Θ(nk), while non-adaptive algorithms are extremely limited: even for k=3, such algorithms require Ω(n2) queries, matching the trivial upper bound. However, non-adaptivity is highly desirable since it allows queries to be asked in parallel. To break the quadratic barrier for non-adaptive queries, we study a natural generalization of this problem to subset queries for |S|>2, where the oracle returns the number of clusters intersecting S. Previous work obtained an O(n) query adaptive algorithm, but the realm of non-adaptive algorithms remained completely unknown. In this paper, we give the first non-adaptive algorithms for clustering with subset queries. Our main result is a non-adaptive algorithm making O(n log k ⋅ (log k + loglog n)2) queries, improving to O(n log log n) when k is constant. In addition to non-adaptivity, we make other practical considerations, such as enforcing a bound, s, on the query size. We show Ω(max(n2/s2,n)) queries are necessary and obtain algorithms making \smash\widetildeO(n2k/s2) queries for any s ≤ √(n) and \smash\widetildeO(n2/s) queries for any s ≤ n. Finally, we obtain improved upper bounds when the clusters are roughly balanced, and when the algorithm is allowed two rounds of adaptivity.