search

geocaml / ocaml-rtree

A pure OCaml implementation of R-Trees
BSD 3-Clause "New" or "Revised" License
26 stars 7 forks source link

Add nearest neighbour function #20

Open patricoferris opened 10 months ago

patricoferris commented 10 months ago

It seems very common for Rtree implementations to provide a nearest_neighbour function, so we should do the same! A few examples from other Rtree (or related) libraries.

  1. Rust RStar library: https://github.com/georust/rstar/blob/master/rstar/src/algorithm/nearest_neighbor.rs
  2. Another one in Go: https://github.com/dhconnelly/rtreego/blob/master/rtree.go

The Go one makes reference to http://www.cs.ucr.edu/~ravi/CS236Papers/roussopoulosNN95.pdf

This is quite involved so do have a look for other good first issues if you haven't made a contribution yet unless you feel comfortable. And do ask questions!

harshey1103 commented 9 months ago

Hi @patricoferris, I would love to work on this issue. Is there any documentation pertaining to the nearest neighbor function of what it should do or should I just check the code in Go/Rust and try to mimic it in Ocaml?

AryanGodara commented 9 months ago

Hi @patricoferris, I would love to work on this issue. Is there any documentation pertaining to the nearest neighbor function of what it should do or should I just check the code in Go/Rust and try to mimic it in Ocaml?

It can be a good approach to go through the Rust implementation :) Did you find any good resources over these last days?

harshey1103 commented 9 months ago

Hi @patricoferris, I would love to work on this issue. Is there any documentation pertaining to the nearest neighbor function of what it should do or should I just check the code in Go/Rust and try to mimic it in Ocaml?

It can be a good approach to go through the Rust implementation :) Did you find any good resources over these last days?

Nope :( I didn't find any, I have been preoccupied with some other work recently, and I had expected the project mentors to provide me with the resources. I'll look up the resources and see what I can find.

kushalpokharel commented 9 months ago

Hi @patricoferris, do we want to calculate the nearest neighbor from a point specifically to our values (leaf nodes)? My question is where do I keep the distance functions? Should it be inside of module V or should I create a module called Point?

patricoferris commented 9 months ago

Good question @kushalpokharel , for now let's start with a dedicated Point module and go from there