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.00017101297
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.00024465994
524	Supporting Top-k Join Queries in Relational Databases	2003	VLDB	0.00016909926
638	An Optimal and Progressive Algorithm for Skyline Queries	2003	SIGMOD	0.00015338893
838	Minimal Probing: Supporting Expensive Predicates for Top-k Queries	2002	SIGMOD	0.00013550235
942	SPARK: Top-k Keyword Query in Relational Databases	2007	SIGMOD	0.00012956137
961	RankSQL: Query Algebra and Optimization for Relational Top-k Queries	2005	SIGMOD	0.0001282305
1,535	Top-k Query Evaluation with Probabilistic Guarantees	2004	VLDB	0.00010331242
1,760	Structured Querying of Web Text: A Technical Challenge	2007	CIDR	9.7106555e-05
1,773	Rank-aware Query Optimization	2004	SIGMOD	9.6719067e-05
2,254	Relational link-based ranking	2004	VLDB	8.7448663e-05
2,396	Integrating DB and IR Technologies: What is the Sound of One Hand Clapping? *	2005	CIDR	8.5278724e-05
2,561	Answering Top-k Queries Using Views	2006	VLDB	8.2977193e-05
2,591	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	8.2468757e-05
2,614	Evaluating Rank Joins with Optimal Cost	2008	PODS	8.2255837e-05
2,620	Ranking with Uncertain Scoring Functions: Semantics and Sensitivity Measures	2011	SIGMOD	8.2168186e-05
2,874	KLEE: A Framework for Distributed Top-k Query Algorithms	2005	VLDB	7.9221111e-05
4,752	Optimal Join Algorithms Meet Top-k	2020	SIGMOD	6.434561e-05
5,229	Robust and Efficient Algorithms for Rank Join Evaluation	2009	SIGMOD	6.2196057e-05
5,269	Efficient Approximation of Optimization Queries Under Parametric Aggregation Constraints	2003	VLDB	6.2014805e-05
5,482	Beyond Equi-joins: Ranking, Enumeration and Factorization	2021	VLDB	6.111411e-05
7,327	Anytime Measures for Top-k Algorithms	2007	VLDB	5.5512161e-05
7,339	Sum-Max Monotonic Ranked Joins for Evaluating Top-K Twig Queries on Weighted Data Graphs	2007	VLDB	5.5490881e-05
7,394	Efficient and Generic Evaluation of Ranked Queries	2011	SIGMOD	5.5370795e-05
7,497	Boolean + Ranking: Querying a Database by K-Constrained Optimization	2006	SIGMOD	5.5089205e-05
7,615	Processing Top-k Join Queries	2010	VLDB	5.4834169e-05
8,048	Progressive Join Algorithms Considering User Preference	2021	CIDR	5.4004443e-05
8,183	On the Complexity of Package Recommendation Problems	2012	PODS	5.3817332e-05
8,234	An Incremental Algorithm for Computing Ranked Full Disjunctions	2005	PODS	5.3711847e-05
9,681	Rank Join Queries in NoSQL Databases	2014	VLDB	5.1427987e-05
10,153	Threshold Queries in Theory and in the Wild	2022	VLDB	5.0715586e-05
11,526	Relational Algorithms for Top-k Query Evaluation	2024	SIGMOD	4.9793485e-05
11,598	Searching Data Lakes for Nested and Joined Data	2024	VLDB	4.9793485e-05
12,718	Finding Maximum Degrees in Hidden Bipartite Graphs	2010	SIGMOD	4.9793485e-05
12,766	Building Ranked Mashups of Unstructured Sources with Uncertain Information	2010	VLDB	4.9793485e-05
13,131	Searching on the Secondary Structure of Protein Sequences	2002	VLDB	4.9793485e-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.0010679641
111	Optimizing Multi-Feature Queries for Image Databases	2000	VLDB	0.00032675259

Semantically Similar Papers

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