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: 8943
Venue: VLDB
Year: 2001
Pagerank: 0.00017431827
Overall Rank: 499 | 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
212	Efficient IR-Style Keyword Search over Relational Databases	2003	VLDB	0.000247733
509	Supporting Top-k Join Queries in Relational Databases	2003	VLDB	0.00017220967
623	An Optimal and Progressive Algorithm for Skyline Queries	2003	SIGMOD	0.00015684963
827	Minimal Probing: Supporting Expensive Predicates for Top-k Queries	2002	SIGMOD	0.00013769938
930	SPARK: Top-k Keyword Query in Relational Databases	2007	SIGMOD	0.0001312728
973	RankSQL: Query Algebra and Optimization for Relational Top-k Queries	2005	SIGMOD	0.00012874284
1,519	Top-k Query Evaluation with Probabilistic Guarantees	2004	VLDB	0.00010513777
1,728	Structured Querying of Web Text: A Technical Challenge	2007	CIDR	9.9098087e-05
1,759	Rank-aware Query Optimization	2004	SIGMOD	9.8160244e-05
2,211	Relational link-based ranking	2004	VLDB	8.9422791e-05
2,359	Integrating DB and IR Technologies: What is the Sound of One Hand Clapping? *	2005	CIDR	8.698016e-05
2,525	Answering Top-k Queries Using Views	2006	VLDB	8.4653166e-05
2,571	Ranking with Uncertain Scoring Functions: Semantics and Sensitivity Measures	2011	SIGMOD	8.4029939e-05
2,585	Evaluating Rank Joins with Optimal Cost	2008	PODS	8.3774452e-05
2,745	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	8.1747954e-05
2,813	KLEE: A Framework for Distributed Top-k Query Algorithms	2005	VLDB	8.0975254e-05
5,138	Robust and Efficient Algorithms for Rank Join Evaluation	2009	SIGMOD	6.3495536e-05
5,164	Efficient Approximation of Optimization Queries Under Parametric Aggregation Constraints	2003	VLDB	6.3372067e-05
5,593	Beyond Equi-joins: Ranking, Enumeration and Factorization	2021	VLDB	6.1552328e-05
5,601	Optimal Join Algorithms Meet Top-k	2020	SIGMOD	6.1540123e-05
7,185	Anytime Measures for Top-k Algorithms	2007	VLDB	5.6779179e-05
7,202	Sum-Max Monotonic Ranked Joins for Evaluating Top-K Twig Queries on Weighted Data Graphs	2007	VLDB	5.6755422e-05
7,299	Efficient and Generic Evaluation of Ranked Queries	2011	SIGMOD	5.6513289e-05
7,352	Boolean + Ranking: Querying a Database by K-Constrained Optimization	2006	SIGMOD	5.6353412e-05
7,550	Processing Top-k Join Queries	2010	VLDB	5.6011318e-05
8,024	Progressive Join Algorithms Considering User Preference	2021	CIDR	5.5052493e-05
8,028	On the Complexity of Package Recommendation Problems	2012	PODS	5.504636e-05
8,071	An Incremental Algorithm for Computing Ranked Full Disjunctions	2005	PODS	5.4935818e-05
9,497	Rank Join Queries in NoSQL Databases	2014	VLDB	5.2608378e-05
9,961	Threshold Queries in Theory and in the Wild	2022	VLDB	5.1879626e-05
11,183	Relational Algorithms for Top-k Query Evaluation	2024	SIGMOD	5.093636e-05
11,270	Searching Data Lakes for Nested and Joined Data	2024	VLDB	5.093636e-05
12,427	Finding Maximum Degrees in Hidden Bipartite Graphs	2010	SIGMOD	5.093636e-05
12,475	Building Ranked Mashups of Unstructured Sources with Uncertain Information	2010	VLDB	5.093636e-05
12,841	Searching on the Secondary Structure of Protein Sequences	2002	VLDB	5.093636e-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.0010828372
108	Optimizing Multi-Feature Queries for Image Databases	2000	VLDB	0.00033228866

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,622	Towards Efficient Random-Order Enumeration for Join Queries	2026	VLDB
2	5,593	Beyond Equi-joins: Ranking, Enumeration and Factorization	2021	VLDB
3	1,759	Rank-aware Query Optimization	2004	SIGMOD
4	12,386	Efficient Rank Join with Aggregation Constraints	2011	VLDB
5	7,286	Efficient Computation of Quantiles over Joins	2023	PODS
6	509	Supporting Top-k Join Queries in Relational Databases	2003	VLDB
7	6,412	Ranked Enumeration of Join Queries with Projections	2022	VLDB
8	3,017	Joining Ranked Inputs in Practice	2002	VLDB
9	7,550	Processing Top-k Join Queries	2010	VLDB
10	2,585	Evaluating Rank Joins with Optimal Cost	2008	PODS