用于针对基于位置的服务生成数据集结构的方法以及用于向移动设备提供基于位置的服务的方法和系统

摘要

本发明公开了一种用于针对基于位置的服务生成数据集结构的方法，所述方法包括以下步骤：将地理区域分割成多个优选为尺寸相等的区块，其中所述地理区域包括多个兴趣区域，将所述区块与多个服务器相关联，其中每个区块根据一致性哈希函数与所述服务器中的至少一者相关联，针对每个区块生成包括与所述区块相交的兴趣区域的第一数据集，其中所述第一数据集的所述兴趣区域由所述区块的边缘修整或者完全包含在所述区块中，针对每个区块生成包括溢出部分的第二数据集，其中所述溢出部分中的每一者均是第一数据集的兴趣区域的一部分，由所述区块的边缘修整并且位于所述区块的外部，以及针对每个区块将所述第一数据集和所述第二数据集存储在与所述区块相关联的服务器处。此外，还公开了一种用于使用这种数据集结构来提供基于位置的服务的方法和系统。

说明书

本发明的第一方面涉及一种用于针对基于位置的服务生成数据集结构的方法。本发明的第二方面涉及一种使用通过根据本发明第一方面的方法生成的数据集结构在地理区域内向移动设备提供基于位置的服务的方法和系统。

在移动性越来越高的世界中，源自移动设备的大量信息都可供应用程序开发人员利用。然而，对原始数据的访问几乎都是不够的，并且可能显得过于繁琐。尤其是在基于位置的服务(LBS)方面，对原始位置数据的处理可能复杂而庞大，使得这种处理不应由资源有限的移动设备来执行。通常，应用程序开发人员依赖于对数据提供某种预处理的框架，从而实现了更高水平的抽象以及更丰富的应用。

地理围栏就是一种这样的更高水平的抽象。考虑到两次连续位置更新PL(先前位置)和CL(当前位置)，地理围栏问题在于，确定在两个位置之间退出的兴趣区域集合以及进入的兴趣区域集合以便生成与这些进入和退出的区域有关的动作。

图1示出了地理围栏问题的基本概念。在第一位置更新时，移动设备位于区域1内的先前位置PL处。在于第一位置更新之后执行的第二位置更新时，移动设备位于区域2内的当前位置CL处。这就意味着，移动设备已从PL移动到CL并且从区域1移动到区域2。地理围栏系统将以正被退出的形式触发区域1并且以正被进入的形式触发区域2。

一种用于计算退出和进入的地理围栏的简单算法是，首先获得其中包含先前位置PL的地理围栏集合(先前集合)以及其中包含当前位置CL的地理围栏集合(当前集合)。退出和进入集合(是指退出和进入的地理围栏)可以如下方式确定：

这就意味着，进入集合包含当前集合的不包含在先前集合中的每个地理围栏。

随着利用地理标记数据的基于位置的服务激增，以及启用这些服务的移动设备的数量与日俱增，需要采用策略来处理所涉及的大量数据。此外，必须生成对大量查询的响应。地理标记数据编索引的现有技术采用了某种分区机制来更好地分配数据和平衡负荷。

Jinbao Wang et al.“Indexing multidimensional data in a cloud system”(SIGMOD 10，2010)(王金宝等人，“在云系统中对多维数据编索引”，数据管理专业委员会会议，2010年)中公开了一种方法，这种方法使用基于RT-CAN(CAN中基于R树的索引)的方法。将全局索引散布到被组织为基于逻辑CAN(内容可寻址网络)的叠加网络的不同群集服务器。使用多种算法(其中之一为动态算法)来优化系统，从而降低查询和索引维护成本。

在地理围栏系统中，当跨不同服务器来对不同区域分区时，算法要求所有服务器计算当前集合和先前集合，并且然后对这两个集合进行运算以分别计算进入的和退出的区域(如先前两个公式所详述)。这就意味着，要么由不同服务器将这两个集合转发到负责减去这些集合的第三服务器，要么集合在随后执行减法的两个服务器之间自己交换。这就引起高延迟以及在服务器之间要交换大量消息。

