高效处理快照和连续反向k最近邻居查询外文翻译资料

 2022-12-25 14:20:17

英语原文共 26 页，剩余内容已隐藏，支付完成后下载完整资料

高效处理快照和连续反向k最近邻居查询

摘要：给定一组对象和一个查询q，点p称为q的反向k最近邻( RkNN )，如果q是p的k个最接近的对象之一。本文引入了影响区的概念，即影响区内的每一点都是q的RkNN，而影响区外的每一点都不是RkNN。影响区在基于位置的服务、营销和决策支持系统中有若干应用。它还可以用于高效地处理RkNN查询。首先，我们提出了计算影响区的有效算法。然后，基于影响区域，我们提出了有效的算法来处理RkNN查询，对于快照和连续RkNN查询，该算法明显优于现有的最著名的技术。本文还对RkNN算法的影响区域和IO代价进行了详细的理论分析。实验证明了理论分析的正确性。本文是我们先前工作的扩展版本( Cheema等)。《国际反歧视公约》议事录，第577 - 588页，2011年)。我们在这个扩展版本中做出了以下新的贡献: ( 1 )我们进行了严格的复杂度分析，并证明了我们在Cheema等中提出的算法之一的复杂度。( ICDE，第577 - 588页，2011 )可以从O ( m2 )减少到O ( km )，其中m gt; k是用于计算影响区的对象的数量，( 2 )我们表明我们的技术可以应用于维数高于2的维度，以及( 3 )我们提出了处理数据更新的有效技术。

关键字：反向最近邻；RNN空间查询；快照查询；连续查询

  1. 介绍

反向k最近邻( RkNN )查询[ 23，24，28，33，34，36，41，45 ]自引入[ 24 ]以来，一直受到极大的研究关注。RkNN查询查找查询点q是其k个最近邻居之一的每个数据点。因为q接近于这样的数据点，所以q据说对这些点具有高影响。因此，作为查询的RkNNs的一组点称为其影响集[ 24 ]。以加油站为例, 这个加油站(是最近的加油站之一)的司机是其潜在客户。在本文中，提供设施或服务的对象（例如加油站）被称为设施，使用该设施的对象（例如驾驶员）称为用户。给定设施q的影响集合是由q为其k个最近设施之一的每个用户组成的集合。

在本文中，我们首先介绍一个更通用的概念，称为影响区，然后，我们表明影响区可以用来有效计算影响集（即RkNNs）。考虑一组设施F = {f1，f2，...，fn}其中fi表示欧几里德空间中的一个点，并表示第i个设施的位置。 给定一个查询qisin;F，影响区域Zk是这样一个区域，使得对于每个点pisin;Zk，q是其k个最近设施之一，并且对于每个点prsquo;不属于 Zk，q不是其最近k个设施之一。

影响区在基于位置的服务，营销和决策支持系统方面有各种应用。考虑一个咖啡店的例子。其影响区域可能用于市场分析以及有针对性的营销。例如，其影响区域的人口统计数据可能会被市场研究人员用来分析其业务。影响区也可以用于市场营销，例如广告板或海报可能会放置在其影响区，因为这个区域的人更可能受到市场营销的影响。同样，影响区的人们可能会发送短信广告。

请注意，影响区域的概念比影响集合更为通用，也就是说，q的RkNNs可以通过查找位于其影响区域中的用户集来计算。在本文中，我们表明，基于影响区域的RkNN算法明显优于快照和连续RkNN查询（第2节中正式定义）的最佳已知算法。现有的RkNN处理技术[10,23,33,36,41]需要验证阶段来回答查询。 最初，通过使用设施点的位置修剪该空间。 然后，检索位于未修剪空间的用户。这些用户是可能的RkNNs，被称为候选人。最后，在验证阶段，为每个候选人发出一个范围查询来检查它是否是RkNN。

与现有方法相比，我们基于影响区域的算法不需要验证阶段。最初，我们使用我们的算法来有效地计算影响区。然后，位于影响区域的每个用户都被报告为RkNN。这是因为用户可以是RkNN当且仅当它位于影响区域。同样，为了连续监测RkNNs，最初计算影响区域。然后，为了更新结果，我们只需要监视进入或离开影响区域的用户（即进入影响区域的用户成为RkNNs，离开影响区域的用户不再是RkNN）。为了进一步提高绩效，我们提出了有效的方法来检查一个点是否位于影响区域内。

