（计算机应用技术专业论文）空间网络数据库中最近邻查询技术的研究.pdf

摘要 摘要 最近邻( n n ) 查询技术是空间数据库领域中一个重要的研究课题。k - n n 查询计算距离一个给定的查询点最近的k 个对象。由于定位装置的广泛应 用和定位服务的增加，对空间网络数据库中静态k - n n 查询、移动数据的 连续k - n n 监视技术的研究已经成为空间数据库领域的热点课题。 本文首先介绍了现有的空间数据索引技术，对k - n n 查询及监视技术 的研究现状进行了分析。 其次，提出了一个空间网络数据两层存储模式，将网络与兴趣数据集 分开存储，并讨论了其各个组件，对其易于扩展性进行了分析。 再次，提出了增量k - n n 查询算法( i k n n q a ) ，实现了查询结果的真正 增量输出。更进一步，为了提高查询速度，提出了基于“预计算”的k - n n 查询算法( p k n n q a ) 。它们共同解决了空间网络数据库中静态的k - n n 查询 问题。 然后，对空间网络数据库中动态的k n n 监视问题进行了深入研究， 提出了增量监视算法( i k n n m a ) 和群组监视算法( g k n n m a l 。i k n n m a 以 扩展树的形式存储在n n 搜索期间遇到的网络节点的最短路径，只更新使 查询q 的n n 集发生改变的落在扩展树之内的对象和边的更新，不相关的 更新被忽略；另一方面，当更新影响到q 的结果或者当q 移动到一个新的 位置时，i k n n m a 保持扩展树的有效部分并加以利用来加速q 的新的n n s 的计算。而g k n n m a 采用共享策略减少处理时间，它将落在网络两个连 续的交叉点间的路径上的查询聚集起来，通过监视这些交叉点的n n 集来 生成结果，从而将监视移动查询转化为监视静态的网络节点，精简了问题。 最后，基于上述研究成果，对提出的算法进行了实验验证，给出了实 验结果并对其进行了分析。 关键词定位服务；空间数据库；索引结构；最近邻；r 树 燕山大学工学硕士学位论文 a b s t r a c t n e a r e s tn e i g h b o r ( n n ) q u e r yt e c h n o l o g yi sa l li m p o r t a n tt o p i ci nt h ef i e l d o fs p a t i a ld a t a b a s e s ak - n nq u e r yc o m p u t e st h ekd a t ao b j e c t st h a tl i ec l o s e s t t oag i v e nq u e r yp o i n t d u et ot h ew i d ea v a i l a b i l i t yo fp o s i t i o n i n gd e v i c e sa n d t h er i s eo fl o c a t i o n b a s e ds e r v i c e s ，r e c e n t l yt h er e s e a r c hf o c u sh a ss h i f t e dt o s t a t i ck - n nq u e r yi ns p a t i a ln e t w o r kd a t a b a s e s ( s n d b ) a n dc o m i n u o u sk - n n ( c k n n ) m o n i t o r i n go v e rm o b i l ed a t a f i r s t l y , t h i sp a p e ri n t r o d u c e st h ee x i s t i n gi n d e x i n gt e c h n o l o g i e so fs p a t i a l d a t a ；t h er e l a t e dw o r k so f k - n nq u e r ya n dm o n i t o r i n ga r ea l s og i v e n s e c o n d l y , t h i sp a p e rp r o p o s e sas t o r a g es c h e m aw i t ht w ol a y e r so fi n d e x s t r u c t u r e s ；t h es t o r a g eo fn e t w o r ka n dp o i n t so fi n t e r e s td a t as e t si sd i v i d e d i t s c o m p o n e n t sa r ed i s c u s s e d ；t h ee x p a n s i b i l i t yo f s t o r a g es c h e m ai sa n a l y z e d a g a i n , i n c r e m e n t a lk - n nq u e r ya l g o r i t h m ( i k n n q a ) i sp r o p o s e d , i tc a n o u t p m t h eq u e r yr e s u l t si n c r e m e n t a l l y f u r t h e r , f o rt h es a k eo f q u e r ys p e e d ，t h i s p a p e rp r o p o s e sap r e e o m p u t a t i o n - b a s e dk - n nq u e r ya l g o r i t h m ( p k n n q a ) t h e yr e s o l v et h ep r o b l e mo f s t a t i ck n nq u e r yi ns n d b t h e n , t h ep r o b l e mo fd y n a m i ck - n nm o n i t o r i n gi ns n d bi sr e s e a r c h e d t h o r o u g h l y ；i n c r e m e m a lk - n nm o n i t o r i n ga l g o r i t h m ( i k n n m a ) a n dg r o u p k - n nm o n i t o r i n g ( g k n n m a ) a l g o r i t h ma r ep r o p o s e d i k n n m as t o r e st h e s h o r t e s tp a t h s ( f r o mq ) t ot h en e t w o r kn o d e se n c o u n t e r e dd u r i n gt h en ns e a r c h i nt h ef o r mo f a ne x p a n s i o nt r e e i to n l yu p d a t e sf r o mo b j e c t sa n de d g e sf a l l i n g i nt h ee x p a n s i o nt r e ec a na l t e rt h en ns e to fq ；i r r e l e v a n tu p d a t e sa r es i m p l y i g n o r e d o nt h eo t h e rh a n d ，w h e nt h eu p d a t e sa f f e c tt h er e s u i to fqo rw h e nq m o v e st oan e wl o c a t i o n , i k n n m ad e t e r m i n e st h ep a r to ft h ee x p a n s i o nt r e e t h a tr e m a i n sv a l i d ，a n dr e u s e si tt oa c c e l e r a t et h ec o m p u t a t i o no f t h en e wn n s o fq ，g k n n m af o l l o w st h es h a r e de x e c u t i o np a r a d i g mt or e d u c et h e i i a b s t r a c t p r o c e s s i n gt i m e i np a r t i c u l a r , i tg r o u p st o g e t h e rt h eq u e r i e st h a tf a l li nt h ep a t h b e t w e e nt w oc o n s e c u t i v ei n t e r s e c t i o n si nt h en e t w o r k , a n dp r o d u c e st h e i r r e s u l t sb ym o n i t o r i n gt h en ns e t so ft h e s ei n t e r s e c t i o n s i tb e n e f i t st h e r e d u c t i o no ft h ep r o b l e mf r o mm o n i t o r i n gm o v i n gq u e r i e st om o n i t o r i n gs t a t i c n e t w o r kn o d e s f i n a l l y , b a s e d o nt h e s e r e s e a r c h e s ，t h e s ep r o p o s e da l g o r i t h m s a r e e x p e r i m e n t a l l yv e r i f i e d e x p e r i m e n tr e s u l t sa r eg i v e na n da n a l y z e d k e y w o r d sl o c a t i o n - b a s e ds e r v i c e s ；s p a t i a ld a t a b a s e s ；i n d e xs t r u c t u r e ； n e a r e s tn e i g h b o r s ；r - t r e e 燕山大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文空间网络数据库中最近 邻查询技术的研究，是本人在导师指导下，在燕山大学攻读硕士学位期间 独立进行研究工作所取得的成果。据本人所知，论文中除已注明部分外不 包含他人已发表或撰写过的研究成果。对本文的研究工作做出重要贡献的 个人和集体，均已在文中以明确方式注明。本声明的法律结果将完全由本 人承担。 作者签字 j 圭古7 , -日期：枷石年7 月曲日 燕山大学硕士学位论文使用授权书 空间网络数据库中最近邻查询技术的研究系本人在燕山大学攻读 硕士学位期问在导师指导下完成的硕士学位论文。本论文的研究成果归燕 山大学所有，本人如需发表将署名燕山大学为第一完成单位及相关人员。 本人完全了解燕山大学关于保存、使用学位论文的规定，同意学校保留并 向有关部门送交论文的复印件和电子版本，允许论文被查阅和借阅。本人 授权燕山大学，可以采用影印、缩印或其他复制手段保存论文，可以公布 论文的全部或部分内容。 保密口，在年解密后适用本授权书。 本学位论文属于 不保密日。 ( 请在以上相应方框内打“”) 作者签名5 睡，卜 新躲讪抬 日期：跏6 年9 月功日 日期：沙产? 月胡 第1 章绪论 1 1 研究背景 第1 章绪论 最近邻( n e a r e s t n e i g h b o r s ，n n ) 查询是计算机科学中一个传统的问题。 这种查询类型通常应用于内容的相似性检索、模式识别、地理信息系统 f g e o g r a p h i ci n f o r m a t i o ns y s t e m , o r s ) 等。 地理信息系统是能够收集、管理、查询、分析、操作以及表现与地理 相关的数据信息的计算机信息系统，能够为分析、决策提供重要的支持平 刽。它广泛地应用于地学、资源管理、土地规划、环境监视、防灾减灾、 电力行业、交通管理、城市规划、科研、教育和国防等领域，在国民经济 建设中发挥着越来越重要的作用。 空间数据库( s p a t i a ld a t a b a s e s ，s d b ) 是g i s 的重要组成部分，空间数据 的查询是空间数据库的基本操作。其中一种最重要的查询类型就是最近邻 查询，最近邻查询问题是由k n u t h 在1 9 7 3 年提出来的，即邮局问题【”。可 以简单描述为：给定n 维空间内的n 个点所组成的集合s ，将这n 个点存 储在一种数据结构中，使得对于空间内的任何查询点q ，都可以有效地找 到它的最近邻，即在s 中找到一个点p ，使其到q 的距离最近。最近邻的 数目可以是一个，也可以是多个即k - n n 。例如，某一用户可能在屏幕上 点击一个特定的位置或者一个目标，要求系统查找并返回数据库中5 个距 离它最近的对象。由于空间数据量庞大，数据结构复杂，操作代价昂贵， 因此空间查询的优化是人们所关心的问题，其中最近邻查询也成为空间查 询研究中的难点和热点。 随着移动通信、数据库技术以及定位技术如全球定位系统( g l o b a l p o s i t i o ns y s t e m , o p s ) 的发展，定位服务( l o c a t i o nb a s e ds e r v i c e s ，l b s ) 的重 要性正在增加，多种创新型的移动计算应用正在出现，有能力支持一个网 络移动用户端的n n 查询是必要的。但空间数据库中的大部分研究仅考虑 1 燕山大学工学硕士学位论文 了欧氏空间。与之相应，以距离为基础的查询如k n n 查询，采用对象之 间的欧氏距离【3 4 l 来度量。然而在空间网络中，对象的位置和运动被约束在 网络上，如道路、高速公路、铁路等。在这些应用中，距离度量采用网络 距离。为了有效的处理这些空间数据，空间网络数据库( s p a t i a ln e t w o r k d a t a b a s e s ，s n d b ) 应运而生。每种传统的空间查询类型( 如最近邻、范围搜 索、空间连接和最近对) 在s n d b 中都有对应项1 5 】。 欧氏空间的k - n n 查询通常假定距离函数很容易计算。这一假定对网 络距离显然是不成立的。简单地将对欧氏距离调用变更为对网络距离的调 用很明显不是有效的方式。因此有必要对s n d b 中的n n 查询问题进行深 入的研究。 1 2 最近邻查询分类及面临的挑战 空间网络数据库的k n n 查询问题通常定义为：给定移动查询点和对 象( 兴趣点) 集合，以及方向和范围约束集合，检索距离查询点的k 个最近 的对象( 邻居) 。k - n n 查询通常可以分为以下几种形式。 ( 1 ) 点的k 个最近邻查询( 或简单的k - n n 查询) 给定一组空间对象和 一个查询点，检索k 个距离查询点最近的对象。空间对象通常是静态的点。 例如，车辆中g p s 装置所提交的查询：检索距离车辆最近的5 家餐馆。 ( 2 ) 连续的k - n n ( c o n t i n u o u skn e a r e s tn e i g h b o r s ，c k n n ) 查询给定一 组空间对象集，一个查询点和一条预定义的路径，检索位于路径上任何点 处( 查询点) 的k 个最近的对象。例如，沿着一条路径运动的车辆中的g p s 装置所提交的查询：检索5 家最近的餐馆。 ( 3 ) 群组k n n ( g r o u pk n e a r e s tn e i g h b o r s ，0 k n n ) 查询给定一组空间 对象和一组查询点，检索k 个空间对象使之距离查询点的距离之和最小。 例如，两个或更多的人计划去一家餐馆，使他们的行程时间之和最小化。 ( 4 ) 逆k - n n ( r e v e r s ekn e a r e s tn e i g h b o r s ，r 心n 0 查询给定一组空间 对象和一个查询点，检索把查询点作为它们k 个最近邻之一的对象。一个 查询点的r k m i 可以与k n n 有所不同，因为k - n n 查询不是对称函数。 2 第1 章绪论 ( 5 ) 约束k - n n ( c o n s t r a i n e dkn e 盯e gn e i g h b o r s ，c o k n n ) 查询给定一 组空间对象，一个查询点和一组方向或范围约束，检索查询点的k 个最近 邻。例如，检索车辆东南方向且距离车辆不超过5 公里的5 家最近的餐馆。 空间网络数据库中的k - n n 查询面临着许多挑战，主要表现在以下几 个方面。 ( 1 ) 复杂性两个节点间的距离度量通常是很复杂的。例如在网络中， 两个对象间的距离被指定为节点间具有最小权值的最短路径的长度。网络 中的权值既可以是路径的长度也可以是穿过这条路径所需的行程时间，而 计算这些距离的算法是很复杂的( 如网络中计算最短路径的d i j k s t r a 算法1 6 l 的时间复杂度为o ( e q - n l o g n ) ，e 和n 分别是网络中边和节点的数目) 。当 k 小n 查询考虑约束时距离函数的度量变的更为复杂。例如，要求查询点q 东南方向的k - n n 或前进方向的k n n 时，距离函数的度量更为复杂。 ( 2 ) 有效性当查询点q 是一个移动对象时，q 与感兴趣对象的距离函 数就需要经常或实时计算，这就要求候选结果的有效性。 ( 3 ) 弹性空间网络数据库通常是很大的，一个区域可能会包含数万个 交叉点和道路，所以k - n n 查询的解决方法依赖于主存是不实际的。而且 网络中不同类型兴趣点的密度是不同的，有可能在网络中分布差异很大。 因此，解决方法要独立于兴趣点的密度以及它们在网络中的分布情况，并 能处理较大k 值的情况。 ( 4 ) 适应性空间网络数据库可能会经常更新。新的节点、连接和兴趣 点都可能会增加或删除，如高速公路一个路段临时的关闭，某个位置一家 新餐馆的开张等。因此，k - n n 查询有能力适应并且有效的处理数据库的 更新是很重要的。 1 3 研究现状 传统空间数据库的k _ n n 查询问题已经得到了广泛研究且提出了多种 算法【 7 叫引。大多数算法针对欧氏空间m 维对象并且利用一种多维空间索 引结构。常规k n n 查询是几种变体k - n n 查询如c k n n 查询 1 - 1 3 1 的基础。 燕山大学工学硕士学位论文 k - n n 查询的变体或者直接使用常规k - n n 查询的解决方法或者加以变动。 由于实际应用的需要，近年来空间网络数据库中的k - n n 查询问题逐渐成 为研究的焦点。 1 3 1空间网络静态k n n 查询的研究现状 空间网络的静态k - n n 查询可以分为两种类型：增量扫描网络直到第 k 个最近邻被检索的k - n n 查询计算方法；应用一些形式的“预计算”和 通过查询“预计算”数据结构中的数据计算k - n n 查询的方法。两种类型 的方法都假定空间网络以类图数据结构表示。第一种方法如“在线计算” 获得网络的动态性质如刚出现或消失的兴趣点，并且进行网络扩展搜索。 与“在线计算”相比，第二种方法称为“预计算”，一般具有较好的查询性 能，但是在网络和兴趣点的更新上比较困难。 s h a h a b i 等人提出了一种嵌入技术，把网络转换到一个高维空间，从而 利用简单的距离度量进行计算f l9 1 。这方法的主要缺点是只能提供真实距 离的近似结果。 j e n s e n 等人提出了空间网络数据库的n n 查询所需要的数据模型和抽 象的功能性定义1 2 0 】。他们使用与d i j k s t r a 算法相似的方式来在线计算从查 询点到对象之间的最短距离。s h e k h a r 等人提出了四种技术来检索在给定 路径上运动对象的个最近邻( 2 i l 。 在2 0 0 3 年的v l d b ( v e r yl a r g ed a t ab a s e s ) 会议上，p a p a d i a s 等人提出 了两种方法，即增量欧几里德约束( i n c r e m e n t a le u c l i d e a nr e s t r i c t i o n , i e r ) 和增量网络扩展( i n c r e r n e n u dn e t w o r ke x p a n s i o n , i n e ) t 2 2 1 ，其中，i n e 显著的 优于i e r 。i n e 方式以与d i j k s t r a 算法类似的方式扩展网络边。i n e 算法的 主要缺点是节点的扩展方式，当一个节点扩展的时候，它无法只返回在每 个毗邻边上的下个最近点，而是在点的r 树上执行搜索返回每个毗邻边上 所有的点，而且如果边未包含兴趣点，在点的r 树上的查询仍被执行。 在2 0 0 4 年的v l d b 会议上，k o l a h d o u z a n 和s h a h a b i 指出这一算法对 稀疏的网络是不适用的2 3 1 ，但是本文认为即使在密集网络情况下，许多工 作仍被浪费。 4 第l 章绪论 k o l a h d o u z a n 和s h a h a b i 针对当对象分布在稀疏的网络中时i n e 方法执 行效率低的缺点，提出了基于v o r o n o i 图的v n 3 方法1 2 3 1 ，它试图把一个大 的网络分割为较小的v o r o n o i 区域，预计算区域内部和穿过这一区域的距 离。实验显示v n 3 方法优于i n e 。然而对于k 值增加的情况，由于许多路 径在v o r o n o i 区域之间穿过，它的计算代价很高。对于稀疏的数据集，网 络v o r o n o i 分割( n e t w o r k v o r o n o ip a r t i t i o 鹏。n v p s ) 的数目很少，相应的它的 多边形却很复杂，导致边界点数目很多，这使得精炼步骤的计算更为复杂。 另一方面，如果数据集是稠密的，s v p s 的数目很大，则候选集也很大， 这意味着精炼步骤需要从多个可能中来判定。 h u a n g 等人提出了一种称之为“岛屿”( i s l a n d s ) 僦【2 4 】，它预计算 并存储与兴趣点不超过一定距离( 即岛屿的半径) 的节点。这种方式结合了 预计算方式高效率和网络扩展方法的优点。 在2 0 0 5 年的v l d b 会议上，c h o 和c h u n g 提出了一种同i s l a n d s 非常 相似的方法 2 5 1 ，但是它不是预计算兴趣点的最近节点，而是预计算网络中 一些节点( 即聚集点) 的最近兴趣点。而且这种方法为每个聚集点计算固定 数目而不是一定半径内的最近邻。 除了v s 3 ，所有这些方法的缺点是它们无法增量地检索最近邻。增量 最近邻算法以迭代的形式实现下一个n n 的检索。这种增量的检索方式是 比较好的，如用户( 使用用户界面) 能在k 个最近邻检索完成之前停止；用 户可以在处理完k 个最近邻后继续检索第( “1 ) 个最近邻；由于它是非块 ( n o n - b l o c k i n g ) 的，所以这种方式能够以流水线方式执行。 1 3 2空间网络c i 渊查询的研究现状 f e n g 等人提出了网络中c n n 查询方法 2 6 , 2 7 1 。这种方法以检索路径上 必须执行n n 查询的位置为基础。这种方式的主要缺点是它只解决了连续 的第一个最近邻( 也就是c i n n ) 查询而未解决c k n n 查询问题。 k o l a h d o u z a n 等人为空间网络数据库的c k n n 查询提出了一种称为上限算 法( u p p e rb o u n da l g o r i t h m , u b a ) i y j 方法【2 8 】。u b a 限制只在必要的位置进 行n n 查询计算，因此减少了n n 计算的数目，具有较好的效率。u b a 利 燕山大学工学硕士学位论文 用v n 3 在一个静态位置返回( k + 1 ) 个n n 。然后计算查询点不需要提交新的 n n 查询的最小移动距离。然而u b a 仍然需要大量的n n 查询来找出分割 点( 分割点是一个对象的k - n n 发生变化的路径位置) 。结果当n n 的数目和 对象的密度增加时运行时间也急剧增加。 c h o 和c h u n g 解决了同样的问题【2 刊，他们通过计算查询路径上所有网 络节点的k - n n 集，并联合落在查询路径上的数据对象来检索路径上任何 点处的k - n n s 。很容易计算结果包含查询轨迹上的任何点处的k - n n s 。 上述的c k n n 查询方法对连续的k n n 监视都是不适用的，因为( 1 ) 它 们针对的是静态数据对象；f 2 ) 假设查询轨迹是预先知道的。总之现有的网 络n n 处理技术，对象和查询或者是静态的或者移动速度、轨迹是已知的。 此外，它们可以归类为快照方法，因为它们返回一个单一结果后就终止了。 1 3 3 空间查询的连续监视问题研究现状 现有的空间查询的连续监视研究集中在欧氏空间。q 索引1 2 9 】监视移动 对象的静态范围查询。它使用r - 树索引范围并且探查移动对象对索引的影 响，更新受到影响的结果。m o b i e y e s 口0 1 和m q m 【3 i 】利用数据对象的计算能 力减少中央服务器的负载。s i n a 3 2 利用移动对象和范围之间三步空间连接 执行范围查询的连续估计。 关于k - n n 监视问题，k o u d a s 等提出一个系统，用于执行多维点数据 流的近似k n n 查询i ”】。现在存在三种算法处理欧氏空间的精确k - n n 监 视问题：y p k - c n n t 3 4 1 、s e a - c n n 1 3 5 1 和c p m 3 6 1 。三种方法都是用一个规则 的网格索引数据。检索一个新的查询q 的初始结果时，首先在格子中搜索 附近的区域。为了使结果在下一个时间戳之前保持有效， y p k - c n n ( s e a - c n n ) 计算最远的早先先前n n 的当前距离d 并且处理落在 以q 为中心，边长为2 d 的正方形( 半径为d 的圆) 内的对象。而c p m 中结 果的维护有所不同。令c 表示围绕先前n n 位置的圆心为q 的圆。如果移 出c 的n n s 的个数超过移入c 的外部对象的个数，查询就要重新计算一 次。否则c 中最靠近q 的k 个对象就组成了新的结果。 y p k - c n n 、s e a c n n 和c p m 所采用的栅格索引不能获得网络施加 6 第l 章绪论 的约束。这些方法使用圆和矩形处理对象和更新结果，然而这些形状在网 络距离空间是毫无用处的。它们不能够处理边的权值变化引起的更新( 即使 对象和查询保持静态) 。因此，它们不适用于网络。 1 4 研究意义 随着定位技术的进步，定位服务的重要性正在增加。l b s 的应用包括 智能旅行系统、定位广告、旅客导游、定位游戏等。k - n n 查询是l b s 中最 重要的查询类型之一p ”，在许多实际应用领域中已变得越来越重要，如在 定位游戏应用中，使用者可以检索他的k 个最近的对手。 在空间网络数据库操作中，最近邻查询是一种频繁的操作。因此，人 们对支持最近邻查询的数据存储结构、查询算法以及k n n 查询变体形式的 研究有着浓厚的兴趣，对k - n n 查询的研究有着巨大的实际应用意义。 1 5 研究内容 本课题的第一个研究内容是提出一个空间网络数据存储模式，以有效 的支持k - n n 查询算法的执行，减少查询运行时问和i o 操作。为此首先 探讨了空间网络数据存储技术的一些关键问题，然后列举了现有的存储模 式并进行分析研究，最后借鉴这些已有的存储模式，提出一个空间网络数 据两层存储模式。 本课题的第二个研究内容主要包括增量k n n 查询算法( i k n n q a ) ，以 及“预计算”方式的l 【- n n 查询算法( p k n n q a ) ，有效的执行空间网络数据 库中静态k 小烈查询操作。 本课题的第三个研究内容是c k n n 查询的监视问题，提出增量k - n n 监视算法( i k n n m a ) 和群组k 小监视算法( g k n n m a ) 。i k n n m a 以扩展树 的形式存储在n n 搜索期间遇到的网络节点的最短路径，减少更新并加速 q 的新的n n s 的计算。而g k n n m a 采用共享策略减少处理时间，它将落 在网络两个连续的交叉点间的路径上的查询聚集起来，通过监视这些交叉 7 燕山大学工学硕士学位论文 点的n n 集生成结果，从而将监视移动查询转化为监视静态的网络节点， 精简了问题。 1 6 本文组织结构 本文共分5 章，从第2 章开始各部分组织如下。 第2 章首先探讨了空间网络数据存储技术的一些关键问题，然后列举 了现有的存储模式并进行了分析，并提出了空间网络数据两层存储模式。 第3 章提出了增量k n n 查询算法，以及“预计算”的k n n 查询算 法，有效的执行空间网络数据库中静态k 小n 查询操作。 第4 章提出了c k n n 查询监视算法，有效执行动态的k - n n 监视操作。 第5 章实验验证了所提出算法的有效性以及正确性。 最后，总结了本文的工作并提出了下一步的设想。 第2 章空间网络数据存储模式 2 1引言 第2 章空间网络数据存储模式 第1 章中介绍了课题背景、n n 查询的分类及面临的挑战、研究现状、 研究内容及意义，本章将详细地阐述现有的空间数据库存储模式、与课题 研究相关的基础知识以及所提出的空间网络数据存储模式。 2 2 空间数据索引技术概述 空间数据库的研究始于2 0 世纪7 0 年代的地图制图与遥感图像处理领 域，其目的是为了有效地利用卫星遥感资源迅速绘制出各种经济专题地图。 由于传统的关系数据库在空间数据库的表示、存储、管理、检索上存在许 多缺陷，从而形成了空间数据库这一数据库研究领域。随着地理信息系统 ( o l s ) 、计算机辅助设计与制造( c a d c a m ) 、机器人、多媒体系统、数字 地球、移动通信及定位服务等应用领域的发展，对空间数据库以及时空数 据库的研究越来越受到人们的重视。 空间数据是某个空间框架中对象的位置信息。一般来说，空间数据是 指与二维、三维或更高维空间的空间坐标及空间范围相关的数据，常用于 表示空间物体的位置、形状、大小和分布特征等诸方面信息。 空间数据库索引技术是对存储在介质上的数据位置信息的描述，用来 提高系统对数据获取的效率。空间数据库索引技术的提出是由两方面因素 所决定的：其一是由于计算机的体系结构将存储器分为内存和外存两种， 访问这两种存储器一次所花费的时间大约相差十万倍以上。在实际应用中， 绝大多数数据是存储在外存磁盘上的，尤其是在与空间数据库相关的应用 中，如地理信息系统、定位服务等，由于其涉及的是各种海量的复杂数据， 索引对于处理的效率是至关重要的；其二是空间数据库所表现的空间数据 9 燕山大学工学硕士学位论文 多维性使得传统的数据库索引技术( 如b 树【3 8 】等) 并不适用。而目前不存在 从二维或高维空间到一维空间的映射，使得任何两个在高维空间接近的对 象在一维排序序列中也相互接近。因此传统的数据库索引技术并不能对空 间数据库进行有效索引，需要研究特殊的能适应多维特性的空间索引方式。 空间数据库索引技术是提高空间数据库查找性能的关键技术，直接影 响到空间数据库系统的成败。因此空间索引技术研究一直是空间数据库研 究领域中的一个热点，对它的研究可以追溯至传统数据库中多属性数据的 索引研究。 根据对象描述和索引结构的处理，针对空问数据本身的特点及空间数 据的点查询、范围查询、最近邻域查询的特点，国内外学者开发了很多空 间索引技术。其中主流方法都是采用树索引结构。从空间目标映射方法分， 空间索引技术可大致分为两大类。 第一类，基于空间目标排序的索引方法。 其基本思想是：按照某种策略将索引空间细分为许多格子，并给每一 网格分配编号，然后用这些编号为空间目标获得一具有代表意义的数字。 这样，多维的空间目标转换为简单的数字，因此一维索引技术可以利用， 常规的数据库系统可以用于管理空间目标的属性与几何信息。用一维值给 多维空间目标排序的技术很多如p c a n o 曲线口9 1 、位置键 4 0 l 、z 排序【4 1 l 等。 第二类，专门的空间索引方法。 在系统中加入专门的外部空间数据结构，来提供对空间数据的索引。 常用的方法有： ( 1 ) 不允许空间重叠的索引法这种方法将k 维的空间数据空间按某种 方法( 如二叉树划分、四叉树划分、格网划分等) 划分成彼此不相交的子空 间，然后对属于这些子空间的目标分别存储在对应的磁盘页或数据桶中。 目标复制：目标标识重复存储在与该目标相交的所有子空间。 目标裁减：目标被分解成几个不相交的小目标，从而使每一小目标完 全包含在一子空间。k d 树h 孙、r + 树【4 3 1 等是这类方法的典型代表。 ( 2 ) 允许空间重叠的索引法这种方法的基本思想是：按某种策略将索 引空间层次划分成多级的子空间，这些子空间允许重叠从而使点与非点状 1 0 第2 章空间网络数据存储模式 目标都完全包含在某一子空间之内。这种方法的一个重要的优化策略是尽 量最小化各级子空间的重叠与覆盖，因为子空间重叠与覆盖直接关系到查 找路径的多少，关系到空间检索的效率。r 树【“1 及其变体是这种方法的主 要代表。 图2 - i 给出了常见的索引结构m 5 州。 ， m 牺口卜一 一 以“i ii ! m t - - 坼_ _ 妇 l 1 z 小, a - - th l 锊r 呻畦上 缮州b q f r ， 一一 ： r ! k pib 少 p 一 一 1 7 “! 。 黑 ： 一驾左一 ，o 璎 p 等 凸息铒9d q 4 “ o 至 弩 , - v - h o h 。 妒 盥乒 蔫” h 山口 ：；：邕剿： 蛐9 1 9 2 ”舛9 59 69 7辨9 90 0o l0 2 。3 图2 - 1常见的索引结构h 6 l f i g u r e2 - 1s u r v e yo f l n d e xs t r u c t u r e l 4 6 1 2 3 典型的空间索引r - 树 2 3 1r - 树的定义 r - 树是b 树在多维空间的扩展，它由g u t t m a n 于1 9 8 4 年提出。 对于一棵m 阶的r 树，其节点结构可描述如下： 叶子节点：( c o u n t , l e v e l ， ， ) 。 燕山大学工学硕士学位论文 中间节点：( c o u n t , l e v e l ， ， ) 。 其中， 称为数据项，o l i 为空间目标的标识，m b r i 为该目标在 k 维空间中的最小包围矩形( m i n i m u mb o u n d i n gr e c t a n g l e ) ； 称为索引项，c p i 为指向子树根节点的指针，m br i 代表其子树索引空间， 为包围其子树根节点中所有目录矩形或数据矩形的最小包围矩形( 简称为 目录矩形) 。c o u n b m 指示节点中用到的索引项或数据项个数( 即该节点 的“孩子”个数) ，l e v e l 兰o 指示该节点在树中的层数( o 表示叶节点) 。由 于整数和指针所占存储空间相同，且可以相互转换，因此r 树的叶子节点 和中间节点在结构上是相同的。 设m ( 2 m o ) 返回 r c _ p 且满足条件i r l _ k ，v ( r rp p l r ) ：d n ( q ，r ) s d n ( q ，p ) ，即根据网络距离 返回最靠近q 的k 个兴趣点。 2 5 空间网络数据存储模式 如果采用d i j k s t r a 算法【6 】执行k 小n 搜索，最直观的想法就是改变网络 数据集使之包含兴趣点，由于兴趣点位于边上，也就是说网络需要增加新 的节点并且需要分割边，然后采用邻接表部分表示图的连接性。很明显这 种方式会有一些缺点：首先，插入兴趣点会增加网络的复杂性，而且邻接 表部分的遍历性能将会降低；其次，假定网络基本是固定的也就是不会有 1 4 第2 章空间网络数据存储模式 太大变化，但是兴趣点数据集是动态的。而邻接表部分的更新却不易执行， 因为同一空间中的节点存储在相同的磁盘页中。这种数据结构要想实现有 效的更新机制必须采用再组织技术1 2 2 , 4 7 1 。 比较好的方式是将网络和兴趣点数据集分开。网络数据，也就是网络 边的最小包围矩形储存在r 树中，它的叶子节点项用一个指针指向网络边 的真正表示。对于网络的每个边都用一个b + 树来索引边上兴趣点的相对 位置。这种方式可以视为m o n 树1 4 s l 的一个静态版本( m o n 树是处理网络 上移动对象的索引结构) ，由于在这里对象位置固定，就不需要底部的r - 树，而改用b + 树。但是仍需要额外的部分来储存网络的连接性，即使用 邻接表部分来表示。 假定查询点所在的边在查询时未知，所以所有的边都使用r - 树索引。 如果边的“i d ”或“名字”对于查询己知，可以使用b + 树索引这些属性 并且直接访问邻接表部分。 网络的存储模式表示在图2 4 中。它包括四个部分：网络r 树索引、 边的折线表示、邻接表、兴趣点b + 树。 图2 1 4 存储模式的组成 f i g u r e2 - 4c o m p o n e n t so f t h es t o r a g es c h e m a 网络r 树部分索引折线部分的m b r s 。每个叶子项包含一个指针，指 向存储相应折线的磁盘页面。边的折线部分储存网络中每条边的详细的折 线表示。折线项( n i ，码) 也包含一对指针，分别指向包含端点n l ，n j 邻接表的 1 5 燕山大学工学硕士学位论文 磁盘页面。邻接表部分储存网络的连通性，每项代表一条边且表示为 。这里e s t a r t 和e e n d 是始点和终点的i d ，p t n b v e 标明包含终点的磁盘页，e w 是边的权值( 长度) ，p t d p 指向这个边上数据 点的b + 树。如果没有链接，指针设为n i l 。这一部分依据节点的h i l b e r t 值安排磁盘页。 2 6 本章小结 本章首先对空间数据的索引技术进行了介绍，对其分类进行了总结t 然后介绍了广泛采用的r 树索引方法，并进行了分析；最后对空间网络进 行了定义，进一步提出了空间网络数据两层存储模式，来满足后面的所提 出的空间网络数据库中的k - n n 查询算法。 1 6 第3 章s n d b 中静态的k - n n 查询算法 第3 章s n d b 中静态的k - n n 查询算法 3 1引言 第2 章介绍了空间数据索引技术，并提出了空间网络数据的两层存储 模式。本章将在此基础上提出s n d b 中静态的k - n n 查询算法，它包括增 量查询算法( i k n n q a ) 和基于“预计算”的查询算法( p k n n q a ) 。 3 2 增量k - n n 查询算法( i k n n q a ) 3 2 1 算法基本思想 本算法参照了f r e d m a n 和t a r j a n 提出的d i j k s t r a 算法的修改版本，它 采用斐波纳契( f i b o n a c c i ) 堆依照网络距离排序来确定下一个要扩展的节 点。如第2 4 节所解释的那样，由于在存储模式中采用两层结构：网络和 兴趣点。相应的在堆中有两种类型的项：节点项和点项。节点的扩展返回 所有从这个节点出发的边，而点的扩展只是在边的b + 树中简单地向前( 或 向后) 移动。 f i b o r t a c c i 堆中的项包含下列信息： ( ) ；依据c o s t 值排序；t y p e 表明这个项的类型是节点( n ) 或兴趣点( p ) ；i n t o 包含额外的信息：对于节点，节点信息被传递，对于兴趣点，传递相应的 b + - 树迭代器。迭代器包含下列信息： ，d i r 表明方向( 向前 或向后) ，p = q 。，p y ) 储存当前兴趣点的坐标，p o s 储存当前兴趣点在边上的 相对位置，而l e n 是边的长度。 3 2 2 算法描述与解释 算法描述：i k n n q a ( q ，k ) 。 1 7 燕山大学工学硕士学位论文 输入：查询点q ，查询要求的最近邻数目k ； 输出：结果集耻元素形式为 ) 。 1 r 卜o ，s 卜o ，i = o s 为已扩展过的节点和访问过的兴趣点的集合 2搜索网络边的砧树，发现点q 所在的网络边e 3 在边的底层b + 一树中搜索点q 的相对位置p o s 4 打开一个向前的迭代器f w 和一个向后的迭代器b 。，检索p f 和p b 的下 一个点( 如果迭代器到达b + - 树的端部，这些点设为上) 5 i f p f = - - t h e n 6 i n s e r t ( h e a p , ) 7e l s e 8 i n s e r t ( h e a p ， ) 9 i f p b - 上t h e n 1 0 i n s e r t ( h e a p ， ) 1 1e l s e 1 2 i n s e r t ( h e a p ， ) 1