{'fraction_non_alphanumeric': 0.03299203640500569, 'fraction_numerical': 0.004550625711035267, 'mean_word_length': 5.616541353383458, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
DeltaTree: A Locality-aware Concurrent Search Tree

Like other fundamental abstractions for high-performance computing, search trees need to support both high concurrency and data locality. However, existing locality-aware search trees based on the van Emde Boas layout (vEB-based trees), poorly support concurrent (update) operations. We present DeltaTree, a practical locality-aware concurrent search tree that integrates both locality-optimization techniques from vEB-based trees, and concurrency optimization techniques from highly-concurrent search trees. As a result, DeltaTree minimizes data transfer from memory to CPU and supports high concurrency. Our experimental evaluation shows that DeltaTree is up to 50% faster than highly concurrent B-trees on a commodity Intel high performance computing (HPC) platform and up to 65% faster on a commodity ARM embedded platform.