（管理科学与工程专业论文）移动对象反向最近邻查询处理技术研究.pdf

国防科学技术大学研究生院硕士学位论文 摘要 随着全球定位系统、无线通信网络等基础设施的飞速发展和普及，传统数据 库查询处理技术已远不能满足用户不断增长的应用需求，针对移动对象的查询处 理技术得到了国内外研究者的广泛关注，是充满挑战性的研究方向。反向最近邻 查询是其中最重要的查询之一，是在最近邻查询的基础上提出的一种新的查询类 型，有着广泛的应用前景。传统的反向最近邻查询方法主要是静态对象的查询， 而现实生活中对象更多地处于运动的状态，传统算法不能解决移动环境下的反向 最近邻查询。 论文主要是针对移动对象数据库领域中的研究难点和热点，在全面总结和分 析国内外相关工作的基础上，面向实际应用需求，对移动对象的反向最近邻查询 处理技术和连续反向最近邻查询处理技术进行研究，并将相关研究成果应用于实 际中。本文的主要工作和创新点如下： ( 1 ) 研究面向移动对象的反向最近邻查询处理技术，提出了一种基于网格索 引的查询处理算法。通过在网格单元中加入移动对象数目信息，并结合移动对象 在网格中的几何分布特征作为剪枝搜索准则，大大减少了查询所需要的节点访问 代价。 ( 2 ) 研究大量并发的连续反向最近邻查询处理技术，提出了一种基于多线程 的连续查询处理框架，利用多线程技术来提高多用户连续查询处理的并行性。基 于框架和网格索引，提出了一种连续反向最近邻查询处理算法，将查询分组批处 理以提高多用户查询整体性能，支持查询集合中加入或删除查询和移动对象数据 集的插入、删除等动态更新。 ( 3 ) 基于上述研究成果，设计并实现了战场应急保障服务系统，验证了网格 索引、反向最近邻查询和连续查询处理框架的有效性和实用性。 主题词：移动对象网格索引最近邻查询反向最近邻查询 连续查询处 理 第i 页 国防科学技术大学研究生院硕士学位论文 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fg l o a lp o s i t i o n i n gs y s e m ( g p s ) a n dw i r e l e s s c o m m u n i c a t i o nn e t w o r k , t h ed a t a b a s e st e c h n i q u e st o w a r d sm o v i n gt a r g e t sc a n n o tm e e t t h en e e d so fu s e r sa n df a c em a n y c h a l l e n g e s t h eq u e r yt e c h n i q u e sf o rm o v i n go b j e c t s i nd y n a m i ce n v i r o n m e n t ，w h i c ha r ec h a l l e n g i n gd i r e c t i o n s ，h a v eb e e nf o c u s e do nb y m a n yr e s e a r c h e r s o n eo ft h em o s ti m p o r t a n tq u e r i e si nm o v i n go b j e c t sd a t a b a s e si s r e v e r s en e a r e s tn e i g h b o rq u e r yw h i c hi san e wq u e r yp r o p o s e db a s e do nn e a r e s t n e i g h b o rq u e r y c o n v e n t i o n a lq u e r ym e t h o df o c u s e so ns e a r c h i n gs t a t i co b j e c t s ，w h i l e t h eo b j e c t sa c t u a l l ya r ea l m o s tm o v i n g ，s ot h em e t h o dc a n n o ts o l v et h i sp r o b l e m i no r d e rt os t u d yt h ed i f f i c u l ta n dh o ti s s u e si nm o v i n go b j e c t sd a t a b a s e s ，t h i sp a p e r g i v e sc o m p r e h e n s i v ed i s c u s s i o n sa n da n a l y s i so nf o r m e rw o r ki nr e l a t e da r e a s a n d t o w a r d st h ea p p l i c a t i o nn e e d s ，t h i sp a p e rs t u d i e st h ek e yt e c h n i q u e si nm o v i n go b j e c t s d a t a b a s e si n c l u d i n gr e v e r s en e a r e s tn e i g h b o rq u e r ya n dc o n t i n u o u sr e v e r s en e a r e s t n e i g h b o rq u e r y ，a n da p p l i e sa c h i e v e m e n t st op r a c t i c a la p p l i c a t i o n s 1 1 1 em a i n w o r ka n d i n n o v m i o n sa l ed e t a i l e da sf o l l o w s ： ( 1 ) t oi m p r o v et h eq u e r yp e r f o r m a n c eo fr e v e r s en e a r e s tn e i g h b o rq u e r i e s ，w e p r e s e n ta ne f f i c i e n tq u e r ya l g o r i t h m ，w h i c hi sb a s e do n 鲥d i n d e xs t r u c t u r ea n da d d e d 、析t ho b j e c t si n f o r m a t i o ni nc e l l s am o r ep r e c i s eb r a n c ha n db o u n ds e a r c h i n gs t r a t e g y b a s e do nt h eo b j e c t sm dg e o m e t r yc h a r a c t e r i s t i c si sa l s ou s e dt or e d u c et h ed i s k a c e e s s e s ( 2 ) t od e a l 晰t l lt h em u l t i p l ec o n c u r r e n tc o n t i n u o u sr e v e r s en e a r e s tn e i g h b o r q u e r i e s ，w ep r o p o s eam u l t i t h r e a d i n gp r o c e s s i n gb a s e do ng r i da c c e s so fm u l t i p l e c o n t i n u o u sq u e r i e s ( m p b g a m ) f r a m e w o r k ，w h i c ha d o p t sp i p e l i n es t r a t e g yt oi m p r o v e t h ep a r a l l e l i s m b a s e do nm p b g a mf r a m e w o r ka n d 鲥di n d e x ，am u l t i t h r e a d i n g p r o c e s s i n go fc o n t i n u o u sr e v e r s en e a r e s tn e i g h b o rq u e r i e s ( g - c r n n ) a l g o r i t h mi sa l s o p r e s e n t e d ，w h i c he v a l u a t e si n c r e m e n t a l l yb a s e do nf o r m e rq u e r ya n s w e r sa n ds u p p o r t s i n s e r t i o no rd e l e t i o no fb o t hq u e r yc o l l e c t i o na n dm o v i n go b j e c t s ( 3 ) b a s e do nt h ea b o v ea c h i e v e m e n t s ，w ed e s i g nap r o t o t y p es y s t e mf o rw a r e m e r g e n c ys u p p o r ts e r v i c e s ( e s s ) t ov a l i d a t et h ee f f i c i e n c ya n dp r a c t i c eo fo u r p r e s e n t e dt e c h n i q u e si n c l u d i n gg r i di n d e x ，r e v e r s en e a r e s tn e i g h b o rq u e r i e sa n d c o n t i n u o u sq u e r yf r a m e w o r k k e yw o r d s ：m o v i n go b j e c t s ，g r i di n d e x ，n e a r e s tn e i g h b o rq u e r y ，r e v e r s e n e a r e s tn e i g h b o rq u e r y ，c o n t i n u o u sq u e r yf r a m e w o r k 第i i 页 国防科学技术大学研究生院硕士学位论文 表目录 表2 1 深度优先搜索算法l6 表2 2 最佳优先搜索算法17 表3 1 符号及意义2 9 表3 2 实验参数3 3 表3 3 实验结果数据3 4 表4 1 实验参数描述4 7 表5 1 移动对象相关描述信息5 4 第1 i i 页 国防科学技术大学研究生院硕士学位论文 图1 1 图2 1 图2 2 图2 - 3 图2 4 图2 5 图3 1 图3 2 图3 3 图3 4 图3 5 图3 6 图3 7 图3 8 图3 9 图3 1 0 图4 1 图4 2 图4 3 图4 4 图4 5 图4 6 图4 7 图4 8 图4 9 图5 1 图5 2 图5 3 图5 4 图5 5 图目录 论文研究思路7 基于r 树的n n 查询范例。16 分布式连续最近邻查询示例2 0 m i n d i s t ( q ，m ，r ) 和m i n m a x d i s t ( q ，m ，r ) 的图解。2 1 节点1 可以被剪除2 2 全最近邻查询的不同剪除策略2 3 口的反向最近邻是口和e 2 5 半空间剪除2 5 s a a 图解2 6 网格索引思想2 8 g r n n 查询处理算法流程31 上海的道路图及移动对象分布图3 3 网格划分粒度对查询性能的影响3 6 数据集大小对查询性能的影响3 7 网格粒度划分对更新性能的影响3 7 g r n n 算法更新性能比较3 8 连续c r n n 查询的监测区域4 l m p b g a m 查询处理框架4 2 m c r n n 查询处理算法流程4 5 移动对象数据集n 对初始查询性能的影响4 7 移动对象数据集n 对更新性能的影响4 8 时间窗口范围对初始查询性能的影响4 8 时间窗口范围对更新性能的影响4 9 连续查询处理个数g v 对初始查询性能的影响。4 9 连续查询处理个数g v 对更新性能的影响5 0 整个应用系统的总体框架5 2 系统的组成5 3 反向最近邻查询提交5 4 系统运行流程5 5 返回查询结果5 6 第页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料与我一同2 r _ 作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意 学位论文题目：丝边盟基区囱基适堡查询丛猩蘧盔盟窒 学位论文作者签名： 兰蔓逊系 日期：矿q 年l1 月r 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目： 整边数錾丛囱量塑垫查询处翌挞盎盟窥 学位论文作者签名： 查夔达妻日期：加年。月厂日 作者指导教师签名： 二璧! 主 日期： 卅年，月歹日 国防科学技术大学研究生院硕士学位论文 第一章绪论 1 1 研究背景及意义 无线通信、g p s 等空间定位技术及移动计算技术的发展使得跟踪和管理实际 生活中的移动对象成为现实。在许多重要应用如数字战场、交通调度控制、气象 监控、电子商务以及个人位置服务等领域往往需要对移动终端的位置进行追踪管 理以提供相关查询服务。反向最近邻查询作为一种新兴的查询，得到了广泛的关 注和应用【l 】。例如，一家百货公司想在某一地点设一个新的分公司，这必然会对附 近的同类公司或商店( 假设人们一般选择就近购物) 带来影响，而受其影响最大 的公司或商店，就是其反向最近邻查询所得的结果；某公司为一新产品做广告， 以电子邮件的形式发到用户的信箱里，而要发给那些对本产品相当感兴趣的人， 这就不会使用户的信箱总是被一些垃圾邮件充满，也能使产品的广告更加有效， 而要发给哪些用户? 实际上，这就是反向最近邻查询问题。反向最近邻查询是最 近邻查询的变种，返回将查询点作为其最近邻的移动对象。其固有的复杂性和海 量性使得传统的数据库查询处理技术不能或不能有效地发挥作用，进而必须研究 新的查询处理技术来支持反向最近邻的查询问题。因此，如何提供高效的移动对 象反向最近邻查询处理技术成为当前涉及最近邻查询的移动对象数据库研究领域 的重点与热点之一。 目前在移动对象反向最近邻查询处理技术方面，研究工作尚局限于静止点的 非连续查询上，许多重要的研究点急需解决【2 】。例如，移动对象的动态反向最近邻 查询和连续的反向最近邻查询。本文拟对移动对象的反向最近邻查询处理技术进 行深入地研究，因为它是现实生活中应用很广泛的一种技术【3 j 。 面向移动对象的反向最近邻查询是移动对象数据库中一个新兴的研究领域。 移动对象数据库( m o v i n go b j e c t sd a b a s e s ，m o d ) 是指对移动对象( 如车辆、飞机、 移动用户等) 的位置及其他相关信息进行存储与管理的数据库【4 】，属于时空数据库 的研究范畴。它主要可以用于民航管制、交通管理、军事指挥以及基于位置的信 息服务等众多领域。移动对象数据库技术涉及数据库技术、分布式计算技术、以 及移动通信技术等多个学科领域，具有较高的学术起点。移动对象数据库研究的 主要领域包括：移动对象位置的表示与建模、移动对象索引技术、移动环境下的 查询处理技术、以及移动对象位置不确定性的表示与处理等等【5 】。 ( 1 ) 移动对象位置的表示与建模 为了有效地管理移动对象的位置，移动对象数据库系统必须能够准确地获取 移动对象的当前位置信息。而定位技术和无线通信技术的发展使得跟踪和记录移 第1 页 国防科学技术大学研究生院硕士学位论文 动对象的位置成为可能，如g p s 等定位技术。 有了移动对象的位置信息之后，就可以处理与位置相关的查询请求，如查询 当前某城区的所有清洁车等，但这仅仅是一类最为简单的应用。在更为复杂的应 用中，不仅需要查询移动对象的当前位置，而且还要查询移动对象的过去位置或 者预测移动对象未来位置，因此需要建立更复杂的模型以支持描述移动对象的全 时态位置信息。 数据库存储移动对象的“实际位置信息，当移动对象位置变化时，必须向 数据库发出更新请求，而数据库则记下每次更新时移动对象的空间位置。为了保 持移动对象位置信息的有效性，一种简单的方法就是周期性地刷新数据库，但这 种方法效率非常低下：如果周期选择过短，则会给系统带来严重的计算及通讯开 销；反之，又会造成较大的误差。所以在实际应用中为了减少数据库存储移动对 象历史轨迹花费的代价，人们提出了两种解决方法：( 1 ) 抽样方式，将移动对象 位置信息按照某种采样时间间隔进行抽样存储，然后各抽样点之间则用线性插值 进行拟合；( 2 ) 存储移动对象的运动模式，即在数据库中存储描述移动对象运动 的参数信息( 如起始位置、速度矢量等) ，只有当移动对象的某个运动参数发生 变化时才对数据库进行更新。 针对移动对象当前和未来位置的建模通常是将移动对象的位置抽象为关于时 间的函数。系统可根据该函数计算出移动对象在未来任意时刻的位置。这样一来， 移动对象就不再需要周期性地向服务器报告自己的当前位置，而只有当实际位置 与计算位置的偏差达到一定的阈值或速度矢量发生变化时，才需要发出位置更新 请求并对数据库进行更新。这种方法极大地降低了数据库的计算及通讯代价，已 经成为目前移动对象数据库研究领域中位置建模的主要方法【6 】，目前较为通用的建 模方法是利用线性时间方程对移动对象轨迹进行拟合，另外国内外许多学者也提 出了利用多项式时间方程对移动对象轨迹进行建模的方法。 ( 2 ) 移动对象索引技术 移动对象数据库中通常管理着数量非常庞大的移动对象数据集。在查询处理 时如果遍历所有的移动对象记录将会极大地影响系统的性能。为了减少数据库搜 索空间，提高查询效率，就必须对移动对象的位置进行索引。 移动对象索引方法通常借鉴传统空间数据库索引技术，不同之处在于移动对 象索引中有一维是时间维。在空间数据索引方面人们已经提出了许多方法，如r 树及其变种r i 树、x 树、g r i d 文件等。这些方法对移动对象的索引具有很好的借 鉴意义，但是它们并不能直接用于移动对象的索引。这是因为上述方法着重考虑 的是空间查询效率，而没有考虑索引的更新代价。在移动对象数据库中，移动对 象的位置更新会引起索引结构的频繁变化，因此必须考虑索引查询性能随着时间 第2 页 国防科学技术大学研究生院硕士学位论文 下降以及索引更新性能的问题。 移动对象索引技术根据查询时间窗口范围可以分为三类：索引移动对象历史 轨迹信息、索引移动对象当前位置信息以及移动对象未来位置预测。目前国内外 研究学者提出了多种移动对象索引技术，但总体来说移动对象索引技术方面的研 究仍然处于初步阶段，能够应用于实际的索引技术有待于进一步的研究 7 1 。 ( 3 ) 移动环境下的查询处理技术 传统数据库中研究广泛的范围查询、k 近邻查询以及聚集查询等在移动环境下 有着相应的查询类型。与传统空间数据库不同，由于移动环境下查询对象( 移动 对象) 及查询本身的动态性，上述查询结果有着很强的时态语义。例如查询“根 据我当前的运动速度和方向，在未来5 分钟内距离我最近的两个加油站 。在移动 环境下，查询对象和或查询本身位置一旦发生变化，查询结果很快变为无效，需 要及时更新查询结果。 移动环境下查询通常表现为连续查询，即使查询对象是静态的，但是由于查 询本身的动态性，查询结果也会发生变化( 如查询的新加、删除等) 。因此，一 旦移动对象数据库发生变化，则移动环境下连续查询必须经常性的进行更新以保 证查询结果的正确性。另外，在实际应用中，服务器需要同时处理大量并发的用 户查询，那么保证客户端在合适时间得到查询结果，避免由于过度延迟造成查询 结果无效，也是移动环境下查询需要解决的问题。 ( 4 ) 移动对象位置不确定性的表示与处理 移动对象位置管理的方式本质上就具有不确定性【8 】。不管采用何种位置管理及 位置更新策略，移动对象数据库中保存的位置信息与移动对象的实际位置之间总 会存在着一定的偏差。例如，在周期性位置更新方法中，由于位置信息的更新是 周期性完成的，在一个更新周期内数据库中的位置信息是不变的，而实际上移动 对象可能已经在此期间离开了原来的位置；同样的，将位置表示为时间函数也存 在着位置的不确定性，由于位置函数仅仅只是近似地描述了实际位置的变化，因 此偏差总是客观地存在着。另外，在实际应用中为了减少频繁的位置更新所带来 的通讯及计算代价，在系统中通常设定一个阈值，当位置偏差小于该阈值时，系 统并不对数据库中的信息进行更新，只有当偏差大于该阈值时，系统才会对移动 对象位置进行更新。 这种策略虽然降低了数据库的维护及通讯开销，但同时也增加了位置的不确 定性。因此，在移动对象数据库系统中，建立模型、查询处理、索引结构等诸方 面都要考虑不确定性因素的存在。 在上述研究领域中，移动对象索引技术和动态环境下的查询处理技术尤其是 大量并发的连续查询处理技术得到了国内外研究者的广泛关注，是充满挑战性的 第3 页 国防科学技术大学研究生院硕士学位论文 研究方向。本文研究目的是借鉴现有的移动对象数据库研究领域最新成果，针对 其不足之处进行改进和完善，提出新的查询处理技术，着重解决移动对象数据库 系统设计和应用中的关键问题。课题研究意义归纳如下： ( 1 ) 移动对象数据库技术在交通调度、数字战场等领域得到了广泛的应用。作 为位置服务系统的关键支撑技术，移动对象数据库技术目前已经成为数据库领域 的研究热点，国内外许多学者进行了仔细深入研究，但总体来说仍处于初步阶段。 ( 2 ) 在动态环境下，移动用户会向服务器提交如k 近邻查询、反向最近邻查询 等多种类型的查询，基于现有的通用移动对象索引技术，研究高效的查询处理框 架和查询处理方法以快速处理大量并发的用户查询具有重要的应用价值。 ( 3 ) 面向应用需求，为军队应急保障研究与开发提供理论与技术支持，设计并 实现了战场应急保障服务实验系统。 1 2 国内外研究现状 反向最近邻查询问题最早是由f k o m 和s m u t h u k r i s h n a n 在2 0 0 0 年提出的【1 1 ， 近几年来，相关研究机构投入了大量的人力和物力来从事该领域的研究。目前， 在反向最近邻查询问题的研究中，国外已经提出了几种处理模型和相应的算法， 并作了大量的模拟分析和评测工作，结合理论和实践，积累了较多的经验；而在 国内，对移动对象的反向最近邻查询问题的研究还刚刚起步，目前只有少量的相 关论文发表，哈尔滨理工大学的郝忠孝教授带领的研究小组对反向最近邻查询问 题做了专门的研究，并发表了一系列论文【9 1 4 】。 求反向最近邻一个最直接的方法是先计算每个点的最近邻，然后利用最近邻 查询或者范围查询判断集合中的哪些点将查询点作为最近邻。但是这种方法是不 可行的。因为此方法的时间复杂度是o ( n 21 ，当数据集很大时，复杂度会迅速增加 ( 刀为集合中元素的个数) 。 现有的研究按不同的分类方法，基本上可以分为：单色和双色反向最近邻查 询问题；低维( 一般为二、三维) 和高维( 三维以上) 反向最近邻查询问题；静态和动 态反向最近邻查询问题；预处理方法和空间修剪方法的反向最近邻查询问题等等。 现有的方法基本上都是单色r n n 的情况，所谓单色也就是所有的点都是属于 同一种类。双色反向最近邻查询问题与单色的情况不同的是，有两种不同种类的 数据点集。双色反向最近邻查询目前研究的还很少【1 5 】。 在单色r n n 的基础上，提出了各种有效的处理方法。这些方法可以分成两类： 预处理方法( p r e c o m p u t a t i o n ) 和空间修剪方法( s p a c ep r u n i n g ) 。 预处理方法在索引结构中提前处理和存储每个数据点的最近邻，并通过n n 查询或者范围查询来判断是否为反向最近邻。文献 1 1 首先定义了两种反向最近邻 第4 页 国防科学技术大学研究生院硕士学位论文 查询：b i c h r o m a t i cr n n 查询和m o n o c h r m a t i cr n n 查询，并提出- - ；f d e 称为r n n 树 的索引结构以支持反向最近邻查询。他们采用两种索引结构，r 树用于最近邻查询， r n n 树用于反向最近邻查询。这种方法由于采用两种索引结构仅仅在更新数据较 少或静态时效率高，在处理频繁更新数据时，查询性能就会急剧下降。为了提高 更新速度，k i n gl 等人【l6 】提出了种能够在r d n n 树中高效地插入大量数据点的 技术。r d n n 树将上述两种索引树合二为一，数据节点包含数据对象，目录节点包 含m b r s ，采用自顶向下的方式，当某一节点中最近邻的最大距离大于查询点与该 节点的距离时，不去访问该节点，以此为减枝策略减少了计算量。由于物化了所 有数据对象到其最近邻的距离，所以该方法无需进行最近邻查询。但是这种预处 理方法是不能处理r l c n n 查询的，除非相应的k 最近邻信息是有效的。空间修剪 方法利用了反向最近邻的几何属性，在原节点集的基础上查找更小范围的点集作 为候选点集，并通过最近邻查询或者范围查询来证实他们是否是查询点的反向最 近邻。现有的方法都是以r 树为索引结构。空间修剪的方法之所以灵活是因为这 种方法不需要预处理最近邻信息。然而，当数据维数高或者k 值大的时候，这种算 法的代价也是很昂贵的。 以往讨论的反向最近邻查询问题大都是静态的，也就是说查询点g 和数据点集 s 是静态的、不动的，并且是可以定义和存储数据点集的。然而，在许多应用中， 查询点和数据点集都是动态的，先前讨论的静态的方法就不能满足这样的查询。 目前此类的最近邻查询也有许多，并在此基础上提出了针对移动对象、数据点集 是动态的情况的反向最近邻查询。t a o 等人【1 7 】提出了一种数据点集是动态情况的反 向最近邻查询方法。其基本思想是采用查询点与对象点都成的线段的垂直平分线 将空间分成两个半平面，则对象点所在的半平面肯定不包含查询点的反向最近邻， 可以裁剪掉。通过这样不断的重复，使得查询的空间区域越来越小。k o m 等人u m 提出了基于数据流的反向最近邻问题的研究，并提出了反向最近邻聚集的概念， 通过它可以形式化地探索和研究基于数据流的反向最近邻问题。s t a n o i 等人【l 州用到 了空间修剪方法，将二维空间以查询点为中心分成六个相等的区域，规定每个区 域只包括一条边界。他们证明每个区域最多只有1 个反向最近邻，整个空间最多 存在6 个查询点的反向最近邻。这种方法将r n n 问题转化为n n 问题，不需要特 殊的索引结构，避免了数据点更新时频繁的计算和修改索引结构，效率大大地提 高了。b e n e t i s 2 0 将t p r 树作为底层的索引结构。t p r 树引入了时间参数，可以查 询在某时间片段内的移动对象的最近邻和反向最近邻。此方法可以针对移动对象 来进行查询，这是前面的方法所不能实现的，t p r 树在移动对象的查询中有广泛 的应用。 在现存的研究中，大部分方法都是只能应用到一、二、三维的空间中，如果 第5 页 国防科学技术大学研究生院硕士学位论文 维数增加就会使算法的效率急剧降低。高维的情况【2 1 , 2 2 1 研究得也不是很多，如t a o 给出了高维反向k n n 的查询算法【2 3 1 ，此方法以r 树索引结构为基础，不需要预处 理计算，并采用t p l 方法，此方法使用了过滤提纯技术，分两步处理：1 过滤： 检索所有的候选结点，并保证包含所有的反向最近邻；2 提纯：排除所有不是反向 最近邻的结点。第二步中采用了无缝的方法，不存在重复访问同一个结点的情况。 这种方法效率比前面的提高了，但是只能针对静态查询点的情况。 除了以上的反向最近邻查询问题外，还提出了大图中的反向最近邻查询问题 和连续的反向最近邻查询问题。m a n 等人【2 4 】提出的大图中的反向最近邻查询问题 中给出两个算法：e a g e r 算法和l a z y 算法，这两个算法可以在查询过程中对图进行 裁剪，大大缩小了查询范围。t a o 2 5 】等人提出的连续反向最近邻查询问题中给出了 c r n n 查询算法，该算法能够有效地处理查询对象不为点，而为一条线段的反向 最近邻查询问题。面对移动对象任意运动时就无能为力。 反向最近邻查询处理技术在理论上已经取得了一定的研究成果，然而距离实 际上的应用还有一短距离，因为已有的算法能够回答反向最近邻查询，但在处理 大规模移动对象数据集时响应较慢，不能满足用户的需求，而且大量并发的连续 查询不能得到处理，而在现实中这是经常存在的。在数据频繁更新时也没有算法 可以很好地及时地进行响应。 1 3 研究内容与思路 随着移动对象数据库相关技术的进一步发展，移动对象反向最近邻查询研究 成为移动数据库研究领域的一个热点。本文在对现有的移动对象反向最近邻查询 处理技术进行分析比较，把握各种方法的优点和不足的基础上，开展了以下方面 内容的研究： ( 1 ) 移动对象非连续反向最近邻查询处理技术 研究面向移动对象的反向最近邻查询，提出了基于网格索引的查询算法，根 据网格单元内移动对象的数目和查询对象所在单元在网格索引中的几何分布特征 判断单元是否为候选单元，从而将查询空间缩小至候选单元集。通过对候选单元 集中的对象计算其最近邻是否为查询点得到查询结果。实验分析和比较了实现算 法的性能。 ( 2 ) 移动对象连续反向最近邻查询处理技术 研究基于网格索引的大量并发连续反向最近邻查询处理技术，提出了一种多 线程的多用户连续查询处理框架，采用流水线处理策略，将连续查询处理过程分 解为可同时作业的查询预处理、查询执行以及查询结果分发三个阶段，通过利用 多线程技术来提高多用户连续查询处理的并行性，基于框架和移动对象内存网格 第6 页 国防科学技术大学研究生院硕士学位论文 索引，提出了一种基于多线程的连续反向最近邻查询处理算法，利用以往连续查 询的结果缩小查询空间，且支持查询集合中加入或删除查询和移动对象数据集的 插入、删除等动态更新。并且通过大量实验证明了更新算法的有效性和查询算法 的优越性。 ( 3 ) 基于上述成果，设计实现了战场应急保障服务实验系统，验证了网格索引、 反向最近邻查询技术和连续查询处理框架的有效性和实用性。 本文的研究思路如下图所示： 绪论 背景分析研究现状研究思路 易问题 相关技术研究 移动对象索引移动对象近邻查询现有方法比较 d 多基础 基于网格索引的移动对象反向最近邻查询算法( g 础州) 网格索引结构g r n n 算法实验分析 jb 扩展 、 大量并发连续反向最近邻查询算法( g c r n n ) 基本定义连续查询处理框架算法描述实验分析 jb 应用 战场应急保障服务原型系统 总体框架系统组成 运行流程 妙结论 总结全文，确定进一步工作 图1 1 论文研究思路 1 4 论文组织结构 根据上述研究内容及思路，文章的组织结构如下： 第一章：绪论。简单介绍了论文的研究背景和意义，回顾了国内外相关课题 的研究工作，提出了论文主要研究内容和所取得的成果。 第7 页 国防科学技术大学研究生院硕士学位论文 第二章：通过介绍移动对象索引技术和最近邻查询的各种类型，以及相关的 研究进展，大致概括了最近在此基础上的各种查询热点和若干关键技术。为后面 介绍反向最近邻查询起到一定的铺垫作用。 第三章：本章研究了移动对象的非连续反向最近邻查询处理问题，提出了基 于网格索引的1 3 r n n 查询算法，设计了有效的剪枝策略以减少存储空间和c p u 消耗，并通过实验证明了g r n n 算法的优越性。 第四章：本章首先给出连续反向最近邻查询的基本概念，针对大量并发的 c r n n 查询问题，提出了一种基于多线程的反向最近邻查询处理m p b g a m 框架， 详细描述了基于网格索引和m p b g a m 框架的g c r n n 查询更新算法。最后通过 实验比较了g c r n n 算法与其他算法的性能。 第五章：本章设计实现了一个战场应急保障服务实验系统，介绍了系统的总 体框架和组成模块，详细描述了反向最近邻查询模块的运行流程。 第六章：本章对全文内容进行了总括，回顾了本文的主要研究内容，并指出 了进一步可以进行研究的内容，作为下阶段研究的重点。 第8 页 国防科学技术大学研究生院硕士学位论文 第二章移动对象反向最近邻查询相关技术 合适的移动对象索引结构是构建良好查询算法的基础。移动对象数据库通常 管理着数量非常庞大的移动对象。在查询处理时如果逐个扫描所有的移动对象显 然会极大地影响系统的性能。为了减少搜索空间，提高查询性能，就必须对移动 对象进行索引。 反向最近邻查询从k 近邻查询衍变而来，具有和k 近邻查询相似的定义【2 6 j ：给 定查询点g ，点集尸，则反向最近邻查询得到点集r n n ，该点集包括n 个点，这 些点满足对v p ( p r n n ) 和跏r n n ，d i s t ( p ，p 。) d i s t ( q ，p ) ，其中，d i s t ( p ，p ) 是点p 和点p 之间的距离。关于移动对象的k 近邻查询国内外学者已经取得了大 量的研究成果，有许多思想和方法值得反向最近邻查询借鉴。因此，为了便于理 解并进行进一步的研究，下面对反向最近邻查询处理相关的关键技术：移动对象 索引技术和最近邻查询处理技术分别进行详细介绍。 2 1 移动对象索引技术 移动对象索引技术根据查询时间窗口范围可以分为以下三类口7 】：移动对象历 史轨迹索引、移动对象当前位置索引、移动对象当前及未来位置索引。下面对它 们分别详细介绍。 2 1 1 移动对象历史轨迹索引 传统空间索引方法的研究现已非常成熟，那么对现有空间访问方法进行修改 和扩展来索引移动对象历史轨迹是很直观的想法。基于这种思路，人们对标准r 树索引进行变换和扩展，如r t 树、3 dr 树、s t r 树等来对移动对象历史轨迹进 行索引，其思想是在传统空间索引方法中加入时间要素来处理用户带有时态语义 的空间查询。 r t 树【2 8 】对标准r 树进行扩充，利用时间间隔来标识移动对象历史轨迹有效时 间范围，历史轨迹所覆盖的空间区域仍然使用m b r ( m i n i m u mb o u n d i n gr e c t a n g l e ， 简称为m b r ) 来近似。r t 树的节点记录形式为四元组模型 。其 中谢标识移动对象，m b r 是包含移动对象历史轨迹的最小包围框，t 。和，。表示移 动对象历史轨迹m b r 的有效时间间隔。r t 树的空间查询性能与标准r 树相当， 时态查询( 包括时间片查询和时间窗e l 查询) 则使用t s b 树【2 9 】来进行访问，对于 时间片查询具有较好的查询性能，但时间窗口查询在某些情况下则可能需要搜索 第9 页 国防科学技术大学研究生院硕士学位论文 整个r t 树。 t h e o d o r i d i s 等人则将时间维与空间维( 二维空间) 查询语义等同考虑，对2 d r 树在三维空间中进行扩展提出了3 dr 树( 3 dr 树) 【3 0 】索引结构。3 dr 树可以直 接利用现有的r 树算法来处理空间及时态查询而无需修改，其前提是必须知道移 动对象历史轨迹存在的有效时间范围，如果移动对象轨迹结束时刻不确定，那么 3 dr 树将无法有效工作。比如若移动对象运动轨迹从某个历史时刻开始一直延伸 到当前时刻，显然包围移动对象轨迹的3 dm b r 将会非常巨大且造成空间区域的 大量重叠，直接导致3 dr 树的查询搜索性能下降。因此，在应用中要求移动对象 轨迹是封闭的，即移动对象历史轨迹必须在某个过去时刻终止而不能延伸到当前 时刻。由于3 dr 树将时间维与空间维等同索引，时间片查询则必须扫描整个3 dr 树而非在此时间片下的有效子树，因此性能非常低下。 与空间查询相比，时态查询语义非常简单( 时间片和时间窗口查询) ，因此 人们考虑在空间维上用传统方式建立索引，然后把时态查询转换为不同时间片下 的空间查询来解决移动对象历史轨迹查询问题。其实质是在每个时间片上建立相 应的r 树，将时间窗口查询转换为不同时间片下的传统空间查询。显然，这种索 引方式需要大量的存储空间。具有代表性的方法包括h r 树、m v 3 r 树、h i h 树、 p p r 树等。 h r 树【3 1 】目的是避免在每个时间片上构建独立的r 树而造成额外的空间存储 开销。h r 树在每个时间片都有一个独立的r 树根节点，包含当前的时间戳。相邻 时间片的r 树之间若存在公共对象( 节点) 时，则在新时间片r 树节点中使用一 个指针指向它们的公共节点而无需进行拷贝。由于相邻时间片r 树公共节点只存 储了一次，存储开销大大降低。显然，沿着不同的根节点可以访问各时间片下的 移动对象。这种索引方式在回答时间片查询时非常有效，但是对时间窗口查询来 说性能较差，而且可能会造成索引树中记录的大量复制。考虑这种情况，若相邻 时间片的r 树中只有一个移动对象位置发生变化，那么由于m b r 变化所产生的传 播操作将会导致包含此对象的叶节点( 中间节点) 中所有记录必须进行复制。 t a o 等人提出的m v 3 r 树【3 2 】采用一种混合索引结构来处理移动对象历史轨迹 查询。m v 3 r 树利用m v r 树来处理时间片查询，对于时间窗口查询则使用一个建 于叶节点之上的3 dr 树来处理。对于较短的时间窗口查询则根据优化准则从中选 择合适的索引m v r 树或3 dr 树来进行查询。m v 3 r 树以较高的空间存储代价换 取了很好的时间片和时间窗口查询性能，是目前最高效实用的移动对象历史轨迹 索引方法。 与上述两类面向移动对象位置的索引方法不同，面向移动对象轨迹索引方式 存储移动对象历史轨迹( 线段) 而不是位置( 点) 。移动对象历史轨迹使用线段 第1 0 页 国防科学技术大学研究生院硕士学位论文 集合( 每条线段有起始和终止时间戳) 来表示，即一条根据时间戳大小顺序连接 起来的折线段。根据空间划分方式和索引方法的不同此类索引方法可以分为s e t i 、 s e b 树、t b 树等。 s e t i t 3 3 】索引将空间区域分割成静态且不重叠的分区，在每个分区下对移动对 象的轨迹线段利用r 树进行索引。其考虑是，相对于无限连续变化的时间维而言， 移动对象轨迹受空间范围所限，那么可以把受限的空间区域利用某种规则静态划 分以分而治之。良好的划分函数应尽量把同一移动对象不同轨迹线段聚类在同一 个分区中。若一条轨迹线段穿过多个分区，那么必须将此线段裁剪并分别存储在 不同分区r 树中，这样会导致查询结果的重复，在查询处理后必须进行重复结果 的剔出。相应的，时态查询则被转换为对折线段集合的空间窗口查询，利用几何 计算方法可以得到空间窗口内的折线段集合，其对应的移动对象集合即是时态查 询结果。 s e b 树【3 4 】思想与s e t i 类似，但是在进行空间静态划分时允许不同分区之间区 域重叠。对每个移动对象s e b 树索引方法首先利用哈希变换将其映射到不同的分 区中，然后在每个分区中利用s e b 树对移动对象轨迹线段起始和结束位置进行索 引。s e b 树与s e t i 索引最主要的区别在于s e b 树存储移动对象轨迹线段的起始 和终止位置( 点) 而非轨迹本身( 线段) 。s e b 树时态查询则被转换为对点集合 的空间窗口查询，落在窗口内的移动对象轨迹线段起始和终止位置点所对应的移 动对象即为满足时态查询的结果。 2 1 2 移动对象当前位置索引技术 在移动对象历史轨迹索引中，必须预先知道移动对象轨迹范围，即数据库存 储移动对象的封闭轨迹，当前位置并不存储和检索，然而在现实许多应用中要