R-tree to be available in mdds
libreoffice at kohei.us
Tue Jul 31 00:06:06 UTC 2018
I'm currently working toward getting the next version of mdds  released. One highlight of the next release is the inclusion of R-tree. For those of you unfamiliar with R-tree, it is a data structure known to be optimal for indexing multi-dimensional spatial data, and is heavily used in e.g. storing 2D/2D map data and shape data with bounding boxes. The one being implemented in mdds is a variant of R-tree known as R*-tree .
I can think of many areas where R-tree could be used inside the libreoffice code base, but one area I am particularly interested in is formula dependency tracking, especially those that involve cell ranges. I suspect that, if implemented correctly, the use of R-tree could improve the query speed and also potentially minimize the complexity of the range-based listener-broadcaster handling on the libreoffice side (by moving the complexity of managing the data structure into mdds). Also, by using R-tree to manage formula dependency data, we could in theory merge all of cell-to-cell, cell-to-range, range-to-cell and range-to-range dependency tracking into a single data structure, which to me is a very attractive proposition.
Now, this all sounds good, but I'm fully aware that I'm being overly optimistic not to mention biased, and it's entirely possible that I'm wrong, and using R-tree in range-based dependency tracking would end up in more pain and less gain. So, my current plan is to experiment this idea of mine in the ixion library  first, then if it works well there, we can re-visit it here perhaps with more confidence. I just wanted to throw this idea on this list early, and see what you guys think.
Kohei Yoshida, LibreOffice Calc volunteer hacker
More information about the LibreOffice