值得注意的是，当k = 1时，查询的影响区域与查询的Voronoi单元相同[34]。 对于k的任意值，在文献中不存在等价表示（即，阶数k Voronoi单元与影响区域不同）。尽管如此，我们表明可以使用预先计算的k阶Voronoi图来计算影响区域（参见第5.1节）。然而，使用预先计算的Voronoi图不是处理[49]中提到的空间查询的好方法。例如，k的值并不是预先知道的，并且针对k的不同值预先计算几个Voronoi图是昂贵的并且导致高空间要求。 在5.1章节，我们陈述了这种方法的其他一些限制。

下面，我们总结我们的贡献。

----我们提出了一个有效的算法来计算影响区域。基于影响区计算算法，我们提出了超越快照和连续RkNN查询最佳已知技术的高效算法。

----我们的主要算法使用的算法类似于[41]中提出的算法。结果表明该算法的复杂度为O（m2）[41]，其中m是用于修剪搜索空间的设施数量。在这个扩展版本中，我们进行了严格的复杂度分析，并表明当k小于m时，算法的复杂度可以降低到O（km）。

----我们证明影响区域计算技术可以扩展到高于两维的维度。 我们还提供了在底层数据集发布更新时有效更新影响区的技术。

----我们提供了详细的理论分析来分析我们影响区的IO成本和RkNN计算算法，影响区的面积和RkNNs的数量。该分析适用于任意维度，实验结果证明了我们理论分析的准确性。

----我们在真实和合成数据上的广泛实验证明，我们提出的算法比现有的用于二维快照和连续RkNN查询的最佳已知算法快几倍。

本文是我们以前的工作的扩展版本[9]。在这个扩展版本中，我们进行了严格的复杂度分析，并证明当k小于m时，一个重要算法（算法2）的复杂度可以从O（m2）减小到O（km）（参见5.4）。在这个版本中，我们还证明我们的影响区计算技术可以扩展到高于2的维度（参见3.4节）。我们还提出了适用于任意维度的理论分析，其准确性由实验结果验证。在第6节，当底层数据集通过插入或删除来更新时，我们扩展了我们的技术来高效地更新影响区。

本文的其余部分安排如下。 在第2节，我们定义问题并描述相关工作。第3节介绍了我们的技术来有效地计算影响区域。 在第4节，我们通过使用影响区域来呈现有效的技术来回答RkNN查询。详细的理论分析见章节5。在第6节，处理数据更新的技术在其中介绍。 其次是实验结果见章节7。第8部分结束了论文。

  1. 正文前书页

2.1问题定义

首先，我们定义一些术语和符号。 考虑欧几里得空间中的一组设施F = {f1，f2，...，fn}和查询qisin;F 1。给定一个点p，Cp表示一个以p为中心的圆，半径等于dist（p，q），其中dist（p，q）是p和q之间的距离。|Cp| 表示位于圆Cp内的设施的数量（即，对于每个设施f，dist（p，f）lt;dist（p，q））的设施计数。 请注意，查询q可以是点p的k个最接近的设施之一iff | Cp | lt;k。现在，我们定义影响区域和RkNN查询。

影响区域Zk 给定一组设施F和查询qisin;F，影响区Zk是这样的区域，使得对于每个点pisin;Zk，| Cp | lt;k和每个点plsquo; 不属于 Zk，| Cprsquo;| ge;k。

现在，我们定义反向k最近邻居（RkNN）查询。 RkNN查询被分类为[24]双色和单色RkNN查询。 下面，我们定义两者。

双色RkNN查询 给定一组设施F，一组用户U和一个查询qisin;F，一个双色RkNN查询是检索每个用户uisin;U，其中| Cu | lt;k。

考虑一个城市的超市和房屋分别对应于一组设施和用户。 可以使用双色RkNN查询来查找给定超市为最接近的k个超市之一的每个房屋。

单色RkNN查询 给定一组设施F和查询qisin;F，单色RkNN查询将检索每个设施fisin;F，其中| C f | lt;k 1。

请注意，对于每个f，C f都包含f。 因此，我们有条件| C f | lt;k 1而不是| C f | lt;k。 考虑一组警察站。对于给定的警察局q，其单色RkNN是警察局，q是其中最近的警察局之一。 如果发生紧急事件，这些警察局可能会寻求协助（例如，额外的警察）。

