R or R* tree implementations

Hi everyone, I'm wondering whether anyone is using (or knows of) any R– or R*–tree crates that might not be immediately obvious on crates.io. I'm using spade at the moment, but really need to benchmark its performance against some other implementations. Is Servo using anything that might be useful here? I know @pcwalton was working on an R-Tree implementation, but that was 3 years ago, and every other crate I've looked at is abandoned or very early-stage. My needs are quite modest: I need to be able to insert and remove line segments (2D, with a start and an end point), and query within a bounding box.

1 Like

There are bunch of projects in geo rust github project, may be one of these projects usefull for you? Like this one.
Personaly I use r-tree implementation inside sqlite via rust sqlite bindings.

1 Like

Unfortunately, it's for a new trait in rust-geo, which definitely doesn't include any tree implementations. Do you have any examples of creating and querying a (presumably in-memory) sqlite db R* virtual table?

1 Like

Actually, sqlite documentation describe exactly what you want: The SQLite R*Tree Module

1 Like

Using:

  • an in-memory DB with a big cache size
  • PRAGMA synchronous=OFF
  • prepared statements
  • transactions for the initial inserts (around 9k rows x 2)
  • indexes

My benchmark runs in around 2100 ms, so not order-of-magnitude slower, but around 7x. Was worth a shot, but I don't see any particularly low-hanging fruit; even if I cut that in half, it's nowhere near Spade.

@urschrei

My benchmark runs in around 2100 ms

Is it possible to share benchmark?

Sure.

You can test the SQLite version by stashing, checking out vw_topology_preserve_sqlite, and popping the stashed changes, before re-running cargo test --release

@urschrei

Thanks, I tried, but:

And with vw_topology_preserve_decrease works,
but there is no vw_topology_preserve_sqlite branch here:

or if check with command line:

$ git branch -r | grep vw
  origin/vw_benchmarking
  origin/vw_topology_preserve
  origin/vw_topology_preserve_decrease

forget to push?

Yep, sorry! Fixed now. You'll see some failing tests, but that's OK at the moment.