Search code examples
knnspatial-queryspatial-indexr-tree

knn search for a trajectory (a line of points) in an r-tree

I have some trajectory data (a set of gps points, they are from the same trip so spatially close to each other). I want to find the k-nearest-line-segments for each of the point. I know that I can do a knn search in a RTree to get the knn for one point and repeat it for every other point. I think there might be some better solutions since these points are close to each other and so the searching doesn't need to start from root every time. Is there such a quick way? Thank you

Solution

  • Try to formulate your query using "regions of interest".

    With trajectories, you usually have an upper bound on what is a possible match, and region queries can be ued to retrieve multiple candidates efficiently.