LBS目前是非常热门的话题，自然利用了越来越多地“连接的”世界的本质，在这个世界中存在各种各样的移动设备。US 7,848,765B2公开了涉及LBS的多种方法和系统。然而，其内容并未提供与降低延迟或减少所交换的消息数量有关的任何帮助。

因此，本发明的目的在于，提供一种用于生成数据集结构的方法，该数据集结构可用于基于位置的服务并且允许在降低交换消息的必要性以及降低延迟的同时执行与兴趣区域有关的分布式计算。此外，应提供一种使用这种数据集结构来向移动设备提供基于位置的服务的方法和系统。

根据本发明，前述目的通过包括权利要求1的特征的方法来实现。根据该权利要求，此类方法包括以下步骤：

将地理区域分割成多个优选为尺寸相等的区块，其中所述地理区域包括多个兴趣区域，

将所述区块与多个服务器相关联，其中每个区块根据一致性哈希函数与所述服务器中的至少一者相关联，

针对每个区块生成包括与所述区块相交的兴趣区域的第一数据集，其中所述第一数据集的所述兴趣区域由所述区块的边缘修整或者完全包含在所述区块中，

针对每个区块生成包括溢出部分的第二数据集，其中所述溢出部分中的每一者均是第一数据集的兴趣区域的一部分，由所述区块的边缘修整并且位于所述区块的外部，以及

针对每个区块将所述第一数据集和所述第二数据集存储在与所述区块相关联的服务器处。

关于用于提供基于位置的服务的方法以及根据本发明，前述目的通过包含权利要求7的特征的方法来实现。根据该权利要求，此类方法包括以下步骤：

接收所述移动客户端的位置信息，其中所述位置信息包括所述移动客户端的在两次连续位置更新时确定的先前位置和当前位置，

确定当前区块，其中所述当前区块是所述多个区块中的一者并且包含所述当前位置，

根据一致性哈希函数确定与所述当前区块相关联的当前服务器，其中所述当前服务器是多个服务器中的一者，

在所述当前服务器处访问所述数据集结构的第一数据集和第二数据集，

由所述当前服务器确定兴趣区域的当前集合，其中所述当前集合包括所述第一数据集的其中包含所述当前位置的每个兴趣区域，以及

使用所述当前集合和所述先前位置来确定位置改变。

关于用于提供基于位置的服务的系统以及根据本发明，前述目的通过包含权利要求14的特征的系统来实现。根据该权利要求，此类系统包括：

多个服务器，其中所述服务器中的每一者根据一致性哈希函数与所述多个区块中的至少一个区块相关联，

用于接收所述移动客户端的位置信息的装置，其中所述位置信息包括所述移动客户端的在两次连续位置更新时确定的先前位置和当前位置，

用于确定当前区块的装置，其中所述当前区块是所述多个区块中的一者并且包含所述当前位置，

用于使用所述一致性哈希函数来确定与所述当前区块相关联的服务器的装置，以及

用于基于所述第一数据集和所述第二数据集使用所述先前位置和所述当前位置来计算所述客户端的位置改变的装置。

根据本发明，首先已经认识到，前述目的可通过以特定方式对与兴趣区域有关的数据进行预处理和分配来实现。根据本发明，在第一步骤中，生成将地理区域分割成多个区块的网格。这就为另外的步骤创建了结构化基础。优选地，网格的单个元素(后文称为区块)是尺寸相等的。网格与兴趣区域基本上是独立的，即，区块的位置和取向不依赖于地理区域中包含的兴趣区域。在正常操作期间不调节区块的尺寸、位置和取向。它们是可以事先调节并且可能考虑了兴趣区域的配置参数。然而，这不是必要性约束。在许多情况下，尤其是如果使用尺寸相等的区块以及通常具有任意形状的兴趣区域，网格与兴趣区域之间的依赖性甚至难以确立。

