[prev] [index] [next]

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

  • .....


[prev] [index] [next]