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

Koala++'s blog

计算广告学 RTB

 
 
 

日志

 
 

范围搜索 (Range Query)[4]  

2011-07-03 22:56:55|  分类: 搜索引擎 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

Fractional Cascading

    有一种方法可以提高区域树的查找时间log n。二维查找可以在O(log n)时间内完成。

    基本思想:区域树首先找到在[xlo,xhi]区间的点集,这些点集是由O(log n)canonical集合组成的。

    接下来,每个canonical集合用y区域树查找[ylo,yhi]。我们先找到ylo的位置,然后一直读到yhi边界。

    我们接下来要做的是,首先在O(log n)时间内进行第一次查找,但是会利用查找的信息到另一种数据结构上更高效地查找。

    方法的关键是在canonical集合上加上一些指针。

Basic Idea

    我们通过一个简单的例子来了解这种方法的基本思想。

    假设我们有两个数组,A1A2,它们都是无序的。

    给定一个范围[x,x’],我们想得到A1A2中所有在这个范围中的元素。

    一个直观的做法是用两分查找找到A1A2k的位置,它的时间复杂度是O(2log n + k)

Fractional Cascading Idea

    假设有A2属于A1,添加一些从A1指向A2的指针。

    如果A1[i]=yi,将一个指针指向A2中大于yi的最小元素。

    假设我们想得到范围[y,y’]中的元素。

    A1中查找y,然后一直遍历到y’,时间复杂度为O(log n + k1)

    如果A1A1[i]位置找到y,可以使用它的指针开始在A2中的查找。这一步的时候复杂度为O(1 + k2)

 

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

 

    例子所示为查找[20,65]

FC in Range Trees

    元素的特点:S(l(v))S(r(v))canonical集合是S(v)canonical集合的子集。

    X区域树还是和以前一样。但在这里不建立y区域树,而是根据y坐标将它们保存到排序数组里。

    A(v)中的每个entry保存两个指针,指向A(l(v))A(r(v))数组。

    如果A(v)[i]保存着点p,那么指针指向A(l(v))中最小大于的y坐标元素(y(p))。对r(v)也是一样。

Range Tree FC

    下图中给出了一部分指针的示例。

 

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

 

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

 

FC Search

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

    考虑一个区域R=[x,x’]*[y,y’]

    x区域树中查找x, x’

    vsplit为两条查找路径开分开的结点。

    O(log n)canonical子集对应vsplit下的子结点,它们是在查找x(x’)路径向左()时的右()子结点。

    vsplit结点,在A(vsplit)中二分查找y,时间复杂度为O(log n)

    用我们x区域树查找x,x’的方式向下查找。从entries的指向得到指向子结点中>=y的位置,这个操作的时间复杂度为O(1)

    A(v)O(log n)canonical结点的一个,现在要在A(v)中查找[y,y’]区域内的元素。

    我们只需要找到A(v)>=y的最小entry

    我们可以在O(1)时间复杂度内找到是因为parent(v)在查找路径上,并且我们通过v数组中的指针,知道最小>=yentryA(parent(v))中的位置,

    所以我们可以将在A(v)中在[y,y’]中的所有点在O(1 + kv)时间复杂度内输出,其中kv是结果集大小。

    对二维范围搜索,最终的时间复杂度为O(log n + k),空间复杂度为O(n log n)

    d维范围搜索使用分散层叠的时间复杂度为O((log n)d-1)

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

历史上的今天

评论

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

页脚

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