Density-optimized Intersection-free Mapping and Matrix Multiplication for Join-Project Operations

Summary: DIM3 accelerates join-projects via intersection-free sparse/dense partitioning, optimized value-to-matrix mapping, and Join-Project-specific dense/sparse matrix multiplication. It extends to caching and Join-Aggregate/MJP, yielding 2.3–18× speedups. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: hcadc6e671e4c4f32
Venue: VLDB
Year: 2022
Pagerank: 6.1020763e-05
Overall Rank: 5,500 | 63.04%
DOI: 10.14778/3547305.3547326
PDF: Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

Authors

1. Zichun Huang (Institute of Computing Technology, Chinese Academy of Sciences)
2. Shimin Chen (Institute of Computing Technology, Chinese Academy of Sciences)

BibTeX Citation

@article{huang_vldb22,
        title = {{Density-optimized Intersection-free Mapping and Matrix Multiplication for Join-Project Operations}},
        author = {Huang, Zichun and Chen, Shimin},
        journal = {PVLDB},
        series = {{VLDB} '22},
        volume = {15},
        number = {10},
        pages = {2244--2256},
        doi = {10.14778/3547305.3547326},
        url = {https://doi.org/10.14778/3547305.3547326},
        year = {2022}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,576	Output-Optimal Algorithms for Join-Aggregate Queries	2025	PODS	5.7428578e-05
7,294	Computing the Difference of Conjunctive Queries Efficiently	2023	SIGMOD	5.5616228e-05
10,515	SPALM: A Sparsity-Pattern-Adaptive Library for Matrices	2026	SIGMOD	4.9769913e-05
11,095	Fast Matrix Multiplication meets the Submodular Width	2025	PODS	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 16 of 16 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
39	Efficiently Updating Materialized Views	1986	SIGMOD	0.00046583225
40	The Case for Learned Index Structures	2018	SIGMOD	0.00046363107
210	Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs	2009	VLDB	0.00024844328
251	Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited	2014	VLDB	0.00023136934
551	Computing Queries from Derived Relations	1985	VLDB	0.000165456
688	Cardinality Estimation Done Right: Index-Based Join Sampling	2017	CIDR	0.00014749318
726	Left-Deep Vs. Bushy Trees: An Analysis Of Strategy Spaces And Its Implications For Query Optimization	1991	SIGMOD	0.00014459508
920	Tradeoffs in Processing Complex Join Queries via Hashing in Multiprocessor Database Machines	1990	VLDB	0.00013075939
1,283	Managing Non-Volatile Memory in Database Systems	2018	SIGMOD	0.00011205832
1,465	Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities	2019	SIGMOD	0.00010572023
2,274	Transparent Mid-Tier Database Caching in SQL Server	2003	SIGMOD	8.7082344e-05
3,974	TCUDB: Accelerating Database with Tensor Processors	2022	SIGMOD	6.8848857e-05
3,983	Simplicity Done Right for Join Ordering	2021	CIDR	6.8722161e-05
5,491	Fast Join Project Query Evaluation using Matrix Multiplication	2020	SIGMOD	6.1067499e-05
7,295	Parallel Algorithms for Sparse Matrix Multiplication and Join-Aggregate Queries	2020	PODS	5.5612427e-05
7,368	Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries	2021	SIGMOD	5.5392867e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,154	Robust Join Processing with Diamond Hardened Joins	2024	VLDB
2	2,923	Leveraging Set Relations in Exact Set Similarity Join	2017	VLDB
3	1,619	Efficient Processing of Joins on Set-valued Attributes	2003	SIGMOD
4	7,351	A Scalable and Generic Approach to Range Joins	2022	VLDB
5	7,472	Parallel Algorithms for High-dimensional Proximity Joins	1997	VLDB
6	10,398	Towards Output-Optimal Uniform Sampling and Approximate Counting for Join-Project Queries	2026	PODS
7	7,295	Parallel Algorithms for Sparse Matrix Multiplication and Join-Aggregate Queries	2020	PODS
8	201	Efficient set joins on similarity predicates	2004	SIGMOD
9	6,569	Fast Matrix Multiplication for Query Processing	2024	PODS
10	5,491	Fast Join Project Query Evaluation using Matrix Multiplication	2020	SIGMOD