{'fraction_non_alphanumeric': 0.011283497884344146, 'fraction_numerical': 0.0, 'mean_word_length': 5.142857142857143, '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}}
A hybrid split strategy for k-d-tree based access structures G⃗

With spatial access structures the split strategy determining how the objects stored in an overflowing bucket are distributed over two buckets. is crucial for the performance and robustness. Two categories of split strategies can be distinguished: Data dependent split strategies depend only on the objects stored in the bucket to be split. Distribution dependent split strategies choose the split dimension and the split position independently of the objects actually stored in the bucket to be split based on an hypothesis about the object distribution. Unfortunately both types of split strategies have specific drawbacks. For a distribution dependent split strategy a sound hypothesis for the spatial distribution of the objects is needed in advance and with data dependent split strategies the directory tree becomes extremely unbalanced for insertions in a geometrically presorted order. In this paper we present a hybrid split strategy which tries to combine the advantages of both types of split strategies. Normally it adapts the behavior of a data dependent split st.rategy, but when the risk of a degeneration of the access structure is detected, it mutates to a distribution dependent split strategy. We will show that this hybrid split strategy is robust with respect to skew distributions and with respect to insertions in presorted order.