Geek asks and answers

Rtrees - the basics of the algorithm

I am trying to understand the basics of the RTree algorithm, and I am trying to figure out how it performs a search, for example. all restaurants within 1 km. We would have all the objects stored in rectangles in our database, then we (prbably) built a query rectangle based on our current position, and then we find all the rectangles that overlap with it. Then we looked through the results to find objects of interest, i.e. Only objects that are restaurants?

+5
source share
1 answer

Yes, this is basically how range queries work on R-trees: if the rectangle overlaps the query area, expand it (look at the contents, rectangles, or dots). Otherwise, ignore it. The overlap test is simple for a rectangle-rectangle, and for spherical queries you need to calculate the minimum distance of the center of the sphere to the rectangle ("minDist").

k nearest neighbor queries are a bit more complicated; here you need priority queues. Always expand the best candidate (using "minDist") until you find k objects that are closer than the following "minDist" rectangles.

" ", r-tree, . ( , , , SQLite, R-, , , )

R- - , . , (STR), - . R * -trees R- ; , R * -trees, . R *, . R R * .

kd-trees: r-, : -, , . -, ( ), , , . ( ), , . , .

+4

More articles:


All Articles