Priority R-tree

<h2 id="performance">Performance</h2>
<p>Arge <i>et al.</i> writes that the priority tree always answers window-queries with

O
        
          (
          
            
              
                (
                
                  
                    N
                    B
                  
                
                )
              
              
                1
                −
                
                  
                    1
                    d
                  
                
              
            
            +
            
              
                T
                B
              
            
          
          )
        
      
    
    {\displaystyle O\left(\left({\frac {N}{B}}\right)^{1-{\frac {1}{d}}}+{\frac {T}{B}}\right)}
  
 I/Os, where N is the number of d-dimensional (hyper-) rectangles stored in the R-tree, B is the disk block size, and T is the output size.
</p>
<h2 id="dimensions">Dimensions</h2>
<p>In the case of 
  
    
      
        d
        =
        2
      
    
    {\displaystyle d=2}
  
 the rectangle is represented by 
  
    
      
        
        (
        (
        
          x
          
            m
            i
            n
          
        
        ,
        
          y
          
            m
            i
            n
          
        
        )
        ,
        (
        
          x
          
            m
            a
            x
          
        
        ,
        
          y
          
            m
            a
            x
          
        
        )
        )
      
    
    {\displaystyle \,((x_{min},y_{min}),(x_{max},y_{max}))}
  
 and the MBR thus four corners 
  
    
      
        
        (
        
          x
          
            m
            i
            n
          
        
        ,
        
          y
          
            m
            i
            n
          
        
        ,
        
          x
          
            m
            a
            x
          
        
        ,
        
          y
          
            m
            a
            x
          
        
        )
      
    
    {\displaystyle \,(x_{min},y_{min},x_{max},y_{max})}
  
.
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Bounding_volume_hierarchy/1FBFkwNe">Bounding volume hierarchy</a></li>
<li><a href="/facts/B-tree/IHE2l8GR">B-tree</a></li>
<li><a href="/facts/R-tree/9X5AQWln">R-tree</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>L. Arge; M. de Berg; H. J. Haverkort; K. Yi (2004). "The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree" (PDF). SIGMOD. Retrieved 12 October 2011. <a href="/wiki/Lars_Arge" target="_blank">/wiki/Lars_Arge</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
</ol>

Priority R-tree open-in-new

Priority R-tree