liveBook · Manning

Split index

As explained in Advanced Algorithms and Data Structures

A split index is a position in an ordered sequence that separates its entries into two partitions.

A split index is a position in an ordered sequence that divides entries into left and right partitions. In an SS-tree node split, each partition must contain at least m entries, so valid indices range from m through M−m. section 10.3.4

Eight-point node

With eight ordered points and m=3, the possible split indices are 3, 4, and 5. The selected index produces two partitions with at least three points each and the lowest combined variance.

How Advanced Algorithms and Data Structures covers it

How deep it goes
Explains candidate bounds, coordinate ordering, variance comparison, and resulting node construction.
Examples
Uses eight points, maximum variance along the y-axis, and candidate indices 3, 4, and 5.
What it assumes
Assumes ordered entries, a fixed minimum occupancy m, and variance calculations.
What you can do after
Apply it via SS-tree insertion to select and construct two balanced node partitions.
How it connects
Connects SS-trees with variance, centroids, bounding envelopes, and R-trees.
Cover of Advanced Algorithms and Data Structures
liveBookmanning.com
Read Advanced Algorithms and Data Structures on liveBook Get the book at manning.com

This explainer was generated by Manning's knowledge graph from the text of Advanced Algorithms and Data Structures. The section links point to the parts of the book it draws on.