[Question] A R-Tree search performance question

[bluefantasy2014]

Hi Dave,

I have a performance related question.

I created a R-Tree and added 3000 Line objects to it . Then I create a new Line object and call the R-Tree's search() funciton to search all the lines that intersect with the input line.

My question is the first search() call cost about 50ms. After the search() is called multiple times. I call the search() again , it only cost 1~5ms. I want to know why?

Does R-Tree need some warm up process? Or maybe the JIT matters?

I am looking forward for your reply.

Thanks,
Jerry Shi

---

The following is my pseudo code:

RTree<String, Line> tree = RTree.maxChildren(5).create();
for (int i = 0; i<1000; ++i){
tree = tree.add(i+"", createRandomLine(100,500));
}

Line line = Geometries.line(10.5, 10.5, 100, 200);

//the first call cost about 50ms;
tree.search(line).subscribe((t)-> {});

for (int i = 0; i<10000; ++i){
Line line = Geometries.line(1.0,1.0,i,i);
tree.search(line).subscribe((t)-> {});
}

//the same call cost about 1~5ms;
tree.search(line).subscribe((t)-> {});

[plokhotnyuk]

@bluefantasy2014 you can use the JMH framework to write such kind of micro benchmarks.

[davidmoten]

Thanks @plokhotnyuk for chiming in.

@bluefantasy2014 what you're seeing is expected. You should do some reading about Java performance and benchmarking, and Just-in-time compilation on the JVM.

[bluefantasy2014]

@plokhotnyuk @davidmoten
Thanks for your suggestion. I write a JMH test , in the test I create a R-Tree and added 3000 Lines to it , then I search a Line(this line will intersect with most of the lines in the tree) against the tree. The QPS is around 2000. I think the performance is not so good because the line intersect with almost all lines in the tree. I don't know how to improve the performance.

Following is the result :
Benchmark Mode Samples Score Score error Units
c.j.MyBenchmark.testMethodThroughput thrpt 200 2125.233 54.474 ops/s

[davidmoten]

Can you show us your benchmark code?

[davidmoten]

Are you trying to benchmark the search bit only?

[bluefantasy2014]

@davidmoten
Please see the attachement for my benchmark code. The code is very simple. I only benchmark the search performance.

What I am working on is a point-in-polygon (PIP) problem. For a given geo polygon(with less than 10k lines forming the border), I need to check whether a Point(longitude,latitude) located in the polygon.
I am using the Ray casting algorithm to do this. So I need to search which line in the tree intesect with the ray line.
The QPS of the load is heavy, so I need do some research about the preformance of the R-Tree.

Want if I added the rectangles of all the lines to the tree and search against the tree? Will that boost the performance?

Great thanks for your reply.

MyBenchmark.java.zip

[davidmoten]

Want if I added the rectangles of all the lines to the tree and search against the tree? Will that boost the performance?

Under the covers that's what is happening anyway so no. An R-Tree is based on rectangles. i doubt that an R-Tree is right for the point-in-polygon problem that you refer to. I'll leave the research to you!