R-Trees can take several paths to retrieve an item because of overlaps in data being indexed or index structure. However, if we run the same search many times on the same unmodified structure, can we remember the correct path and avoid taking the wrong path?

Maybe caching the correct path? But I'm not so sure that R-Tree implementations do this or that R-Trees fully loaded in memory do this either.


Sure, you can cache the results of lookups into a R-tree (or any other data structure). Simply build a cache (e.g., a hashtable) where after each lookup into the R-tree, you update the cache; and before doing a lookup into the R-tree, check the cache first. You don't need to store the entire path in the cache: it's enough to just store the results of the search.

Whether this will improve performance or not will depend on your particular workload.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.