2-3 Cuckoo Filters for Faster Triangle Listing and Set Intersection

Summary: Proposes 2-3 cuckoo filters/tables: a two-out-of-three power-of-choices variant storing items in two of three buckets so any intersection item shares a location, enabling O(1) expected updates. Applies to set intersection and triangle listing with output-sensitive RAM time o(n)+O(k) and improved arboricity-aware I/O bounds. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: hf323fe5c32a8e216
Venue: PODS
Year: 2017
Pagerank: 5.6341313e-05
Overall Rank: 6,957 | 53.23%
DOI: 10.1145/3034786.3056115

Incoming Non-self Citations Over Time

Authors

1. David Eppstein (University of California Irvine)
2. Michael T. Goodrich (University of California Irvine)
3. Michael Mitzenmacher (Harvard University)
4. Manuel R. Torres (University of California Irvine)

BibTeX Citation

@inproceedings{eppstein_pods17,
        address = {New York, NY, USA},
        series = {{PODS} '17},
        title = {{2-3 Cuckoo Filters for Faster Triangle Listing and Set Intersection}},
        url = {https://dl.acm.org/doi/10.1145/3034786.3056115},
        doi = {10.1145/3034786.3056115},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Eppstein, David and Goodrich, Michael T. and Mitzenmacher, Michael and Torres, Manuel R.},
        year = {2017}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,844	Morton Filters: Faster, Space-Efficient Cuckoo Filters via Biasing, Compression, and Decoupled Logical Sparsity	2018	VLDB	9.5159229e-05
9,653	Indexing for Keyword Search with Structured Constraints	2023	PODS	5.1453267e-05
10,202	Sage: Parallel Semi-Asymmetric Graph Algorithms for NVRAMs	2020	VLDB	5.0610409e-05

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
600	Massive Graph Triangulation	2013	SIGMOD	0.00015740352
2,215	The Input/Output Complexity of Triangle Enumeration	2014	PODS	8.8194236e-05
5,069	Join Dependency Testing, Loomis-Whitney Join, and Triangle Enumeration	2015	PODS	6.2890683e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,712	Vector Quotient Filters: Overcoming the Time/Space Trade-Off in Filter Design	2021	SIGMOD
2	2,316	Fast Set Intersection in Memory	2011	VLDB
3	2,019	Speeding Up Set Intersections in Graph Algorithms using SIMD Instructions	2018	SIGMOD
4	5,232	Better Algorithms for Counting Triangles in Data Streams	2016	PODS
5	1,844	Morton Filters: Faster, Space-Efficient Cuckoo Filters via Biasing, Compression, and Decoupled Logical Sparsity	2018	VLDB
6	1,121	Counting and Sampling Triangles from a Graph Stream	2013	VLDB
7	6,192	Prefix Filter: Practically and Theoretically Better Than Bloom	2022	VLDB
8	8,580	Conditional Cuckoo Filters	2021	SIGMOD
9	600	Massive Graph Triangulation	2013	SIGMOD
10	2,215	The Input/Output Complexity of Triangle Enumeration	2014	PODS