Working Example

[parth1988]

Hi,

Thank you for this library. I am trying to use this library, but I cannot find a working example. Do you have a working example that you can share? Or at least point to some link that has one?

Thanks for your time.

[parth1988]

My apologies for all the questions. I have been able to put together code from the test file to create an Rtree index. I have 2 more questions:

1. Does this library support intersection or a range query?
2. The DiskRTree constructor takes in 3 parameters: int n, int nodeBlockSize, boolean updateRowNumbers
   Would it be possible to elaborate on these parameters?

Thank you for your time again.

[fergonco]

The only query method is getRow(Envelope). I don't understand what you mean by "intersection" or "range query". The envelope is indeed a range, isn't it?

n is the number of elements in each node of the tree. I have used it with n=255. With that, you can store up to 255³ elements in an index of only three levels (each level having 255 elements to check sequentially). You can play around with your data and see which number is better. Normally the optimal would be: the minimum size that allows you to have at most three levels.

nodeBlockSize is a parameter for the NIO API. The size of the buffer to read the nodes. The units are 64bits (size of double type) so that 1024 will mean the buffer will hold 1024 doubles. I have always used it as 4 times n but maybe a value a bit bigger can save some buffer operations as each node holds 4 doubles for the envelope coordinates and the row number and some headers. If you don't care a lot for your memory consumption I would set it to 8xn, to be sure the whole node fits there. For n=255 it would be a buffer of 255_8_64 bits ~= 16kb. This parameter is actually more annoying than useful.

updateRowNumbers is used when the row indices can change. For example, I index a dataset with three rows 1, 2, 3. But then I insert a record on the second position of the dataset. If updateRowNumbers is true, the indices 2 and 3 in the tree will be increased to reflect the changes in the dataset: 1, new 2, 2->3, 3->4. The same for the delete method.

Hope it helps.

[parth1988]

Thanks a lot for your reply! It certainly helps. For my research, I am trying to compare my index structure with an R-tree and a packed Hilbert R-tree, for very large static datasets (ranging from 100M to 700M 2D points). I am trying to use your code as the basis for the R-tree and modify it to create a Hilbert R-tree (of course I will be citing your work - do let me know if there is any specific way you would like us to cite your code - I am purposely avoiding a database to avoid any additional overhead such as locking, etc).

I have few more questions/issues that I hope you don't mind answering.

1. Like you said, the envelope is indeed a range. I was able to use that. Is this a top-down approach where you see if the root node MBR/envelope intersects with the given range, if yes you check the same for all the children and so on?

2. Is there any particular way that you can view the hierarchy structure? I have tried my best to modify the code just to print out the internal node envelopes but haven't been successful. This is going to help me in my Hilbert R-tree modification.

3. For data greater than 20.8 million tuples, I get an java.lang.ArrayIndexOutOfBoundsException in the function DiskRTree.writeNodeBytes(). Have you experienced something similar? I will further analyze the error in the morning (to also make sure that the problem is not with my data).

The error occurs on the line: System.arraycopy(nodeBytes, 0, bytesInThisBlock, 0, bytesInThisBlock.length);

This is a partial error stack:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException
at co.geomati.indexes.rtree.DiskRTree.writeNodeBytes(DiskRTree.java:219)
at co.geomati.indexes.rtree.DiskRTree.writeNodeAt(DiskRTree.java:283)
at co.geomati.indexes.rtree.DiskRTree.createLeaf(DiskRTree.java:141)
at co.geomati.indexes.rtree.RTreeLeaf.splitNode(RTreeLeaf.java:91)

Thank you again for your help and time!

[fergonco]

1. The query is delegated to the root element here (https://github.com/fergonco/rtree/blob/master/src/main/java/co/geomati/indexes/rtree/DiskRTree.java#L514) and the implementation is here (https://github.com/fergonco/rtree/blob/master/src/main/java/co/geomati/indexes/rtree/RTreeInteriorNode.java#L702). You can see it checks the envelope of each element in the node and when it intersects it delegates to the child.

2. Nop, I remember printing a tree structure in a sheet of paper with n=3 and doing tests with pecil and eraser. It was really a pain! I would really advise you to invest in such a visualization if you are going to put your hands in the code for drastic changes.

3. I never indexed datasets with so many points. You could sysout the nodeBytes.length and bytesInThisBlock.length to know the values that make this fail. That along the n and nodeBlockSize could help to diagnose.

[parth1988]

Thank you again. I will do the testing on paper too.

I looked into the error in detail. I think the main problem is that the value of blockEnd surpasses the maximum value of Integer and the value is changed to the minimum value of integer, and hence the if condition turns to true (since blockEnd is negative). Inside this if condition, in the System.arrayCopy statement, the srcPos + length > src.length, and hence it gives the indexOutOfBoundsException.
One hack I tried was to try to change blockEnd to long, but obviously that didn't work because byte array takes only integer value as the size parameter.

The code never goes inside the if statement until the blockEnd value is changed to negative. Do you think there is a realistic scenario for which the if statement is turned to true?

Thank you for your time!

[fergonco]

Hi, it's a long time since I wrote this code, but I think this "if" block is checking if there is enough space for the node in the current position of the file, without overriding the next node. I recall the nodes where written in the file sequentially:

rootbytes|firstchildbytes|secondchildbytes|...

and if one node grows more than nodeBlockSize, it creates an extension node:

rootbytes|firstchildbytes|secondchildbytes|...|firstchildbytesextension|...

If you set the nodeBlockSize big enough, the if condition can never happen, but you will waste space for the nodes that are not completely full (not sure if this is too bad or not).

Regarding the base problem, I am afraid that I didn't take into account so big datasets. I am not sure why in this case turning blockEnd to int does not work. In lines 217 and 237 it is used to create an array and the result of the operation is potentially long, but must fit into an int because it must be smaller than nodeBlockSize. You will run into the same problem with the buffer position in the same lines, which is also an int, but maybe it can be also changed. In general, although the file that stores the index can be huge, the buffers should be rather small.