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

Koala++'s blog

计算广告学 RTB

 
 
 

日志

 
 

范围搜索 (Range Query)[2]  

2011-07-03 09:44:26|  分类: 搜索引擎 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

Multi-Dimensional Data

    如何在高维空间中进行范围搜索?

 

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

    kD-tree [Jon Bertley 1975]。它是k-dimensional tree的缩写。

    它适用于一般的任意维空间。渐近搜索复杂度不是很好。

    通过在x-y坐标上分裂这种方式来推广一维的树。在k维空间中,将会循环所有维坐标。

kD-Trees

   

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

    一个二叉树,每个结点有两个值,所分裂的维,和分裂的值。

    如果分裂在x坐标的s处,那么左子树的点都有x坐标<=s,右子树的点都有x坐标>s。对y坐标也是一样。

    当只有O(1)个点剩余时,将它们放到一个叶子结点。

    只有叶子结点中有点位置的信息,非叶子结点只用于分裂。

Splitting

    为得到一个平衡树,使用坐标中位数来分裂——中位数本身放到左子树或是右子树都可以。

    使用中位数分裂,可以保证树的高度为O(log n)

    分裂可以使用循环所有维的方式,或是根据数据做出选择,比如,可以选择数据分布最广的维。

Space Partitioning View

    kD-tree是对空间的划分,每个结点都会引入对x轴或是y轴的划分。

    点被划分成两部分,这两部分分别是左子树和右子树。

    这些划分由矩形区域组成,称为单元(cell)(可能是没有边界的)

    根对应的是整个空间,随后每个子结点都只继承一半的空间。

    叶子对应的是终止单元。

    它是二分空间(Binary space Partitioning)的一种特殊情况。

construction

    它可以以递归方式在O(n log n)时间内建成。

    预先对x坐标和y坐标排序,并将两个排序数组交叉链接起来。(译注,即将每个点的x,y坐标链接起来)

    比如,可以通过扫描x数组得到x坐标的中位数,将数组分成两部分。再用交叉链接将y数组在O(n)时间复杂度内分成两部分。

    现在有两个子问题,每个都有n/2的大小,并且它们都有自己的排序数据。递归。

    递归式为T(n)=2T(n/2) + n,故它的时间复杂度为T(n) = O(n log n)(译注,可以参考算法导论4.3节的主方法)

Searching kD-Trees

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

    设查询矩形为R。从根结点开始查找。

    假设当前分裂的线是垂直的(也可以是水平的)。令v,w分别是左子结点和右子结点。

    如果v是一个叶子结点,返回cell(v)R,如果cell(v)属于R,返回cell(v)中所有点,如果cell(v)R为空集,跳过。

    w进行相同的处理。

    查询过程明显是没有问题的。那么它的时间复杂度是什么呢?

Search complexity

    cell(v)属于R,时间复杂度与cell(v)的大小成线性关系。

    结点v访问的结点个数满足由cell(v)R交集边界的限定。

   如果cell(v)R区域之外,我们就不用去查找它,如果cell(v)R之内,我们就要枚举v中的所有点。只有在cell(v)R局部重叠时才会去递归调用。kD-Tree的高度是O(log n)

    l为穿过R的一条直线。

    有多少个单元会与这条线相交?

    因为分裂的维是从两个维中选择一个,所以思考的关键在于每次将树的两层一起考虑。

    假设第一次划分是垂直的,第二次是水平的,我们就有四个单元,每一个有n/4个点。

    一条直接只与两个单元相交。单元或是在R区域之内或是R区域之外。

    递归式为:

 

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

 

    从递归式可以得到时间复杂度为:Q(n)=O(n1/2)

    kD-Tree是一个有O(n)空间复杂度的数据结构,它可以在最坏时间O(n1/2+m)内完成二维空间范围查找,其中m是输出的大小。

d-Dim Search Complexity

更高维的时间复杂度是什么呢?

先尝试三维情况,再推广。

递归式是:

Q(n)=2d-1Q(n/2d)+1

从它推出时间复杂度:

    Q(n)=O(n1-1/d)

    kD-Tree是一个有(nd)空间复杂度的数据结构,它在d维空间中查找范围的最坏时间复杂度为O(n1-1/d+m),其中m是输出的大小。

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

历史上的今天

评论

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

页脚

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