I'd take a look at dynamic icoseptrees.
1 ) Icoseptrees overall fares very well for large spaces due to its sparse nature. The memory requirements of the tree is directly proportional to the number of objects in the scene.
2 ) You can use it for rendering as well ( in fact, that is the primary application of Icoseptrees ).
3 ) Icoseptrees can deffer optimization of the tree while providing no false negatives.
4 ) Terrific worst case performance.
Icoseptrees loose vs pre processed octrees of static objects, but this is obviously no con for your use case.