Finding Maximum Degrees in Hidden Bipartite Graphs

摘要

An (edge) hidden graph is a graph whose edges are not explicitly given. Detecting the presence of an edge requires expensive edge-probing queries. We consider the k most connected vertex problem on hidden bipartite graphs. Specifically, given a bipartite graph G with independent vertex sets B and W, the goal is to find the k vertices in B with the largest degrees using the minimum number of queries. This problem can be regarded as a top-k extension of a semi-join, and is encountered in many applications in practice (e.g., top-k spatial join with arbitrarily complex join predicates). If B and W have n and m vertices respectively, the number of queries needed to solve the problem is nm in the worst case. This, however, is a pessimistic estimate on how many queries are necessary on practical data. In fact, on some easy inputs, the problem can be efficiently settled with only km+n edges, which is significantly lower than nm for k 《 n. The huge difference between km + n and nm makes it interesting to design an adaptive algorithm that is guaranteed to achieve the best possible performance on every input G. We give such an algorithm, and prove that it is instance optimal among a broad class of solutions. This means that, for any G, our algorithm can perform more queries than the optimal solution (which is currently unknown) by only a constant factor, which can be shown to be at most 2. Extensive experiments demonstrate that, in practice, the number of queries required by our technique is far less than nm, and agrees with our theoretical findings very well.