注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Koala++'s blog

计算广告学 RTB

 
 
 

日志

 
 

范围搜索 (Range Query)[3]  

2011-07-03 16:29:51|  分类: 搜索引擎 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

Orthogonal Range Trees

   

范围搜索 (Range Query)[3] - quweiprotoss - Koala++s blog

 

    将一维查找树推广到d维空间。

    每次查找都会递归地分解到多个低维空间中去查找。

    查找时间复杂度为O((log n)d+k),其中k是结果集大小。

    时间和空间复杂度是O(n(log n)d-1)

    分散层叠(fractional cascading)从查找时间中消除了一个log n因子。

    我们着眼于二维情况,但是它的思想是可以扩展到多维空间的。

2D Range Tree

    令二维空间中的一个点集合为P={p1, p2, ...,pn}

    一个查询的一般形式为:R=[xlo,xhi]*[ylo,yhi]

    我们开始不考虑y坐标,在P上建立一个一维的x区域树。

 

范围搜索 (Range Query)[3] - quweiprotoss - Koala++s blog

    [xlo,xhi]区间的点集属于O(log n)canonical集合。

    这是一个结果的超集。它明显比|RP|要大,所以我们不能采用依次查看每个点在不在canonical集合中这种耗时的方式。

Level 2 Trees

    思想的核心是取得每个canonical集合的点,并在它们上面建立y区域树。

    比如,canonical集合{9,12,14,15},用它的y坐标建立了一个新的区域树。

 

范围搜索 (Range Query)[3] - quweiprotoss - Koala++s blog

    我们查找每个O(log n) canonical集合需要查找x区域树中的[xlo,xhi]范围和用它们的y区域树查找[ylo,yhi]范围。

    y区域的查找中得到RP这个结果集。

Canonical Sets

范围搜索 (Range Query)[3] - quweiprotoss - Koala++s blog

analysis

    二维的查找时间复杂度为O((log n)2)

1.    查找O(log n)canonical集合。

2.    每个集合进行y范围查找需要O(log n)时间复杂性。

 

范围搜索 (Range Query)[3] - quweiprotoss - Koala++s blog

空间复杂度为O(n log n)

1.    x区域树中cononical集合的总大小是多少?

2.    非叶子结点个数=叶子结点个数。

3.    有一个大小为n的集合,二个大小为n/2的集合,以此类推。

4.    总共是O(n log n)

5.    每个大小为mcanonical集合需要O(m)的空间来存储y区域树。

6.    所以,总的空间复杂度是O(n log n)

construction

   

范围搜索 (Range Query)[3] - quweiprotoss - Koala++s blog

    x区域树可以在O(n log n)时间内建立。

    初看起来,因为y树的总大小是O(n log n),所以它需要O(n(log n)2)的时间来建立。

    但是通过自底向上建立它们,我们可以避免在每个结点上的排序时间。

    一旦子结点的y区域树建立了,我们就可以将它们的y数组在线性时间内合并。

    建立一维区域树在排序后的时间复杂度是线性的。

    所以,总的时间复杂度是O(n log n),是所有y区域树的总大小。

d-Dim Range Trees

    多级区域树的思想可以很自然地扩展到任意d维。

    在第一维上建立一个x区域树。

    在树中每个结点v上,在v结点的cononical集合上为剩余的(d-1)维建立一个(d-1)维的区域树。

    查找时间复杂度每一维增加log n因子——每一维都会增加canonical集合总大小log n倍。

    所以查找时间为O((log n)d)

    建树的空间和时间复杂度是O(n(log n)d-1)

  评论这张
 
阅读(1897)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017