在下一个步骤中，网格的单个区块与将用于确定移动客户端的位置改变的多个服务器相关联。使用一致性哈希函数来执行区块的关联：每个区块与所述多个服务器中的至少一者相关联。如果未提供副本，一个区块将与仅一个服务器相关联。根据所需副本的数量，一个区块可与两个或更多个服务器相关联。优选地，若干区块与一个服务器相关联。然而，还可能的是，每个服务器与仅一个区块相关联。

一致性哈希函数提供了区块与服务器之间的唯一链路。该链路可以相当随机的方式将区块关联到服务器。然而，该链路是唯一的并且在每次访问时都引起相同的结果。这就实现了对关联服务器的直接访问而无需在服务器之间跳跃以寻找正确的服务器。

在第三步骤中，将兴趣区域分配到单个服务器，从而生成特定数据集结构。该数据集结构包括第一数据集和第二数据集。每个第一数据集均包括与区块相交的兴趣区域。每个第二数据集均包括溢出部分。

由于区块不具有到兴趣区域的直接链路，并且由于分区步骤不考虑兴趣区域，因此大多数兴趣区域将不会落在单个区块中。因此，许多兴趣区域的部分包含在两个或甚至更多个区块中。如果若干区块与兴趣区域相交，则包含兴趣区域的一部分的区块具有也包含该兴趣区域的一部分的至少一个邻近区块。在生成第一数据集和第二数据集时使用兴趣区域到若干区块的这种分配。

针对所述多个区块中的每个区块T执行生成第一数据集和第二数据集的步骤。在区块T，确定与区块T相交的每个兴趣区域，即，兴趣区域的落在区块T中的每个部分均被视为相交。将与区块T相交的每个兴趣区域添加到针对区块T生成的第一数据集。第一数据集中包含的兴趣区域可完全包含在区块T中或者可由区块T的一个或多个边缘修整。如果兴趣区域由一个或多个边缘修整，则存在兴趣区域的包含在与区块T相邻的区块中的部分。兴趣区域的这些部分被称为“溢出部分”。将每个溢出部分添加到针对区块T生成的第二数据集。因此，第一数据集包含与区块T相交的每个兴趣区域，第二数据集包含第一数据集的兴趣区域的由区块T的边缘修整并且包含在区块T外部的每个部分。在针对所述多个区块中每个区块T的生成步骤之后，地理区域的每个兴趣区域均包含在至少一个第一数据集中并且最可能包含在一个或多个第二数据集中。

第一数据集和第二数据集存储在关联到特定区块的服务器处，使得服务器可在操作期间访问第一数据集和第二数据集，即，参与到用于提供基于位置的服务的系统中。应当理解，不是必须将数据集存储在服务器的硬盘上。也可能将数据集存储在可由服务器访问的数据存储装置处。然而，优选以分布式方式存储数据集以避免热点或单个故障点。

尽管存储在服务器上(或为服务器存储)的数据总量增加，但在必须确定移动客户端的位置改变时，这种数据集结构尤其有用。由于与区块相关联的服务器知悉整个兴趣区域(不仅是其一部分)，因此服务器可确定移动客户端在从先前位置移动到当前位置时是进入了还是退出了兴趣区域。这可在不与另一服务器通信的情况下执行。因此，所述数据集结构降低了在服务器之间交换消息的必要性。由于可由单个服务器执行计算，因此整个系统的延迟可降低。归因于使用了与兴趣区域基本上独立的区块并且归因于一致性哈希函数，可在不搜索树或其他数据结构的情况下基于移动设备的位置来确定区块以及与该区块相关联的服务器。这就更进一步地降低了延迟并且减少了所交换的消息数量。

根据本发明的提供基于位置的服务的方法和系统可使用这种数据集结构。在第一步骤中，由相应装置接收位置信息，该位置信息反映移动设备在两次连续位置更新时的位置。术语“两次连续位置更新”是指第一位置更新以及在第一位置更新之后的第二位置更新。关于第一位置更新和第二位置更新之间的时间间隔，不存在直接约束。时间间隔通常由基于位置的服务来定义。然而，间隔通常小于10分钟，优选小于1分钟。位置信息包括在第一位置更新时确定的先前位置(PL)以及在第二位置更新时确定的当前位置(CL)。

