新闻组数据仓库管理与选择算法解析

### 新闻组数据仓库管理与选择算法解析 #### 1. 引言 在新闻组管理系统中，高效地维护和选择新闻组是至关重要的。一方面，需要处理新文章的到来并确定其应插入的新闻组；另一方面，要从众多新闻组中选择合适的进行预维护（物化），以平衡存储资源和查询响应时间。本文将详细介绍独立搜索树算法用于新闻组维护，以及新闻组选择问题的相关内容。 #### 2. 新闻组维护问题 ##### 2.1 点定位问题现状 目前在设计最优主存算法解决点定位问题上已有大量工作，但在设计具有最优最坏情况边界的二级存储算法方面尚无相关报道。而在范围搜索的对偶问题上，有一些近期的研究成果。现有的用于点定位问题的二级存储数据结构，如各种R树、单元树、hB树等，在常见空间数据库问题中具有良好的平均情况性能，但缺乏理论上的最坏情况边界。 ##### 2.2 独立搜索树算法 为解决新闻组维护问题，提出了独立搜索树算法，该算法在I/O和CPU方面具有高效性。下面分情况详细介绍该算法的实现。 ###### 2.2.1 超矩形新闻组维护 考虑n个新闻组$V_1, \cdots, V_n$，每个新闻组$V_i$定义为$V_i = \bigwedge_{j\in I_i}(f_{ij})$，其中$f_{ij}$形式为$(A_j \in c_{ij})$，$c_{ij}$是有序域$D_j$上的一个区间。使用的数据结构由d个外部段树结构$T_1, T_2, \cdots, T_d$组成，树$T_j$存储区间$\{c_{ij} | j \in I_i, 1 \leq i \leq n\}$。 具体计算受影响新闻组的步骤如下： 1. 维护一个大小为n的数组$I$，$I[i]$初始化为$|I_i|$，即新闻组$V_i$的索引集大小。 2. 当一篇文章$m = (b_1, b_2, \cdots, b_d)$到达时，在外部段树$T_j$中搜索包含$b_j$的区间，对于所有$1 \leq j \leq d$。 3. 在段树$T_j$中搜索$b_j$时，若区间$c_{ij}$被命中（即$b_j \in c_{ij}$），则将$I[i]$减1。 4. 若$I[i]$降为0，则将对应的新闻组$V_i$报告为受影响的新闻组，即文章$m$需要插入的新闻组。 下面是该过程的mermaid流程图： ```mermaid graph TD; A[文章m到达] --> B[初始化数组I]; B --> C[遍历j从1到d]; C --> D[在Tj中搜索包含bj的区间]; D --> E{区间cij被命中?}; E -- 是 --> F[I[i]减1]; E -- 否 --> C; F --> G{I[i]是否为0}; G -- 是 --> H[报告新闻组Vi为受影响新闻组]; G -- 否 --> C; C --> I[结束遍历]; ``` ###### 2.2.2 处理“包含”运算符 对于非结构化文本属性（如主题），新闻组定义可能使用“包含”运算符，即$f_{ij}$可以是$(A_j \text{ contains } s_{ij})$。为处理这种情况，使用字典树数据结构代替段树。 具体操作如下： 1. 给定字符串集合$S_j = \{s_{ij} | j \in I_i\}$和查询字符串$b_j$，构建一个基于$S_j$的字典树。 2. 对于查询$b_j$，在字典树中搜索其每个后缀的超字符串匹配。 3. 搜索可以在$(|b_j|^2 + l)$次字符比较内完成，其中$|b_j|$是查询字符串$b_j$的大小，$l$是报告的字符串数量。字典树的空间需求为$k|\Sigma|$个字符，用于存储k个字符串，$|\Sigma|$是字母表的大小。 以下是该过程的表格总结： |步骤|操作| |----|----| |1|构建基于$S_j$的字典树| |2|对查询$b_j$，搜索其每个后缀的超字符串匹配| |3|完成搜索并记录匹配结果| ###### 2.2.3 处理正文属性的选择条件 对于新闻组定义中可能使用的正文属性（如$A_d$）的“相似阈值”谓词，即$f_{id}(A_d) = \bigvee_{k}(C(A_d, B_{ik}, T_{ik}))$，其中$C(A_d, B_{ik}, T_{ik})$表示$(A_d \text{ similar-to } B_{ik} \text{ with-threshold } T_{ik})$。 实现步骤如下： 1. 构建倒排列表$L_1, L_2, \cdots, L_p$，$p$是字典（相关单词集合）的大小。每个典型文章正文$B_{ik}$用相似度向量$B_{ik} = (w_{ik1}, \cdots, w_{ikp})$表示，$w_{ikl}$是$B_{ik}$中第l个单词的权重。 2. 定义所有不同相似度向量的集合为$W_1, W_2, \cdots, W_m$。倒排列表$L_l$记录所有第l个单词权重非零的相似度向量$W_j$。 3. 对于每个相似度向量$W_j$，维护一个列表$R_j = \{(i, T_{ik})|W_j = B_{ik}\}$，按阈值升序存储，同时维护一个点积整数$P_j$（初始化为0）。 4. 当新文章$m = (b_1, b_2, \cdots, b_d)$到达，其正文属性值$b_d = (w_{m1}, w_{m2}, \cdots, w_{mp})$是表示文章正文的单词向量。对于$j < d$的每个$b_j$，在外部段树或字典树$T_j$中搜索，相应地减少$I$中的条目。 5. 为计算$f_{id}$，对于新文章单词向量$b_d$中的每个非零值$w_{ml}$，顺序扫描倒排列表$L_l$。对于$L_l$中的每个$W_j$，将与$W_j$关联的点积值$P_j$增加$(w_{jl} * w_{ml})/|b_d||W_j|$。 6. 扫描完所有所需的倒排列表后，对于每个$W_j$，扫描其列表$R_j$，对于每个$(i, T_{ik}) \in R_j$，若$T_{ik} \leq P_j$，则将$I[i]$减1