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.
maximum degree bipartite graph instance optimality competitive analysis