在第二步骤中，确定当前区块，即，所述多个区块中的包含当前位置(CL)的区块。可由各种实体来执行这个步骤。根据一个可能的实施例，移动客户端基于其当前位置使用区块的可由移动客户端访问或存储在移动客户端处的地理信息来确定当前区块。根据另一实施例，可由一个或若干服务器确定当前区块，所述服务器可访问将位置信息与分区方案相链接的信息。

在确定了当前区块之后，确定与当前区块相关联的当前服务器。由于每个区块均依据一致性哈希函数来与至少一个服务器相关联，因此可容易地确定当前服务器。如果区块与两个或更多个服务器相关联，情况也同样如此。由于系统不依赖于执行计算的服务器而是取决于涉及当前或先前位置的区块，因此由哪个服务器执行计算并不重要。因此，可由与特定区块相关联的每个服务器来处理针对计算位置改变的请求。

在下一个步骤中，当前服务器访问第一数据集和第二数据集。在优选实施例中，这些数据集存储在当前服务器的存储器(例如硬盘)处。然而，也可将第一数据集和第二数据集存储在由当前服务器经由局域网等访问的远程数据存储点。

在另一步骤中，当前服务器确定包括其中包含当前位置的每个兴趣区域的当前集合。由于第一数据集包含与当前区块相交的每个兴趣区域并且由于当前区块包含当前位置，因此可使用第一数据集来确定这个当前集合。在另一步骤中，使用当前集合和先前位置来确定位置改变。

在本发明的特定优选实施例中，由地理围栏系统提供基于位置的服务。在这种情况下，兴趣区域是地理围栏。尽管地理围栏系统是优选实施例，但本发明不仅限于这些系统。本文档中所述的步骤和实体还可用于其他基于位置的系统。

根据分区方案的特定简单具体实施，区块具有四边形或矩形形状。这种具体实施降低了确定位置是否包含在区块内的复杂度。然而，区块的其他形状也可与本发明结合使用。例子有六边形、八边形或其他多边形形状。由于网格应覆盖整个地理区域，因此区块应具有一形状使得区块可直接放置在彼此旁边而不在区块之间留间距。

为了避免服务器之间的热点，一致性哈希函数可采用负荷平衡方案。优选地，在服务器间均匀地分配区块。

优选地，一致性哈希函数采用负荷平衡方案。这可通过使用一哈希函数来建立，该哈希函数提供在哈希范围中均匀(或至少基本上均匀)分布的值。对于此类哈希函数而言，服务器与区块的关联是相当随机的，使得可以提供良好的负荷平衡方案。

一致性哈希函数的一个优选实施例使用由编程语言java提供的方法String.hashCode()。在第一步骤中，可将标识符(ID)分配给所述多个区块中的每一者。优选地，对区块编号。在第二步骤中，可确定哈希，优选地使用以下函数来确定：

其中s是表示区块的ID的字符串，n是字符串的长度。这个哈希h(s)是不带符号的32位整数，因此哈希间距具有[-(2^31)，2^31-1]的总范围。每个服务器然后可获得该范围的相等份额。在这个优选实施例中，哈希函数结果是随机的，并且每个服务器具有整个哈希范围的相等比例。这就提供了良好的负荷平衡方案。

为引入冗余，可采用若干哈希函数，其中每个哈希函数提供一致性哈希算法。哈希函数可被配置使得区块依据所述若干哈希函数中的每一者来与另一服务器相关联。如果例如提供了R哈希函数，则每个区块将关联到R个不同的服务器。如果接收到关于当前区块的请求，则可选择哈希函数中的一者以便确定执行该方法的另外步骤的服务器。这个选择过程还可采用负荷平衡方案使得请求被均匀分配到服务器。

