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 _______________________________________________ LibreOffice mailing list [email protected] https://lists.freedesktop.org/mailman/listinfo/libreoffice
