面向分布式列式存储的轨迹大数据k近邻查询.docx资源-CSDN文库

版权申诉

191 浏览量 2022-11-30 09:27:08 上传评论收藏 464KB DOCX 举报

资源推荐

资源详情

资源评论

随着导航定位技术的进步、移动互联网的发展和智能终端的普及，人们能够愈加方便

地获取并记录关于人、车、动物与自然现象（如台风、雨云）等移动对象的轨迹数据

[1]

。

目前，交通行业（如优步、滴滴出行等）和开放街道地图（OpenStreetMap，OSM）等众

源门户已经汇聚了大量轨迹数据，且其规模与日俱增，已形成轨迹大数据。海量的轨迹数

据为人们理解自然和社会的变化规律提供了前所未有的信息，促进了基于位置的社交网

络、智能交通系统和城市计算的发展

[2]

。轨迹大数据携带的时空信息也催生了许多基于轨

迹的应用，如传染病潜在接触人员追溯

[3]

、个性化路线推荐

[4]

、路网生成与更新等。

在上述应用中，人们通常希望查询在某一时间范围内经过指定地点附近的轨迹。例

如，在传染病潜在接触人员追溯中，需要查询近期经过疫情暴发地附近的人员或车辆轨

迹，更进一步地，可能需要查询与这些人员或车辆轨迹存在时空相关性的轨迹，以追溯潜

在的接触人员；当游客前往陌生景点时，希望查询最近经过该景点附近的轨迹，将其路线

作为下一步的出行参考

[5]

；在利用轨迹生成或更新局部路网时，需要获取最近一段时间内

经过相应范围的轨迹。显然，上述应用需要根据地理空间位置从大规模轨迹数据集中高效

查询出带有时间约束的最近邻轨迹。因此，本文面向轨迹大数据，利用分布式存储技术研

究具有一定时间约束的点-轨迹 k 近邻（point to trajectory k nearest neighbor，

P2T_kNN）查询处理问题。

目前，已有学者对 P2T_kNN 查询处理进行了研究。文献[6-7]使用 R 树或全局堆

[7]

等

数据结构设计了高效的 P2T_kNN 查询算法。然而，这些研究只关注轨迹的空间语义，难

以满足带时间约束的 P2T_kNN 查询需求。更重要的是，这些方法侧重于算法设计，仅适

用于集中式存储方案。为满足大规模时空数据的存储及查询需求，越来越多的研究试图在

非关系型数据库（not only SQL，NoSQL）

[8]

上建立时空数据引擎，充分利用其非固化模

式与分布式存储来实现时空数据的高效存储与查询

[9]

。MD-HBase

[10-11]

和 G-HBase

[12]

借助

Z 阶曲线在 HBase

[13]

之上建立了高效的空间索引，支持空间点数据的快速 k 近邻查询，但

是对时间语义的支持不足。GeoMesa

[14-15]

和 GeoWave

[16-17]

利用空间填充曲线

[18]

（space-

filling curve，SFC）对高维时空数据进行降维处理，从而建立了面向分布式键值存储的统

一时空引擎，支持时空点数据的快速 k 近邻查询，但其对时间约束的处理仍不够灵活。此

外，这些时空数据引擎仅支持传统的点-点 k 近邻查询处理，难以直接应用于 P2T_kNN 查

询。THBase

[19]

基于 HBase 的协处理机制，提供了轨迹数据的存储及 P2T_kNN 查询处理

方案，但是并没有考虑轨迹数据的空间分异性给查询带来的不利影响，数据稀疏区域的查

询性能较低。综上所述，本文工作与现有工作的异同见表 1。

表 1 近邻查询相关工作比较

Table 1. Comparison Between Related Works on Nearest Neighbor Query

统计项

输入

输出

扩展性

时空支持

平台

P2T_

时间约束、空间点

Top-

近邻轨迹

可扩展

时空

NoSQL

文献[7-8]

空间点

Top-

近邻轨迹

不可扩展

空间

单机

MD-HBase

[10-11]

、G-HBase

[12]

空间点

Top-

近邻点

可扩展

空间

NoSQL

GeoMesa

[14-15]

、GeoWave

[16-17]

时间范围、空间点

Top-

