（计算机科学与技术专业论文）基于web的无线导航服务技术及其空间数据组织方法研究.pdf

摘要 出门在外，人们离不开导航。本文旨在随时随地向人们提供细致周到的导航 服务深度的、实时的、个性化的和综合的导航帮助。 目前，陆上导航产品主要有手持导航设备和车载导航系统两种。两种产品都 属于自主导航系统，除定位外不需要其他外界协助即可独立完成导航任务。自主 导航系统的最大特点是本地存储电子地图，本地执行包含最优路径求解等复杂任 务在内的全部计算。这一特点使得自主导航系统存在以下不足：( 1 ) 受存储容量的 限制，手持导航设备无法存储精细的地图，不能向用户提供深度的导航帮助。( 2 ) 受 c p u 性能的限制，执行复杂计算耗时严重。( 3 ) 地图更新不及时，使用陈旧数据可 能带来错误的导航。可见，手持导航设备无力提供细致周到的导航服务。 无线导航服务是一种更好的技术方案。在国外这项技术已经走向实用，不过 因为属于商业机密，我们只能了解到技术概况。而在国内没有见到成功的应用案 例的推出。于是，本文提出了“基于w e b 的无线导航服务( w w n s ) ”技术。w w n s 系统由连接于i n t e m e t 的服务器和接入移动通信网络的移动设备组成。服务器管理 海量的地图数据，承担主要的计算任务，通过移动通信网络向移动设备提供全部 或部分地图数据。传输协议采用h t t p 协议，通讯基于x m l 语言。移动设备本地 不存储或存储部分地图，执行简单计算和人机交互。w w n s 基于w e b 和浏览器( 安 装于移动设备内) ，这是与国外同类技术方案的不同之处。因为将来几乎所有移动 设备都会具备w e b 访问能力，这使得w w n s 的导航服务能够送达各种各样的移 动设备。 w w n s 能够提供细致周到的导航服务，原因在于：( 1 ) 服务器能够存储任意 精细的电子地图( 不会有存储容量的限制) 并共享i n t e m e t 上的信息资源；f 2 ) 服 务器执行复杂计算，快速响应用户请求；( 3 ) 地图数据在线维护，始终保持最新； ( 4 ) 服务器融合实时信息，对外提供实时信息服务；( 5 ) 服务器开展个性化适配， 支持个性化服务；( 6 ) 服务器支持位置服务集成，提供综合的导航帮助。 w w n s 系统的可用性受制于三大问题。一是带宽有限问题，是指移动网络带 宽有限使得地图数据无法及时送达移动客户端。二是访问量大问题，是指输出地 图时需要访问大量数据使得i o 开销大。三是处理复杂问题，是指输出地图前的复 杂的处理工作使得计算开销高。针对三大问题，本文分别给出有效的对策。 对于带宽有限问题，本课题从数据传输格式角度展开研究。在功能和应用前 景等方面对多种传输格式作出比较分析之后，得出以下结论：基于x m l 的s v g 语言最适宜用作w w n s 的地图数据传输格式。然而，s v g 文档相当累赘。针对这 一问题，本课题设计和实现了两种精简方法并通过基于实际地图数据集的实验加 以评测。评测结果表明，分别用g i f 、j p e g 和s v g 描述同一幅地图，经过精简处 第1 页 国防科学技术大学研究生院学位论文 理的s v g 文档最简洁。进一步的统计实验得出以下数据：通过g p r s ( 带宽假定 为4 0 k b p s ) 传输分辨率为3 0 0 * 2 0 0 的s v g 格式的地图，下行传输时间小于1 秒的 占到8 1 。而s v g 文档经过g z i p 压缩之后，下行传输时间小于1 秒的占到9 7 n 可见，基于g p r s 向手机传输s v g 格式的地图是可行的。 对于访问量大问题，本文提出新型的空间索引作为对策。空间索引是提高访 问效率的必要手段。本文归纳分析得出导航应用的数据访问过程存在“成批性”、 “区域性”和“多尺度性”三种最重要的特性。成批性是指数据访问的总量大， 因此数据i o 宜采用大粒度。区域性是指所读取的数据总是聚集在一个矩形区域 内，因此相互邻近的要素( 即空间对象) 的数据记录宜聚簇存储。多尺度性是指 重要性等级相同的要素经常被一起使用，因此同等级要素的数据记录宜聚簇。传 统空间索引重点关注区域性，没有把另外两个特性考虑在内。基于传统空间索引 的数据访问方法存在i o 粒度偏小和同等级要素之间的聚簇性差两个问题，造成效 率不高。为此，本文提出多尺度r - t r e e 索引，它综合三种特性，避免了i o 粒度偏 小和同等级要素弱聚簇问题。基于实际地图数据集的性能评测表明，对于区域查 询，基于多尺度r - t r e e 的数据访问方法在效率上明显优于基于h i l b e r t r t r e e 或 r e a c t i v er t r e e 的数据访问方法。使用多尺度r t r e e 索引能够提高服务器响应速度。 对于处理复杂问题，本文从数据组织角度提供对策。由于实际应用要求w w n s 服务器能够输出任意l t 侈, j 尺的地图，而地图数据库出于成本考虑只存储一份基础 比例尺地图，更小比例尺的地图需通过自动综合处理得到。自动综合处理包含选 择、精简、合并、移位、局部放大和变形等操作，计算代价非常高。为降低自动 综合处理的计算代价，目前广泛采用多尺度数据库技术。该技术通过特别的数据 组织方法来支持自动综合处理。然而，已有的多尺度数据库模型存在破坏数据聚 簇性、访问无效数据的概率大和额外存储空间开销偏大等问题。为此，本文提出 了基于分片的多尺度数据库( f m s d ) 模型。与已有模型相比，f m s d 模型的优点 有：数据组织结构更加合理、所需的额外存储空间开销更小、访问无效数据的概 率趋小和支持更多的自动综合处理操作等。f m s d 模型可自然地与多尺度r - t r e e 索引结合在一起，加快w w n s 服务器的响应速度。 综上所述，本文的主要贡献有：( 1 ) 提出了能够解决自主导航系统所存在的种 种不足的w w n s 技术；( 2 ) 通过定量分析指出通过移动通信网络传输s v g 格式的 地图是可行的；( 3 ) 提出多尺度r t r e e 索引以提高数据访问效率；( 4 ) 提出f m s d 模 型以减少自动综合处理的计算代价。 关键词：导航技术，自主导航系统，无线导航服务，多尺度r - t r e e 索弓l ，多 尺度数据库，基于分片的多尺度数据库模型 第1 i 页 a b s t r a c t b e i n go u t s i d e ，a l l o fu sn e e dn a v i g a t i o n t h i sd i s s e r t a t i o nw o r k so v e ran o v e l n a v i g a t i o nt e c h n o l o g y i t so b j e c t i v e i st op r o v i d eu sak i n do fc o m p r e h e n s i v ea n d e l a b o r a t en a v i g a t i o ns e r v i c e ，t h a ti s ，p r o f o u n d ，r e a l t i m e ，p e r s o n a l i z e da n di n t e r g r a t e d n a v i g a t i o nh e l p s ，a n y w h e r ea n da n y t i m e t o d a y , t h e r e a g e m a i n l y t w ok i n d so fl a n d - u s e n a v i g a t i o ns y s t e m s ：h a n d h e l d n a v i g a t i o n d e v i c e sa n dc a r n a v i g a t i o ns y s t e m s ( c n s ) t h e y b o t h b e l o n g t o a u t o n o m o u ss y s t e m s ，w h i c hc a l lc o m p l e t en a v i g a t i o nt a s k so n l yw i t ht h eh e l po f p o s i t i o n i n g f r o mo u t s i d e a u t o n o m o u s s y s t e m s s t o r e m a p sl o c a l l y , e x e c u t e a l l c o m p u t a t i o n si n c l u d i n gc o m p l e x t a s k ss u c ha s f i n d i n g t h eb e s tr o u t e t h e i r d i s a d v a n t a g e si n c l u d e ：( 1 ) w i t h l i m i t e d m e m o r yc a p a c i t y , b a n d h e l dn a v i g a t i o n d e v i c e sc a n n ts t o r ed e t a i l e dm a p ，a n ds oc a n n tp r o v i d ep r o f o u n dn a v i g a t i o nh e l p s ( 2 ) w i t hl i m i t e dc p u c a p a b i l i t y , e x e c u t i n gc o m p l i c a t e dt a s k sa r et i m e c o m s u m i n g ( 3 ) t h em a pd a t a s e tc a n tb eu p d a t e do nt i m ea n dm a y b ei n c o r r e c tn a v i g a t i o nh i n t sr e s u l t f r o mo u t - o f - d a t ed a t a i ti so b v i o u st h a th a n d h e l dn a v i g a t i o nd e v i c e sc a nn o t p r o v i d e c o m p r e h e n s i v ea n d e l a b o r a t en a v i g a t i o ns e r v i c e w i r e l e s sn a v i g a t i o ns e r v i c e ( w n s ) i sab e t t e rs o l u t i o nt h a na u t o n o m o u sn a v i g a t i o n s e r v e r a lw n ss y s t e m sa r e d e p l o y e dn o wi n f r e n c ha n da m e r i c a , e t c d u et o c o m m e r c i a ls e c r e c y , w eo n l yc a nl e a r nt h es y n o p s e so ft h e mi nc h i n a , t h e r ei sn o t a n ys u c c e s s f u lw n s s o l u t i o n s ot h i sd i s s e r t a t i o np r e s e n t san e w t e c h n o l o g yc a l l e d “w e b - b a s e dw i r e l e s sn a v i g a t i o ns e r v i c e ( w w n s ) ”w w n ss y s t e m sa r ec o m p o s e d o f i n t e m e tm a ps e r v e r sa n dm o b i l ed e v i c e s 。s e r v e r s m a n a g eh u g em a pd a t a s e t ， c o m p l e t em o s to fc o m p u t a t i o n sa n dt r a n s m i ta l lo rp a r to fm a p st om o b i l ed e v i c e s t h r o u g hm o b i l et e l e c o m m u n i c a t i o nn e t w o r k s t h ct r a n s p o r tp r o t o c o li sh t t pa n da l l c o m m u n i c a t i o n sa g ex m l c o d e d m e s s a g e s am o b i l ed e v i c es t o r e sn oo rj u s taf e w m a p s ，c o m p l e t e ss i m p l ec o m p u t a t i o n sa n di n t e r a c t sw i t hu s e r s w w n sa r ew e b - b a s e d a n dw e b b r o w s e r , a si sd i f f e r e n tf r o mt h ef o r e i g nw n ss o l u t i o n s b e c a u s ea l m o s ta l l o fm o b i l ed e v i c e sw i l lb ew e b - e n a b l e di nt h ef u t u r e ，t h ew w n s n a v i g a t i o ns e r v i c e w i l lb ea c c e s s e d b y a v a r i e t y o f m o b i l ed e v i c e s ， w w 溺c a n p r o v i d ec o m p r e h e n s i v ea n de l a b o r a t en a v i g a t i o ns e r v i c e t h er e a s o n sa r e ( 1 ) w w n s s e r v e r sw i t hh u g em e m o r y c a p a c i t yc a ns t o r ea sd e t a i l e dm a pa sn e e d e d a n ds h a r ei n f o r m a t i o nr e s o u r c e so ni n t e m e t ( 2 ) c o m p l i c a t e dt a s k sa g ee x e c u t e di n s e r v e r sw i t hh i g hc p u c a p a b i l i t ya n dt h er e q u e s t sf r o mu s e r sa r er e s p o n s e d p r o m p t l y ( 3 ) t h em a pd a t a s e ta r eu p d a t e do n l i n ea n da r eu p - t o d a t ea ta n yt i m e ( 4 ) s 、白 v e r s 第页 国防科学技术大学研究生院学位论文 s v n c r e t i z et h er e a l t i m ei n f o r m a t i o na n dp r o v i d er e a l t i m ei n f o r m a t i o ns e r v i c e s ( 5 ) s e r v e r sc m r yo u tp e r s o n a l i z e da d o p t i o na n dp r o v i d ep e r s o n a l i z e ds e r v i c e s ( 6 ) s e r v e r s i n t e r g r a t eo t h e r l o c a t i o n b a s e ds e r v i c e sa n dp r o v i d ei n t e r g r a t e ds e r v i c e s w w n s s y s t e r o i sh a v et h r e ep r o b l e m st h a ts e v e r e l yr e s t r i c tt h e i ra v a i l a b i l i t z t h ef i r s t o n ei s m a pt r a n s m i s s i o n ，w h i c h r e s u l t sf r o mt h el i m i t e db a n d w i d t ho fm o b i l e n e t w o r k s t h es e c o n do n ei sm a pa c c e s s ，w h i c hr e s u l t sf r o mt h eh u g em a pd a t a s e t t h et h i r do n ei sd a t ap r o c e s s i n g ，w h i c hr e s u l t sf r o mt h eh i g hc o s to f o p e r a t i o n ss u c h a s m a pg e n e r a l i z a t i o n t h ed i s s e r t a t i o np r e s e n t se f f e c t i v em e t h o d st o d e a lw i t ht h e t h r e ep r o b l e m s f o rt h ed a t at r a n s m i s s i o np r o b l e m ，o u rr e s e a r c h e sf o c r so nd a t at r a n s m i s s i o nf o r m a t s b yc o m p a r i n gt h e f e a t u r e so fas e r i e so ft r a n s m i s s i o nf o r m a t s ，t h ed i s s e r t a t i o n c o n c l u d e st h a tt h ex m 艮- b a s e ds v gi st h em o s ta p p r o p r i a t eo n ef o rw w n so r i g i n a l s v gd o c u m e n t sa r ev e r b o s e ，s ow ed e s i g n e da n di m p l e m e n t e dt w om e t h o d st o s i m p l i f ys v gd o c u m e n t s ，e x p e r i m e n t sb a s e do na c t u a lm a p d a t as e tw e r em a d et o m e a s u r et h ee f f e c t i v e n e s so ft h et w om e t h o d s r e s u l t si n d i c a t et h a tw h e nu s i n gg i f , j p e ga n ds v gt or e p r e s e n ts a m em a p s t h es i m p l i f i e ds v gd o c u m e n t sa r et h e c o m p a c t e s tf u r t h e r ，t h ef o l l o w i n gs t a t i s t i c sw e r e c o l l e c t e d ：f o rt h et r a n s m i s s i o nt i m e s o f s v g - f o r m a t t e dm a p st h r o u g hg p r s ，w h o s er e s o l u t i o ni s3 0 0 + 2 0 0 ( p i x e l ) ，8 1 o f t h e ma r el e s st h a no n es e c o n d 9 7 o ft h e mc o m p r e s s e db yg z i pa r el e s st h a no n e s e c o n d s oi ti sf e a s i b l et ot r a n s m i ts v g - f o r m a t t e d m a p st h r o u g h g p r s f o rt h ed a t aa c c e s sp r o b l e m ，t h i sd i s s e r t a t i o np r o p o s e san o v e ls p a t i a li n d e x s p a t i a l i n d e xi san e c e s s i t yt oi m p r o v et h ee f f i c i e n c yo fd a t aa c c e s s b yd e e pi n v e s t i g a t i o n s ， w ef o u n dt h a tt h ed a t aa c c e s so f n a v i g a t i o na p p l i c a t i o n s h a st h r e e p r o p e r t i e s ： “i n b a t c h e s ”“i n a - r e g i o n ”a n d “m u l t i s c a l e ”i n b a t c h e sm e a i l st h a tt h ea m o u n to f d a t aa c c e s s e di sl a r g e ，a n ds oc o a r s ei og r a n u l a r i t ys h o u l db ep r e f e r e d i n a - r e g i o n m e a n st h a ta l lf e a t u r e so fm a p sa c c e s s e da r ea s s e m b l e di nar e c t a n g l er e g i o n ，a n ds o t h en e i g h b o r i n gf e a t u r e s d a t ar e c o r d ss h o u l db ec l u s t e r e di nt h ed i s km u l t i - s c a l e m e a n st h a tt h em a ps c a l ed e t e r m i n et h ed e t a i ll e v e lo fc o n t e n t s w h i c hc a u s e st h e f e a t u r e so f $ a r o el e v e l sa l eo 矗u s e dt o g e t h e r , a n ds ot h e i rr e c o r d ss h o u l db e c l u s t e r e d e x i s t i n gs p a t i a li n d e x e so n l yp a ya t t e n t i o nt oi n - a - r e g i o n ，b u ti g n o r et h e o t h e rt w o t h ea c c e s sm e t h o d sb a s e do nt h e mh a v et w o p r o b l e m s ：l 证k i 0 g r a n u l a r i t ya n dn o n c l u s t e r e dr e c o r d so ff e a t u r e so fs a l t l el e v e l s ，w h i c hk e e pt h e a c c e s s e f f i c i e n c yw i t h i n l i m i t s s o ，t h i sd i s s e r t a t i o np r o p o s e san e ws p a t i a li n d e x c a l l e dm u l t i s c a l er - t r e e i ti n c o r p o r a t e sa l lo f t h e s et h r e e p r o p e r t i e sa n d s oc a na v o i d t h ea b o v et w od i s a d v a n t a g e s 1 1 1 ee v a l u a t i o ne x p e r i m e n tb a s e do na c t u a l m a p d a t a 国防科学技术大学研究生院学位论文 s h o w s ，f o rr a n g eq u e r i e s ，t h ea c c e s sm e t h o d b a s e do nm u l t i s c a l er t r e ei sm u c h m o r e e 币c i e n tt h a nt h o s eb a s e do nh i l b e r t r - t r e eo rr e a c t i v er - t r e e a p p l y i n gm u l t i s c a l e r t r e ec a l la c c e l e r a t et h er e s p o n s es p e e do fw w n s s e r v e r s f o rd a t ap r o c e s s i n gp r o b l e m ，t h i sd i s s e r t a t i o nt a k e sa d v a n t a g eo ft h es u p p o r to fd a t a o r g n i z a t i o n a p p l i c a t i o n sr e q u k ew w n s s e l v e l st oo u t p u tm a p so fa n ys c a l e s ，b u t c o m m o n l y , t h e r ee x i s t so n l yo n eb a s em a pc o p yi n ad a t a b a s ea n dm a p so fl o w e r s c a l e sh a v et ob eg e n e r a l i z e df r o mi tm a pg e n e r a l i z a t i o ni sc o m p o s e do fo p e r a t i o n s i n c l u d i n gs e l e c t i o n ，s i m p l i f i c a t i o n ，a g g r e g a t i o n ，d i s p l a c e m e n t ，e n l a r g e m e n t a n d c o l l a p s e ，e t c i ti sat i m e c o n s u m i n gt a s k t oc u tt h ec o s td o w n ，t h em u l t i s c a l e d a t a b a s e t e c h n o l o g y i s e x t e n s i v e l y u s e da t p r e s e n t ，w h i c ha p p l i e ss p e c i a l d a t a o r g a n i z a t i o nt os u p p o r tg e n e r a l i z a t i o n b yd e e pi n v e s t 塘a t i o n s ，w ep o i n t so u tt h a tt h e e x i s t i n g m u l t i s c a l ed a t a b a s em o d e l sh a v eaf e wp r o b l e m ss u c ha s b r e a k i n g t h e c l u s t e r n e s so f d a t a , h i g hp r o b a b i l i t yo fa c c e s s i n gu s e l e s sd a t aa n do c c u p y i n gl a r g e s t o r a g es p a c e ，e t c a n e wm u l t i - s c a l ed a t a b a s em o d e lc a l l e d f r a g m e n t b a s e d m u l t i s c a l ed a t a b a s em o d e l ( f m s d ) i sp r o p o s e di nt h i sd i s s e r t a t i o n f m s di s c o m p o s e do fm u l t i s c a l er - t r e ea n dm u l t i s c a l e s t r u c t u r eo ff e a t u r e s f m s dh a s a d v a n t a g e so v e rt h ee x i s t i n gm o d e l s ，i n c l u d i n g ：( 1 ) t h es t r u c t u r eo f d a t ao r g a n i z a t i o n i s 】! d r e a p p r o p r i a t e ( 2 ) i tn e e d sl e s ss t o r a g es p a c e ( 3 ) t h ep r o b a b i l i t yt oa c c e s s u n u s e f u ld a t ad e c r e a s e s ( 4 ) i ts u p p o r t sm o r e g e n e r a l i z a t i o no p e r a t i o n s f m s dm o d e l c a nb en a t u r a l l yc o m b i n e dw i t hm u l t i s c a l er - t r e ea n d i m p r o v et h er e s p o n s es p e e do f w w n ss e r v e r s t o g e t h e r a l t o g e t h e r , t h em a i nc o n t r i b u t i o n so ft h i s d i s s e r t a t i o n i n c l u d e ：( 1 ) i tp r o p o s e st h e w w n s t e c h n o l o g y w h i c hc a l lo v e r c o i t l et h ed i s a d v a n t a g e so fa u t o n o m o u s n a v i g a t i o n s y s t e m s ( 2 ) i tg e t s ac o n c l u s i o na sac o n s e q u e n c eo fq u a n t i t a t i v e a n a l y s i s e st h a t t r a n s m i t t i n g s v g - f o r m a t t e d m a p st h r o u g h g p r si s f e a s i b l e ( 3 ) i tp r o p o s e s m u l t i 。s c a l er t r e ew h i c hc a l li m p r o v et h ee f f i c i e n c yo fd a t aa c c e s s ( 4 ) i t p r o p o s e s f m s dm o d e lw h i c hc a nc u tt h ec o s t o f m a p g e n e r a l i z a t i o nd o w n k e y w o r d s ：n a v i g a t i o nt e c h n o l o g y , a u t o n o m o u sn a v i g a t i o n s y s t e m , w i r e l e s s n a v i g a t i o ns e r v i c e s ，m u l t i s c a l er - f l e ei n d e x ，m u l t i s c a l ed a t a b a s e ，f r a g m e n t - b a s e d m u l t i s c a l ed a t a b a g em o d e l 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意。 学位论文题目：赶遄鲎趔擞峰缝辜熊奎渔避堡越缉究 学位论文作者签名：兰p 军鑫_ 日期：；一牛年争月日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学使论文在解密后适用本授权书。) 学位论文题目： 学位论文作者签名：，一! 牟缂童l 作者指导教师签名：刘兰翌 日期：2 。午年争月f 日 日期：电d 早年每月乎日 国防科学技术大学研究生院学位论文 图12 1 图1 22 图l23 图21l 图2 1 2 图22 1 图222 图2 ，31 图232 图23 3 图234 图2 35 图2 36 图23 7 图238 图25l 图25 2 图2 61 图321 图33 1 图332 圈33 3 图3 34 图33 5 图33 6 图337 图338 图35l 图352 图353 图354 图3 55 图356 图3 5 7 图358 图421 图422 图4 4l 图4 42 圈443 图目录 c e c 9 6 8 0 外观图 车载导航系统 日本车载导航终端历年销售数 s m a r t z o n e 导航解决方案示意图 j e n t r o 导航系统一 w m s 的体系结构 o p e n l s 的位置服务应用框架 w w n s 系统示意图 w w n s 服务器的结构 出行路径 个性化适配示意图 位置服务集成示意图 实时信息融台示意图 短消息导航服务器 会面导航服务过程 a r c l m s 的应用体系结构 w m t s 的结构 地图输出流程 文字沿着曲线路径铺开 地图样本l ( 1 0 0 0 6 0 0 ) 地图样本2 ( 1 0 0 0 6 0 0 ) 地图样本3 ( 1 0 0 0 6 0 0 ) 地图样本4 ( 1 0 0 0 * 6 0 0 ) 地图样本5 ( 1 0 0 0 6 0 0 ) 地图样本6 ( 1 0 0 0 6 0 0 ) 地图样本7 ( 1 0 0 0 * 6 0 0 ) 地图样本8 ( 1 0 0 0 * 6 0 0 ) 样本l ( 3 0 0 * 2 0 0 ) 样本2 ( 3 0 0 * 2 0 0 ) 样本3 ( 3 0 0 * 2 0 0 ) 样本4 ( 3 0 0 * 2 0 0 ) 样本5 ( 3 0 0 * 2 0 0 ) 样本6 ( 3 0 0 * 2 0 0 ) s v g 文档的尺寸分布 经孕i p 压缩的s v g 文档的尺寸分布 点列 空间数据模型 预选择操作 选择操作 精简操作 3 5 5 1 l 】3 1 5 1 8 1 9 2 0 2 2 2 3 2 4 2 5 2 5 2 6 2 8 2 9 3 l 3 6 3 9 3 9 4 0 4 0 4 0 4 0 4 1 4 l 4 6 4 6 4 6 4 6 4 6 4 6 4 7 4 7 5 0 5 0 5 5 5 5 5 5 国防科学技术大学研究生院学位论文 图4 4 4 变形操作 图4 4 5 局部放大操作 图4 4 6 移位操作 图4 4 7 平滑操作 图4 48 合并操作 图4 49 取样操作 图4 4 1 0 归类操作 图4 4 1 1 复杂的移位操作 圈5 2lr t t t e 图5 2 2h i l b e f t 曲线 图52 3r e a c f i v er - t r c c 图524i o 粒度决定i ，o 速率 图53 1 多尺度r - t r e e 图5 32 查询吞吐率 图6 2 1 多段线精简示意图 图6 2 2 精简导致自相交 图6 2 3 偏差数组一 图6 2 4 偏差数组变换为比例尺数组 图6 3 1 通用的空间数据模型 图6 3 2c a r d i f f 模型的层次 图6 3 3 子图形的裁剪 图634 无效顶点群 图635m b r 面积对区域查询性能的影响 图6 3 6w a t e r l o o 模型的层次 图6 3 7 w a t e r l o o 模型的存储结构 图6 38 包含两个比例尺的c u b e 图6 3 9g a p t r e e 及其实际情景 图631 0 填充被去除的区域一 图6 4 if m s d 模型的分片 图6 4 ，2 f m s d 空问数据模型 图6 4 3 f m s d 模型的存储结构 图6 4 4 多边形的分片方法 图645 分片的m b r 与顶点群的d m b r 之比较 图65 i 精简产生空隙 6 6 、7 4 7 8 7 9 8 l 8 2 8 3 8 4 8 5 8 7 8 8 8 9 9 0 9 l 9 2 9 3 9 4 9 4 9 5 9 7 9 9 1 0 2 托她跖铂“卯印n甜 里堕型兰茎查奎兰竺耋圭堕兰些堡苎 表目录 两种传输机制性能比较 矢量格式v s 栅格格式 描述线型地图的s v g 、g i f 和j p e g 文件尺寸比较( 单位 g z i p 压缩比 j p e g 、g i f 的g z i p 压缩 平均时间开销( 单位：毫秒) 统计和磁盘i o 统计数据 数据i o 时间( 单位：毫秒) 3 0 3 4 字节) 4 2 、4 3 4 3 一 7 3 7 4 ：l，1， 5 3 4 4 3 3 2 3 ，j 1j! 表丧表表表表襄 国防科学技术大学研究生院学位论文 第1 章绪论 1 1 导航技术 出门在外，我们每个人都离不开导航。本文所述的导航专