Consider a kd-tree, just like as kd-tree definition in Mark de. Berg's computational geometry textbook. There are two different analyses of cache-complexity of query answering in the attached pdf file? Which analysis is the right one? Which one is more accurate?
Harsh Bhasin
The details of Data Structures (including kd tree) can be found in the following
Book: Hand Book of Data Structures and Applications, Edited By Sartaj Sahini.
Lars Arge, Cache Ob. Data Structures, Chapter 38, By CRC Press, 2005
1 votes
1 thanks
Majid Imani
sqrt(N/M) is O(sqrt(N/B)), and in cache-ob. analysis of kd-tree, maximum number of block transfers that can occur are O(sqrt(N/B)).
0 votes
0 thanks
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Graphs
More Majid Imani's questions See All
Similar questions and discussions