Finding maximum degrees in hidden bipartite graphs
Refereed conference paper presented and published in conference proceedings

Times Cited
Altmetrics Information

Other information
AbstractAn (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. © 2010 ACM.
All Author(s) ListTao Y., Sheng C., Li J.
Name of Conference2010 International Conference on Management of Data, SIGMOD '10
Start Date of Conference06/06/2010
End Date of Conference11/06/2010
Place of ConferenceIndianapolis, IN
Country/Region of ConferenceUnited States of America
Detailed descriptionorganized by ACM,
Pages891 - 902
LanguagesEnglish-United Kingdom
Keywordsbipartite graph, competitive analysis, instance optimality, maximum degree

Last updated on 2021-24-02 at 00:35