Skip to content

[Issue #405] RTree in memory index#563

Merged
mschoema merged 22 commits intoMobilityDB:masterfrom
Matematikoi:rtree_index
Aug 25, 2024
Merged

[Issue #405] RTree in memory index#563
mschoema merged 22 commits intoMobilityDB:masterfrom
Matematikoi:rtree_index

Conversation

@Matematikoi
Copy link
Copy Markdown
Contributor

Implementation of an RTree in memory index to solve issue 405.

The original code has been taken from Josh Baker rtree implementation and strip down to a more simple RTree.

This first version is only working with intersection but future versions should be able to work with any supported function that is already implemented for GIST.

The basic unit of inserting and querying is an STBox although the code has been done in a way that it allows an easy transition to other structures likes spans or boxes.

When querying the RTree returns an ID that identifies the STBox that was inserted.

There are two important structures. RTreeNode and RTree. There are 4
basic functions to interact with this structures: create and rtree,
insert something to it, query and rtree and free the memory of an rtree.
We include a basic structure for the Rtree which is working for STBoxes.
It allows to insert one by one. Queries are done with an STBox. A
function to find each value as a double is required to be passed down to
the RTree itself.
Since there is no tests for C code and only for sql code, this example
is in some way also a test.

It shows how you would normally use the Rtree, inserting and querying.
@Matematikoi Matematikoi marked this pull request as ready for review August 15, 2024 15:33
The largest axis was always choosing to split via the first element. Now
it changes. Some thought should be done for the temporal axis since it
is normally in a different scale. Maybe a mahalanobis distance would be
better.
meos.h should only have information that the user would use. RTreeNode
is no an structure that a user would use. Thus, is better to have it in
tpoint_rtree.h and have a forward definition in meos.h for RTree node.
Keeping it consistent with the rest of the codebase
RtreeNode will allocate only once and there will be no need to allocate
when inserting since it copying to an already allocated block of memory.
I have assumed meostype as an int since I meostype is defined in
meos_catalog and I can't import it from meos.h, thus int was best option
I had.
It was ambiguous that both #defines were related so they were refactored
as RTREE_INNER_NODE and RTREE_INNER_NODE_NO
Adds missing documentation to newly add functions
To answer the query of rtree_search it is necessary to realloc memory,
thus the code can become a little obscure. Added one extra function and
some comments to make life easier for maintenance.
Included some time taking sinceit is important to know the difference
between bruteforce and RTree search.
Change it so that when finding the minimum enclosing STBox there is no
need to allocate new memory.
Use a simple STBox instead of a palloc.
@Matematikoi Matematikoi requested a review from mschoema August 22, 2024 13:39
@mschoema mschoema merged commit d087be4 into MobilityDB:master Aug 25, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants