1. A method of adding a video entity to a full motion video database supporting search capabilities, the method comprising: determining a starting cell in the full motion video database; if the starting cell is full: determine a split axis by splitting the starting cell, create two new child cells along the split axis, move one or more entities from the starting cell to the two new child cells, and add the video entity to one of the two new child cells.