过载P2P系统中的高效早期Top-k查询处理

### 过载P2P系统中的高效早期Top-k查询处理 在过载的P2P系统中，高效处理Top-k查询是一项具有挑战性的任务。本文将详细介绍相关的查询处理机制、分布式路由索引的构建与维护，以及性能评估的结果。 #### 1. 查询处理流程 查询处理主要包括查询初始化、查询转发、本地查询执行和结果冒泡等步骤。 ##### 1.1 查询初始化 查询处理从查询发起者开始，即用户发出Top-k查询q的对等节点。查询发起者会进行一些初始化操作： - 设置生存时间（ttl），可以是用户指定的值，也可以是默认值。 - 为查询q创建一个唯一标识符qid，由唯一的对等节点标识符和查询发起者管理的查询计数器组成，用于区分新查询和之前收到的查询。 - 将查询q包含在消息中，广播给其可达邻居。 ##### 1.2 查询转发 在经典的查询转发方法中，对等节点会将任何传入的查询并行转发给所有邻居。但在过载的P2P系统中，这种方法可能会使系统崩溃，因为它通常需要大量的计算资源。因此，我们考虑让对等节点最多并行地将查询转发给m个邻居，m取决于对等节点的当前查询负载。 当m小于对等节点的邻居总数时，对等节点需要决定以何种顺序将查询转发给邻居。为此，对等节点会根据其邻居的数据描述对邻居进行排序，即通过估计每个邻居为查询提供的结果质量。 每个对等节点会将其当前的Top-k中间结果包含在查询消息中，以避免发送比目前计算出的结果更无趣的结果。此外，这些Top-k中间结果还用于避免将查询发送给那些无法返回比当前Top-k中间结果中最小分数更好结果的邻居。 ##### 1.3 本地查询执行 在当前的方法中，对等节点按照先进先出（FIFO）的策略执行传入的查询。但在过载的P2P系统中，对等节点的查询队列通常很长，这种方法会显著增加用户的等待时间。 为了解决这个问题，对等节点本地执行传入查询的顺序取决于根据其本地数据描述对查询结果质量的估计。由于对等节点优先转发结果质量估计最好的查询，它们可能会从邻居那里收到尚未在本地执行的查询的结果。在这种情况下，对等节点的数据描述的乐观属性允许它们避免执行无法提供比当前Top-k中间结果中最小分数更好结果的查询。 ##### 1.4 结果冒泡 一种简单的减少用户等待时间的方法是，对等节点在执行完查询后，直接将Top-k结果返回给查询发起者。但返回大量结果会增加网络流量，并可能在查询发起者处造成瓶颈。 在QUAT中，当对等节点提交Top-k查询q时，收到查询q的对等节点的本地结果会通过查询q的转发树冒泡到查询发起者。 对等节点决定发送中间结果的依据是其当前的Top-k中间结果集相对于已经发送给其父节点的Top-k中间结果集带来的改进影响。我们引入了基于分数的改进影响的概念： 给定Top-k查询q和对等节点p（p属于收到查询q的对等节点集合），设Tcur是对等节点p处查询q的当前Top-k中间结果集，Told是对等节点p到目前为止发送的查询q的Top-k中间结果集。查询q在对等节点p处的基于分数的改进影响IScore(Tcur, Told)计算公式如下： \[IScore(Tcur, Told) = \frac{\sum_{d\in Tcur} q.f(d, q.\overline{q}) - \sum_{d'\in Told} q.f(d', q.\overline{q})}{k}\] 基于分数的改进影响值在区间[0, 1]内。在QUAT中，对等节点在将新收到的中间结果发送给其父节点之前，改进影响必须达到的最小值最初由应用程序设置，并且系统中的所有对等节点都相同。这个阈值会随着查询执行的进行而降低。 为了使用动态阈值方法，我们需要动态计算阈值。有两种可能的解决方案： - 使用查询执行时间的估计值，但在大型P2P系统中估计查询执行时间非常困难，因为它取决于网络动态和最慢的被查询对等节点。 - 使用每个对等节点的本地结果集覆盖率来降低阈值。对等节点的本地结果集覆盖率是指其查询转发树子树中（包括自身）已经处理该查询的对等节点的比例。计算公式为： \[Cov(E, A) = \frac{\|E\|}{\|A\|}\] 其中，A是查询q的转发树中以对等节点p为根的子树中的对等节点集合，E是A中已经在本地处理了查询q的对等节点集合。 为了减少计算本地结果集覆盖率的消息开销，我们计算其估计值。每个对等节点在开始时根据查询的ttl和系统中对等节点的平均度计算该估计值，并随着子树中的对等节点冒泡结果而逐步更新。 我们使用线性函数来根据本地结果集覆盖率设置对等节点的改进影响阈值： \[H : [0, 1] \to [0, 1]\] \[x \to -\alpha * x + \alpha\] 其中，α属于[0, 1)，x是给定时