Progressive Join Algorithms Considering User Preference

Summary: Introduces ContourJoin, a progressive, preference-aware join algorithm that leverages contour lines to avoid expensive global sorting when delivering user-ordered join results. Empirically outperforms naive blocking and top-k RankJoin in both early-result latency and total computation. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 400
Venue: CIDR
Year: 2021
Pagerank: 5.5052493e-05
Overall Rank: 8,024 | 44.95%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Mengsu Ding (Chinese Academy of Sciences; University of Chinese Academy of Sciences)
2. Shimin Chen (Chinese Academy of Sciences; University of Chinese Academy of Sciences)
3. Nantia Makrynioti (Centrum Wiskunde & Informatica)
4. Stefan Manegold (Centrum Wiskunde & Informatica)

BibTeX Citation

@inproceedings{ding_cidr21,
        address = {Amsterdam, Netherlands},
        series = {{CIDR} '21},
        title = {{Progressive Join Algorithms Considering User Preference}},
        booktitle = {Proceedings of the {Conference} on {Innovative} {Data} {Systems} {Research}},
        author = {Ding, Mengsu and Chen, Shimin and Makrynioti, Nantia and Manegold, Stefan},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,593	Beyond Equi-joins: Ranking, Enumeration and Factorization	2021	VLDB	6.1552328e-05
11,312	QPJVis Demo: Quality-boost Progressive Join Query Processing System	2024	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 16 of 16 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
131	Ripple Joins for Online Aggregation	1999	SIGMOD	0.00030424509
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
1,134	A Framework for Expressing and Combining Preferences	2000	SIGMOD	0.00012035449
1,198	Overview of Data Exploration Techniques	2015	SIGMOD	0.00011706307
2,745	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	8.1747954e-05
4,212	Data Series Progressive Similarity Search with Probabilistic Quality Guarantees	2020	SIGMOD	6.8283344e-05
5,601	Optimal Join Algorithms Meet Top-k	2020	SIGMOD	6.1540123e-05
5,676	Scalable Progressive Analytics on Big Data in the Cloud	2013	VLDB	6.1251441e-05
5,737	Kyrix: Interactive Visual Data Exploration at Scale	2019	CIDR	6.1049023e-05
7,550	Processing Top-k Join Queries	2010	VLDB	5.6011318e-05
8,825	Creating Top Ranking Options in the Continuous Option and Preference Space	2019	VLDB	5.3616725e-05
9,017	PR-Join: A Non-Blocking Join Achieving Higher Early Result Rate with Statistical Guarantees	2010	SIGMOD	5.3311284e-05
9,524	Output-sensitive Evaluation of Prioritized Skyline Queries	2015	SIGMOD	5.2555551e-05
9,525	Towards Indexing Functions: Answering Scalar Product Queries	2014	SIGMOD	5.2555551e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,909	Improving Join Reorderability with Compensation Operators	2018	SIGMOD
2	499	Supporting Incremental Join Queries on Ranked Inputs	2001	VLDB
3	12,712	Scalable Continuous Query Processing by Tracking Hotspots	2006	VLDB
4	509	Supporting Top-k Join Queries in Relational Databases	2003	VLDB
5	6,412	Ranked Enumeration of Join Queries with Projections	2022	VLDB
6	5,467	On Producing Join Results Early	2003	PODS
7	7,550	Processing Top-k Join Queries	2010	VLDB
8	12,386	Efficient Rank Join with Aggregation Constraints	2011	VLDB
9	3,255	Processing Sliding Window Multi-Joins in Continuous Queries over Data Streams	2003	VLDB
10	2,787	Progressive Merge Join: A Generic and Non-Blocking Sort-Based Join Algorithm	2002	VLDB