6.2 POI数据的组织与应用（教学课件）信息技术浙教版2019选择性必修1

第2节 POI数据的组织与应用 （1课时） 第6章 大数据时代数据的组织 浙教版（2019） 选修一 POI数据的概念 01 POI数据的组织与表示 02 POI数据处理中的数据结构与算法分析 03 学习目录 熟悉 POI数据的特点与应用。 01 了解空间索引技术，熟悉POI数据典型的数据组织与处理方式，初步分析POI数据处理过程中的算法效率。 02 理解数据结构与算法的迭代性。 03 学习目标 PART 01 POI数据的概念 新课导入 北斗导航系统 地理信息系统GIS 计算机技术 通信技术 遥感技术RS 地理信息服务 随着计算机技术、通信技术和3S技术（遥感技术RS、地理信息系统GIS、全球定位系统GPS的统称）的发展融合，互联网环境中的地理信息服务已经成为人们网络生活的重要组成部分。 新课导入 看 看 一 网络地理信息服务离不开POI的支持 POI数据的概念 一 概念 POI是“Point of Interest” 的 缩 写， 可 以翻译成“兴趣点”，有些时候也叫作“Point of Information”，即“信息点”。电子地图上一般用气泡图标来表示POI。 导航地图中显示的兴趣点 POI数据的概念 一 描述了空间实体或者区域的空间位置、名称地址等 基本信息:名称、类别、空间坐标信息(经纬度)、地址、电话、邮政编码等 衡量POI数据价值:空间位置的准确性和覆盖率、空间位置的数量 POI数据的概念 一 应用 POI数据在社会各个领域都得到了广泛的应用。 地铁、公交动态数据--行进线路名称、站点名称、到站时间等 基于北斗导航、GPS获取的公交数据重要应用：路段行程速度估算 POI数据的概念 一 为城市公交线路设置提供科学依据 某条道路的24小时动态人流量，做出道路的改造方案、商业店铺选址决策等 哈啰单车停车点 POI数据的概念 一 只需知道数据之间相互链接的顺序 探讨与讨论 一 不属于衡量POI数据价值的指标是（ ） A.空间位置的准确性 C.空间位置的数量 B.空间位置的面积大小 D.空间位置的覆盖率 B POI数据的组织与表示 PART 02 POI数据的组织与表示 二 POI数据一般以表记录或点状数据集的形式存在，如以表结构形式储存于Oracle的大型数据库中。 POI数据的组织与表示 二 数据结构主要包含下列数据 唯一标识号 点的POI分类编码 POI名称 点要素属于的矩形分幅的网格号 POI地址 POI电话 POI的经纬度 坐标 POI数据的组织与表示 二 针对这样的大数据进行处理，可以用什么技术 来实现呢？ POI数据的组织与表示 二 只需知道数据之间相互链接的顺序 探讨与讨论 一 如何根据自己所在位置来查询附近50米的POI？（如商家、景点） 枚举算法：计算位置与所有POI的距离，并保留距离小于50米的POI 经纬度计算公式复杂 算法效率低 POI数据的组织与表示 二 提供了一种超大规模、高可靠性、高可扩展性的存储及计算海量数据的框架，可降低成本 基于HBase的存储可靠性强、检索性能高、存储列可按需增加的特点存储地理信息专题数据 基于HDFS文件系统的高容错性和高吞吐量特点存储空间影像数据 基于MapReduce的计算能力对地理信息中的各种数据进行搭建，对地理信息专题数据进行信息提取，提取有效信息 Hadoop 1 3 2 4 POI数据的组织与表示 二 包含空间对象的概要信息，如：标识、外接矩形、指针 使空间操作快速访问对象，缩短查询时间 基于树结构 基于网格划分 POI数据的组织主要涉及空间索引问题，空间索引是指依据空间对象的位置和形状或者空间对象之间的某种空间关系，按一定的顺序排列的一种数据结构。 考虑到POI数据本身为点信息，一个数据仅可能出现在一个索引位置中，因此经常使用网格空间索引来对POI建立空间索引。 POI数据的组织与表示 二 网格空间索引 将一副地图的地理范围均等划分为M行N列的二维空间数据，得到M×N个小矩形网格区域。 判断哪些信息点落在矩形框中只需对A,B,C,D,E运算即可 ※不建立空间索引，所有POI遍历一遍 ※建立索引使得查询次数下降很多 每个网格索引为一个索引项 网格示意图 POI数据的组织与表示 二 如果一个图层有10万个POI，不建立空间索引，任何地图操作都将对整个图层的所有POI遍历一次，也就是要循环10万次；建立索引将使得程序循环的次数下降很多，效率也随之提高。 网格示意图 POI数据的组织与表示 二 只需知道数据之间相互链接的顺序 探讨与讨论 一 在大数据环境下，处理海量POI数据时，以下哪种技术最为关键？（ ） A. 传统的关系型数据库管理 B. 简单的文件存储系统 C. 单机数据处理模式 D. 分布式计算框架（如Hadoop） D POI数据处理中的数据结构与算法分析 PART 03 POI数据处理中的数据结构与算法分析 三 POI数据操作 1 1 2 连接POI数据库，将POI数据写入索引数据库。 根据关键字进行查询，存储符合条件的记录，获得结果集。 将POI的名称、地址、电话、分类、经纬度坐标写入索引数据 将兴趣点信息“名称：浙江大学（玉泉校区）；地址：浙江省杭州市西湖区浙大路38号；分类：教育；经纬度坐标：120.129649, 30.270072”写入索引数据库。 POI数据处理中的数据结构与算法分析 三 ① ② 在获得结果集的前提下，如果要根据某个点的坐标在海量的数据点中找到该坐标所在的区域或者最接近的点 ※二分查找： 不适用与经纬度 ※B 树查找： 查找效率没有提高 3.增加了对地理坐标优化的空间索引算法 POI数据处理中的数据结构与算法分析 三 01 R树 K-D树 02 03 四叉树 高效查找临近点 01 存在数据冗余 不稳定的查改效率 02 缺点 抛开时间效率、空间效率以及算法复杂度等因素，用了这些数据结构也就意味着放弃了使用现成强大的数据库而需要自己编写数据查改系统。 POI数据处理中的数据结构与算法分析 三 二维的信息转化为一维的数据 用于空间检索 用于POI数据查询的算法 良好的稳定性和拓展性 GeoHash 算法 GeoHash算法：二维-->一维 能够广泛引用与空间检索，尤其是POI数据查询的算法 POI数据处理中的数据结构与算法分析 三 拓展链接 GeoHash算法 GeoHash算法由古斯塔沃·尼迈尔（Gustavo Niemeyer）大概于2013年提出，目的是为地球上的每一个点（根据经纬度）确定一条短的URL作为唯一的标识。 GeoHash算法把一个坐标点映射到一个字符串上，每一个字符串代表的就是一个以经纬度划分的矩形区域。比如右图展现了北京地区所在的九个区域，分别是WX4ER、WX4G2、WX4G3等。 POI数据处理中的数据结构与算法分析 三 03 01 02 GeoHash算法特性 层级空间数据结构，将地理位置用矩形网格划分，同一网格内地理编码相同； 可以表示任意精度的地理位置坐标，只要编码长度足够长； 编码前缀匹配的越长，地理位置越邻近 GeoHash算法用类似四叉树的方法来寻求一个点，对经度和纬度不断地进行二分，最终确定到想要的精度。 POI数据处理中的数据结构与算法分析 三 第四次 第三次 第二次 第一次 GeoHash算法用类似四叉树的方法来寻找一个点，对经度和纬度不断地进行二分，最终确定到想要的精度，划分的过程如下： POI数据处理中的数据结构与算法分析 三 每5位为一组，用0—9，b—z（去掉a, i, l, o）进行Base32编码，即可得到该区域经过编码后的GeoHash值。 POI数据处理中的数据结构与算法分析 三 c g v z b f u y 9 e t x 8 d s w 3 7 m r 2 6 k q 1 5 j p 0 4 h n 编码结果 在坐标写入数据库的同时，将程序计算出坐标的GeoHash值并一起入库。 POI数据处理中的数据结构与算法分析 三 只需知道数据之间相互链接的顺序 探讨与讨论 一 下列关于POI数据处理中的数据结构与算法的说法,不正确的是( ) A.使用 R树来存储数据可以做到高效地查找临近点 B.GeoHash算法能把一个一维的信息转化为二维的数据加以存储 C.四叉树存在数据冗余,不稳定的查改效率等缺点 D.可以使用二分查找找到指定坐标所在的区域或者最接近的点 B 课堂小练 四 只需知道数据之间相互链接的顺序 探讨与讨论 1.以下关于POI数据的描述中不正确的是( ) A.电子地图上的景点、公司、商场、饭馆等,都是POI B.POI描述了空间实体或者区域的空间位置、名称地址等信息 C.POI数据一般用Access等小型数据库来进行组织和存储 D.Hadoop为海量POI数据的存储与计算提供了保障 C 2.POI数据的组织主要涉及空间索引问题。下列有关空间索引问题的描述中错误的是（ ） A.空间索引是一种特殊的数据结构 B.空间索引可以使空间操作快速访问对象 C.空间索引技术大致分为基于链表结构和基于图结构两种 D.经常使用网格空间索引来对POI建立空间 C 小结 五 小 结 1.POI数据的概念 (1)概念（2）应用 2.POI数据的组织与表示 （1）数据结构（2）Hadoop （3）空间索引（4）网格空间索引 3.POI数据处理中的数据结构与算法分析 （1）POI数据操作 （2）GeoHash算法 ①特性②规则 谢谢观看 第2节 POI数据的组织与应用 浙教版（2019） 选修一 $$