一种P2P环境中的窗口查询方法

具体实施方式

现结合附图和具体实施例对本发明作进一步说明。

本发明具体实施过程和工作原理如下：

1)选择具备集中式网络和完全无结构化网络的超级节点(super-peer)P2P网络作为底层网络基础；

2)在每个单独的网络节点上，数据通过一种降维算法映射到一维空间；

3)在超级节点上构建数据的统计信息表以及构造网络查询树；

4)当一个节点P发起查询请求时，查询q被发送到节点P所在的超级节点，超级节点在内部完成查询；

5)超级节点查询其他所连接的超级节点的数据，并返回结果。

步骤1)中的网络结构如图1所示，每个超级节点SP管理P₁到P_n个底层节点，超级节点之间互相连接构成整个P2P网络，原始数据存在底层节点上，超级节点SP仅仅存储统计信息等数据。

步骤2)中的数据空间表示为：考虑一个维度为d的数据空间，数据每个维度的值范围是[0，1]，因此一个d维的点所在的范围空间可以表示为([0，1]，[0，1]，…[0，1]，[0，1])。将一个数据点x以及其最大最小值表示为式(1)：

x＝(x ₁，x ₂...，x_d)

x∈([0，1]₁，[0，1]₂...[0，1]_d)

$x_{\max }={\max }_{i=1}^d{x}_i$

$x_{\min }={\min }_{i=1}^d{x}_i---\left(1\right)$

将窗口查询q表示为式(2)，将窗口查询结果集表示为window(q)。

q＝([x₁₁，x₁₂]，...[x_d1，x_d2])          (2)

步骤2)中选用的降维算法是iMinMax，数据映射式如(3)所示，将数据映射到所有维度的最大值或者最小值，其中θ表示用户指定的参数，c表示一个常量，通常取值为1，d_min表示数据的最小值的维度，d_max表示数据的最大值的维度。

$y=\left(\begin{array}{cc}{d}_{\min }\times c+x_{\min }& \mathrm{if}{x}_{\min }+\theta <1-x_{\max }\\ d_{\max }\times c+x_{\max }& \mathrm{otherwise}\end{array}\right)---\left(3\right)$

同时，iMinMax将窗口查询映射到式(4)，其中q_j表示窗口查询q的第j个维度上的分量。

$q_j=\left(\begin{array}{c}[j+{\max }_{i=1}^d{x}_{i1},j+x_{j2}]\\ \mathrm{if}{\min }_{i=1}^d{x}_{i1}+\theta >=1-{\max }_{i=1}^d{x}_{i1}\\ [j+x_{j1},j+{\min }_{i=1}^d{x}_{i2}]\\ \mathrm{if}{\min }_{i=1}^d{x}_{i2}+\theta <1-{\max }_{i=1}^d{x}_{i2}\\ [j+x_{j1},j+x_{j2}]\\ \mathrm{otherwise}\end{array}\right)---\left(4\right)$

映射示意图如图2所示，例如，图2(a)中的数据B(0.2，0.7)通过式(3)映射为值1.2。因此，数据经过算法映射后，变成了1维数据，可以用B+树来索引和查询，图2(b)表示查询时需要查询的范围。

步骤3)中主要包含以下内容：

1)超级节点根据映射后的一维数据来构建统计信息。由图2(a)可知，数据都映射到Range(i)＝[i*c，i*c+1]1＝＜i＜＝d)区间内，对每一个i(维度)，分为RangeA(i)＝[i*c，i*c+0.5]和RangeB(i)＝[i*c+0.5，i*c+1]。根据iMinMax的思想，Range(i)的值大部分会分布在区间的两边，因此，取RangeA(i)和RangeB(i)的范围来构成统计信息。比如在图2(a)中，2维的统计信息为：2：(2.15，2.2)，(2.75，2.8)。对节点P，所有维度的信息组合成一个节点统计信息：

2)由于超级节点SP之间连接是一个图结构，为了查询的方便以及避免网络的泛洪，在初始化时，构建一个超级节点网络树，如图3所示。

3)针对窗口查询，为了事先能够判断一个超级节点所在的子树是否含有满足条件的数据，需要对超级节点所在的子树的所有数据做一个统计信息表，用SPST表示此表，并保存在超级节点中，如图3所示。对于叶子节点如C，D，E，SPST只包含一项，就是所有节点P_i(1＝＜i＜＝n)统计信息的并集。针对非叶子节点B，统计信息包含儿子节点的统计信息，以及自己的统计信息，并且最后将这两类信息汇总为B_total，然后将B_total发送给其父亲节点。

步骤4)中查询q被发送到P所在的超级节点。根据存储在超级节点中的数据的统计信息表来判断包含数据的节点P_i，然后将查询发送到包含数据的节点P_i，在P_i上完成查询工作，并返回结果。

步骤5)中当超级节点在内部完成查询时，然后比较SPST，将查询发送给含有数据的儿子节点(也是超级节点，根据图3的网络树)，最后将查询发送给超级节点的父亲节点，由父亲节点来处理剩下的子树查询，最终返回查询结果。