基于位置变换的分布式空间查询处理

可在www.sciencedirect.com在线获取ScienceDirectFutureComputing and Informatics Journal 3（2018）296e303http://www.journals.elsevier.com/future-computing-and-informatics-journal/基于位置变换的分布式空间查询处理M. Priyaa，*，R.卡尔帕纳ba印度卡拉伊卡尔Bharathiyar工程技术学院计算机科学系b印度Puducherry本地治里工程学院计算机科学系接收日期：2017年11月18日;修订日期：2018年3月16日;接受日期：2018年9月19日在线发售2018年摘要基于位置的服务是通过互联网在智能手机上提供的流行的地理敏感现在这些系统找到了自己的增强，因为他们正在使用设备它允许用户根据自己当前的位置得到查询的响应，而位置则成为用户最基本的上下文。例如，这些服务用于检查餐馆，咖啡店，以从最近的商店获得商业奖励或跟踪人的位置。智能手机的用户在使用这些服务时需要克服某些限制要处理的数据集大小和内存大小在本文中，一个新的分布式索引结构的基础上的优势点变换技术，以提高查询空间以及数据空间的查询结果。该技术的任务是在查询处理中对并行分析算法的执行产生更好的改进。这种方法不仅提高了系统的效率，而且减少了误报和漏报的数量Copyright © 2018埃及未来大学计算机与信息技术学院由爱思唯尔公司制作和主持这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。关键词：优势点;条带索引结构;框查询;基于位置的查询; Minkowski距离1. 介绍在互联网时代，手持计算设备（如PDA、笔记本电脑和智能手机）的简易技术使他们能够访问基于位置的服务。基于位置的服务是指利用智能手机的地理信息来提供用户所需的重要信息的服务大多数的商业服务，如检查在客栈，基于邻近的营销，获得旅游信息，即，可以通过移动设备访问。设备的位置或定位在文档检索中起着至关重要的作用可以使用GPS接收器接收位置信息。从* 通讯作者。电子邮件地址：shyamnithy@gmail.com（M. Priya），rkalpana@pec.edu（R.Kalpana）。同行审查，由埃及未来大学计算机和信息技术系负责。从用户的角度来看，用户可以使用位置信息来检索关于位置的文档，检索与位置（x，y）相关的文档，以及检索与位置相关的数据。必须解决基于位置的GIS静态空间数据访问的空间技术和空间方法学的应用为位置使能服务提供了基础。GIS工具允许位置服务访问空间数据库或地理数据库，以分析和可视化数据。基本的基于位置的查询可以被分类为点查询、2维（2D）范围查询和增量2D查询。点查询用于给出关于坐标（x，y）的信息.由于其使用较少，大多数情况下，点查询被修改为2D范围查询。二维范围查询最适合用户静止的情况。增量式2D查询非常适合用户在运动时使用。基于位置的索引方案在处理2D范围和增量索引中起着先决条件的作用。https://doi.org/10.1016/j.fcij.2018.09.0022314-7288/Copyright © 2018埃及未来大学计算机与信息技术学院。Elsevier B. V.制作和托管这是CC BY-NC-ND许可证下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。M. 普里亚河Kalpana/Future Computing and Informatics Journal 3（2018）296e 303297图1.一、面向空间查询处理的索引结构分类查询.此外，增量查询承受的空间关系，而不是超越索引，但对象之间。定位使能设备在处理查询时具有一定的限制。第一个限制与数据库的大小有关。最近数据集大小的爆炸，在记录和属性的数量方面，导致数据库增加其指定为大数据库或大型数据库的大小。第二个限制指向启用位置的设备的内存大小。这些设备使用基于磁盘的页面访问机制来克服这一限制。为了提高范围查询的处理速度，优化这些设备的页面访问，引入了一种并行处理算法。在本文中，提出了一种新的方案，并行和分布式处理的查询。首先将给定的范围查询转换为矩形查询。然后将查询的矩形邻近度划分为相等的条带，以便通过实现并行分析算法以并行和分布式的方式处理它们。第2节介绍了现有系统的文献和第3节通知所提出的模型的基础上的优势点近似变换技术。第4节用实时系统说明了所提出的模型。第5节是工作模型结论。2. 相关工作移动对象的空间查询处理分为快照查询和连续查询两类。快照查询是查询基于当前位置和时间返回结果的查询。连续查询[11，15]是使用增量算法的查询，其中查询结果基于移动对象的位置。这些查询执行范围搜索或最近邻搜索来检索对象。图1讨论了用于解析空间查询的不同索引结构支持。R树是最适合于空间查询的索引结构，但其性能随维数的增加而降低。一个有效的索引结构，如X树，VA文件，A树提供了更好的性能比R树派生高维数据。多维索引结构中的数据对象之间的相关性较差，不能被R索引有效地处理。空间索引结构不适用于分层数据划分，因为很少的分区是不平等的Naresh等人[5]讨论了一种空间查询的空中索引方法，该方法使用网格来存储和处理数据对象，并设计了一种新的算法来处理无线环境中的快照该指标的主要目标是降低IO成本和通信成本，但遗憾的是，它留下了某些因素对结果更新。快照时空增量索引算法[7]提供了空间和时间查询处理的改进数据库在数据库规模方面的最新改进坚持通过分布式和并行处理来处理查询的方法。在MapReduce[14]编程框架上处理的VegaGiStore[10]基于两层的分布式空间索引[12，13]用于处理全局索引的四叉树索引和局部索引的空间填充曲线的并行性。SpatialHadoop[2]是Hadoop的一个扩展版本，它能够在大规模数据上充分处理空间查询。它增加了一种叫做鸽子的空间语言空间索引和空间操作，如范围查询、空间连接和一套计算几何操作。分布式Voronoi索引[1]用于以并行方式处理地理空间查询。使用MapReduce模型298M. 普里亚河Kalpana/Future Computing and Informatics Journal 3（2018）296e 303图二、解决基于位置的查询处理的体系结构.X¼¼¼以指定范围查询、最近邻查询和反向最近邻查询。与基于MapReduce的R树索引相比，基于Voronoi的索引在2D空间中产生适当的查询响应时间。原型EGIS（工程地理信息系统）[4，6]使用GPS技术对3D空间的空间信息技术进行实时监控。动态索引方案[8，9]启动基于图的方法来回答最新快照的查询。它基于精确方法和近似方法协调查询。精确方法归纳方案用于解决不包含错误的查询。近似方法用于解析包含错误的查询。提出了基于地理哈希的索引[3]来访问空间数据对象。Geo hash是从经纬度对中提取交织比特，并将其作为GIS中空间对象的索引。它提高了空间数据查询处理的性能。3. 分布式模型为了检索在距当前位置L的特定范围内的空间对象，必须计算每个对象O距当前位置L的距离。主要问题是在欧氏空间中计算距离的成本是昂贵的。为了减少计算成本，在构造索引结构之前将距离值转换为简单值。地理坐标系中的每个空间对象O被表示为一对属性（经度、纬度）。设SD为空间数据库，数据库中包含O个对象.每个对象OV SD沿着n维空间具有n个特征值{f1，f2，它可以表示为n维空间Rn中的一点设d为度量空间数据库中两点之间的相异性的距离函数，表示为d：Rn× Rn/ RnMinkowski距离d（x，y）是用于在法向量空间中测量两点x和y之间的距离的类型，图 2描述了解决空间范围查询的一般架构。例如，用户给出的基于快照位置的查询是“查找5公里范围内的酒店列表”。基于位置的查询也可以附加到LP¼ni¼1jxi-yijp ！1=p与关键字一样“查找5公里内的AC设施的酒店列表”。通过与用户的移动设备附接的GPS跟踪器来识别用户的当前位置通过从数据库构造索引结构来解决给定的范围查询。然后通过索引结构进行搜索以检索文档。p表示Minkowski参数。LP空间中的查询可以基于参数值p1，2，3改变其形状，-. ∞每个形状都由原点O和半径作为单位向量组成。如果p2，则范围查询具有圆形形状，称为欧几里得空间或L2空间.如果p ∞，则范围查询具有正方形形状。M. 普里亚河Kalpana/Future Computing and Informatics Journal 3（2018）296e 303299图三. Vantage point transformation.ð Þ ðÞ¼A) 度量空间其基本思想是将原始数据库中的每个数据点转换为基于预先计算的全局点的点，该全局点称为有利点（V），如图所示。 3.设d是对象O到当前位置L的距离。在欧几里德空间中具有距离d的SD中的每个对象点O以距有利点V的距离d '进行变换度量变换函数定义为：MO;d0MO;d0**yf：SD/SD0有利点的选择和所选有利点的数量是问题所在。可以基于原始空间中的数据的纬度和经度值来选择有利点。选择有利位置的三种可能方法如图4所示。给定度量空间M（SD，d）和三个对象V，L，OV SD，距离d（V，O）被如下约束d V; L-d L; O≤d V; O≤d V;L d L; O如果距离d（V，O）小于范围半径，则检索空间对象，否则对象不合格。同时，在原始空间中的给定的基于位置的范围查询被转换为在转换后的空间中的最小包围盒查询，如图5所示。转换后的查询空间中存在所有对象在原始空间中沿着线45●相同地添加一些不在原始空间中的对象因此，基于点的变换支持几何变换和查询变换。现在，转换后的数据库由具有简单属性值的数据B) 关键字关联条带索引该模块主要包括关键字关联条索引的设计。在构建条带索引时，框空间中的感兴趣区域R被划分为非重叠条带，如图6所示。分区是分别沿x轴和y轴进行的。因此，分区的结果是两组条带：垂直条带和水平条带。在下文中，描述将基于垂直条带;水平条带的特性除了取向之外完全相同（参见图11）。 7）。见图4。选择有利位置。图五.查询的转换见图6。带索引。300M. 普里亚河Kalpana/Future Computing and Informatics Journal 3（2018）296e 303见图9。条带索引的算法。见图7。R树索引。分区策略使其易于在分布式系统中部署，并且单个条带可以在集群中的不同节点上维护。条带不重叠，从而可以并行执行查询处理。每个客户端可以处理一定数量的条带。由于每个条带中的对象数量都在给定的范围内，因此索引的容量与服务器的数量成正比，从而很好地适用于大规模数据处理。条带中的每个对象都与（距离，关键字）相关联。的由服务器将条带分配给客户机并合并从客户机在本地索引中，每个客户端从主机接收条带并构造如图7所示的R树索引。对于给定的查询q，该算法首先通过识别保证落在查询指定的范围内的条带来然后，它检查包含在这组条带中的对象。使用与对象相关联的距离为条带内的对象集合构造R树。通过比较每个数据对象之间的距离和范围值来修剪R树中的搜索空间如果距离小于范围值，则使用给定的查询关键字检查与对象相关联的关键字。如果找到匹配，则相应的对象是合格的。C) 提出的模型该模型由三个重要部分组成，如创建转换数据库，全局索引和局部索引。下面的图8描述了用于创建转换后的数据库的算法。图9所示的称为条带索引的全局索引应用相等分区技术。见图8。数据转换算法。M. 普里亚河Kalpana/Future Computing and Informatics Journal 3（2018）296e 303301图十一岁优势点对距离计算的影响图13岁查询半径与距离计算的影响图10. 分布式R树索引算法每个分区被称为条带，它由称为R树索引的本地索引处理，如图所示。 10.4. 实验评价实验是在一组机器上进行的。集群由一个主服务器和四个以上的客户端组成。每个客户端都有一个2.4 GHz的英特尔处理器和8 GB的RAM。关于酒店的合成数据集是从Data.Gov.Geoda1.8软件工具发布的七个真实数据集中收集的，该软件工具为获取特定位置的位置坐标提供了支持合成数据集由近10 000条记录组成实验是针对二维数据空间进行的A) 有利位置转换后的数据库的优势点的选择是一个重要的问题。取决于数据库的大小，选择的有利点的数量几乎相同。有利点数量的增加导致距离计算数量的减少，如图11所示。为了进行这个实验，数据库大小和查询半径是固定的。距离计算的数量是通过选择完全在范围之外、内部或角落的有利位置来测量的。B) 数据库大小在这组实验中，查询半径和有利点的数量保持不变，数据库的大小增加。查询半径固定为0.5。计算的数量随着数据库的大小适度地增加.此外，角点优势的选择需要更少的距离计算，如图11所示。 12个。C) 查询半径在这组实验中，有利点的数量和数据库大小是固定的。查询半径增大。的图12个。数据库大小对距离计算的影响302M. 普里亚河Kalpana/Future Computing and Informatics Journal 3（2018）296e 303图十七岁分布式R指标和R指标在误报方面的比较角点的距离计算数量比图2所示的内外点的距离计算要少。 13岁D) 索引的响应时间图14.比较响应时间。图15.分布式索引的响应时间图16. 精度在原始数据库中的R树索引的建设时间进行了比较，对一个分布式的R树与转换后的数据库的建设。结果进行了比较，在其时间复杂度。R树索引的时间复杂度是O（logMn），其中M是每个索引页中的条目数，n是节点数。在分布式索引结构中，响应时间取决于计算中涉及的客户端数量。X轴表示分布式环境中使用的客户端数量，Y轴表示查询的响应时间（以秒为单位），如图所示。14个。分布式索引支持全局索引并行求值的概念，将全局索引划分为多个分区，并借助R树以并行方式处理每个分区。查询的并行实现导致响应时间的减少当客户端的数量增加时，响应时间减少。同时，如图15所示，将分布式条带索引与原始数据库和经变换的数据库的响应时间进行比较。分布式条带索引与转换后的数据库相结合，具有使用简单的数学函数来检查对象是否落入范围内的优点。在图16中比较了针对给定范围查询检索的数据对象的数量。并对转换后的数据库的分布式R索引和原始数据库的R树索引进行了比较。X轴表示以km为单位的范围，Y轴表示查询返回的数据对象与R树索引相比，分布式树索引为用户视图产生更多的对象，因为分布式树索引实际上是执行基于优势点创建的框查询。M. 普里亚河Kalpana/Future Computing and Informatics Journal 3（2018）296e 303303同时，分布式R树比R树索引产生更多的误报，如图17所示。可以基于所选择的有利点的数量和数据对象的维度来限制误报的数量。5. 结论空间R树索引可以有效地处理基于位置的范围查询。必须优化查询的处理，以处理数据库中的大量记录。本文讨论了使用分布式R树索引的基于位置的查询，它支持以并行方式执行查询的概念。通过利用优势点技术将给定范围查询转换为数据空间中的盒查询，并将盒查询划分为相等的条带进行分布式处理，提高了并行性。查询的性能进行了比较，实验结果进行评估的响应时间和检索的数据对象的数量。实验结果表明，使用分布式R树索引的位置服务范围查询性能优于空间R树索引。引用[1] Akdogan Afsin ， Demiryurek Ugur ， Banaei-Kashani Farnoush ，Shaidian Cyrus.基于Voronoi图的地理空间查询处理。在：IEEE第二届云计算技术和科学会议（CloudCom）; 2010年。[2] Eldawy Ahmed，Mokbel Mohamed F. Spatial Hadoop：MapReduce框架 。 In ： Proceedings of the IEEE International Conference onDataEngineering，Seoul，South Korea; April，2015.[3] SuwardiIping Supriana，Dharma Dody，Satya Dicky Prima，LestariDessiPuji. 基于Geohashindex的企业空间数据模型在：电气工程和信息学国际会议（ICEEI）; 2015年。[4] 张健，陈晓玲。地理空间信息技术在碾压施工工程管理中的应用。在：IEEE地球科学和遥感国际会议专题讨论会，IGARSS; 2008年。[5] Naresh Koenni，Thangakumar J，Pannem Durga Mahesh.无线广播环境 下 的 空 间 查 询 监 控 。 互 联 网 计 算 和 信 息 通 信 国 际 会 议（ICICI）。Springer;2012.[6] 宣可峰，赵耿，塔尼亚尔大卫，Srinivasan 巴拉，萨法尔·梅瑟姆加夫里洛娃·玛丽娜基于网络Voronoi图的范围搜索。高级信息网络和应用国际会议。09. AINA;2009.[7] 林丽，蔡永忠，徐忠。基于快照增量的时空索引机制。在：先进的时空分析。伦敦：泰勒和弗朗西斯集团，2008年。[8] Hariharan Ramaswamy，Hore Bijit，Chen Li，Mehrotra Sharad.地理信息检索系统中空间关键字查询的处理.在：电气工程和信息学国际会议（ICEEI）; 2015年。[9] 秋叶拓哉岩田洋一吉田雄一在大型演化网络上通过修剪地标标记进行动态和历史最短路径距离查询。收录于：2014年第23届万维网国际会议论文集。[10] 钟云琴韩继忠张铁映李振华方锦云陈贵海面向大空间数据的并行空间查询处理。在：IEEE第26届并行和分布式处理研讨会研讨会&博士论坛（IPDPSW）国际会议; 2012年。[11] 奥斯本·温迪，欣兹·安妮卡.协作移动信息系统中基于位置的索引问题。2007.出版于Springer-Verlag，Berlin Heidelberg。[12] 于自强，刘洋。移动对象上K个最近邻查询的可扩展分布式处理。IEEE 2015;10.[13] 郑波，徐军，李伟春，李良.网格分区索引：无线定位服务中最近邻查询的混合方法。VLDBJ 2006;15（1）：21e 39.[14] Zhang C，Li F，Jestes J. Efficient parallel kNN joins for large datainMapReduce. 2012年第15届国际数据库技术扩展会议论文集。p.38和49。[15] 吴晓松，王晓松，王晓松.无线广播环境中空间查询的连续监视。IEEE跨移动计算，10月。2009;8（10）：1297e 311.