common_entry_cmp PLACE_LEFT PLACE_RIGHT Set_gist_compress span_gist_consider_split span_gist_consistent Span_gist_consistent Span_gist_distance span_gist_double_sorting_split span_gist_fallback_split Span_gist_fetch span_gist_get_span Span_gist_penalty Span_gist_picksplit Span_gist_same Span_gist_union span_index_consistent_leaf span_index_recheck spanbounds_cmp_lower spanbounds_cmp_upper Spanset_gist_compress

span_gist_double_sorting_split() static void span_gist_double_sorting_split ( GistEntryVector *  entryvec, GIST_SPLITVEC *  v  ) static Double sorting split algorithm. The algorithm considers dividing spans into two groups. The first (left) group contains general left bound. The second (right) group contains general right bound. The challenge is to find upper bound of left group and lower bound of right group so that overlap of groups is minimal and ratio of distribution is acceptable. Algorithm finds for each lower bound of right group minimal upper bound of left group, and for each upper bound of left group maximal lower bound of right group. For each found pair span_gist_consider_split considers replacement of currently selected split with the new one. After that, all the entries are divided into three groups: 1) Entries which should be placed to the left group 2) Entries which should be placed to the right group 3) "Common entries" which can be placed to either group without affecting amount of overlap. The common spans are distributed by difference of distance from lower bound of common span to lower bound of right group and distance from upper bound of common span to upper bound of left group. For details see: "A new double sorting-based node splitting algorithm for R-tree", A. Korotkov http://syrcose.ispras.ru/2011/files/SYRCoSE2011_Proceedings.pdf#page=36