Prune Early, Intersect Fast: PRISM, a Prefix-based Radix Integer Set with Morphing Nodes

Summary: PRISM indexes 64-bit integer sets as prefix tries with occupancy bitmaps, pruning absent ranges early and using SIMD for leaf-level intersections; occupancy-adaptive morphing nodes cut sparse-data memory by up to 8×. It delivers the fastest intersection-heavy performance across three real workloads, outperforming compressed bitmaps and general-purpose containers. (summarized by gpt-6-luna on Oct 08 2026)

Paper ID: h2ba37c49954c5134
Venue: VLDB
Year: 2027
Pagerank: 4.9769913e-05
Overall Rank: 10,354 | 30.41%
DOI: 10.14778/3845598.3845603
PDF: Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Adrian Riedl (Technical University of Munich)
2. Thomas Neumann (Technical University of Munich)

BibTeX Citation

@article{riedl_vldb27,
        title = {{Prune Early, Intersect Fast: PRISM, a Prefix-based Radix Integer Set with Morphing Nodes}},
        author = {Riedl, Adrian and Neumann, Thomas},
        journal = {PVLDB},
        series = {{VLDB} '27},
        volume = {20},
        number = {1},
        pages = {53--65},
        doi = {10.14778/3845598.3845603},
        url = {https://doi.org/10.14778/3845598.3845603},
        year = {2027}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1,212	A Seven-Dimensional Analysis of Hashing Methods and its Implications on Query Processing	2016	VLDB	0.00011521857
1,853	Speeding Up Set Intersections in Graph Algorithms using SIMD Instructions	2018	SIGMOD	9.499042e-05
2,011	An Experimental Study of Bitmap Compression vs. Inverted List Compression	2017	SIGMOD	9.1924806e-05
2,120	Fast Set Intersection in Memory	2011	VLDB	9.0077549e-05
2,977	Faster Set Intersection with SIMD instructions by Reducing Branch Mispredictions	2015	VLDB	7.7881518e-05
7,541	HERO: A Hierarchical Set Partitioning and Join Framework for Speeding up the Set Intersection Over Graphs	2024	SIGMOD	5.4977034e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,853	Speeding Up Set Intersections in Graph Algorithms using SIMD Instructions	2018	SIGMOD
2	7,032	Efficient Similarity Join and Search on Multi-Attribute Data	2015	SIGMOD
3	965	Can We Beat the Prefix Filtering? An Adaptive Framework for Similarity Join and Search	2012	SIGMOD
4	6,195	Prefix Filter: Practically and Theoretically Better Than Bloom	2022	VLDB
5	13,904	PRISM: Concept-preserving Summarization of Top-K Social Image Search Results	2015	VLDB
6	2,120	Fast Set Intersection in Memory	2011	VLDB
7	277	FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs	2010	SIGMOD
8	8,685	PrismX: A Single-Machine System for Querying Big Graphs	2024	VLDB
9	9,352	Prism: Private Verifiable Set Computation over Multi-Owner Outsourced Databases	2021	SIGMOD
10	2,977	Faster Set Intersection with SIMD instructions by Reducing Branch Mispredictions	2015	VLDB