So, after reading several articles on Spatio-Temporal data structures, as well as after conducting several experiments with QuadTrees and R-Trees, Ive decided to settle down with an Octree as the efficient In-Memory Data Structure for Zet Universe. This is an another experiment towards creation of a more stable serializable storage subsystem, with focus on fast retrieval of data within the provided boundaries in 3 dimensions, including two spatial ones (x,y) and one time dimension. As you can see in the video below, by moving a slider one can quickly define the viewbox for the entire tree, to see objects that are either within the viewbox, or intersect with it. List of items changes automatically as the viewbox changes. Finally, it is also fully serializable/deserializable as any other tree (like R-trees commonly used in the databases). This looks promising, isnt it? Thanks a lot to Denis Altudov, Alexander Popov for help with the underlying math, as well as thanks to Svetlana Tomson for a chance to see the problem from an entirely different perspective.
Posted on: Tue, 19 Aug 2014 11:11:41 +0000