Supporting Incremental Join Queries on Ranked Inputs

Summary: Introduces J* for top-k incremental joins over multiple ranked inputs with arbitrary user-defined predicates, even without random access or unique keys. Supports indexed access, nested join hierarchies, ε-approximations, and includes optimality guarantees. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h5e4e589d6da7ec91
Venue: VLDB
Year: 2001
Pagerank: 0.00017093562
Overall Rank: 507 | 96.60%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Apostol Natsev (Duke University)
2. Yuan-Chi Chang (IBM)
3. John R. Smith (IBM)
4. Chung-Sheng Li (IBM)
5. Jeffrey Scott Vitter (Duke University)

BibTeX Citation

@article{natsev_vldb01,
        title = {{Supporting Incremental Join Queries on Ranked Inputs}},
        author = {Natsev, Apostol and Chang, Yuan-Chi and Smith, John R. and Li, Chung-Sheng and Vitter, Jeffrey Scott},
        journal = {PVLDB},
        series = {{VLDB} '01},
        year = {2001}
}

Incoming Citations (Sorted by Pagerank)

Showing 35 of 35 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
217	Efficient IR-Style Keyword Search over Relational Databases	2003	VLDB	0.00024454844
524	Supporting Top-k Join Queries in Relational Databases	2003	VLDB	0.00016902116
638	An Optimal and Progressive Algorithm for Skyline Queries	2003	SIGMOD	0.00015331662
840	Minimal Probing: Supporting Expensive Predicates for Top-k Queries	2002	SIGMOD	0.00013544367
942	SPARK: Top-k Keyword Query in Relational Databases	2007	SIGMOD	0.00012950177
962	RankSQL: Query Algebra and Optimization for Relational Top-k Queries	2005	SIGMOD	0.00012818013
1,535	Top-k Query Evaluation with Probabilistic Guarantees	2004	VLDB	0.00010326646
1,759	Structured Querying of Web Text: A Technical Challenge	2007	CIDR	9.7090189e-05
1,773	Rank-aware Query Optimization	2004	SIGMOD	9.6683429e-05
2,256	Relational link-based ranking	2004	VLDB	8.7407334e-05
2,397	Integrating DB and IR Technologies: What is the Sound of One Hand Clapping? *	2005	CIDR	8.5238625e-05
2,561	Answering Top-k Queries Using Views	2006	VLDB	8.2940439e-05
2,593	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	8.2429717e-05
2,615	Evaluating Rank Joins with Optimal Cost	2008	PODS	8.2217676e-05
2,621	Ranking with Uncertain Scoring Functions: Semantics and Sensitivity Measures	2011	SIGMOD	8.2130891e-05
2,874	KLEE: A Framework for Distributed Top-k Query Algorithms	2005	VLDB	7.9186028e-05
4,745	Optimal Join Algorithms Meet Top-k	2020	SIGMOD	6.4369578e-05
5,233	Robust and Efficient Algorithms for Rank Join Evaluation	2009	SIGMOD	6.2167391e-05
5,275	Efficient Approximation of Optimization Queries Under Parametric Aggregation Constraints	2003	VLDB	6.1985695e-05
5,487	Beyond Equi-joins: Ranking, Enumeration and Factorization	2021	VLDB	6.1085184e-05
7,329	Anytime Measures for Top-k Algorithms	2007	VLDB	5.5485926e-05
7,342	Sum-Max Monotonic Ranked Joins for Evaluating Top-K Twig Queries on Weighted Data Graphs	2007	VLDB	5.5464639e-05
7,396	Efficient and Generic Evaluation of Ranked Queries	2011	SIGMOD	5.5344583e-05
7,502	Boolean + Ranking: Querying a Database by K-Constrained Optimization	2006	SIGMOD	5.5063128e-05
7,621	Processing Top-k Join Queries	2010	VLDB	5.4808989e-05
8,054	Progressive Join Algorithms Considering User Preference	2021	CIDR	5.3978878e-05
8,190	On the Complexity of Package Recommendation Problems	2012	PODS	5.3791856e-05
8,241	An Incremental Algorithm for Computing Ranked Full Disjunctions	2005	PODS	5.3686457e-05
9,688	Rank Join Queries in NoSQL Databases	2014	VLDB	5.1403642e-05
10,157	Threshold Queries in Theory and in the Wild	2022	VLDB	5.0691578e-05
11,532	Relational Algorithms for Top-k Query Evaluation	2024	SIGMOD	4.9769913e-05
11,604	Searching Data Lakes for Nested and Joined Data	2024	VLDB	4.9769913e-05
12,724	Finding Maximum Degrees in Hidden Bipartite Graphs	2010	SIGMOD	4.9769913e-05
12,772	Building Ranked Mashups of Unstructured Sources with Uncertain Information	2010	VLDB	4.9769913e-05
13,137	Searching on the Secondary Structure of Protein Sequences	2002	VLDB	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 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.0010679903
111	Optimizing Multi-Feature Queries for Image Databases	2000	VLDB	0.00032668973

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,487	Beyond Equi-joins: Ranking, Enumeration and Factorization	2021	VLDB
2	11,077	Towards Efficient Random-Order Enumeration for Join Queries	2026	VLDB
3	1,773	Rank-aware Query Optimization	2004	SIGMOD
4	12,683	Efficient Rank Join with Aggregation Constraints	2011	VLDB
5	7,438	Efficient Computation of Quantiles over Joins	2023	PODS
6	524	Supporting Top-k Join Queries in Relational Databases	2003	VLDB
7	6,547	Ranked Enumeration of Join Queries with Projections	2022	VLDB
8	7,621	Processing Top-k Join Queries	2010	VLDB
9	3,051	Joining Ranked Inputs in Practice	2002	VLDB
10	2,615	Evaluating Rank Joins with Optimal Cost	2008	PODS