Finding Maximum Degrees in Hidden Bipartite Graphs

Summary: Adaptive, instance-optimal algorithm for finding the k highest-degree vertices in B of a hidden bipartite graph via edge-probing queries. Provides a tight constant-factor guarantee (≤2) within a broad solution class and shows practical query reductions (often near km+n). (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4364
Venue: SIGMOD
Year: 2010
Pagerank: 5.093636e-05
Overall Rank: 12,427 | 14.74%
DOI: 10.1145/1807167.1807263

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Yufei Tao (Chinese University of Hong Kong)
2. Cheng Sheng (Chinese University of Hong Kong)
3. Jianzhong Li (Harbin Engineering University)

BibTeX Citation

@inproceedings{tao_sigmod10,
        title = {{Finding Maximum Degrees in Hidden Bipartite Graphs}},
        author = {Tao, Yufei and Sheng, Cheng and Li, Jianzhong},
        series = {{SIGMOD} '10},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1807167.1807263},
        url = {https://dl.acm.org/doi/10.1145/1807167.1807263},
        year = {2010}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
5	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0010828372
499	Supporting Incremental Join Queries on Ranked Inputs	2001	VLDB	0.00017431827
509	Supporting Top-k Join Queries in Relational Databases	2003	VLDB	0.00017220967
601	Exact Indexing of Dynamic Time Warping	2002	VLDB	0.00015870156
792	Finding k-Dominant Skylines in High Dimensional Space	2006	SIGMOD	0.00013979615
2,585	Evaluating Rank Joins with Optimal Cost	2008	PODS	8.3774452e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,261	Index-based Optimal Algorithms for Computing Steiner Components with Maximum Connectivity	2015	SIGMOD
2	3,997	Efficient Bi-triangle Counting for Large Bipartite Networks	2021	VLDB
3	1,740	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB
4	321	Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems	2018	PODS
5	5,540	Efficiently Computing k-Edge Connected Components via Graph Decomposition	2013	SIGMOD
6	2,860	Efficient Maximal Biclique Enumeration for Large Sparse Bipartite Graphs	2022	VLDB
7	10,407	Theoretically and Practically Efficient Maximum Biclique Search	2026	SIGMOD
8	7,550	Processing Top-k Join Queries	2010	VLDB
9	809	Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins	2019	VLDB
10	5,370	Diversified Top-k Subgraph Querying in a Large Graph	2016	SIGMOD