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.00017061618
Overall Rank: 511 | 96.58%
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.00024417824
505	Supporting Top-k Join Queries in Relational Databases	2003	VLDB	0.00017162373
640	An Optimal and Progressive Algorithm for Skyline Queries	2003	SIGMOD	0.00015286314
840	Minimal Probing: Supporting Expensive Predicates for Top-k Queries	2002	SIGMOD	0.00013521251
941	RankSQL: Query Algebra and Optimization for Relational Top-k Queries	2005	SIGMOD	0.00012938573
947	SPARK: Top-k Keyword Query in Relational Databases	2007	SIGMOD	0.00012910239
1,539	Top-k Query Evaluation with Probabilistic Guarantees	2004	VLDB	0.00010292787
1,712	Rank-aware Query Optimization	2004	SIGMOD	9.7961248e-05
1,769	Structured Querying of Web Text: A Technical Challenge	2007	CIDR	9.6796356e-05
2,264	Relational link-based ranking	2004	VLDB	8.7252155e-05
2,406	Integrating DB and IR Technologies: What is the Sound of One Hand Clapping? *	2005	CIDR	8.4962449e-05
2,566	Answering Top-k Queries Using Views	2006	VLDB	8.2679821e-05
2,602	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	8.2157154e-05
2,625	Evaluating Rank Joins with Optimal Cost	2008	PODS	8.1948138e-05
2,628	Ranking with Uncertain Scoring Functions: Semantics and Sensitivity Measures	2011	SIGMOD	8.1859431e-05
2,880	KLEE: A Framework for Distributed Top-k Query Algorithms	2005	VLDB	7.8948229e-05
4,730	Optimal Join Algorithms Meet Top-k	2020	SIGMOD	6.4313418e-05
5,254	Robust and Efficient Algorithms for Rank Join Evaluation	2009	SIGMOD	6.1964074e-05
5,285	Efficient Approximation of Optimization Queries Under Parametric Aggregation Constraints	2003	VLDB	6.1819623e-05
5,506	Beyond Equi-joins: Ranking, Enumeration and Factorization	2021	VLDB	6.0883761e-05
7,348	Anytime Measures for Top-k Algorithms	2007	VLDB	5.5302579e-05
7,362	Sum-Max Monotonic Ranked Joins for Evaluating Top-K Twig Queries on Weighted Data Graphs	2007	VLDB	5.5281595e-05
7,413	Efficient and Generic Evaluation of Ranked Queries	2011	SIGMOD	5.516158e-05
7,521	Boolean + Ranking: Querying a Database by K-Constrained Optimization	2006	SIGMOD	5.4881075e-05
7,637	Processing Top-k Join Queries	2010	VLDB	5.4630004e-05
8,071	Progressive Join Algorithms Considering User Preference	2021	CIDR	5.3800399e-05
8,207	On the Complexity of Package Recommendation Problems	2012	PODS	5.3613986e-05
8,259	An Incremental Algorithm for Computing Ranked Full Disjunctions	2005	PODS	5.351182e-05
9,717	Rank Join Queries in NoSQL Databases	2014	VLDB	5.1233669e-05
10,192	Threshold Queries in Theory and in the Wild	2022	VLDB	5.052396e-05
11,581	Relational Algorithms for Top-k Query Evaluation	2024	SIGMOD	4.9605343e-05
11,651	Searching Data Lakes for Nested and Joined Data	2024	VLDB	4.9605343e-05
12,767	Finding Maximum Degrees in Hidden Bipartite Graphs	2010	SIGMOD	4.9605343e-05
12,815	Building Ranked Mashups of Unstructured Sources with Uncertain Information	2010	VLDB	4.9605343e-05
13,178	Searching on the Secondary Structure of Protein Sequences	2002	VLDB	4.9605343e-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.0010688884
110	Optimizing Multi-Feature Queries for Image Databases	2000	VLDB	0.00032662513

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,138	Towards Efficient Random-Order Enumeration for Join Queries	2026	VLDB
2	5,506	Beyond Equi-joins: Ranking, Enumeration and Factorization	2021	VLDB
3	1,712	Rank-aware Query Optimization	2004	SIGMOD
4	12,726	Efficient Rank Join with Aggregation Constraints	2011	VLDB
5	7,459	Efficient Computation of Quantiles over Joins	2023	PODS
6	505	Supporting Top-k Join Queries in Relational Databases	2003	VLDB
7	6,557	Ranked Enumeration of Join Queries with Projections	2022	VLDB
8	3,059	Joining Ranked Inputs in Practice	2002	VLDB
9	7,637	Processing Top-k Join Queries	2010	VLDB
10	2,625	Evaluating Rank Joins with Optimal Cost	2008	PODS