在将新兴趣区域插入到该地理区域时，必须更新数据集结构使得在未来计算时可以考虑该新兴趣区域。插入新兴趣区域的步骤可包括确定所述多个区块中的与新兴趣区域相交的每个区块的第一步骤。在第二步骤中，可将新兴趣区域映射到已确定的区块。在第三步骤中，可将新兴趣区域添加到相关联的服务器处的每个已确定区块的第一数据集和第二数据集。第三步骤类似于在数据集结构的初始设置时执行的并且前文所描述的步骤。如果采用了若干一致性哈希函数，则应在与已确定区块中的一者相关联的每个服务器处存储或者为所述服务器存储第一数据集和第二数据集存储。

移除旧兴趣区域的步骤可以是类似的：在第一步骤中，可确定与该旧兴趣区域相交的区块。在第二步骤中，可确定与已确定的区块相关联的服务器。在第三步骤中，可将旧兴趣区域从每个已确定服务器的第一数据集和第二数据集中移除。

在根据本发明的用于提供基于位置的服务的方法中，确定位置改变的步骤可包括确定进入集合的步骤。该进入集合包含由移动设备在从先前位置PL移动到当前位置CL时所进入的每个兴趣区域。确定进入集合的一个可能性包括：如果先前位置不包含在当前服务器处第一数据集或第二数据集的兴趣区域中，则将当前集合的兴趣区域添加到进入集合。换句话讲：检查当前集合的每个兴趣区域，即其中包含当前位置的每个兴趣区域。如果先前位置落入当前集合的一个兴趣区域中，则不进入这个兴趣区域。如果先前位置不包含在当前集合的兴趣区域中，则进入这个兴趣区域。归因于第一数据集和第二数据集的特殊结构，这可在不与另一服务器互动的情况下加以确定。检查当前集合的每个兴趣区域是将先前位置包含在了第一数据集中还是包含在了第二数据集中。

此外或替代地，确定位置改变的步骤可包括确定退出集合的步骤。该退出集合包含由移动设备在从先前位置移动到当前位置时所退出的每个兴趣区域。

根据第一选项，先前位置落在当前区块上。在这种情况下，可在不涉及另一服务器的情况下由当前服务器确定退出集合，因为当前服务器可访问每个相关信息片段。在这种情况下，当前服务器可确定先前集合。先前集合包含第一数据集中所包含的并且其中包含先前位置的每个兴趣区域。通过从先前集合中减去当前集合来确定退出集合：

这就意味着，退出集合包含先前集合的不包含在当前集合中的每个兴趣区域。如所见，归因于特定的数据集结构，这个确定退出集合的步骤还可由当前服务器执行。

根据第二选项，先前位置不落在当前区块上。尽管当前服务器在不涉及另一服务器的情况下确定进入集合，但当前服务器不能肯定地确定退出集合。然而，归因于所使用的数据集结构，可在不涉及另一服务器的情况下，以与进入集合类似的方式确定退出集合。在这种情况下，可确定先前区块，即，包含先前位置的区块。通过使用一致性哈希函数，可确定与先前区块相关联的先前服务器。可将先前位置和当前位置或者先前位置和当前集合从当前服务器传输到先前服务器。通过使用先前位置，先前服务器可确定包含其中包含先前位置的每个兴趣区域的先前集合。基于该先前集合以及当前位置，先前服务器可确定退出集合。可以与确定进入集合的步骤完全独立的方式来执行这个确定退出集合的步骤。如果先前服务器和当前服务器都接收到位置信息，则两个服务器均可彼此独立地计算相应集合。这还实现了两个集合的同时且独立的动作触发。

可以与当前服务器处的进入集合类似的方式来确定退出集合：如果当前位置不包含在第一数据集和第二数据集的这个兴趣区域的一部分中，则将先前集合的兴趣区域添加到退出集合。即，先前服务器访问先前集合的每个兴趣区域并检查当前位置是否落入包含在第一数据集或第二数据集中的这个兴趣区域的一部分中。如果当前位置不包含在这个兴趣区域中，则退出该兴趣区域并将该兴趣区域添加到退出集合。如果当前位置包含在这个兴趣区域中，则不退出该兴趣区域。

