R-tree to be available in mdds

[Kohei Yoshida]

Hey there,

I'm currently working toward getting the next version of mdds [1] 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 [2].

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 [3] 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.

Thoughts?

Kohei

[1] https://gitlab.com/mdds/mdds
[2] https://en.wikipedia.org/wiki/R*_tree
[3] https://gitlab.com/ixion/ixion

--
Kohei Yoshida, LibreOffice Calc volunteer hacker