（应用数学专业论文）几何区域查询算法的研究.pdf

哈尔滨理t 人学理学硕f ? 学位论文 几何区域查询算法的研究 摘要 几何区域查询问题是计算几何领域的一个重要研究内容，它来源于数据库 和地理信息系统应用的需求而产生并迅速发展，同时在计算机图形学、模式识 别等领域得到了广泛的应用。该问题往往是某一领域中的关键性子问题，如光 线追踪、隐藏面消除、相交性判定、相似性查询、最近邻查询等。 数据查询的实质是对数据的分类索引的过程，一般分为两类：一类是对数 据空间的分割，将整个数据空问递归划分为一系列子空间；另一类是将高维空 间中的数据对象映射到一维空间中，然后利用一维空问中数据问的有序性高效 的处理数据。 本文主要做了以下工作： 1 凹顾了计算几何及几何区域查询的相关理论、常见的区域查询类型以及 国内外的研究现状。从数学理论的角度出发，利用代数学中半群的概念，在加 权意义下给出了区域查询问题统一的理论模型，并利用耗费函数作为衡量算法 效率的计算模型，为区域查询算法的提出、实现及复杂度分析提供了理论依据 和判断准则。 2 对正交区域查询问题的一些经典数据组织结构的构建思想、查询算法及 实现方法做了详细分析和研究，这是进行算法改进和创新的基础和依据。 3 根据数据对象多个属性问重要性的差异，采用“粗筛”与“细筛”相结 合，层次化的查询结构对数据空问进行了分割。首先，对数据对象进行大尺度 的粗选，排除大量无关数据；其次，采用较小的尺度进一步缩小可选集的范 围；最后，采用精确的查询。具体来讲，为了获得较高的查询和动态更新效率 并且提高数据组织的灵活性，采用了以地址方式存储数据的链表结构作为基本 数据载体；为了实现不同尺度的分割，采用了改进的1 3 确定性跳跃表；由于 链表是一种线性存储结构较难用于高维数据对象，为此采用了将一维链表映射 到高维空间的办法实现了层次化数据结构，使其成为适应高维空间区域查询的 索引结构。该结构继承了跳跃表的优点。利用确定性跳跃表来代替高度递归的 区域查询树，该结构既实现了对k 维空间区域查询的高效性，又规避了跳跃表 结构本身的缺点。本文给出了该结构的完整定义，并给出了该结构的实现算法 以及建立在该结构之上的查询、插入和删除算法。通过对计算模型分析证明了 哈尔滨理t 人学理学硕l ：学位论文 相应算法复杂度。 关键词k 维区域查询；区域树；跳跃表；1 3 确定性跳跃表 i l 哈尔滨理t 人学理学顾l ：学化论文 a l g o r i t h mr e s e a r c ho ng e o m e t r i cr a n g eq u e r y a b s t r a c t t h eg e o m e t r i cr a n g eq u e r yp r o b l e mi sa l li m p o r t a n tr e s e a r c hc o n t e n ti n c o m p u t a t i o n a lg e o m e t r y i ta r i s e si nt h en e e df o rt h ea p p l i c a t i o n so fd a t a b a s ea n d g 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 ( g i s ) ，d e v e l o p sr a p a i d l ya n df i n d si t sw i d e a p p l i c a t i o n si nc o m p u t e rg r a p h i c s ，p a t t e r nr e c o g n i t i o ne t c i ti su s u a l l yac r u c i a l s u b r o u t i n ei nac e r t a i nf i e l ds u c ha sr a yt r a c i n g ，h i d d e n - s u r f a c er e m o v a l ，i n t e r s e c t i o n j u d g e ，s i m i l a r i t yq u e r ya n dn e a r e s tn e i g h b o rq u e r y e s s e n t i a l l y , d a t aq u e r yi st h ep r o c e s so fc l a s s i f y i n gd a t ao b j e c t s g e n e r a l l y , i t c a nb es o l v e di nt w od i f f e r e n tw a y s ：o n ei st op a r t i t i o nt h ed a t as p a c e ，i nw h i c ht h e w h o l ed a t as p a c ei sr e c u r s i v e l yp a r t i t i o n e di n t oas e r i e so fs u b s p a c e s ；t h eo t h e ri st o m a pd a t ao b j e c t si nh i 【g hd i m e n s i o n a ls p a c ei n t oo n e - d i m e n s i o n a ls p a c ef i r s t ，t h e nt o b ed e a l tb yu s i n gt h eo r d e rb e t w e e nd a t ai no n e - d i m e n s i o n a ls p a c ew i t hh i 【g h e f f i c i e n c y t h em a i nr e s e a r c hw o r ko ft h i sp a p e ri sa sf o l l o w s ： 1 t h er e l a t e dt h e o r yi nc o m p u t a t i o n a lg e o m e t r ya n dg e o m e t r i cr a n g eq u e r y , c o m m o nt y p e so fr a n g eq u e r i e sa n dt h ed o m e s t i ca n di n t e r n a t i o n a lr e s e a r c h d e v e l o p m e n ta r ei n t r o d u c e d f r o mt h ev i e wo fm a t h e m a t i c s ，t h eu n i t e dt h e o r e t i c a l m o d e lf o rr a n g eq u e r yb yu s i n gt h ec o n c e p to fs e m i g r o u pi na l g e b r au n d e rt h e m e a n i n go fw e i g h ti sg i v e n a n dc o s tf u n c t i o n sa r eu s e da sc o m p u t a t i o n a lm o d e lt o p o r t r a ya n da n a l y z ea l la l g o r i t h m se f f i c i e n c y w h i c hp r o v i d e st h e o r e t i c a lj u d g er u l e 南rt h ep r o p o s a la n di m p l e m e n t a t i o no fr a n g eq u e r ya l g o r i t h m sa n dt h e i rc o m p l e x i t y a n a l y s i s 2 t h ec o n s t r u c t i o ni d e a so fc l a s s i cd a t ao r g a n i z a t i o ns t r u c t u r e si no r t h o g o n a l r a n g eq u e r y , q u e r ya l g o r i t h m sa n dt h e i ri m p l e m e n t a t i o na l ea n a l y s e da n ds t u d i e di n d e t a i la n dd e e p l y , w h i c hi st h eb a s i sf o ru st om a k ei m p r o v e m e n ta n dc r e a t i o nf o r r e l a t e da l g o r i t h m s ， 3 d a t as p a c ei sp a r t i t i o n e da c c o r d i n gt ot h ed i f f e r e n c eo ft h ei m p o r t a n c e b e t w e e na t t r i b u t e so fd a t ao b j e c t sb yh i e r a r c h i c a lq u e r ys t r u c t u r e ，c o m b i n i n gc o a r s e s c r e e n i n ga n dr e f i n es c r e e n i n g a tt h eb e g i n n i n gr u g g e dg r i di su s e dt oe x c l u d ea 1 1 1 哈尔滨理t 人学理学硕i ：学位论文 l a r g ea m o u n to fu n r e l a t e dd a t ao b j e c t s t h e n , ar e f i n e d 鲥di su s e dt or e d u c et h e s c o p ef o rs e l e c t a b l eo b j e c t sf u r t h e rb yt a k i n gs m a l l e rs c a l e s f i n a l l ya l l a c c u r a t e q u e r yi st a k e n i nd e t a i l ，l i n k e dl i s ts 咖c t u r e s ，i nw h i c hd a t ai ss t o r e di na d d r e s s ，a r e a d o p t e d 嬲b a s i cd a t ac a r r i e rt oa c h i e v et h eh i g he f f i c i e n c yo fq u e r ya n dd y n a m i c u p d a t i n ga n dt oi m p r o v et h ef l e x i b i l i t yo fd a t ao r g a n i z a t i o n ；t h ei m p r o v e d1 - 3 d e t e r m i n i s t i cs k i pl i s ti st a k e nt oc a r r yo u tt h ep a r t i t i o nf o rd a t as p a c eu n d e rd i f f e r e n t s c a l e s h i e r a r c h i c a ld a t as t r u c t u r ei sr e a l i z e db ym a p p i n gl i n k e dl i s t si no n e - d i m e n s i o n a ls p a c ei n t oh i g hd i m e n s i o n a ls p a c et om a k ei tb et h ei n d e xs t r u c t u r e s u i t a b l et or a n g eq u e r yi nh i g hd i m e n s i o n a ls p a c ed u et ot h ef a c tt h a tal i n k e dl i s ti s l i n e a rs t o r a g es t r u c t u r ed i f f i c u l tt ob ea p p l i e di nh i g hd i m e n s i o n a ls p a c e t h e s t r u c t u r ei n h e r i t st h ea d v a n t a g e so ft h es k i pl i s t t h eq u e r yo fh i g he f f i c i e n c yi nk - d i m e n s i o n a ls p a c ei sr e a l i z e db yr e p l a c i n gh e i g h t - r e c u r s i v er a n g eq u e r yb yt h e d e t e r m i n i s t i cs k i pl i s t ，m e a n w h i l et h ed r a w b a c k ( r a n d o mu n d e t e r m i n i s t i cf a c t o r s ) c a n d ea v o i d e d t h ec o m p l e t ed e f i n i t i o no ft h i sk i n do fs t r u c t u r e ，i t si m p l e m e n t a t i o n a l g o r i t h ma n dr a n g eq u e r y , n o d ei n s e r t i o na n dd e l e t i o na l g o r i t h m sb a s e do nt h i s s t r u c t u r ea l eg i v e n t h et i m ec o m p l e x i t i e so ft h ec o r r e s p o n d i n ga l g o r i t h m sa r e a c h i e v e db ya n a l y z i n gt h ec o m p u t a t i o n a lm o d e l k e y w o r d sk - d i m e n s i o n a lr a n g eq u e r y , r a n g et r e e ，s k i pl i s t ，1 - 3d e t e r m i n i s t i c s k i p l i s t i v 哈尔滨理工大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文几何区域查询算法研究，是 本人在导师指导下，在哈尔滨理工大学攻读硕士学位期间独立进行研究工作所 取得的成果。据本人所知，论文中除已注明部分外不包含他人已发表或撰写过 的研究成果。对本文研究工作做出贡献的个人和集体，均已在文中以明确方式 注明。本声明的法律结果将完全由本人承担。 作者签名：莓博 日期： 砷年；月3 0 日 哈尔滨理工大学硕士学位论文使用授权书 几何区域查询算法研究系本人在哈尔滨理工大学攻读硕士学位期间在 导师指导下完成的硕士学位论文。本论文的研究成果归哈尔滨理工大学所有， 本论文的研究内容不得以其它单位的名义发表。本人完全了解哈尔滨理工大学 关于保存、使用学位论文的规定，同意学校保留并向有关部门提交论文和电子 版本，允许论文被查阅和借阅。本人授权哈尔滨理工大学可以采用影印、缩印 或其他复制手段保存论文，可以公布论文的全部或部分内容。 本学位论文属于 保密口，在年解密后适用授权书。 不保密团。 ( 请在以上相应方框内打) 作者签名：事博 日期：2 ，稗多月如日 导师签名：o 搠濞日期：秒，年3 月歹oe l 哈尔滨理t 人学理学硕l ：学位论文 第1 章绪论 1 1 研究目的及意义 区域查询( r a n g eq u e r y ) 是许多应用科学领域中的基本问题，已经在计算 几何和空间数据库中进行了广泛并深入的研究。给定一个几何对象集，一仑典 型的范围查询是要求报告出于查询目标相交的所有对象。区域查询算法广泛地 应用于计算机图形学、数据库查询、地理信息系统、多媒体信息检索技术和数 据挖掘等领域中。 随着计算机硬件性价比的大幅提升交互式图形学的时代已经到来，它在医 学镜像、虚拟现实、电影特技、数据的可视化等方面显示了强大的生命力，这 些技术中却蕴含着大量支持诸如光线追踪和隐藏面消除的区域查询算法。 计算机图像数码技术以及互联网技术的飞速发展，使人们接触到大量的图 形、图像等超文本信息，如何实现高维特征向量的相似性查询成了一个重要的 研究课题。区域查询算法成为访问高维数据库的重要工具，例如人脸自动识 别：这时如果能提取出适当多的人脸特征，就可以将有关人群的人脸特征向量 存入数据库。应用时输入待查找人脸特征向量，在数据库中查找与之距离在某 个指定范围内者，如此实现对输入信息的识别。其抽象形式为，假定有一个n 维向量空间，其中点x 称为特征向量，x = ( 五，x 一，x 。) ，对l fsn ，x i 是第 f 个特征的数值。对一高维数据点c ，一个固定的半径长度，与c 距离不超过 ，的所有点形成了一个刀维超球c 。这时高维数据点的超球区域查找问题，就 是已知一个点集s ，输入一个超球c ，问c 中包含有s 中哪些点。不难看出， 前述人脸自动识别例子中，在人脸数据库中的查找问题就可以看作是此问题一 个具体的实例。在基于内容的多媒体信息检索等应用中，经常需要从多媒体数 据库中查找与给定对象最相似的k 个对象，这就是k 近邻查询。 随着智能化的、自动化的办公管理理念的提出与实施，对数据库的管理与 操作日益显得重要。当我们考察一个学籍管理的数据库，这样一个数据库所存 储的信息包括每位员工的姓名、住址、生日和工资等。对数据库的一次典型查 询，可能是要求报告出所有出生于1 9 8 0 年至1 9 8 5 年之间、身高在1 7 0 c m 至 1 8 0 c m 之间的所有学生，为了将此描述为一个数学问题，我们将每位学生表示 为平面上的一个点：点的第一个坐标是出生只期，第二个坐标是身高。在每个 点处还可以储存诸如姓名、地址等其他信息，这时对数据库的查询就转化为找 出第一坐标在1 9 8 0 至1 9 8 5 ，第二坐标在1 7 0 至1 8 0 这个矩形范围内的所有 哈尔滨理t 人学理学硕l j 学位论文 点。在计算几何中，这类查询称为矩形区域查询( r e c t a n g u l a rr a n g eq u e r y ) ，或 正交区域查询( o r t h o g o n a lr a n g eq u e r y ) 。 随着时空数据库理论研究的深入和无线网络、卫星通讯技术的进步，在汽 车或飞机等移动工具上配备一个导航系统来辅助定位和航行引导已被广泛的应 用。这样一个系统中存有一张线路图，比如我国的公路图。系统也会跟踪你的 位置，这样无论何时你总能在车载计算机的屏幕上看到自己局部的路线图，通 常是你当前所在位置周围的一块矩形区域。给定一个称为截窗的矩形区域系统 必须能够确定地图中的那些部分( 公路、城市等) 落在截窗内部，并显示这些 内容。这个过程称为截窗查询( w i n d o wq u e r y ) 。它不仅对地理图的操作有用， 在c a d c a m 等应用领域中也扮演着重要的角色，例如飞行模拟。 因此，我们对区域查询算法进行深入细致的研究，针对高维的查询要求构 造出更为合理的数据结构，在保持算法查询的效率的同时，使算法更易于理解 和便于应用。 1 2 国内外研究现状分析 1 9 7 5 年，s h a m o s 用计算机有效地计算平面的v o r o n o i 图，并发表了一篇 著名论文，从此计算几何诞生了。自那时以来该研究领域取得了辉煌的成果， 使得计算几何成为理论计算机科学领域中一个新的极有生命力的子领域，计算 几何中的研究成果已在计算机图形学、化学、统计分析、模式识别、地理数据 库以及其他许多领域中得到了广泛的应用。区域查询问题是计算几何的核心问 题之一。正交区域查询又是区域查询问题中最重要的问题之一，有许多学者致 力于研究它，并取得了丰富的研究成果。 在解决j 下交区域查询问题方面，人们采用的第一种数据结构是由f i n k e l 和 b e n t l e y t l l 于1 9 7 4 年提出的四叉树( q u a d t r e e ) 。不幸的是，四叉树在最坏情况 下的性能相当差。b e n t l e y 2 】于1 9 7 5 年提出的k d 一树( 七d i m e n s i o n a lt r e e ) ，是对 四叉树的改进。s a m e t t 3 4 l 在其专著中，对四叉树、k d 一树及其应用做过详细的 论述。数年后b e n t l e y t 5 1 于1 9 7 9 年，l e e 和w o n g 【6 l 于1 9 8 0 年，l u e k e r 【7 】于 1 9 7 8 年，w i l l a r d t 8 1 于1 9 7 9 年分别独立的提出了区域树，而借助于分散层叠技 术将查询时间改进至o ( 1 0 9 ，l + 后) 的方法，这是由l u e k e r t 7 1 和w i l l a r d 【9 】提出 的。分散层叠不仅可以用于区域树，实际上在很多需要根据同一关键码进行多 次查找的场合，都同样适用。c h a z e l l e 和g u i b a s t l 0 川对这一技术做了透彻的介 绍。分散层叠还可以应用于动态设置【1 2 1 。c h a z e l l e t l 3 】提出了一种修改后的层次 化区域树，这是解决二维区域查询问题很有效的数据结构。他成功地将存储空 哈尔滨理t 人学理学硕l j 学位论文 间降至o ( n l o g n l o g l o g n ) ，同时保持了o ( 1 0 9 n + 七) 的查询时间。c h a z e l l e 还指 出如果待查询区域在某一侧是无界的( 例如形为 x ，x 】【y ，佃】) ，那么借助于 一棵优先查找树( p r i o r i t ys e a r c ht r e e ) ，只需线性空间，就能够实现o ( 1 0 9 n ) 的 查询时问。对于更高维的情况，c h a z e l l e t 4 l 同样提出了一种结构，使用 o ( n ( 1 0 9 n l o g l o g n ) 扣) 的存储空间，就可以在对数多项式的查询时闯 ( p o l y l o g a r i t h m i cq u e r yt i m e ) 内回答一次d 维查询。o v e r m a r s l l 5 l 提出了一种解 决区域查找问题的更加有效的数据结构：如果所有点的位置都限制在u u 的网 格上，那么查询时间将是o ( 1 0 9 l o g u + k ) 或者o ( v - j + 七) ，具体是哪一结果， 取决于允许的预处理时问。随着数据属性复杂性要求的增加大量范围查询问题 表现为多维查询问题，而经典的查询算法是采用，| 个独立的一维查询，因此查 询效率很有限。j 下是这个原因，一种被称为空问访问法的算法s a m s ( s p a t i a l a c c e s sm e t h o d s ) 被广泛采用。g a e d e 和g u n t h e r t l 6 】，b o h m t 1 详细的介绍了各 种s a m s 算法。随后各种针对多维查询的数据结构如b t r e e ，b + t r e e ，a v l t r e e ，u n i v e r s a lb t r e e ( u b t r e e ) 0 8 】相继被提出。近年来，针对空问数据库索引 的研究引起了人们越来越多的兴趣和关注。为了快速有效地处理存储于空间数 据库中的海量空间数据，专家学者提出了大量的基于磁盘的空问查询方法。其 中，1 9 8 4 年由g u t t m a n 提出的r 树是目前最流行的动态空间索引结构，广泛 应用于原型研究和商业应用中。其后，人们在此基础上针对不同空间运算提出 了不同改进。经过2 0 年的发展，不断产生的r 树变体逐渐形成了一个枝繁叶 茂的空间索引r 树家族，张明波等0 9 1 给出了详细的介绍。 1 3 主要研究内容 本课题来源于黑龙江省自然科学基金项目。 1 研究常见的区域查询类形以及目前国内外的研究现状等基本问题，从 数学理论的角度出发，利用代数学中半群的概念，在加权意义下统一区域查询 问题的理论模型，并利用执行耗费函数作为衡量算法效率的计算模型。 2 对于正交区域查询问题的一些较为经典数据组织结构及查询算法，以 它们不断的发展为线索，深入研究k 以树、区域树、高维区域树、分散层叠等 结构的构建思想和实现算法以及相应查询算法和其它一些操作算法的性能和复 杂度。 、 3 通过深入分析、比较、整理上述经典数据结构和相关算法及其创新思 想，采用由p u g l l 提出的跳跃表( s k i pl i s t ) ，并由m u n r o 等进行改进得到的确 定性跳跃表( d e t e r m i n i s t i cs k i pl i s t ) 为基础设计一种适应多维空问区域查询的 哈尔滨理t 人学理学顾l ：学位论文 索引结构。 4 给出该结构的完整定义，并给出该结构的实现算法以及建立在该结构 之上的查询、插入和删除算法。通过对计算模型分析证明算法复杂度。 哈尔滨理t 人学理学硕l ：学化论文 第2 章区域查询问题简介 计算几何是设计一种能够处理具有有限的性质和参数几何对象的算法并分 析其计算效率的学科。比如以下几种情况都是该学科的研究范畴： 1 给定平面( 或d 维欧氏空间) 内一个包含r 1 个元素的点集p ，找到p 中 具有最小距离的点对。 2 给定平面内的n 条线段，计算这一条线段的所有交点。 3 给定d 维欧氏空间中由，1 个半空自j 的交构成的凸多面体p ，求出p 中一 点，使某一给定的线性函数在该点取最小值。 4 给定平面内的一多边形p ( 不必是凸的) 和其内部的两点a ，b ，找出p 内由a 至：l j b 的最短路径。 这些都是计算几何的生动例子。区域查询问题是计算几何的核心问题之 一，它贯穿于该领域的整个过程。下面引入较为严密的概念。 2 1 区域查询问题的基本概念 歌是由d 维欧氏空间足d 的子集构成的一个系统，9 i 中的元素就称为区 域。下面是一些典型的区域： 1 孵咖= 与坐标轴平行的矩形或超矩形) ，即具有下列形式的集合： lt 。k ，6 ，h ，岛，a a , b d r 。 2 孵删鼬= r 4 中的半空间 。 3 孵，呻妇= r 4 中的单纯型) 。 4 9 t k 。= 尺4 中的球) 。 p 是r 4 中给定的一个包含n 个元素的点集，那么几何区域查询问题定义 为：设计一种高效的算法，使得对于给定的区域r 孵，找出p 中有哪些元素 包含在r 中，如图2 1 所示。如果p 和尺同时给定，问题转化为仅需求出 户n r 。那么对尸中的元素进行逐个测试就可以了，显然这个方法是耗时的。 通常p 是事先给定的，我们可以对它进行预处理。例如：对于d = 1 的情况， 以区问作为区域，如不进行预处理，回答个查询即有多少个点在给定区间内 的时问复杂度为0 ( 珂) ，若把数据点存储到有序结构中我们可以在o ( 1 0 9 n ) 的时 间内完成。计算这些点仅是区域查询问题的一种形式，我们称之为计数查询。 还有报告查询( 即报告出满足条件的具体是哪些点，在什么位置) 和非空测试 哈尔滨理t 人学理学硕i j 学位论文 查询( 即判断尺中是否有尸的点) ，类似的还可以给p 中的点赋上权值，然后 计算满足条件的点中具有最大权值的点或它们权的和。下面我们将上述所有情 况用抽象的数学语言表达出来：对于任意的点p p ，被赋予权w ( p ) s ，其 中( s ，+ ) 是一个可换半群，查询可表述为求出包含在r 中的所有p p 的权的 和。例如，对于计数查询( s ，+ ) 是一个自然数加法半群，且所有的以p ) = l ；对 于求最大权的查询，( s ，+ ) 是一个实数集上的，定义了一个取两数最大值运算 的可换半群；对于非空测试查询，( s ，+ ) 中s = y e s ，n o ，”+ ”= 逻辑或，所有点 的权都为y e s 。 图2 1 区域夯询 f i g 2 - 1r a n g eq u e r y 2 2 区域查询的常用数据结构 2 2 1 q u a d e r - t r e e 石脚 图2 - 2 四义树中某个节点及其四个孩子 f i g 2 - 2n o d ea n dt h ef o u rc h i l d r e no fq u a d t r e e 所谓四叉树是一棵有根的树，其中每个内部节点都有四个孩子。在四叉树 中，每个节点对应于一个正方形。如果节点v 有孩子，那么这些孩子就分别对 哈尔滨理t 人学理学硕i j 学位论文 应于，所对应正方形的四个象限。这种结构j 下是因此而得名。也就是说所有叶 子对应的正方形合在一起，就形成了对根节点所对应正方形的一个子区域划 分，称作四叉树划分( q u a d t r e es u b d i v i s i o n ) 。图2 3 给出了一棵四叉树及与之 对应的子区域划分。根节点的四个孩子，分别标记为n e 、n w 、s w 和s e ， 借此表示他们各自对应的象限，n e 表示东北象限，n w 表示西北象限等。 l ( a ) 四义树划分( b ) 对应的四义树 ( a ) q u a d t r e es u b d i v i s i o n( b ) c o r r e s p o n d i n gq u a d t r e e 图2 3 四义树及其对应的子区域划分 f i g 2 - 3q u a d t r e ea n dq u a d t r c es u b d i v i s i o n 借助于四叉树，可以存储不同类型的数据。下面介绍其中的一种一平面上 的一组点。对于这种数据，只要某个j 下方形中包含的点多于一个，就要递归地 对其进行分割，因此对于一个j 下方形仃中给定的一组点p ，可以定义一棵四叉 树如下：设盯= i x 口，x ：】【y ，y ：】 若c a r d ( p ) l ，则四叉树由唯一的一片叶子组成，其中存放了点集p 以及 正方形盯。 否则，分别设o n e 、盯矿、o r 靶为盯的四个象限。 令x 。甜= ( b + 工：) 2 ，y 。盈= ( y 口+ j ，：) 2 ，并定义 = p p ip ， 工蒯勘， y 删) ， p 品= p p p ，x 。甜且p ， y 蒯) ， e s 矿= p p ip ，工。耐且p ，y m 讨) ， 户蠢= p pip ， x 。耐上p ，y ，耐 。 如图2 2 所示，这样一棵四叉树的根节点v 中存放了盯。那么，我们将存放于， 处的j 下方形仃( ，) 。此外，有四个孩子： n e 一集合( 即落在正方形仃艇中各点) 对应的四叉树，以它为根节点； 哈尔滨理t 人学理学顾i ：学位论文 n w 一集合尸矽( 即落在正方形仃中各点) 对应的四叉树，以它为根节点； s w 一集合p s ( 即落在正方形o r s w 中各点) 对应的四叉树，以它为根节点； s e 一集合只f ( 即落在正方形仃。f 中各点) 对应的四叉树，以它为根节点； 定义中对“小于或等于”以及“大于的选择，根据这种选择，每条垂直分割 线都属于左侧的两个象限，而每条水平分割线都属于下方的两个象限。 2 2 2b t r e e 结构 当查找的文件较大，且存放在磁盘等直接存取设备中时，为了减少查找过 程中对磁盘的读写次数，提高查找效率，基于直接存取设备的读写操作以 “页为单位的特征。 1 9 7 2 年r b a y e r 和e m m c c r e i g h t 提出了一种称之为b 树的多路平衡查找 树。它适合在磁盘等直接存取设备上组织动态的查找表。 图2 4b 树的父母节点 f i g 2 - 4p a r e n tn o d eo fb 一吮 一棵m ( m23 ) 阶的b 树是满足如下性质的m 叉树： 1 每个结点至少包含下列数据域：( ，p o ，k l ，p 。，七2 ，k i ，p ，) 其中：为关 键字总数，k i ( 1 i j ) 是关键字，关键字序列递增有序：k 。 k ： k i 。 p ，( 0 f ，) 是孩子指针，如图2 _ 4 所示。对于叶结点，每个p ，为空指针。实 用中为节省空间，叶结点中可省去指针域辟，但必须在每个结点中增加一个标 志域l e a f , 其值为真时表示叶结点，否则为内部结点。在每个内部结点中，假 设用k e y s ( p ，) 表示子树n 中的所有关键字，则有： l 琵, y s ( p o ) k l k e y s ( p 1 ) k 2 k f k e y s ( p j ) 。 2 所有叶子是在同一层上，叶子的层数为树的高度h 。 3 每个非根结点中所包含的关键字个数，满足：im 2l 一1 j m l 即 每个非根结点至少应有i m 2l 1 个关键字，至多有m 1 个关键字。因为每个 内部结点的度数正好是关键字总数加l ，故每个非根的内部结点至少有im 2l 子树，至多有m 棵子树。 哈尔滨理t 人学理学硕l j 学位论文 4 若树非空，则根至少有1 个关键字。故若根不是叶子，则它至少有2 棵子树。根至多有m 1 个关键字，故至多有m 棵子树。 回囱 2 53 44 0 豳囱豳囱豳囱 图2 - 5 四阶b - 树 f i g 2 - 5f o u ro r d e rb t r e e 在大多数系统中，b 树上的算法执行时间主要由读、写磁盘的次数来决 定，每次读写尽可能多的信息可提高算法得执行速度。b 。树中的结点的规模一 般是一个磁盘页，而结点中所包含的关键字及其孩子的数目取决于磁盘页的大 小。如图2 5 为一棵四阶b 树。 2 2 3k dt r e e 结构 k 维查询树( k - d i m e n s i o n a ls e a r c ht r e e ) 简记为k dt r e e ，它是利用平行于 各个属性轴的半平面来分割空间，使得每个点都包含在某个矩形( 超矩形) 中 的树结构。 p 7 9 q p 5 鼍 譬 p 1 1 p 3p 9 l p 8 图2 石2 维查询树 f i g 。2 - 62 - dq u e r yg e e 下面以2 - dt r e e 为例来说明它的构造。对于二维查询树，在奇数层上的分 支按第一个属性进行，而在偶数层上的分支按第二个属性进行。根是任意选取 哈尔滨理t 人学理学硕i j 学位论文 的奇数层。 如图2 - 6 所示，在根节点处，通过一条垂线，将集合p 大小接近的左、右 两个子集，该分割线存储于根节点处。位于分割线左侧的那个子集记作， 它被存储于左子树中；位于分割线右侧的那个子集记作e 胁，它被存储于右子 树中。在根节点的左孩子处，我们继续通过一条水平线，将划分为( 上、 下) 两个子集：位于该分割线以下或者落于其上的那些点，被存储于该左孩子 的左子树中；而位于分割线以上的那些点，则被存储于右子树中。该左孩子将 记录下水平分割线的位置。类似地，m ，也将被某条水平线划分成两个子集， 它们分别被存储于右孩子的左、右子树中。对于根节点的每个孙子，再次通过 一条垂线进行划分。一般地，对于深度为偶数的节点，使用垂线进行划分；对 于深度为奇数的节点，将使用水平线进行划分。图2 - 6 显示了这种划分的进行 过程，以及对应的二分查找树的结构。称这样的一棵树为k d 树( k d t r e e ) 。 2 2 4 p r i o r i t ys e a r c ht r e e 结构 设p _ ( p i 一，p 。) 为平面上的一组点。希望设计出一种结构，来求解形如 ( 硼，g 】【q 。以】的矩形查询。为了理解如何对这种特殊性质加以利用，先来 看看一维的情况。一般的一维区域查找，就是要找出落在某个区域【g 。，q ：】之内 的所有点。为了能够有效地找出这些点，可以将所有的点组织成一棵一维的区 域树。如果待查找区域的左侧是无界的，实际上就是要查找出落在( 邶，q ，】内 的所有点。可以更高效地解决这个问题，方法是：从最左侧的点开始对一个有 序表进行遍历，一旦遇到第一个没有落在该区域中的点就立即终止遍历。采用 这种方法，查询时间为伙l 均，而不再是通常情况所需要的o ( 1 0 9 n + k ) 。 o 图2 7 集合 l 3 ，4 ，8 ，1 1 ，1 5 ，2 1 ，2 2 ，3 6 对应的一个堆 现在，又该如何将这一策略推广至左侧无界的二维区域查找昵? 无论如 何，如果不使用关联结构，就必须将户坐标的信息集成到该结构中来，这样 哈尔滨理t 人学胖学硕i ：学位论文 才能在驴坐标落在( 棚，q ，】内的所有点中， 那些点。要是采用一个简单的线性列表， 此，采用了另一种结构堆( h e a p ) 。 轻松地找出y - 坐标落在 g ，g j 】内的 并不足以漂亮地完成这任务。因 通常都是利用堆来支持优先级查询( 蹦耐t yq u e r y ) 即从一组数值中 找出最小( 或最大) 者。不过，堆也可以用以支持形如( 咖，g 。，】的一维区域查 找。就查询时间而言，堆与有序表相同，都是o ( 1 + 七) 。通常，堆优于有序表 的方面在于：无论是插入新的点，还是将最大的点删除，都可以更加高效地完 成。对我们来说，堆的树形结构还有另一个优点：它可以使得对弘坐标的集成 更加容易。 o 00 万画 图2 - 8 堆 f i g 2 - 8h e a p 如图2 8 所示，所谓的堆，就是定义如下的棵二叉树。该树的根节点存 放了最小的弘值。集合中其余的点被分成规模接近的两个子集；这两个子集也 是按照同样的规则，分别递归地存储。如图2 7 所示的，就是堆的一个例子。 只要从上而下对这棵树搜索一趟，就可以回答一次针对( 砌，g 。】的查询。每搜 索到一个节点，都要检查一下存储于该节点处的点，看看它的弘坐标是否落在 ( ，g ，】内。如果是，就报告出该点，并对其左、右子树继续搜索下去；否 则，就终止对树中该部分的搜索。例如，在针对区间( ，5 】对图2 7 中的那棵 树进行搜索时，将报告出点l 、3 和4 ，也会访问到节点8 和1 l ，不过一旦 到达这些位置后，就不再会从那里继续搜索下去。 得益于堆的灵活性，每个集合都可以任意地划分为两个子集。如果还希望 对弘坐标进行查找，就可以采用一个技巧在划分子集的时候，不是像普通 的堆那样随意进行划分，而是根据产坐标来进行划分。更准确地说，在将( 除 根节点以外的) 其余各点划分为两个子集的时候，不仅要使子集的规模相互接 近，而且前一子集中每个点的步坐标，都要小于后一子集中的所有点。这一点 哈尔滨理t 人学理学硕i ：学位论文 如图2 9 所示。 在该图中，树被画成了朝向侧面的，其目的是为了说明此处的划分是按照 y 坐标进行的。在图2 - 9 的示例中，点p ，的弘坐标最小，所以存放在根节点 中。其余的( 五个) 点按照y - 坐标一分为二。其中，点p ，、p 。和p 。的户坐标 更小，所以归入左子树。在这三个点中，p ，的弘坐标最小，于是该点就存放 在左子树的根节点处。依此类推。 p 5 p 3 p 6 p 2 n 图2 - 9 个点集及对席的优先夯找树 f i g 2 - 9p r i o r i t yt r e ea n dt h ec o r r e s p o n d i n gp o i n ts e t 对于任一点集p ，其优先查找树的形式化定义如下：( 假定，所有点的坐 标互异) 若p = 矽，则对应的优先查找树为一片空的叶子。 否则，设为集合p 中弘坐标最小的那个点。令y 删为其余诸点y 一坐标 的中值。取 。- p p p 曲) lp ， y 。甜) 对应 的优先查找树的根节点为1 ，其中存放了点p ( v ) p 而。，以及数值 y ( v ) y 。甜。此外v 的左子树为对应于集合只椭的一棵优先查找树，v 的右子 树为对应于集合只加的一棵优先查找树。 由此，可以直接导出一个构造优先查找树的o ( n l o g n ) 算法。只要所有点 已经按照弘坐标排好了序，其对应的优先查找树可以在线性时间内构造出 来。此方法的思想是，自下而上( 而不是自上而下) 地进行构造，具体的构造 过程与普通堆相同。 2 2 5 r a n g et r e e 结构 已经注意到，每次二维区域查找，实质上都是由( 前后) 两次一维子查找 构成的，坐标、，坐标方向上各一次。这就启发我们，轮流沿着驴坐标和户 坐标的方向，对点集进行划分这样就得到了k d