在确定位置改变的步骤之后，方法可包括触发基于位置的动作的步骤，其中确定位置改变的步骤可包括确定进入集合和/或退出集合的步骤。这个动作可基于已确定的位置改变。此类动作可包括向附近客户宣传当前促销；确定某人在某个区域中(例如，在商店、博物馆或运动场馆内)的停留时间；或者向附近移动客户端传送建议(例如，事故周围的半径范围将是兴趣区域并且汽车是移动客户端，或者围绕建筑区域创建兴趣区域并且附近市民可接收建议)。

根据本发明的系统提供了相应的装置，所述相应的装置使系统能够执行用于向移动设备提供基于位置的服务的方法的步骤。优选地，该系统可另外包括

用于确定先前区块的装置，其中所述先前区块是所述多个区块中的一者并且包含所述先前位置，

用于使用所述一致性哈希函数来确定与所述先前区块相关联的服务器的装置，以及

用于基于所述第一数据集和所述第二数据集使用所述先前位置和所述当前位置来计算所述客户端的位置改变(退出的区域)的装置

在根据本发明的系统中，可通过将服务器组织成环形结构来更进一步地提高系统灵活性。这并不一定意味着，连接服务器的网络的拓扑必须是环形结构。然而，服务器的逻辑结构是环形结构。在考虑将服务器添加到环形结构或者从环形结构中移除服务器时，这种组织的优点就变得较明显。

在将新服务器添加到环形结构时，可为与一个或两个邻近服务器相关联的若干区块重新分配新服务器。这样，可将必须重新安排的区块的数量减至最低。在重新分配来自一个邻近服务器的区块时，可将该邻近服务器的一半区块重新分配到新服务器。在重新分配来自两个邻近服务器的区块时，可为与所述邻近服务器相关联的三分之一的区块重新分配新服务器。尽管这会引起区块被不均匀地分配到服务器，但这种方法是处理热点(即，与高频兴趣区域相交的区块)的简单方式。在将单个区块重新分配到新服务器时，可能考虑不均匀的分配。

在将区块重新分配到新服务器时，之前与该区块相关联的服务器可将该区块的第一数据集和第二数据集传送至新服务器。或者，可如前文所述重新计算第一数据集和第二数据集。此外，还更新一致性哈希函数使得哈希函数反映新关联。

在移除服务器时，必须将与所移除的服务器相关联的区块重新分配到一个或若干新服务器。一个可能性包括调适哈希函数并使用经调适的哈希函数来再次重新分配区块。一种替代方法包括将区块重新分配到一个或两个邻近服务器。

根据本发明的向移动设备提供基于位置的服务的方法和系统使用移动设备的先前位置和当前位置来确定位置改变。有关如何提供这些先前位置和当前位置，存在若干选项。第一选项包括引入针对每个移动客户端接收定期位置更新的位置跟踪实体。如果针对移动客户端接收到两次连续位置更新，则位置跟踪实体可删除位置信息。一旦位置跟踪实体接收到移动客户端的新位置更新，位置跟踪实体就可触发对位置改变的计算，这继而又可触发某个与位置有关的动作。

然而，根据优选实施例，先前位置和当前位置由移动客户端自己提供。许多移动客户端提供存储先前位置信息的位置缓存。在位置更新时，移动设备可将先前位置和当前位置传输至系统以用于提供LBS，LBS可触发对位置改变的计算以及某个与位置有关的动作。这个选项更进一步地减少了所交换的消息数量。此外，系统不依赖于可供所有服务器访问的共享数据层。通过将这个问题转移到客户端，使其与当前位置以及先前(可能本地缓存的)位置一起发送，系统是无状态的并且不依赖于共享数据，从而实现了分布式计算。

有几种以有利的方式设计和进一步改善本发明教导的方式。为此，其一方面涉及权利要求1、7和14的从属权利要求，另一方面涉及附图所示的以举例方式给出的本发明的优选实施例的下述说明。结合借助附图的本发明优选实施例的说明，将阐明教导的一般优选实施例及其进一步改进。图中：

