Processing Top-k Join Queries

Summary: Introduces incremental lower/upper-bound and expected-score computation for top-k join results under sorted or random tuple access. An adaptive table-access ordering minimizes wasted evaluation of partially explored candidates, accelerating branch-and-bound over web-accessible databases. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h7919d2c1bca71134
Venue: VLDB
Year: 2010
Pagerank: 5.4834169e-05
Overall Rank: 7,615 | 48.81%
DOI: 10.14778/1920841.1920949

Incoming Non-self Citations Over Time

Authors

1. Minji Wu (Rutgers University)
2. Laure Berti-Équille (University of Rennes)
3. Amélie Marian (Rutgers University)
4. Cecilia M. Procopiuc (AT&T)
5. Divesh Srivastava (AT&T)

BibTeX Citation

@article{wu_vldb10,
        title = {{Processing Top-k Join Queries}},
        author = {Wu, Minji and Berti-Équille, Laure and Marian, Amélie and Procopiuc, Cecilia M. and Srivastava, Divesh},
        journal = {PVLDB},
        series = {{VLDB} '10},
        volume = {3},
        number = {1},
        pages = {860--871},
        doi = {10.14778/1920841.1920949},
        url = {https://doi.org/10.14778/1920841.1920949},
        year = {2010}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,752	Optimal Join Algorithms Meet Top-k	2020	SIGMOD	6.434561e-05
5,482	Beyond Equi-joins: Ranking, Enumeration and Factorization	2021	VLDB	6.111411e-05
8,048	Progressive Join Algorithms Considering User Preference	2021	CIDR	5.4004443e-05
9,681	Rank Join Queries in NoSQL Databases	2014	VLDB	5.1427987e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 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.0010679641
507	Supporting Incremental Join Queries on Ranked Inputs	2001	VLDB	0.00017101297
524	Supporting Top-k Join Queries in Relational Databases	2003	VLDB	0.00016909926
587	Management of Probabilistic Data: Foundations and Challenges	2007	PODS	0.00015933201
1,365	A Unified Approach to Ranking in Probabilistic Databases	2009	VLDB	0.00010913898
1,535	Top-k Query Evaluation with Probabilistic Guarantees	2004	VLDB	0.00010331242
4,262	Maximally Joining Probabilistic Data	2007	PODS	6.6984258e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,545	Ranked Enumeration of Join Queries with Projections	2022	VLDB
2	12,599	Optimal Top-k Generation of Attribute Combinations based on Ranked Lists	2012	SIGMOD
3	3,566	Progressive and Selective Merge: Computing Top-K with Ad-hoc Ranking Functions	2007	SIGMOD
4	7,394	Efficient and Generic Evaluation of Ranked Queries	2011	SIGMOD
5	3,379	Ad-hoc Top-k Query Answering for Data Streams	2007	VLDB
6	507	Supporting Incremental Join Queries on Ranked Inputs	2001	VLDB
7	2,614	Evaluating Rank Joins with Optimal Cost	2008	PODS
8	643	Evaluating Top-k Selection Queries	1999	VLDB
9	524	Supporting Top-k Join Queries in Relational Databases	2003	VLDB
10	4,752	Optimal Join Algorithms Meet Top-k	2020	SIGMOD