手机版
 找回密码
 立即注册
理财客 配资 东南配资
  • QQ空间
  • 回复
  • 收藏

基于Google-S2的地理相册服务实现及应用

xufang1985 2020-2-14 16:17 936人围观 7*24快讯

写在前面

对抗疫情的战斗还在继续。做好个人和家庭的防护,保持良好的心态,过好本身的生存,就是每个平凡人抗击疫情最好的武器。

在如许的变革下,马蜂窝充实发挥内容与社区上风,让各人在疫情期间天天在平台上通过欣赏其他网友发布的视频和条记找到正能量;宅在家的同时可以举行“云观光”,收藏和点赞本身想去的地方。

为了不停优化用户在马蜂窝分享内容的体验,我们不绝在积极。本文告急先容马蜂窝内容业务研发团队在 App 地理相册空间索引方面的探索和应用实践,盼望为有类似题目的同砚带来一些思绪。

疫情终将已往,那些被取消的观光操持,会在风景更美的时间成行。

随着智能手机存储容量的增大,以及相册备份技能的遍及,我们可以随时随地用手机影像纪录生存,在手机中存储几千张乃至上万张照片已经是很常见的变乱。但另一方面,当我们想从这么多张照片中去找到一张,也是一件贫困事。

马蜂窝作为观光玩乐平台,盼望实现「会玩的人」与「好玩的事」之间的毗连。浩繁观光爱好者在这里纪录和分享他们的观光影象,使马蜂窝在旅游 UGC 范畴累积了大量内容。因此,不停优化用户在发布内容时的体验是我们不绝积极的主向。

用照片、视频纪录观光是最直接的方式。本文将先容马蜂窝怎样通过 App 地理相册空间索引的应用,为用户提供直观、好用的图片分享服务。

Part.1应用场景和需求

要想让用户快速地找到想要分享的照片/视频,我们须要一个有用且公道的筛选本领,对用户的相册举行聚合、排序,提升用户依托相册去分享和纪录生存时易用性和便捷性。

起首要确定聚合排序的筛选维度。照片的地理位置就是最直观的分类维度;同时,纪录迩来发生的变乱符适用户的发布举动风俗。因此我们方案要满意的需求是:

  1. 根据目标地和时间,对用户相册举行聚合、排序;
  2. 基于某个地理位置信息和给定范围,在用户相册中搜索给定范围的照片/视频。

本文提及的地理相册服务在马蜂窝 App 内告急有两个落地场景。

1.1 条记

「条记」是以图片、视频为告急出现情势的观光短内容分享。用户发布条记的第一个环节就是从相册中选择须要发布的照片/视频,在新版 App 中,基于地理相册服务联合马蜂窝自有目标地数据,对用户相册举行按照地点维度的聚合分类,而且按照片/视频的创建时间由近及远的排序,提升用户选择发布服从。

基于Google-S2的地理相册服务实现及应用_7*24快讯_2020-2-14 16:17发布_配资查_www.peizicha.com

1.2 足迹

「足迹」这一产物的功能,旨在资助马蜂窝用户以自动同步或手动点选去过的国家和地区这种更浅易的方式纪录观光。在「我的足迹」中有一个场景,会鼓励用户对去过的但还没有发布条记的地点发布条记。此时地理相册服务可以资助用户发布相册中以指定地点为圆心,给定半径范围内的全部照片。

基于Google-S2的地理相册服务实现及应用_7*24快讯_2020-2-14 16:17发布_配资查_www.peizicha.com

Part.2方案计划与算法选型

2.1 初期方案

初期我们想到的方案比力直观,也比力粗暴,就是对相册举行遍历后由服务端盘算效果。具体来说,起首取出用户全部携带地理信息的照片/视频,然后将地理信息(经纬度)上传服务端,由服务端举行聚合和筛选,返回给客户端效果,但是这个方案有很多缺点。

文章开始我们已经形貌了现在用户手机装备中的照片数目是成千上万的,假如遍历全部图片,这上传的数据体量是巨大的;同时,一样寻常用户照片的地理位置会有很多出现出成簇聚集的状态,由于一样寻常我们会在一个地点范围内拍摄很多照片,这就导致了大量的重复聚类的盘算。

假如要优化这个方案,针对第一个需求我们可以接纳缓存+增量哀求的方式,由于用户分类数据是稳固的。但是针对给定范围查询的需求,我们无法做缓存,这就须要每次都哀求服务端做大量的盘算,对于时间的斲丧是不能容忍的。

可以看到,上述方案的寻衅告急在于用户相册中地理信息的数据量和重复度、依赖服务端盘算搜索效果导致的性能题目和用户体验。颠末调研我们发现,基于地理空间点(经纬度)索引算法可以很好地管理这些题目。

2.2 基于地理空间点索引算法的实践

联合我们的实际需求来明白地理空间点索引算法,即找到符合的方法来对地理空间中海量的坐标点添加索引,从而对空间点举行快速查询和排序的一种算法。

我们对一些比力通用的地理空间点索引算法举行了选型比力,下面告急先容 GeoHash 算法和 Google-S2 算法。

2.2.1 算法选型

(1)GeoHash