近邻点

可扩展

时空

NoSQL

定义 4 点-轨迹 k 近邻（P2T_kNN）查询：给定时间约束集合 W，空间点 p，近邻数

k，待查询轨迹集合 S

，P2T_kNN 查询是从 S

中检索出一个有序集合 Q

，满足如下条

件：

1）card (Q

) = k；

2）∀ T ∈ Q

，均有 T ∈ S

；

3）∀ T

∈ Q

，设 p = (x

，y

，t

) ∈ T

，且是使 T

成为第 i 条近邻轨迹的轨迹点，那

么 Ǝ W

∈ W，使得 t

∈ W

；

4）设 T

和 T

分别是 Q

的第 i 条和第 j 条轨迹，如果 1 ≤ i < j ≤ k，那么 D (p，T

)

≤ D (p，T

)；

5）∀ T

∈ S

，T

∉ Q

，T

∈ Q

，均有 D (p，T

)> D (p，T

)。

在上述 P2T_kNN 查询问题的定义中，条件 3）保证满足时间约束条件，条件 4）说

明 Q

是按点-轨迹距离排序的集合，而条件 5）指出距离查询点 p 最近的 k 条轨迹一定在

输出结果之中。需要说明的是，时间约束集合 W 可以包含任意数量的时间区间，这对轨迹

数据的周期性对比分析具有重要意义，如查询过去 1 个月每天同一小时内前 k 条近邻轨迹

的分布和移动信息，用于挖掘蕴含其中的规律或异常。

2. P2T_kNN 查询框架

BigTable 是第一个面向列的存储模型，采用了基于内存表和 SSTable 的存储技术

[21]

。与模式固化的关系型数据库相比，列式存储具有自由模式表达和分布式组织等特征，

支持海量存储、高并发访问和弹性扩展。因此，本文基于分布式列式存储技术设计了面向

P2T_kNN 查询的处理框架，如图 1 所示。在轨迹数据组织方面，数据表以轨迹标识符为

行键来存储整条轨迹，而索引表以时空剖分形成的单元编码为行键来存储落入对应时空范

围内的轨迹片段；在近邻查询处理方面，首先基于空间的递归剖分机制确定搜索空间单元

的起点和步长，然后依据时空编码从索引表检索出候选的轨迹片段，最后进行过滤和排序

处理，以得到满足查询条件的轨迹标识符，据此从数据表中获取完整的 k 条近邻轨迹。

剩余14页未读，继续阅读

评论收藏

内容反馈

版权申诉

罗伯特之技术屋

粉丝: 4047
资源: 1万+

面向分布式列式存储的轨迹大数据k近邻查询.docx

附件4：大数据业务开户指引.docx

审计数据分析培训有感数据分析技术与大数据审计培训心得.docx

产品经理在线教育大数据营销平台实战(一)：大数据平台构建实战.docx

打造“智慧名城”,重庆住建系统实施大数据智能化战略.docx

教育大数据整体解决方案.docx

科技成果——小型水库大坝安全智慧感知一体化装备及大数据服务云平台.docx

大数据技术之spark.docx

大数据技术之Scala.docx

大数据平台项目方案.docx

探析分布式数据库技术运用在大数据中的策略.docx

大数据技术之Phoenix.docx

大数据应用案例分析.docx

大数据治理系列教材.docx

大数据技术与应用.docx

大数据区块链项目介绍.docx

大数据工程师简历模板.docx

云计算大数据平台运维方案.docx

基于分布式技术的银行大数据架构方案.docx

相关实用应用程序（Windows可用）

李飞飞自传 我看见的世界 The World I see

ChatGPT使用总结：150个ChatGPT提示词模板（完整版）

chromedriver-win64.zip

全国计算机二级WPSoffice精选350道选择题题库（含答案）.pdf

哈尔滨工业大学-ChatGPT调研报告-2023.3.6-94页.pdf

智联招聘：2024年大学生就业力调研报告.pdf

4个亲测好用的ChatGPT4渠道

AI大模型-基于深度学习的神经网络模型语言模型图像识别自然语言处理

学术海报模板+论文科研+研究生

北森能力测评题库.zip

最新资源

李飞飞自传我看见的世界 The World I see