Insertion with Trees

Given: a feature vector vobj for a new object.

Insertion procedure:

traverse tree to find leaf node n
		whose region contains vobj

if (enough space in n)
{
	insert vobj into corresponding page
}
else
{
	need to perform local rearrangement in tree
	   by splitting points between n and n's parent
	   and n's siblings according to split heuristic
}


Split heuristics include:

  • minimise total volume of bounding regions

  • minimise variance in volume of regions

  • minimise overlap among regions

  • .....