图1为针对地理围栏系统中位置更新的例子的示意图，

图2示出了被分割成多个四边形区块的地理区域，

图3为服务器环形结构的示意图，该服务器环形结构与根据本发明的方法和系统一起使用，以及

图4示出了由区块的边缘修整的兴趣区域的例子。

图1示出了地理围栏问题的基本概念。在第一位置更新时，移动设备位于区域1内的先前位置PL处。在于第一位置更新之后执行的第二位置更新时，移动设备位于区域2内的当前位置CL处。这就意味着，移动设备已从PL移动到CL并且从区域1移动到区域2。地理围栏系统将以正被退出的形式触发区域1并且以正被进入的形式触发区域2。

图2示出了被分割成尺寸相等的区块的地理区域。该地理区域是由图2所示的地图表示的巴黎的中心。四边形区块将整个空间分割成更小的组块。兴趣区域可由街道、建筑物(诸如购物商场、博物馆、电影院或会议中心)、地铁站等的一部分来定义。

图3A显示了组织成环形结构2的四个服务器1。这些服务器可用于根据本发明的系统和方法中。在图3的例子中，地理区域被分割成6x6网格，从而得到36个区块。每个区块根据一致性哈希函数与四个服务器中的一者相关联。每个服务器与相同数量的区块，即9个区块，相关联。

在图3B中，将新服务器3添加到环形结构2。在添加新服务器3时，为与一个或两个邻近服务器相关联的若干区块分配新服务器。在图3的例子中，一个服务器1为邻近的新服务器3提供4个区块，从而保持了5。这就意味着重新安排4个区块。

通常，在将新服务器添加到环形结构或者从环形结构中移除服务器时，一般情况下都

C＝K/n

必须重新安排区块，其中网格包括K个区块且环形结构包含n个服务器。在该例子中，添加一个服务器将导致重新安排C＝K/n＝36/5＝7.2个区块。如果仅重新安排来自邻近服务器的区块，则这个数量会得到相当程度的降低。即使重新安排来自两个邻近服务器的区块，重新关联的区块的数量也低于这个平均数量。邻近服务器可为新服务器提供三分之一的关联区块，即，将3个区块从每个邻近服务器转移到新服务器。因此，必须重新分配6个区块。

如果系统提供副本，则重新安排的区块的平均数量是

C＝R·K/n

其中，R是副本的数量，即每个区块均与R个服务器相关联。同样这种情况下，仅将来自一个或两个邻近服务器的若干区块重新关联到新服务器就大幅减少了重新安排的区块的数量。

图4A显示了与区块5相交的兴趣区域4。在图4A的例子中，兴趣区域4由矩形区块5的两个边缘修整。这就将兴趣区域划分成与区块5相交的部分和位于区块5外部的部分。根据本申请，兴趣区域被划分成与区块5相交的第一部分6和溢出到区块5外的第二部分7。在生成数据集结构时，生成第一数据集和第二数据集，其中第一数据集包括每个第一部分6且第二数据集包括每个第二部分7。在存储第一数据集和第二数据集时，应存储第一部分与第二部分之间的链路。这会大幅促进对位置改变的确定。

图4B更清楚地显示了第一部分和第二部分的这种分划。

变得明显的是，兴趣区域4将与区块5以及两个邻近区块相交：一个位于区块5的右手侧并且一个位于区块5的底侧。由于针对每个区块生成第一数据集和第二数据集，因此兴趣区域4将包含在针对三个区块生成的第一数据集和第二数据集中。每个区块的每个数据集将包括兴趣区域4的不同部分。

本发明相关领域的技术人员根据上述说明书以及相关附图的教导，便可想到本文中阐述的本发明的许多修改和其他实施例。因此，应当理解本发明并不局限于已经公开的具体实施例，修改和其他实施例也旨在包含在所附权利要求范围内。尽管本发明采用了具体的术语，但仅在一般性及描述性意义上进行使用，并不用于限制之目的。