Multi-Guarded Safe Zone: An Effective Technique to Monitor Moving Circular Range Queries

多监测安全区域：一个监测移动圆形范围查询的有效技术-粗译

Abstract—Given a positive value r, a circular range query returns the objects that lie within the distance r of the query location. In this paper, we study the circular range queries that continuously change their locations. We present an efficient and effective technique to monitor such moving range queries by utilising the concept of a safe zone. The safe zone of a query is the area with a property that while the query remains inside it, the results of the query remain unchanged. Hence, the query does not need to be re-evaluated unless it leaves the safe zone. The shape of the safe zone is defined by the so-called guard objects. The cost of checking whether a query lies in the safe zone takes k distance computations, where k is the number of the guard objects. Our contributions are as follows. 1) We propose a technique based on powerful pruning rules and a unique access order which efficiently computes the safe zone and minimizes the I/O cost. 2) To show the effectiveness of the safe zone, we theoretically evaluate the probability that a query leaves the safe zone within one time unit and the expected distance a query moves before it leaves the safe zone. Additionally, for the queries that have diameter of the safe zone less than its expected value multiplied by a constant, we also give an upper bound on the expected number of guard objects. This upper bound turns out to be a constant, that is, it does not depend either on the radius r of the query or the density of the objects. The theoretical analysis is verified by extensive experiments. 3) Our thorough experimental study demonstrates that our proposed approach is close to optimal and is an order of magnitude faster than a na¨?ve algorithm.

摘要-给定一个正数r，通过一个圆形范围查询，返回查询位置距离r内的所有对象。本文中，我们研究了不断改变位置的圆型范围查询。我们提出了一个有效率的技术来监测这样的移动范围查询，利用了安全区域的概念。一个查询的安全区域指的是一个区域具备这样的性质：当查询点在区域内，查询的结果不变。因而查询不需要重新估计计算，除非它离开了安全区域。监控对象定义为这种形状的区域。检测的代价是由查询点是否在半径r的k距离范围之内，这里的k是监测对象的数目。我们的贡献有如下几点：1）我们提出一个基于强大的剪枝规则和独特的存取命令，可以有效的计算安全区域和最小化I/O代价。2）为了使安全区域更有效，我们理论上估计了查询在一个时间单元内离开安全区域的概率，以及一个查询点在移动离开安全区域的期望距离。另外，对于安全半径小于常于乘于期望值的查询，我们同时给出一个在监测对象数目的期望上界。这个上界的结果是一个常数。也就是说它即不依赖于查询半径r也不依赖于对象密度。这个理论分析被大量的实验所证实。3）我们通过实验研究证明我们设计的渐近是尽可能优化，并且比原始算法快上数量级。

＝＝＝＝＝＝＝＝＝

简单粗译一下，请大家指教。