（计算机软件与理论专业论文）区域搜索的一些问题研究.pdf

区域搜索的一些问题研究 摘要：区域搜索问题和众多的实际应用有着紧密的联系，例如地理信息系统、计算 几何、计算机图形学、空间数据库和时间序列数据库等系统，其实日常生活中也不 乏众多例子。 区域搜索问题有着丰富的内容，本文主要通过一些典型实例来介绍区域搜索问 题。一般来说，讨论的问题或者定义在群上，或者定义在半群上。本文详细描述了 o l a p 上的区域和查询和区域最大值查询两个典型的例子，前者的运算是定义在群 上，而后者的运算是定义在半群上的。 本文的贡献，主要是用基于压缩的方法来研究一维空间中的区域最大值问题。 设计了两种p 日b 数据结构来存储预处理数据，一个用分层的数组，另一个用分层 的v a i le m d eb o a s 树。这两个数据结构的平均空间复杂度都是线性的，后者是前者 的一个改进。基于前一个数据结构的查询算法的平均时间复杂度是o ( 1 0 9 l o g 礼1 ，而 另一个的最坏查询时间复杂度是o ( 1 0 9 l o g n l 。 最后，本文总结了区域搜索算法设计的一些技巧和一些比较深刻或者是比较新 的结果，并根据大量的参考文献例举了几个值得关注的研究方向。 关键词：算法，数据结构，预处理，区域搜索，区域和，区域最大值，时间复杂 度，空间复杂度，预处理，上界，下界。 分类号：t p 3 0 1 6 1 1 1 s t u d y o ns o m epr o b l e m so fr a n g e 一 s e a r c h i n g a b s t r a c t ：r a n g es e a r c h i n g a r i s e si naw i d e r a n g e o f a p p l i c a t i o n s ，i n c l u d i n gg e o g r a p h i c i n f o r m a t i o ns y s t e m ，c o m p u t a t i o n a lg e o m e t r y ，c o m p u t e rg r a p h i c s ，s p a t i a ld a t a b a s e s ， a n dt i m e - s e r i e sd a t a t ) a s e t h e r ea r em a n yi n s t a n c e so fr a n g es e a r c h i n gp r o b l e m t h i sp a p e rd o e s n ta i m t om a k ea c o m p r e h e n s i v es u r v e yo fi t ，b u td i s c u s s e ss o m ep a r t i c u l a rp r o b l e m si nt h i s f i e l ds oa st os h o wt h ef u n c t i o no ft h ep r o p e rd a t as t r u c t u r ea n dt h ea n a l y s i so f q u e r y a l g o r i t h m n e a r l ym 1t h eb i n a r yo p e r a t i o n sa r ed e f i n e do ng r o u po rs e m i g r o u pi nt h e d o m a i no fp r o b l e mi n s t a n c e w ei n t r o d u c er a n g e s u ma n d r a n g e m a xq u e r y i no l a p e n v i r o n m e n t ，w h i c ha r et w ot y p i c a lr a n g es e a r c h i n gp r o b l e m t h ec o n t r i b u t i o no ft h i sp a p e ri st h a tw ed i s c u s st h er a n g em a xp r o b l e mi no n e d i m e n s i o nw i t ht h ec o m p r e s s i o nm e t h o d t w op h bd a t as t r u c t u r e sa r e d e s i g n e d t os t o r et h ep r e p r o c e s s i n gd a t a t h es e a r c ha l g o r i t h mo fo n eh a st h ea v e r a g et i m e c o m p l e x i t yo fo ( 1 0 9 l o g n ) w i t ha r r a yt os t o r ec o m p r e s s i n gd a t a a n da n o t h e ro n e u s i n gv a ne r o d eb o a st h r e eh a st h ew o r s t c a s eq u e r yt i m ec o m p l e x i t yo fo ( 1 0 9 l o g n ) h o w e v e rt h e yb o t hn e e d0 ( n ) s p a c e t h i sp a p e rs u m l l l a r i z e ss o m e p r o f o u n d o rn e wr e s u l t so nt h i sp r o b l e m i ta l s om a k e s as u r v e yo ns o m ec o m m o nt e c h n i q u e st oi m p l e m e n td a t as t r u c t u r ea n da l g o r i t h m ，i n t h ee n d ，i ts h o w ss o m ep r o b l e m sd e s e r v e df u r t h e rr e s e a r c h k e yw o r d s ：a l g o r i t h m ，d a t as t r u c t u r e ，r a n g es e a r c h i n g ，r a n g es u m ，r a n g em a x ， t i m ec o m p l e x i t y s p a c ec o m p l e x i t y ，p r e p r o e e s s i n g ，l o w e rb o u n d ，u p p e rb o u n d c 】a s s i f i c a t i o nn u m b e r ：t p 3 0 】6 l v 1 引言 区域搜索( r a n g es e a r c h i n g ) 问题存在于许多广泛的应用中，譬如地理信息系统、计 算几何、计算机图形学、空间数据库和时间序列数据库。现实生活中处处可见区域 奁询的例子： 例1 1 假设你在一个不熟悉的商业区逛街，而此时你要现钞急用。虽然商业区的自 动提款机很多，但是需要时间去找，并且人们总是希望能就近的取款。如果有一套 系统，你告诉它你所在的位置，然后系统返回最近的取款机的位置，那么生活就变 得更加的方便。 例1 2 邮局面临的问题可能更实际一些，我们知道信件通常都是一级一级分发的， 给定一封信，我们希望能够找到离收信地址比较近的分局。 例l 3 假设有一个商店，他们开发了一套数据库应用系统来纪录整个商店的销售。 商店里恰好正在销售一些文具，经理想知道文具，国产的分类编号从1 2 0 0 至u 1 2 5 0 ， 在2 0 0 2 年1 月到2 0 0 2 年3 月期间中销售量最大的产品。 在这个数据库管理系统中，执行下列s q l 语句： s e l e c tm a x ( a m o u n t ) f r o ms a l e sw h e k e ( ( i t e m = 1 2 0 0 ) a n d ( i t e m = 2 0 0 2 一o l 0 1 ) a n d ( d a t e ，这样就可以描述计数查 询问题。一般的，我们可以如下定义几何搜索问题： 定义1 2 ( 几何搜索) s 是r d 空间中的对象的集合，( s ，+ ) 是一个交换半群，权重函 数w ：s - s ，冗是区域的集合。在对象和区域之间定一个偏序关系s 冗。给 定一个区域q 冗，计算，o o 叫( p ) 。 在s 中的对象可以是点、超平面、球体或者单型体等。如果令s 是础中的点的 集合，并且偏序关系= ，我们就可以得到前面提到的区域搜索问题的形式化描述 了。 2 1 2 关于本文 1 引言 本文主要引入了区域搜索问题，详细介绍了它的些具有代表性的问题，以及这些 问题的算法设计和算法分析。我的主要工作是在第5 章，首次采用压缩的方法来研究 一维区域上的最大值问题，设计了一种p h b 的数据结构，得出了最坏时间复杂度 为o ( 1 0 9 l o g n ) 的查询算法。 第l 章，我们介绍了一些现实生活中碰到的区域搜索问题，然后给出了一个比较 严格的形式化的定义。第2 章，简单的介绍了有关算法分析的一些概念。为了评判区 域搜索问题的查询算法，列举了区域查询算法性能的一些主要的评价标准，并介绍 了存储模式的概念。 第3 、4 章，我们分别介绍了o l a p 系统中的两种区域查询问题：区域和与区域 最大值问题。首先，o l a pf 3 3 系统在近来颇受关注：其次，这两个问题分别是基于 群和半群的典型问题。根据文章f 4 9 ，5 0 1 ，详细的介绍了它们的查询算法的设计和分 析。 第5 章，我们用压缩的方法来研究一维空间中的区域极大值问题，给出了一个最 坏平均时间复杂度为o ( 1 0 9 l o g n ) 的查询算法，和一个最坏时间复杂度为o ( 1 0 9 l o g n l 的改进算法，这两个算法的预处理空间复杂度都是0 ( 礼) 。 第6 章，我们对以往的研究作了一个回顾和总结，主要是关于正交区域的搜索问 题中一些比较深刻的结果。结合当前的研究热点，指出了一些将来值得关注和研究 的方向。 3 2 预备知识 2 1 算法分析 在保证算法的正确性的前提下，一个算法可以用一组标准 1 来评价它的性能质量。 在任何计算模型里，算法的运行总是要使用计算资源。通常而言，算法运行过程中 所使用的资源包括计算时间和存储空间。 2 1 1 复杂度 算法的复杂度是指算法执行时所占用的资源数量，通常与该算法的输入规模有 关。如果算法的输入，的规模为n ，那么我们用t ( n ) 来表示算法执行的时间复杂 度，s ( n ) 来表示算法的空间复杂度，e ( n ) 用来表示t ( n ) 或s ( 由。 我们引入一个单调非减的函数，：n 卜f 0 ，o o ) 来描述算法的复杂度。令函数 ，g ：n + i 【0 ，o 。) ，下面引入一些记号【7 ： ，o ( g ) ：如果对所有的足够的大的n n ，存在一个常数c 0 使得 ，( n ) c t 口( n ) 。也就是说，函数，不比9 增长快。 ，q ( 9 ) ：如果对所有的足够的大的礼n ，存在一个常数c 0 使得 ，( n ) c g ( n ) 。也就是说，函数，的增长速度至少不比g 的增长速度慢。 ，e ( g ) ：如果既有，o ( g ) 也有f q ( 9 ) 。也就是说函数，和g 增长的一样 快。 算法分析中通常考虑的都是n 相当大的情形，所以这些函数叫做渐进函数，因此对 应的也叫渐进复杂度。借助这些记号，我们可以在常数因子的范围内比较不同的算 法复杂度。 因为应用的要求不同，我们对算法性能的要求也不一样。一般情况下，我们会 研究算法以下三种情形的复杂度特性：最坏情形、平均情形和摊销情形。 4 2 预备知识 在相同的输入规模下，最坏复杂度以算法在最糟糕的情形下所占用的资源作 为算法的复杂度；平均复杂性则是根据每一个输入出现的概率及其复杂度所求出 来的期望值作为算法的复杂度。关于它们的严格定义，请参见1 1 。摊销复杂度 f 7 5 ，t 7 1 ( a m o r t i z e dc o m p l e x i t y ) 用一个序列的执行所用的资源的平均值作为算法的 复杂度。 算法研究者总是对给定的问题求出它在特定算法类下的复杂度下限，然后努力 设法设计出达到这一复杂度的算法。前者简称下界问题，后者称为上界问题 1 。 2 1 2 区域搜索的性能指标 解决区域查询问题时，几乎所有的算法都使用辅助的数据结构来存储预处理的结 果。所以，区域查询算法的性能的评估标准主要包括： 1 查询时间：回答一个查询所需要的时问，输入的规模通常是指数据集合的规 模。 2 更新时间：对原始数据执行插入、删除或更改等操作所导致辅助数据结构更新 所用的时间。 3 存储空间：存放预处理数据的辅助数据结构所占用的存储空间。 4 预处理时间：计算原始数据的预处理结果和构造与处理结果的数据结构所用的 时间。 一般来说，辅助的数据结构通常是在执行查询请求之前一次性构造的。所以，我们 更关心查询的响应速度和预处理的数据结构的尺寸。 如果查询请求时区域报告问题，那么查询时问和输出的元素的个数相关。也就 是说，区域报告的查询时间由两部分组成： 搜索时间：由几和d 确定： 报告时间：由n ，d 和输出的大小确定； 在文中，我们用k 来表示查询输出的大小。 2 2 计算模型 在研究不同类型的问题时，研究者设计了多种不同的计算( 机器) 模型。因此算法 的时间和空间复杂度通常与实现的计算模型紧密相关的，因此算法复杂度的下界和 b 2 预备知识 上界也是计算模型相关的。但是因为计算模型的强弱关系，一个计算模型的下界也 可能是另外一些计算模型的下界，但是大部分情况下不成立。 2 2 1 随机存取模型 随机存取机器( r a n d o ma c c e s sm a c h i n e ) f 7 】，由一条只读的输入繁，只写的输出 带，程序和存储单元构成。 计算几何中的大部分算法和数据结构都以r a m 作为计算模型。在r a m 机器模 型里，机器可以有任意多的存储单元来记录长度为( 1 0 9 n ) 比特的整数。在这些存储 单元上，机器可以执行加法、减法、乘法、除法和比较等操作。存储单元的存取是 任意的，存储单元存取的操作时间是常数的，和存储单元的位置无关。 在很多情形下，我们允许r a m 存取任意的实数( 譬如，实空间中某些点的坐 标) ，实数之间的算术运算和比较运算也可以在常数时间里完成，但是不允许实数 和整数之间的转换。对于定义在半群上的问题，r a m 的存储单元可以存取半群定义 域上的任意值，但是r a m 只能对这些值执行半群上定义的加法运算。 2 2 2 指针计算模型 t a r j a n 7 8 1 提出了一种具有更多限制的计算模型：指针机器( p o i n t e rm a c h i n e ) ，以 下简称p m 。p m 和r a m 之间的不同主要在于：指针机器的存储单元只能通过一系 列的指针访问来完成。 几乎所有己知为区域搜索设计的数据结构都可以用指针机器来描述，p m 尤其适 合来研究区域报告问题。在p m 这种计算模型里，设计的数据结构是一个出度为2 的 有向图：图中的每个节点”都有一个整数标号f ( u ) ，取值范围从0 到n ，那些非零的 节点是点集s 中元素的索引。给定一个查询区域q ，查询算法从一个特殊的出发点 开始执行以下的一系列的操作： 1 从已访问的节点开始，沿着出边访问下一个新的节点； 2 创建一个新的节点u 并赋值f ( u ) = 0 ，让这个创建的节点的出边指向上次访问 的节点： 3 重定向离开上次访问节点的出边，使得它指向另外一个已访问的节点。 当算法终止的时候，被访问过的节点的集合w ( q ) 包含了查询区域里的所有点的索 引。如果有b q ，那么一定存在节点u w ( q ) 并且l ( v ) = 2 。但是，w ( q ) 中可 能会包含一些不是查询区域中的点。 6 2 预备知识 为了回答计数问题和半群上的查询问题，c h a z e l l e 2 6 定x 7 一些其它的指针机 器。在这些扩展的模型中，节点上存储的值的可以是长度为o ( 1 0 9 n ) 的任意的二进 制整数。除了可以沿着节点的出边来访问别的节点，查询算法可以对这些整数执行 一些算术运算。根据可以执行的算术运算，p m 可以分成以下几种模型： 1 初等指针机器( e p m 、e l e n e n t a r yp o i n t e rm a c h i n e ) ：可以执行加法的指针机 器。 2 半算术指针机器( s a p m ，s e m i a r i t h m e t i cp o i t e rm a c h i n e ) ：可以执行加、 减、乘、除的指针机器。 3 算术指针机器( a p m ，a r i t h m e t i cp o i t e rm a c h i n e ) ：可以执行加、减、乘、除 和移位的指针机器。 如果问题的空间中的点的数值定义在一个半群上，那么数据结构中的节点一样也赋 给半群上的值。因此，指针机器模型也只能对节点执行半群上所定义的加法运算。 2 。2 3 半群算术模型 为了计算区域查询的下界，f r e e d m a n 3 8 1 引入了半群算术模型( s e m i g r o u pa r i t h m e t i em o d e l ) ，然后y a o g s l 作了进一步的定义。实际上，几乎所有的下界值都是 基于该模型的。 在半群算术模型中，数据结构存放的都是基于半群的部分和。数据结构的存储 空问就是部分和的数目，查询时间就是回答查询结果所需要的最少的半群上的运 算。这里，查询时间忽略了很多非半群上的操作的计算代价，例如如何确定使用哪 一个部分和来计算当前的查询的代价。与p m 和r a m 模型不同，半群算术模型只 考虑半群上的计算代价，存取部分和不需要任何代价。这个模型的缺点是描述能力 太强，以至于有的查询问题不需要查询时间就可以回答了。 半群算术模型的最大弱点就是不支持减法运算，即使空间上的点的定义域是在 群上。因此，c h a z e l l e 2 9 ，3 0 1 引入了允许加法和减法的群算术模型。 2 3 存储模式 在现实生活中，我们把一些对象具有相同或类似特点称为模式。我们设计的数据结 构也可以分成一些模式， 7 2 预备知识 定义2 1 交换半群( s ，+ ) 具有可靠性。如果对任意的指标集i ，j 1 ，n l 和 正整数序列，? j ( i ，j j ) ，n 0 ，只要i j 成立，必然存在半群上的值 s 1 ，5 2 ，s 满足 口池岛。 t ， j e j 令s = p l ，p 2 ，p n ) 是对象的集合 对象和区域上的二元关系。假设z l ，z 2 ， s 里的一个点。 s 是可靠的半群，冗是区域的集合，是 x 。是s 上的变量，每个变量对应于集合 定义2 2 产生式是指形如 g ( x 一，一。) = 叩。 z = l 的线性表达式，其中o z i 0 且：l 口。 0 。 定义2 3 产生式集合 g l ，伪，9 。) 是( s ，s ，亿，) 的存储模式，如果 9 - ，9 2 满足以下性质：对任意的查询区域qe 冗，存在个指标集 1 ，2 负整数标号 屈h 场) 满足 q = 胰肌 m o 口l ，o 换句话说 ( 肌) = 屈肌( ”( p ，) ，叫( p 。) ，w ( p n ) ) m o 口 i e i q 对任意的权重函数w ：s 斗s 成立。 ，g 。) s 和非 p o o n 【6 7 1 弓1 入了健忘的( o b l i v i o u s ) 存储模式，如果存储单元只取决于查询的 区域或者是更新的位置。也就是说，这种类型的数据结构不依赖于数据的值。对应 的，我们把那种依赖于数据值的数据结构称作自适应的( a d a p t i v e ) 存储模式。在设 计的数据结构中，除了笛卡尔树 8 5 是自适应的以外，大部分都属于健忘的存储模 式。 8 3 o l a p 数据立方体上的区域和问题 3 1 引言 在线处理( o l a p ) 3 3 】系统，使得人们能够分析基于数据仓库的大量数据。多维数 据库( m d d b ) 模型6 1 是描述o l a p 的引用的比较流行的数据模型，也被称作数 据立方体f 6 。为了从数据仓库构造一个m d d b ，通常会选取5 一1 0 个属性。这样， 每一个数据记录就记录着这一组属性的值。其中的一些属性是用来作为度量属性 的，剩下的一些属性，假设有d 个，叫做维数或函数属性。相同的函数属性所确定 的度量属性的值，把经过聚类运算得到的最终结果存储在m d d b 中。这样，一个 m d d b 数据库就可以看作是d 的数组，它的索引就是d 个函数属性的值，对应的单 元存放的数值就是度量属性的值。 令d = l ，2 ，d ) 表示维度的集合，每一个维度对应着一个函数属性。首先， 把一个d 维的数据立方体重新表示为一个大小为凡l n 2x n d 的d 维数组4 4 ， 其中n ，2 ，j d 。在这一章里面，我们假设数组的索引从0 开始。方便起见，我 们把数组的一个元素叫做单元。用n = 兀2 ，n ，表示数组a 的大小。 那么，d 维数据立方体上的区域和查询问题可以表示成： 1k 州叱，i a ；l = z l吣= b 我们用q = ( f 1 ：h i ，1 2 ：h 2 ，f d ：h d ) 来表示由( 功d ) ( b 咕h j ) 所限定的 一个d 维区域。用容量来表示区域q ( z t ：h 。，f 2 ：h 。，f d ：h d ) 中所有点的个数，那 么一共有兀名。( ，一f j + 1 ) 个单元。 3 2 简单的算法 我们首先给出一个简单的算法，这个算法需要n = l - i , 叁。啦个额外的单元来存储预 先计算的前缀和。任何一个区域和的计算，最多需要读取2 4 个预先计算的前缀和， 9 3o l a p 数据立方体上的区域和问题 都可以在2 4 1 步中计算出来。 例3 1 当d = 2 ，n l = 6 ，n 2 = 3 时，图3 1 给出了一个数组a 和a 的前缀和数组p 。 l a r r a ya li n d e x01 2345 1 035 122 3 j 17326 82 l 2242335 a r r a yp 。 i n d e x012345 o3891 11 31 6 11 01 82 12 93 94 4 21 22 42 94 05 36 3 第3 1 图：d = 2 ，n 1 = 6 ，n 2 = 3 ，数组j 4 及对应的p 一般来说，存放前缀和的数组p 也是一个n 维数组。p 的大小和原数组a 一 样，都等于n = n l 7 2 2 n d 。对任意的0 q ( n j ，j d ，由下列公式计算 单元( z 1 ，x 2 ，。d ) 的前缀和， f i x l ，x 2 ，x d 】= s u m ( o ：z l ，0 ：x 2 0 ：茹d ) 一，豇1 ( 3 - 1 ) 例3 2 我们先看两个特例，对于维数比较小的数据立方体，可以如下计算任意的区 域和查询。如果礼= 2 ， s u m ( 1 1 ：矗l ，1 2 ：h 2 ) = p h 1 ，h 2 一f i b l ，1 2 一1 1 一p 口1 1 ，h 2 】+ p 1 l 一1 ，1 2 1 1 如果礼= 3 ， s l z m ( j 1 ：h 1 ，2 2 ：h 2 ，l a ：h 3 ) = p h l ，h 2 ，b 一p 脚l ，h 2 ，f 3 1 卜 r i b l ，2 2 1 ，h 3 】+ p h l ，f 2 1 ，l a 一1 卜 p 1 l 一1 ，h 2 ，h a + p 1 1 1 1 ，h 2 ，l a 一1 】+ p 1 l 一1 ，1 2 1 ，h a 】一p i l l 一1 ，f 2 1 ，f 3 1 】 由前缀和数组p 计算区域和s u m 的式子，有点类似于容斥原理的计算公式。 给定一个任意的数组j 4 和相应的p ，定理3 1 给出了区域和的计算公式3 2 。 定理3 1 对任意的j d ，令 s c ，= 二。，：霎耄三二。 1 0 也 a 。唧。唧。 | | 那么对所有的j d 有 3o l a p 数据立方体上的区域和问题 ( 3 2 ) 证明：给定数组a ，假定相应的p 已经预先计算好了。对任意的t d ，先用数学 归纳法证明下面的的等式： s u m ( 6 ( 3 3 ) 显然，如果令= d ，就得到了我们的定理。因为索引l j t ，也就是说一共只有 2 。个p x l ，x 2 ，z 小 当t = 1 的时候，从p 的定义，不难验证等式( 3 3 ) 的正确性。 假设当t = k 的时候( 1 k d ) ，等式( 3 3 ) 成立。也就是说，有下面的式子 s u m ( t l ：h l ， v z j 当t = k + 1 时，在等式( 3 4 ) 中令+ 1 = “+ l ，则有 ：h i ， x 、 厶 v q 2 j ， j ) 同样的，在等式( 3 4 ) 中令z k + l = h t + l ， s u 仇( f l ： 1 ，- ，k ： 女，0 ：h 女+ l ， 划卜 。_ 4 0 ：x d ) + p 【z ，z t ，z t + ，。t + z ，z a 】) 3 5 1 1 茁t ， t + ，z t + 。，- ，z d ， 3 - 6 、；、，j d z 2 z l zp 丰 “r【 j 9 一 g磊 m 咏 似 = 觇 k p 徊 札 一、m 。曲，一一，i “ 卜 g一，蝴 q z 饥 o p ，、 ， “ “ 墙。兀o，“，、l 矗 “ k 一 ， l s k。随 吣，一，cl【 k 曲 b 有 孵 肌 印 0 s 。汹 ，一，j、l泳 埘 妇 3o l a p 数据立方体上的区域和问题 由等式( 3 5 ) 和等式( 3 6 ) ，有 = s u m ( 1 l ：h i ，- ，l k ：h k ，0 ：h k + l ，0 ：x k + 2 ，0 ：x d ) 一s u m ( 1 1 ：h i ，f 女：h k ，0 ：f e + 1 ，0 ：x k + 2 ，0 ：贯d ) = 蛛。舞，岣。 ( 洳，) 姚，一靴， v a v j e l j 丢，1 j k f k 】i = ? i ls c i ，) + r t g - ，。一，z t + - ，z t + z， ，】， l = 。q ；。，磊! ，。+ 。 ( 荩sc i ，) + p c 2 7 1x 2 - ，x d ) 由数学归纳法，等式( 3 3 ) 成立，定理也得到了证明。 在定理3 1 里，等式( 3 2 ) 中一共有2 0 个项相加，每个项都是由p 中的一个单元和它 所决定的符号函数组成的乘积。也就是说，在计算一个区域和的时候，所花的时间 是是0 ( 2 4 1 。 现在我们来讨论计算p 所花的预处理时间，简单地直接计算需要o ( n 。) 的时 间；如果利用定理3 1 ，则有一个计算时间为n ( 2 0 一1 ) 的算法。下面给出一个计算 时间为d n 的算法。 算法一共分为d 个阶段。在第个阶段，在a 中沿着维数为l 的方向计算一维 前缀和，存放到数组p 中，记为p l 。在第i 个阶段，1 曼isd ，在只一1 ( 上一个 阶段输出的数组) 中沿着维数为i 的方向计算一维前缀和，存放到数组p 中，记为 只。实际上，算法的执行过程中只需要一个数组p 来存放预处理的中间结果。当算 法执行完后，单元p y l ，y d 中实际上就是o 。， l ，则称为分块算法。如果使用基本算法计算，因为a 中的每个单元都可以从p 计算出来，那么数组a 可以不用存储，但是分块算法则依赖于数组a 。 给定d 维数组a 及其对应的分块前缀和数组p ，计算区域和s u m ( 1 1 ：h l ，f 2 ： 2 ，f d ：) 。对所有的j d ，令_ = b l z j l b j ，f ；= bf z a b 1 ，h ；= bl h j b j ， ；= m i n ( b f h j b ，n j ) ，显然，有譬墨如兰，sh j5 危? ，但是f ， h j 并不意味着 以 h ：。下面我们分两种情形来讨论分块的计算方法： 3 3 1 第一种情形 先考虑查询区域满足v j d ，g 1 时，更新算法与求分块前缀和数组的算法十分相似，也是分成两个阶段。在第 一个阶段，对a 中所有大小为b b b 的分块，把这个分块中的更新增加值合并 成一个更新增加值，这个更新的增加值就是这个分块中所有发生的更新的增加值的 和。第二个阶段，因为只对数组a 进行压缩，所以压缩后的更新和b = l 的情形一 样，以合并的更新作和新的数组作为输入，执行b = 1 时的算法。 3 5 相关工作 在实际算法设计的时候，问题不同，要考虑的因素会更多，如选取那些维数参与预 处理的计算；在应用分块算法的时候，块的大小也是一个重要的因素。关于这方面 的讨论，请参见文献4 9 1 。 g e f f n e r 等人f 4 3 提出了相对前缀和的数据结构，改进了更新的最坏时间。后 来提出来的动态数据立方体4 2 ，改善了查询时间和存储空间。c h a n 和i o a n n i d i s i 2 3 1 用分层的数据立方体来研究区域和问题，并讨论了如何在查询时间和存储空问之 间保持平衡。文献f 8 4 ，9 3 1 借助小波研究o l a p 上的区域和问题的近似解。 实际上，如果一个查询闯题的二元运算存在逆运算，那么只要对这一章中的算 法稍加修改，就可以移植过去作为相应问题的查询算法。 1 7 4 o l a p 数据立方体上的区域最大值问题 4 1 引言 如果区域搜索问题的定义在半群上，那么数据的之间的二元运算是没有逆运算的。 最大值函数一般没有逆函数，我们以区域上的最大值问题作为典型代表来研究，最 大值的查询算法和数据结构也基本上适用于半群中的其他区域搜索问题。 在o l a p 环境下，考虑求d 维数组a 中的某个矩形的最大值索引的问题，其 中数组a 大小为m m x 扎d 。同第3 章，我们假设数组的索引从o 开始，用 n = ( 0 ：n l 一1 ，0 ：n d 一1 ) 表示a 的索引的定义域，而集合d = l ，2 ，町依 然表示维度的定义域。 o l a p 上的区域极大值的查询问题可以表示成在a 的给定区域中计算m a x a n d e x m a x i n d e x ( 1 l ：h i ，- 一，f d ：h a ) = 忙1 ，z d ) 这里有( v i d ) ( 1 i 冬x i 曼h i ) 且a x t ，z 。 = m a x a y l ，v d l ( v i d ) ( 1 i y i 冬 ) ) 。 如果d = 1 ，我们通常把n ，f 和h 的下标1 去掉。如果没有申明，用q 来表示输 入请求的查询区域。 在一个特定的查询区域中，可能存在不止一个最大值。在这种情形下，我们假 定算法返回查询区域中其中任意一个最大值的索引。 为了方便，在本章中用函数m a x 来表示某个查询区域的最大值，用函数? 7 i a x 来 表示某个集合的最大值。 4 2 基本的树算法 因为不存在逆运算，所以第3 章的算法就不能用了。我们用基于树的算法来查找区 域中的最大值，查询中访问的树的节点数来表示算法时间复杂度。这里用来存放预 1 8 4o l a p 数据立方体上的区域最大值问题 处理信息的树形数据结构，可以看作是一种广义的方树( q u a d t r e e ) f 7 1 1 。树中的每 个非叶子节点z 都覆盖一个d 维的区域，记作g ( z 1 ，包含了以z 为根节点的子树中 的所有叶子节点。我们预先计算c ( x ) 中的最大值，并把这个值存放在节点z 中。非 叶子节点z 所覆盖的区域被分成了b 4 不相交的区域，每个区域被z 的一个孩子结点 所覆盖。这样，我们就构造了一棵几乎每个节点都具有相同的扇出数目的平衡树的 数据结构。 对于所用的树结构，算法采用分支界定( b r a n c ha n db o u n d ) 6 2 1 的方法来加快 某个区域中查找最大值的速度。我们先给出一维情形下的算法，然后推广到d 维的 情形。 4 2 1 树的构造 树的叶子节点被称作l e v e l - o 节点，一个节点是第i + 1 层的节点，如果它的儿子结点 的最大层数是i 。除了每一层的最后一个非叶子节点，所有的非叶子节点都恰好有b 个孩子结点，b 被称作树的扇出。 给定大小为n 的数组a ，它的单元要作为树的叶子节点存储。我们可以按照下 面的方法来自下而上，从左到右的构造a 的b 叉树。把数组a 划分成不相交的区 域，除了最后一个区域，其它的每个区域里有b 个a 的单元。在每个划分的区域 里，给b 个节点创建一个父节点，计算它们的m a x _ i n d e x 并把它存放在父节点中， 这一层中的最后一个父节点可能不足b 个子节点。把新创建的陬6 1 的父节点看作新 的数组a ，递归的执行上述过程，直到在一层里只有一个节点，这个节点就是构造 的树的根节点。图4 1 是一个大小为n = 1 4 的数组，划分为b = 3 而构造的一棵树的 例子。显然，树的根节点在f l 0 9 6 n 层。 给定一棵树，令d = f l o g 。佗 ，用“旷来表示两个串的并，用c i 来表示连续i 个 重复的字符c 的串。首先自左向右的来标记树的叶子节点，它们被编码成长度为5 的b 进制串，树的最左边的节点就是用串0 6 来标记的。其次，把层i 0 上的节点 也自左向右的标记为长度为6 的编码后的b 进制串，最左边的串是( o 扣i i , i ) ( 参见图 42 ) 。 4 2 2 最低的节点 用( f ：h ) 表示a 的查询区域，这个区域包括了所有的单元i ，zl e i 茎h 。c ( x ) 表示 以z 为根节点的子树所覆盖的叶子节点的区域。在图4 1 中，z 2 的覆盖的区域就是 c ( x 2 ) = ( o ：8 ) 。 任意给定一个查询区域q = ( f ： ) ，我们用下面的过程来寻找覆盖区域q 的 1 9 l e v e l 40 l a p 数据立方体上的区域最大值问题 o123456789 1 0 1 ，21 3 l垒l i曼! 塑j1 5 臻l鲢!j l垒l 墼l l 第4 1 图：n = 1 4 和b = 3 的6 叉树的查找 o c o0 0 10 0 1 00 1 10 1 20 2 00 2 1 0 2 21 0 01 0 11 0 21 1 01 1 第4 2 图：佗= 1 4 和b = 3 的b y 树的编码 最底层的节点。把f 和h 表示成d 位的b 进制串，不妨令f = ( “h 一，钍6 ) ，h = ( ”一，v 6 ) 。假设j 和h 的前位是一样的，就是说u 1 = ，u 。= v 。，z l w + 1 让。，。这样，最底层的节点应该是z = ( u 。珏。i p ) ，节点z 在层d w 并且覆盖 区域o f z l 中最多有扩个节点。 这个算法最多经过d 次字符比较就可以找到w ，也就是说最多用o ( 1 0 9 n ) 步就可 以了。如果计算模型支持b 进制串的位操作，叫= f l o g b ( u t ，u 5 ) o ( v l ，一，) 1 ， 那么我们可以在常数时间里找到叫。 晰3 ： ， o 4 2 3 查找算法 4o l a p 数据立方体上的区域最大值问题 给定