近似成員查詢（Approximate Membership Query, AMQ）資料結構廣泛應用於分散式系統、資料庫快取、生物資訊以及邊緣運算等領域。近期提出的Wormhole Filter（WF）作為一種高效能AMQ，透過採用「距離－指紋對（distance-fingerprint pair）」技術，在持久性記憶體（Persistent Memory, PM）上展現出優異的插入與刪除效能。然而，其負查詢（negative lookup）操作存在顯著的效能瓶頸，因為無論負載因子為何，皆需盲目掃描所有p個桶（buckets）。
為了解決此一限制，本論文提出三項系統性最佳化方法，統稱為WF+。首先為「提前終止（Early Exit）」，透過「空槽不變性（Empty-Slot Invariant）」設計，使查詢在遇到包含空槽的桶時即可立即終止並回傳負結果。為維持此不變性，本文重新設計刪除演算法，並提出一種新穎的「空洞移動（hole-shifting）」機制。其次為「空槽預過濾（Empty-Slot Pre-filter）」，利用類似 haszero16 的位元運算檢查，在進行精確比對前快速判斷是否可提前終止，有效降低高負載下的不必要記憶體存取。第三為「基於閾值的自適應模式（Threshold-based Adaptive Mode）」，根據負載因子動態關閉提前終止機制，以避免維護不變性所帶來的額外成本，確保在極端負載情況下仍具穩健效能。
實驗結果顯示，WF+在增量式寫入一次、多次讀取（Incremental Write-Once-Read Many, WORM）情境中展現優異的效能折衷。在最佳運作區間（負載因子約為50%）下，其負查詢吞吐量可達57 MOPS，約為原始WF（18 MOPS）的3.2倍，並顯著降低記憶體頻寬消耗。儘管在高負載（>70%）情況下，為維持結構緊湊性而對插入效能造成影響，但所提出的自適應機制可確保WF+在整體負載範圍內表現不劣於基準方法。此外，本論文亦探討資料緊湊性與現代硬體SIMD向量化之間的「SIMD複雜度倒置（SIMD-Complexity Inversion）」現象，並為未來邊緣運算環境中的過濾器設計提供重要的架構性指引。

Approximate Membership Query (AMQ) data structures are widely utilized in domains such as distributed systems, database caching, bioinformatics, and edge computing. The Wormhole Filter (WF),recently proposed as a high-performance AMQ, employs a distance-fingerprint pair technique to achieve outstanding insertion and deletion throughput on Persistent Memory (PM). However, its negative lookup operation suffers from a significant performance bottleneck, as it must blindly scan all p buckets regardless of the load factor.
To address this limitation, this thesis proposes three systematic optimizations, collectively referred to as WF+. The first is Early Exit, which leverages an ”Empty-Slot Invariant” to terminate a query immediately upon encountering a bucket containing an empty slot, thereby returning a negative result. To maintain this invariant, the deletion algorithm is comprehensively redesigned with a novel hole-shifting mechanism. The second is the Empty-Slot Pre-filter, which utilizes the haszero16-style bitwise check to rapidly check for termination conditions prior to exact matching, effectively reducing invalid memory accesses under high loads. The third is the Threshold-based Adaptive Mode, which dynamically disables the early exit mechanism based on the load factor to prevent excessive maintenance overhead, ensuring robust performance under extreme loads.
Experimental results demonstrate that WF+ exhibits an excellent performance trade-off in Incremental Write-Once-Read-Many (WORM) scenarios. Within the optimal operational margin of a 50% load factor, the negative lookup throughput of WF+ reaches 57 MOPS—approximately 3.2 times that of the original WF (18 MOPS)—while significantly saving memory bandwidth. Although maintaining structural compactness incurs a penalty on insertion throughput under high loads (> 70%), the threshold-based adaptive mode ensures that WF+ performs no worse than the baseline across the entire load spectrum. Furthermore, this thesis explores the ”SIMD-Complexity Inversion” phenomenon between data compactness and SIMD vectorization on modern hardware, providing crucial architectural guidelines for filter design in future edge computing environments.

