Efficient Rank Join with Aggregation Constraints

Summary: Aggregation constraints enrich rank-join semantics, enabling user preferences in top-k queries. The paper develops deterministic and probabilistic algorithms that push constraints into rank-join rather than post-filtering, beating naive pipelines. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10375
Venue: VLDB
Year: 2011
Pagerank: 5.093636e-05
Overall Rank: 12,386 | 15.03%
DOI: 10.14778/3402707.3402754

Incoming Non-self Citations Over Time

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

Authors

1. Min Xie (University of British Columbia)
2. Laks V.S. Lakshmanan (University of British Columbia)
3. Peter T. Wood (Birkbeck, University of London)

BibTeX Citation

@article{xie_vldb11,
        title = {{Efficient Rank Join with Aggregation Constraints}},
        author = {Xie, Min and Lakshmanan, Laks V.S. and Wood, Peter T.},
        journal = {PVLDB},
        series = {{VLDB} '11},
        volume = {4},
        number = {11},
        pages = {1201--1212},
        doi = {10.14778/3402707.3402754},
        url = {https://doi.org/10.14778/3402707.3402754},
        year = {2011}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 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
76	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00037054261
509	Supporting Top-k Join Queries in Relational Databases	2003	VLDB	0.00017220967
973	RankSQL: Query Algebra and Optimization for Relational Top-k Queries	2005	SIGMOD	0.00012874284
1,124	Query Optimization by Predicate Move-Around	1994	VLDB	0.00012087356
1,519	Top-k Query Evaluation with Probabilistic Guarantees	2004	VLDB	0.00010513777
1,535	Exploratory Mining and Pruning Optimizations of Constrained Association Rules	1998	SIGMOD	0.00010463058
1,759	Rank-aware Query Optimization	2004	SIGMOD	9.8160244e-05
2,585	Evaluating Rank Joins with Optimal Cost	2008	PODS	8.3774452e-05
4,758	Constructing and Exploring Composite Items	2010	SIGMOD	6.521122e-05
5,138	Robust and Efficient Algorithms for Rank Join Evaluation	2009	SIGMOD	6.3495536e-05
5,640	Proximity Rank Join	2010	VLDB	6.1384844e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,138	Robust and Efficient Algorithms for Rank Join Evaluation	2009	SIGMOD
2	5,862	RankSQL: Supporting Ranking Queries in Relational Database Management Systems	2005	VLDB
3	10,576	Efficient Query Repair for Aggregate Constraints	2026	VLDB
4	5,640	Proximity Rank Join	2010	VLDB
5	499	Supporting Incremental Join Queries on Ranked Inputs	2001	VLDB
6	7,550	Processing Top-k Join Queries	2010	VLDB
7	2,585	Evaluating Rank Joins with Optimal Cost	2008	PODS
8	6,412	Ranked Enumeration of Join Queries with Projections	2022	VLDB
9	7,286	Efficient Computation of Quantiles over Joins	2023	PODS
10	1,759	Rank-aware Query Optimization	2004	SIGMOD