英语原文共 9 页，剩余内容已隐藏，支付完成后下载完整资料
Hbase中的时空查询
摘要：地球科学让我们了解我们的环境，并有益于我们生活的许多方面。如今，大型传感器被部署用来感测环境的各种参数，现在已收集了数百亿甚至数万亿的感测数据，而这些数据需要进行分析以进行监视或其他目的。从许多角度来看，用户总是根据特定的空间和时间谓词发出查询。对于这些应用程序，关系数据库被大规模和高速率的数据插入所淹没，并且NoSQL数据库被认为是可行的解决方案。HBase是一种流行的键值存储系统，能够解决存储问题，但是无法提供内置的时空查询功能。
以前的许多工作都是通过设计架构来解决该问题的，即为HBase设计行键和列键的格式，我们认为这不是有效的解决方案。在本文中，我们从HBase的本质层面解决了这个问题，并提出了索引结构作为HBase的内置组件。STEHIX（Spatio-TEmporal Hbase IndeX）适用于HBase的两级体系结构，适用于HBase处理时空查询。它由索引中的用于索引HBase区域内部结构的元表（第一级）和区域索引（第二级）。在此结构的基础上，通过提出算法分别解决了两个常见查询，范围查询和kNN查询。为了实现负载平衡和可扩展的kNN查询，还提出了两种优化方法。我们实现了STEHIX并在真实数据集上进行了实验，结果表明我们的设计在许多方面都优于先前的工作。
关键词：时空查询；HBase；范围查询；kNN查询；负载均衡
1 引言
随着地球科学的发展，尤其是在全球定位系统（GPS）和遥感（RS）中，时空数据的累积量已累积到TB，甚至PB或EB。在存储时空数据之后，用户总是有通过特定的时空谓词查询数据的请求，这需要有效的存储和检索功能。传统的数据库管理系统（DBMS）具有数据组织的优势，并配备了多维索引结构。但是，在处理大量数据时，它们无法进行高速率插入和实时查询。另一方面，键值存储系统HBase [1]可以有效地支持大规模数据操作，但本身不支持多属性索引，这限制了丰富的查询应用程序。
- 动机
我们的动机是使HBase适应有效地处理时空查询。尽管先前的一些工作在HBase上提出了分布式索引，但是这些工作仅考虑了空间维度，更关键的是，这些工作中的大多数只涉及如何设计空间数据的模式，除了从一个方面解决HBase的本质问题外，其他问题都没有解决。MD-HBase [2]旨在将索引结构添加到元表中，但是它不提供索引以有效地检索HBase区域的内部数据。我们的解决方案STEHIX（Spatio-TEmporal Hbase IndeX）基于两级查找机制构建，该机制基于HBase的检索机制。首先，我们使用希尔伯特曲线对地理位置进行线性化处理，并将转换后的一维数据存储在元表中，然后针对每个区域，建立索引HBase中StoreFiles的区域索引地区。在本文中，我们专注于针对这种环境的范围查询和kNN查询。
- 贡献
我们解决了如何有效地解释HBase中时空数据的范围和k个最近邻（kNN）查询。我们的解决方案称为STEHIX（Spatio-TEmporal Hbase IndeX），它充分考虑了HBase的内部结构。先前的工作着重于基于传统索引（例如R树，B树）构建索引，而我们的方法基于HBase本身构建索引，因此，索引结构更适合HBase检索。换句话说，STEHIX不仅考虑空间维度，还考虑时间维度，这更符合用户需求。
我们使用希尔伯特曲线将空间划分为初始分辨率，其编码值在元表中用于索引HBase区域，然后使用四叉树划分希尔伯特单元作为更高分辨率，在此基础上，设计区域每个区域的索引结构，其中包含用于索引空间维的更精细的编码值和用于索引时间维的时间段。然后，我们展示了这种二级索引结构，元表 区域索引，它更适合HBase在实验中处理查询。基于我们的索引结构，设计了范围查询和kNN查询的算法，并提出了负载均衡策略和对kNN查询的优化，以提高STEHIX性能。我们比较带有基于真实数据集的MD-HBase的STEHIX，结果表明我们的设计理念使STEHIX优于同类产品。总而言之，我们做出了以下贡献：
- 我们提出了STEHIX结构，该结构完全遵循HBase的内部机制，是在HBase平台上为时空数据建立索引的新尝试。
- 我们提出了用于在HBase中处理范围和kNN查询的高效算法。
- 我们进行了全面的实验，以验证STEHIX的效率和可伸缩性。
本文的其余部分安排如下。第2节回顾了相关作品。第3节正式定义了问题和前提条件。 第4节介绍STEHIX结构。在第5节中，介绍了范围和kNN查询的算法。第6节向索引报告了优化。我们在第7节中对STEHIX进行了实验评估。最后，第8节对本文进行了总结，并提供了未来工作的方向。
2 相关作品
作为大规模数据处理的一种被广泛使用的替代方法，云存储系统当前采用类似哈希的方法来检索仅支持基于关键字的简单查询，但缺乏各种形式的信息搜索的数据。对于数据处理操作，开发了几种云数据管理（CDM），例如HBase。作为NoSQL数据库，HBase能够处理大规模存储和高插入率，但是，它没有为HBase提供太多支持丰富的索引功能。许多作品都围绕这一点提出了各种方法。
Nishimura等人[2]通过提出MD-HBase解决了PaaS的多维查询。它使用k-d树和四叉树来划分空间，并采用Z曲线将多维数据转换为一维，并支持多维范围和最近邻查询，这充分利用了HBase上分层的多维索引结构。 但是，MD-HBase在元表中建立索引，该索引不对区域的内部结构建立索引，因此执行扫描操作来查找结果，效率因此而降低。
Hsu等人的文献[3]提出了一种新的基于R 树的密钥表述方案，称为KR 树，并在此基础上，设计了kNN查询和范围查询的空间查询算法。此外，提出的密钥制定方案在HBase和Cassandra上实现。通过对真实空间数据的实验，它证明了KR 树优于MD-HBase。KR 树能够平衡假阳性和子查询的数量，从而大大提高范围查询和kNN查询的效率。这项工作根据在HBase和Cassandra上进行的实验中发现的功能来设计索引。但是，它仍然没有考虑HBase的内部结构。
周等人[3]提出了一种高效的分布式多维索引（EDMI），它包含两层：全局层采用kd-tree将空间划分为许多子空间，而在本地层中，每个子空间都与Z序前缀R-tree关联 （ZPR树）。 与其他压缩R树和R lowast;树相比，ZPR树可以避免MBR重叠，并获得更好的查询性能。本文实验基于HBase评估EDMI的点，范围和kNN查询，从而验证其优越性。与MD HBase相比，EDMI在底层使用ZPR树，而MD HBase使用扫描操作，因此EDMI提供了更好的性能。
韩等人[5]提出了用于HBase的HGrid数据模型。HGrid数据模型基于混合索引结构，结合了四叉树和常规网格作为主索引和辅助索引，支持范围和kNN查询的高效性能。本文还就如何为HBase中的地理空间应用程序组织数据制定了一套准则。就查询响应时间而言，该模型并不比其所有竞争对手都要好。但是，它需要的空间比相应的四叉树索引和常规网格索引要少。
HBaseSpatial是由张等人提出的基于HBase的可伸缩空间数据存储[6]。实验结果表明， 与MongoDB和MySQL相比，它可以有效提高大空间数据的查询效率，为存储提供良好的解决方案。 但是该模型无法与其他分布式索引方法进行比较。
我们上面提到的所有先前的工作都只考虑了空间查询。对于移动的对象，某些类型的地理空间应用程序需要高更新率，并且需要对多个属性（例如时间段和任意空间维度）进行高效的实时查询。杜等人[7]提出了一种基于HBase的混合索引结构，使用R-tree索引空间，并应用Hilbert曲线遍历逼近空间。它支持高效的多维范围查询和kNN查询，尤其是与MD-HBase和KR -tree相比，它善于歪曲数据。由于这项工作专注于移动对象，它与我们的目标有所不同，并且也没有考虑HBase的内部结构。
3 问题定义和前提条件
在本节中，我们首先正式描述时空数据，然后介绍HBase存储的结构。为简单起见，本文仅考虑二维空间，但是，我们的方法可以直接扩展到更高的二维空间。
时空数据的记录r可以表示为lt;x，y，t，Agt;，其中（x，y）表示记录的地理位置，t表示生成数据的有效时间，A表示其他属性 ，例如用户ID，对象的形状，描述等。
我们在HBase [8] [9]中给出了存储结构和索引的描述，为简单起见，省略了一些无关的组件，例如HLog和版本。通常，HBase群集由至少一个称为“主服务器”的管理服务器以及其他几个保存有数据的服务器组成，这些服务器被称为区域服务器。
从逻辑上讲，HBase中的表类似于网格，在网格中可以通过给定的行标识符和列标识符来定位单元。行标识符由行键（rk）实现，列标识符由列族（cf） 列限定符（cq）表示，其中列族由多个列限定符组成。单元格中的值可以称为格式（rk，cf：cq）。表一显示了逻辑HBase中的表的视图。例如，值v1可以称为（rk1，cf1：cq1）。
在物理上，HBase中的表沿行水平划分为几个区域，每个区域都由一个区域服务器维护。执行读取或写入操作时，客户端直接与相应的区域服务器进行交互。当数据正式形式为lt;rk，cf：cq，valuegt;（我们在本文的其余部分中使用术语键值数据）写入区域时，区域服务器首先将数据保存在称为记忆库的列表式内存结构中，其中每个条目都预先配置了相同的固定大小（通常为64KB），并且一定数量的条目的大小等于基础存储块的大小系统，例如HDFS。当记忆库的大小超过预先配置的数量时，整个记忆库会作为存储文件写入基础系统，其结构类似于记忆库。此外，当存储文件的数量超过一定数量时，区域服务器将执行压缩操作以将存储文件合并到一个新的大文件中。 HBase提供了两级查找机制来查找与密钥（rk，cf：cq）相对应的值。目录表meta存储关系{[表名]：[开始行键]：[区域ID]：[区域服务器]}，因此，给定行键，可以找到对应的区域服务器，然后区域服务器搜索值根据给定的密钥（rk，cf：cq）在本地。图1显示了HBase两级查找结构的示例。
从上面的描述中，我们可以看到HBase仅提供基于元表的简单层次结构索引结构，并且相应的区域服务器必须执行扫描工作以细化结果，这对于处理时空查询是无效的。
4 STEHIX结构
在本节中，我们介绍了索引STEHIX（Spatio-TEmporal Hbase IndeX）的结构 在索引设计期间会考虑以下原则：1）对于应用程序，用户不必专门设计查询时空数据的架构，即我们的索引不应对架构设计添加任何限制，而应添加与之相关的内部结构 HBase，2）索引应尽可能符合HBase的体系结构，3）索引应适应数据分布。
对于设计规则1），我们不在乎架构设计，而是将每个记录一般化为存储文件（MemStore）中的键值数据，形式为（rk，cf：cq，r），其中r = lt;x，y ，t，Agt;。
对于设计规则2），我们的索引基于两级查找机制。我们特别使用了希尔伯特曲线将地理位置线性化，并将转换后的一维数据存储在元表中，并且对于每个区域，我们建立区域索引来索引存储文件。 图2显示了STEHIX体系结构的概述。
- 元表组织
我们使用希尔伯特曲线将整个空间划分为初始粒度。 根据HBase的设计原理，行密钥的前缀应不同，以便可以在区域服务器上分配插入数据的开销。 并且这种设计能够满足该需求。
希尔伯特曲线是一种将多维空间映射为一维空间的空间填充曲线。特别是将整个空间划分为大小相等的单元格，然后就某个序列而言，一条曲线仅在每个单元格中通过一次，以便为每个单元格分配一个序列号。不同的空间填充通过不同的测序方法区分曲线。由于转换过程中的信息丢失，因此通过标准（局部性保留）评估了不同的空间填充曲线，这意味着从原始空间到一维空间，邻近度有多少变化。希尔伯特曲线被证明是最佳的局部保留空间填充曲线[10]。使用希尔伯特曲线，原始空间中的任何对象都将转换为[0，22lambda;-1]空间，其中lambda;称为希尔伯特曲线的阶数。图3显示了二维空间中的四个希尔伯特曲线，其中lambda;= 1、2、3和4。
我们描述了希尔伯特曲线的三个函数，第一个是将原始空间中的点映射到一维空间中的值，第二个是将范围窗口映射到一系列间隔，第三个是获取点的邻近单元格。具体而言，对于阶数为lambda;的希尔伯特曲线，
- coorToCell（p）。给定n维空间S中的点p =（x1，x2，...，xn），coorToCell（p）返回一个单元格编号（介于0和22lambda;-1之间），引用其中p位于S内的单元格。
- rectToIntervals（R）。 给定在n维空间S中的范围窗口R =（xl1，xl2，...，xln，xu1，xu2，...，xun），其中xli和xui（1le;ile;n）是下限和上限，分别是第i维的边界，rectToIntervals（R）返回一系列间隔，这些间隔表示在S中与R相交的单元。
- getNeighborCells（p）。给定n维空间S中的点p =（x1，x2，...，xn），getNeighborCells（p）返回一个单元格列表，该列表引用作为单元格coorToCell（p）邻居的单元格。
例如，在图3（b）
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[238921]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