[1] Alluxio. https://www.alluxio.io/, 2026. Accessed: 2026-07-07.
[2] Apache cassandra. https://cassandra.apache.org/_/index.html, 2026. Accessed: 2026-07-07.
[3] Michael A. Bender, Martín Farach-Colton, Rob Johnson, Russell Kraner, Bradley C. Kuszmaul, Dzejla Medjedovic, Pablo Montes, Pradeep Shetty, Richard P. Spillane, and Erez Zadok. Don’t thrash: How to cache your hash on flash. In Proceedings of the VLDB Endowment, volume 5, pages 1627–1637, 2012.
[4] Timo Bingmann et al. Cobs: A compact bit-sliced signature index. In Proceedings of the International Symposium on String Processing and Information Retrieval, pages 285–303. Springer, 2019.
[5] Burton H. Bloom. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 13:422–426, 1970.
[6] Flavio Bonomi, Michael Mitzenmacher, Rina Panigrahy, Sushil Singh, and George Varghese. An improved construction for counting bloom filters. In Proceedings of the Annual European Symposium on Algorithms, pages 684–695. Springer, 2006.
[7] Alex Breslow and Nuwan Jayasena. Morton filters: Faster, space-efficient cuckoo filters via biasing, compression, and decoupled logical sparsity. Proceedings of the VLDB Endowment, 11:1041–1055, 2018.
[8] Fay Chang et al. Bigtable: A distributed storage system for structured data. ACM Transactions on Computer Systems, 26:1–26, 2008.
[9] Niv Dayan and Moshe Twitto. Chucky: A succinct cuckoo filter for LSM-tree. In Proceedings of the International Conference on Management of Data (SIGMOD), pages 365–378, 2021.
[10] Peter C. Dillinger and Stefan Walzer. Ribbon filter: Practically smaller than Bloom and Xor. Proceedings of the VLDB Endowment, 16:886–899, 2022.
[11] Tomer Even, Guy Even, and Adam Morrison. Prefix filter: Practically and theoretically better than bloom. Proceedings of the VLDB Endowment, 15:1311–1323, 2022.
[12] Bin Fan, Dave G. Andersen, Michael Kaminsky, and Michael Mitzenmacher. Cuckoo filter: Practically better than Bloom. In Proceedings of the 10th ACM International Conference on Emerging Networking Experiments and Technologies (CoNEXT), pages 75–88. ACM, 2014.
[13] Thomas Mueller Graf and Daniel Lemire. XOR filters: Faster and smaller than Bloom and cuckoo filters. Journal of Experimental Algorithmics, 25:1–16, 2020.
[14] Rong Gu et al. Adaptive online cache capacity optimization via lightweight working set size estimation at scale. Proceedings of the USENIX Annual Technical Conference, pages 467–484, 2023.
[15] Gaurav Gupta et al. Fast processing and querying of 170tb of genomics data via a repeated and merged bloom filter (rambo). In Proceedings of the International Conference on Management of Data (SIGMOD), pages 2226–2234, 2021.
[16] Donald E. Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching. Addison-Wesley, 2nd edition, 1998.
[17] Harald Lang, Thomas Mühlbauer, Florian Funke, Peter Boncz, Thomas Neumann, and Alfons Kemper. Performance-optimal filtering: Bloom overtakes cuckoo at high throughput. Proceedings of the VLDB Endowment, 12:502–515, 2019.
[18] Leveldb. https://github.com/google/leveldb, 2026. Accessed: 2026-07-07.
[19] Lailong Luo, Pengtao Fu, Shangsen Li, Deke Guo, Qianzhen Zhang, and Huaimin Wang. Ark Filter: A General and Space-Efficient Sketch for Network Flow Analysis. IEEE/ACM Transactions on Networking, 31, December 2023.
[20] J. H. Mun et al. LSM-trees under (memory) pressure. In Proceedings of the International Workshop on Accelerating Analytics and Data Management Systems Using Modern Processor and Storage Architectures, pages 23–35, 2022.
[21] H. Oh et al. Anifilter: Parallel and failure-atomic cuckoo filter for nonvolatile memories. In Proceedings of the European Conference on Computer Systems (EuroSys),pages 1–15, 2020.
[22] Prashant Pandey et al. Vector quotient filters: Overcoming the time/space tradeoff in filter design. In Proceedings of the International Conference on Management of Data(SIGMOD), pages 1386–1399, 2021.
[23] E. Prakasam and A. Manoharan. A cache efficient one hashing blocked bloom filter(ohbb) for random strings and the k-mer strings in dna sequence. Symmetry, 14:1–24,2022.
[24] Felix Putze, Peter Sanders, and Johannes Singler. Cache-, hash- and space-efficient bloom filters. In Proceedings of Experimental Algorithms, pages 108–121. Springer,2007.
[25] Facebook/rocksdb: A library that provides an embeddable, persistent key-value store for fast storage. https://github.com/facebook/rocksdb, 2026. Accessed: 2026-07-07.
[26] Scylladb. https://www.scylladb.com/, 2026. Accessed: 2026-07-07.
[27] TiKV is a highly scalable, low latency, and easy to use key-value database. https://tikv.org/, 2026. Accessed: 2026-07-07.
[28] Hancheng Wang, Haipeng Dai, Shusen Chen, Meng Li, Rong Gu, Youyou Lu, Chengxun Wu, Jiaqi Zheng, Lexi Xu, and Guihai Chen. Parallel wormhole filters:High-performance approximate membership query data structures for persistent memory. IEEE Transactions on Parallel and Distributed Systems, 36:2229–2246, nov 2025.
[29] Hancheng Wang, Haipeng Dai, Rong Gu, Youyou Lu, Jiaqi Zheng, Jingsong Dai, Shusen Chen, Zhiyuan Chen, Shuaituan Li, and Guihai Chen. Wormhole filters: Caching your hash on persistent memory. In Proceedings of the Nineteenth European Conference on Computer Systems (EuroSys ’24), pages 456–471. ACM, 2024.
[30] Hanhua Wang et al. Bamboo filters: Make resizing smooth and adaptive. IEEE/ACM Transactions on Networking, 32:3776–3791, 2024.
[31] Mingxin Wang et al. Vacuum filters: More space-efficient and faster replacement for bloom and cuckoo filters. Proceedings of the VLDB Endowment, 13:197–210, 2019.
[32] Implementation of the Wormhole filter. https://github.com/wanghanchengchn/wormholefilters, 2026. Accessed: 2026-07-07.