快照与持续的RkNN查询 在快照查询中，查询的结果只计算一次。 相反，在连续查询中，随着基础数据集中的对象更改其位置，结果将不断更新。在本文中，我们关注连续RkNN查询的一个特殊情况，其中只有用户更改其位置。

给定一组设施F，一个查询qisin;F和一组用户U，连续的RkNN查询是当一个或多个用户改变其位置时连续更新q的双色RkNNs。

一个加油站可能希望持续监控其最靠近k个加油站之一的车辆。 它可能会发出连续的RkNN查询来执行此操作。

在本文中，我们使用RNN查询来引用k = 1的RkNN查询。表1定义了本文通篇使用的其他表示法。

2.2相关工作

2.2.1快照RkNN查询

Korn等人 [24]首先研究RNN查询。 他们通过为每个数据对象p预先计算一个圆来回答RNN查询，使得p的最近邻居位于圆的周边。 查询q的RNN是在其圆中包含q的每个点。[28,45]中提出了改进其工作的技术。

现在我们简要描述一下不需要预处理的现有技术。 这些技术有三个阶段，即修剪，遏制和验证。 在修剪阶段，不能包含任何RkNN的空间通过使用这套设施进行修剪。 在收容阶段，检索位于未修剪空间内的用户。 这些是可能的RkNNs，被称为候选人。 在验证阶段，针对每个候选对象发出范围查询以检查q是否是其最近k个设施之一。

Stanoi等人提出了不需要任何预处理的第一种技术[33]。 他们通过将以查询q为中心的整个空间分成六个相等的60°区域（图1a中的S1到S6）来解决RNN查询。可以证明，在每个区域内最接近q的设施定义了可以修剪的区域。 换句话说，假定f是区域Si中与q最接近的设施。那么，任何位于Si且位于距离q大于dist（q，f）的距离的用户都不能成为q的RNN。 图1a显示了每个地区q最近的邻居，并且可以修剪白色区域。 只有位于阴影区域的用户才能成为RNN。

RkNN查询可以用类似的方式解决，也就是说，在每个区域中，q的第k个最近设施定义了修剪区域。

陶等人[36]提出了使用垂直平分线属性来修剪搜索空间的TPL。 考虑图1b的例子，q和a之间的平分线显示为Ba：q，它将空间分成两个半空间。 包含a的半空间表示为Ha：q，并且包含q的半空间表示为Hq：a。 任何位于半空间的点Ha：q总是比q更接近于a，并且因此不能成为RNN。类似地，位于k个这样的半空间中的任何点p不能是RkNN。TPL算法通过q和它的邻近区域之间的等分线在修剪区域修剪空间。 图1b显示了q和a，b和c之间的平分线（分别为Ba：q，Bb：q和Bc：q）的示例。 如果k = 2，则可以修剪白色区域，因为它的每个点至少位于两个半空间中。

在遏制阶段，TPL通过遍历索引用户位置的R树来检索位于未修剪区域的用户。令m为考虑平分线的设施点数。可以修剪任意k个半空间组合的交点。总修剪区域对应于k个平分线的所有这些可能组合（总数为m！/ k！（m-k）！组合）的修剪区域的联合。由于组合的数量太大，TPL使用了一种替代方法，其修剪能力较低但价格便宜。首先，TPL根据希尔伯特值对m个设施点进行排序。 然后，只有k个连续的设施点的组合被用来修剪空间（总共m个组合）。

Achtert等人 [1]和Emrich等人。 [13]提出了可应用于矩形的修剪技术。 他们使用这些修剪技术来修剪索引设施的R树的中间条目。 已经证明，所提出的技术减少了被访问页面的数量。 此外，[13]中提出的修剪技术比[1]中的修剪技术更有效。

Wu等人 [41]提出了一种称为FINCH的算法。不使用等分线修剪对象，而是使用接近未修剪区域的凸多边形。 任何位于多边形之外的对象都可以修剪。图1b显示了一个阴影区域是未修剪区域的示例。 FINCH通过

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[24635]，资料为PDF文档或Word文档，PDF文档可免费转换为Word

原文和译文剩余内容已隐藏，您需要先支付 30元 才能查看原文和译文全部内容！立即支付

以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。

您可能感兴趣的文章