GeoHash 算法即地理位置隔断排序算法。Geohash 是一种地理编码,由 Gustavo Niemeyer 发明。它利用一种分级的数据结构,把空间分别为网格。

GeoHash 属于空间添补曲线中的 Z 阶曲线的实际应用。GeoHash 有一个和 Z 阶曲线干系的性子,那就是一个点附近的地方 Hash 字符串总是有公共前缀,而且公共前缀的长度越长,这两个点隔断越近。由于这个特性,GeoHash 就经常被用来作为唯一标识符,比如在数据库内里可用 GeoHash 来唯一表现一个点。

基于Google-S2的地理相册服务实现及应用_7*24快讯_2020-2-14 16:17发布_配资查_www.peizicha.com

GeoHash 这个公共前缀的特性就可以用来快速的举行相近点的搜索。越靠近的点通常和目标点的 GeoHash 字符串公共前缀越长。但是 Z 阶曲线有一个比力严肃的题目,就是它的突变性。在每个 Z 字母的拐角,都有大概出现序次的突变,导致搜索相近点的准确度较差,不能满意我们的业务场景对准确度的要求。

(2)S2 算法

S2 着实是来自多少数学中的一个数学符号 S,它表现的是单位球。

S2 算法接纳正方体投影的方式将地球睁开,然后利用希尔伯特分形曲线将睁开后的二维地球举行添补,完成了对三位地球的降维和分形,从而得到空间坐标点与希尔伯特分形曲线的函数关系,即将球面经纬度坐标转换成球面 xyz 坐标,再转换成正方体投影面上的坐标,末了变更成修正后的坐标在坐标系变更,映射到 [0,2^30^-1] 区间,末了一步就是把坐标系上的点都映射到希尔伯特曲线上。终极,映射到希尔伯特曲线上的点成为 Cell ID,便是空间坐标点的索引。

基于Google-S2的地理相册服务实现及应用_7*24快讯_2020-2-14 16:17发布_配资查_www.peizicha.com

S2 的最大的上风在于精度高。Geohash 有 12 级,从 5000km 到 3.7cm,中心每一级的变革比力大。偶然候大概选择上一级会大很多,选择下一级又会小一些。而 S2 有 30 级,从 0.7cm 到 85,000,000km,中心每一级的变革都比力平缓,靠近于 4 次方的曲线。以是选择精度时不会出现 Geohash 选择困难的题目。

综上,S2 算法可以大概满意我们对于功能和精度上的要求,因此终极选择 S2 算法作为空间点索引算法的实现方案。

Part.3功能实现与性能优化

3.1 模块计划

本文中的 App 地理相册服务告急基于相册索引数据操纵、用户相册扫描、相册索引服务和相册地点分类盘算四大模块实现:

基于Google-S2的地理相册服务实现及应用_7*24快讯_2020-2-14 16:17发布_配资查_www.peizicha.com

以下分别先容。

3.1.1 相册索引数据操纵模块

相册位置信息的索引接纳数据库作为存储介质,将用户照片信息以及通过 S2 算法盘算出来的 Cell ID 存储到数据库当中。此中,考量存储的数目和对搜索和聚合经度的要求,存储了从 Level4~Level16 经度级别的 Cell ID。

相册索引数据操纵模块,由数据库(DB)和数据库操纵层(DAO)构成。数据表的计划见下图:

基于Google-S2的地理相册服务实现及应用_7*24快讯_2020-2-14 16:17发布_配资查_www.peizicha.com

数据库操纵层(DAO)封装了数据插入、删除、查询等根本操纵的 API。

3.1.2 用户相册扫描模块

用户相册扫描模块基于 iOS 原生提供的相册查询的 API,将用户相册的数据与本地数据库中存储的照片数据举行对比,提取出新增照片数据和用户已经删除的照片。

3.1.3 相册索引服务模块

相册索引服务模块,是基于 S2 算法的相册服务的核心模块。模块功能如下:

  • 直接与数据模块交互,向利用者屏蔽数据层的数据操纵细节,提供满意查询、搜索等需求的 API
  • 查询指定 Cell ID 下的照片资源
  • 查询指定 Level 下,相册照片索引后的 Cell ID
  • 查询以指定坐标点为圆心、指定半径范围内的照片
  • 与用户相册扫描模块交互,获取新增照片和已经删除照片的数据,更新数据库内容,同时支持查询和关照更新状态

3.1.4 相册地点分类盘算模块

相册地点分类盘算模块是盘算用户相册的地点分类效果的核心模块。该模块的主体功能如下:

  • 获取 S2 相册索引服务中的照片 Cell ID,作为参数上传至服务端,服务端根据舆图服务提供的聚合接口,将 Cell ID 的聚合效果返回给服务端
  • 综合考量准确度和 Cell ID 的数据量,选取 Level12 的 Cell ID 作为哀求服务端的 Cell ID 品级
  • 调用相册索引服务模块根据指定 Level 获取 Cell ID 的方法得到去重后的 Cell ID
  • 服务端返回的数据结构是 mdd_id(目标地 ID) 与 Cell ID 的一对多的映射关系
  • 利用本地 S2 相册索引服务中的照片 Cell ID,根据上一步服务端返回的分类数据举行分类
  • 缓存每次地点分类的盘算效果

