Join Dependency Testing, Loomis-Whitney Join, and Triangle Enumeration

Summary: JD testing NP-hard even for binary relations, resolving a long-open question (prior hardness required Omega(d)-arity) and ruling out efficient small-arity JD tests unless P=NP. New I/O-efficient JD-existence algorithm that settles Loomis-Whitney enumeration and gives optimal external-memory I/O bounds for triangle enumeration, improving PODS'14. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1652
Venue: PODS
Year: 2015
Pagerank: 6.4314032e-05
Overall Rank: 4,949 | 66.05%
DOI: 10.1145/2745754.2745768

Incoming Non-self Citations Over Time

Authors

1. Xiaocheng Hu (Chinese University of Hong Kong)
2. Miao Qiao (Chinese University of Hong Kong)
3. Yufei Tao (Chinese University of Hong Kong)

BibTeX Citation

@inproceedings{hu_pods15,
        address = {New York, NY, USA},
        series = {{PODS} '15},
        title = {{Join Dependency Testing, Loomis-Whitney Join, and Triangle Enumeration}},
        url = {https://dl.acm.org/doi/10.1145/2745754.2745768},
        doi = {10.1145/2745754.2745768},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Hu, Xiaocheng and Qiao, Miao and Tao, Yufei},
        year = {2015}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,187	Subgraph Matching: on Compression and Computation	2018	VLDB	8.9966682e-05
4,401	Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins	2016	PODS	6.7233577e-05
5,463	Cover or Pack: New Upper and Lower Bounds for Massively Parallel Joins	2021	PODS	6.2086169e-05
6,855	2-3 Cuckoo Filters for Faster Triangle Listing and Set Intersection	2017	PODS	5.753175e-05
11,635	Two-Attribute Skew Free, Isolated CP Theorem, and Massively Parallel Joins	2021	PODS	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
411	Worst-case Optimal Join Algorithms	2012	PODS	0.00018902089
2,183	The Input/Output Complexity of Triangle Enumeration	2014	PODS	9.0066814e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	13,241	A Less Costly Constraints Checking for Join Dependency	1984	VLDB
2	5,593	Beyond Equi-joins: Ranking, Enumeration and Factorization	2021	VLDB
3	2,436	Computing Local Sensitivities of Counting Queries with Joins	2020	SIGMOD
4	1,467	The Complexity of Evaluating Relational Queries	1983	PODS
5	13,155	A Polynomial Time Algorithm for Testing Implications of a Join Dependency and Embodied Functional Dependencies	1988	SIGMOD
6	5,854	Conjunctive Queries With Self-Joins, Towards a Fine-Grained Enumeration Complexity Analysis	2023	PODS
7	4,187	Maximally Joining Probabilistic Data	2007	PODS
8	8,047	Tight Fine-Grained Bounds for Direct Access on Join Queries	2022	PODS
9	411	Worst-case Optimal Join Algorithms	2012	PODS
10	3,453	On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms	2023	PODS