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.0818991e-05
Overall Rank: 5,522 | 62.99%
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,585	Output-Optimal Algorithms for Join-Aggregate Queries	2025	PODS	5.7238683e-05
7,311	Computing the Difference of Conjunctive Queries Efficiently	2023	SIGMOD	5.5432326e-05
10,581	SPALM: A Sparsity-Pattern-Adaptive Library for Matrices	2026	SIGMOD	4.9605343e-05
11,156	Fast Matrix Multiplication meets the Submodular Width	2025	PODS	4.9605343e-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.00046445099
40	The Case for Learned Index Structures	2018	SIGMOD	0.00046249672
212	Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs	2009	VLDB	0.00024786576
250	Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited	2014	VLDB	0.00023080446
553	Computing Queries from Derived Relations	1985	VLDB	0.00016493992
689	Cardinality Estimation Done Right: Index-Based Join Sampling	2017	CIDR	0.00014725904
728	Left-Deep Vs. Bushy Trees: An Analysis Of Strategy Spaces And Its Implications For Query Optimization	1991	SIGMOD	0.0001441771
921	Tradeoffs in Processing Complex Join Queries via Hashing in Multiprocessor Database Machines	1990	VLDB	0.00013036878
1,288	Managing Non-Volatile Memory in Database Systems	2018	SIGMOD	0.00011172386
1,444	Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities	2019	SIGMOD	0.00010616242
2,287	Transparent Mid-Tier Database Caching in SQL Server	2003	SIGMOD	8.6824091e-05
3,982	TCUDB: Accelerating Database with Tensor Processors	2022	SIGMOD	6.8663329e-05
3,995	Simplicity Done Right for Join Ordering	2021	CIDR	6.8530469e-05
5,514	Fast Join Project Query Evaluation using Matrix Multiplication	2020	SIGMOD	6.0866191e-05
7,313	Parallel Algorithms for Sparse Matrix Multiplication and Join-Aggregate Queries	2020	PODS	5.5428538e-05
7,387	Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries	2021	SIGMOD	5.5212177e-05

Semantically Similar Papers

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