3.2 团体流程

基于Google-S2的地理相册服务实现及应用_7*24快讯_2020-2-14 16:17发布_配资查_www.peizicha.com

相册索引服务模块会在 App 启动时更新服务,将本地数据与相册数据同步。当用户触发地点相册功能时,相册地点分类盘算模块会先取出缓存在本地相册地点分类盘算效果显现给用户,同时驱动相册索引服务更新。

在收到更新服务更新完毕的关照后,起首向相册哀求 12Level 的全量去重的 Cell ID,然后将 Cell ID 上传服务端由服务端盘算分类,末告终合相册索引服务的全量照片数据,盘算照片的地点分类效果,缓存效果并渲染显现给用户。

3.3 性能优化

3.3.1 获取相册增量照片

相册索引服务模块须要同步服务和用户相册的照片资源数据,找到新增数据,到场到服务数据库中。最初计划的获取新增数据方案如下:

Step.1 获取全量的用户相册的数据

Step.2 遍历用户照片,查询是否存在本地服务数据库中

但是这个方案应用到照片量较大的手机上时,获取新增照片的时延很高。排查后我们发现缘故起因在于全量遍历用户相册时延很高,同时在遍历中频仍查询数据库也比力耗时。颠末调研发现,iOS 的用户相册有「迩来项目」的相册分类,该相册分类下的资源只按照添加序次的倒序分列,即越新的照片越靠前。故将方案优化如下:

Step.1:从列表头部截取 100 条

Step.2:将该 100 条追加为新增照片

Step.3:判定该 100 条中的末了一条,即新增时间最晚的一条,查询是否存在于服务数据库中

  • 若不存在,继续 Step.1
  • 若存在,制止截取,从而得到新增照片

3.3.2 渐进盘算相册照片的地点分类

相册地点分类盘算模块在得到服务端返回的分类效果(mdd_id 与 Cell ID 列表的映射关系)后,根据效果对本地服务数据库中的照片举行分类。最初的方案如下:

Step.1:遍历效果列表,得到每个 mdd_id 映射的 Cell ID 列表

  • A. 遍历 Cell ID 列表,通过 Cell ID 向相册索引服务模块查询属于该 Cell ID 索引下的照片资源,从而得到该 mdd_id 对应的照片资源
  • B. 对该目标地下的照片按照创建时间倒序排序

Step.2:将全部目标地维度照片分类效果,按照每个效果会合照片最晚创建时间,即第一个照片的创建时间,举行倒序排序,得到按照地点维度和建时间维度排序的地点相册的终极盘算效果。

如许的方案导致在地点相册初次盘算的时间,用户须要等待全部目标地下的效果盘算完毕后才华显现给用户,同时须要多次按照创建时间排序,导致时延很高,冷启动下用户体验很差。

为此,我们做出了方案优化,淘汰排序次数,同时通过渐进加载的方式优化用户体验。告急思绪是相册索引服务模块的数据库中,存储照片的创建时间可以通过 SQL 查询,按照创建时间倒序分列的全部照片资源,获取倒序分列的照片资源聚集:

Step.1T媚课从照片资源聚集头部取 1000 条照片

  • 遍历每一张照片,根据照片的 Cell ID,从 mdd_id-Cell ID 映射表中查询所属的目标地, 判定照片目标地分类效果会合是否存在该目标地的照片资源分类聚集
  • 存在,追加该照片
  • 创建该目标地的效果集,追加到照片目标地分类效果会合,并追加该照片

Step.2:将该 1000 张照片的分类效果渲染显现给用户

Step.3:盘算完全部照片的分类,关照竣事渲染,盘算完毕。

以上方案,将全量的本地照片资源以 1000 张为一批次,举行渐进盘算,同时渐进渲染,紧缩了用户的等待时间;同时,依托关系型数据库的排序本事,淘汰排序次数,优化了性能。

Part.4未来规划和总结

现在,本文先容的基于 Google-S2 算法实现的地点相册在马蜂窝 APP iOS 客户端已经上线一段时间,而且为条记发布量带来了正向增长。但是这套方案在数据库数据处置处罚中已经对于 Google-S2 算法的利用上仍然有很大的优化和探索空间,后续我们团队也会对其不停优化和深挖。

Google-S2 算法服务在马蜂窝 App iOS 客户端中的实现和落地,结果不但仅是满意了条记发布场景的探索,更使得客户端具备了对于用户相册照片百米级准确度的索引和搜索的本事,可以为后续更多、更复杂的业务场景服务,信赖在不远的未来能为用户提供更便捷、更风趣的观光纪录产物。


本文来自配资查|www.peizicha.com 自网络收集整理。
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!

鲜花

握手

雷人

路过

鸡蛋
温馨提示:以上内容仅为信息传播之需要,不做任何投资建议,如有侵犯版权,请联系配资查门户 客服人员进行删除处理,谢谢! 配资查股票配资门户网是国内专业的股票配资门户网,是炒股配资和配资交流的首选之站 - www.peizicha.com
我有话说......