间隔匿名算法
    间隔匿名算法的基本思想为：可信第三方匿名服务器构建一个四叉树的数据结构，将二维空间用十字分成四个面积相等的正方形区间，然后对每一个正方形再递归执行相同的操作，直到所得到的最小的正穷形区间的面积为系统要求的允许用户所采用的最小匿名区面积为止，每一个正方形区间对应于四叉树中的一个节点。此算法要求系统中的所有用户每隔固定的时间将自己的当前位置坐标上报给匿名服务器，匿名服务器更新并统计每个节点对应区间内的用户数量。当某个用户进行匿名查询时，匿名服务器检索当前四叉树结构，为用户生成一个匿名区。具体来说，间隔匿名算法从包含用户的四叉树的叶子节点开始向四叉树根的方向搜索，直到找到包含不低于后个用户的节点（包括当前用户在内），并把该节点所对应的区域作为匿名查询用户的一个匿名区。

    如图8-12所示，如果用户ul发起k=2的匿名查询，间隔匿名算法将首先搜索到象限区间[(0，0)，(1，1)]，其中包含的用户数少于2个，不满足匿名要求。然后，该算法继续向根的方向上升一级搜索象限区间[(0，O)，(2，2)]，该象限区间包含3个用户，大于要求的2个，算法停止搜索，并将区间[(0，O)，(2，2)]作为用户u1的匿名区。值得注意的是，该算法所得的匿名区所包含的用户数量可能远远大于k，因此会加大位置服务提供商的查询处理负担和网络流量的负荷。

    为了解决间隔匿名算法对位置服务提供商负载较高的问题，还有一种Casper匿名(Casper cloak)算法。该算法与间隔匿名算法类似，也采用了四叉树数据结构来表示二维空间，不同点有两个：①在识别和访问四叉树的叶子节点时，Casper匿名算法直接通过hash表来完成；②在对节点进行搜索时，当所搜索的节点不满足匿名度k的要求，那么该算法不像间隔匿名算法那样直接搜索其父节点，而是依次检查它的两个相邻的兄弟节点和它所组合起来的区间中所包含的用户数量是否大于等于k，如果满足则直接将组合区间作为用户的匿名区，否则再对其父节点进行搜索。另外，Casper匿名算法允许每个移动用户自由地决定k值的大小和最小的匿名区面积。如图8-12所示，如果用户ul发起k=2昀匿名查询，Casper匿名算法将首先搜索到象限区间[(o，O)，(1，1)]，其中包含少于2个用户；然后，先检查它的两个相邻兄弟区间[(0，1)，(1，2)】和[(1，O)，(2，1)]，如果它们中的一个与自己组合起来的区间中包含的用户数量大于等于k，则直接把组合起来的矩形区间作为匿名区。在这个例子中矩形[(0，0)，(1，2)]将被作为匿名区。与间隔匿名算法相比，Casper匿名算法所生成的匿名区平均要更小，从而提高了位置服务器的查询效率并减少了对网络流量的负荷。