在大数据时代, 各行业所获得的数据呈现海量、类型多样、价值密度低等特征^[1], 传统的数据管理系统已无法满足当今用户的需求, 为此, Franklin等提出了数据空间概念^[2]。其宗旨是为用户提供尽力而为(Best-effort)的服务, 而索引是实现该目标的基础, 因此研究一种高效的数据空间索引技术具有重要意义。

Dong和Halevy^[3]首次研究了数据空间索引问题, 提出一种混合倒排索引技术以支持结构感知的查询。该技术通过统一索引数据空间中异构数据来支持结构感知的查询, 但容易导致数据空间访问效率低。为此, 基于对两个真实数据场景的观察, Song和Chen^[4]提出了一种基于划分的混合索引技术, 该技术包含水平划分和垂直划分两种策略。Wang等^[5]提出了一种紧凑索引技术, 提高了在个人数据空间中的查询质量。Zhong等^[6]提出了一种MVP索引, 解决了大图环境下已知项的高效检索问题。针对星型SPARQL连接查询中大量的计算开销问题, Du等^[7]提出了一种基于实体模式的索引划分方法。Dittrich等^[8]提出了一种朴素(NAIVE)的索引方法。以上成果均无法高效地支持路径查询。

本文基于iDM模型, 提出了一种基于辅助索引的数据空间索引方法(EIBH), 该方法主要结合EIL索引、B-树索引和二级索引来解决路径查询效率低的问题。

iDM^[8]模型本质上是一种图模型。每个资源视图 V由一个四元组 (η, τ, χ, γ)表示, 其中, η为名词组件; τ为元组组件 (W, T), W=< aj>为资源的属性序列, T=< vj>为W对应的属性值序列; χ为内容组件; γ为组组件(S, Q), S和Q均为资源视图V的相关组件集合, 前者是无序, 而后者是有序的。另外 S⋂Q=⌀。

针对iDM模型, 本课题组已提出过一种高效的数据空间索引方法(EIL)^[9], 以支持数据空间的高效访问。EIL方法主要是通过扩展倒排列表来索引资源视图的各个组件。具体来说:①对 η组件中关键词 k建立索引条目k→ < RSid, {Parentid}> , RSid表示当前视图的标识, {Parentid}表示指向当前视图的所有视图标识; ②对于 τ组件 (W, T),为 aj中关键词 k建立索引条目k→ < RSid, {Parentid}> , 为 vj中关键词 k建立索引条目k//a_j→ < RSid, {Parentid}> ; ③对 χ组件中关键词 k建立索引条目k→ < RSid, {Parentid}> 。尽管该索引能够支持路径查询, 但是查询效率低。下面分析其效率低的原因。

由于是讨论两个索引链表的连接操作, 因此只给出了只有两个关键字和对应链表的例子^[9](见表1)。为了方便表示, 本文将索引进行了倒置。

表1

Table 1

表1(Table 1)

表1 包含两个关键字的扩展倒排链表 Table 1 Extended inverted list including term Keyword1 and Keyword2 Keyword1 Keyword2 Keyword1 Keyword2 < 1, {0}> , < 2, {1, 3}> , < 16, {0}> , < 10, {4, 13}> , < 3, {1}> , < 3, {1, 8}> , < 18, {0}> , < 11, {4, 15}> , < 4, {2}> , < 4, {1, 8}> , < 19, {0}> , < 12, {4, 17}> , < 6, {0}> , < 5, {2, 10}> , < 20, {0}> , < 13, {8}, 15> , < 7, {0}> , < 6, {2, 8}> , < 22, {0}> , < 20, {10, 17}> , < 9, {0}> , < 7, {13, 17}> , < 23, {0}> , < 30, {15}> , < 13, {0}> , < 8, {1, 2, 3}> , < 26, {0}> < 33, {17}> < 15, {2}> , < 9, {3, 10}> ,

表1 包含两个关键字的扩展倒排链表 Table 1 Extended inverted list including term Keyword1 and Keyword2

根据文献^[9], 对于路径查询Keyword1/Keyword2, 处理它需要一步步判断L_Keyword2中的节点的父资源视图是否在L_Keyword1中。例如, 为了判断< 2, {1, 3}> 中的1或3是否与L_Keyword1中的某个节点的RSid相等, 将其与L_Keyword1进行比较。通过比较发现, 1出现在L的节点< 1, {0}> 的 RSid中, 说明< 2, {1, 3}> 符合要求。然后, 判断< 3, {1, 8}> 和< 4, {1, 8}> 是否符合要求。由于1在L_Keyword1中, 所以也符合要求, 通过这样一步步的比较可以判断出L_Keyword2中的哪些资源视图满足要求。显然, 在这个比较过程中, 有大量的重复操作。例如, 在比较< 2, {1, 3}> 时已经知道1在L_Keyword1中, 也就知道< 3, {1, 8}> 和< 4, {1, 8}> 满足要求, 因此不需要再进行比较。从上面的分析中, 可以得出下面两点启示:①当索引链表中不同资源视图的set of parentid存在大量相交元素时, 将会有很多不必要的重复判断工作。②连接过程中有大量的比较操作, 对于海量数据搜索环境, 线性搜索效率低下, 需要一种高效的数据结构来改善查找操作的效率。

本节首先定义了路径查询, 然后给出一个基于辅助索引的路径查询算法。

定义1 路径查询形式如下: “ s1t1s2t2…sktk” ,其中, 除了 tk,每一个 ti都是一个标记或者资源视图名称组件, tk除了 ti的情况外, 还可能是元组组件中的属性和内容组件中的关键字; 每一个 si是“ /” , 表示两个资源视图的直接相关关系。

例如, 搜索“ section/title/web” , 将返回路径section/title下面包含关键字“ web” 的资源视图; 其中, title是一个资源视图的名称组件, 则web就是这个资源视图内容组件中的关键字。查询“ member/name” , 表示搜索返回所有实验室成员的名字。member是一个资源视图的名称, name即为这个资源视图的属性。

在处理路径查询时, 其主要思想是:首先将其“ s1t1s2t2…sktk” 进行分解, 得到关键字序列( t1, t2, …, tk); 然后对分解后的每个关键字 t搜索倒排列表得到其辅助结构; 最后进行连接。下面给出了具体的路径查询算法。

算法1 路径查询

输入:EIBH索引, 它由包含EIL、B-树索引和H索引组成; 用户查询Q=“ t₁s₁t₂…s_k-1t_k” , k≥ 2。

输出:返回资源视图集合。

(1) set up a stack, split the string “ t₁s₁t₂…s_k-1t_k” into “ t₁t₂…t_k” and Push these keywords from right to left into the Stack.

(2) Stack pop two items key1 and key2.

(3)Perform a keyword search for key1 and key2 in index EIBH.

If exists, attain B_key2 and H_key1.

(4)join B_key2 and H_key1, and the result is a set of RSid that his parented exists in B_key2,

construct a B-tree for the set, denote B_temp.

(5)While (Statck is't empty)

1)get the top item key of Stack;

2)Perform a keyword search for key. If exists, attain H_key, Else, return null;

3)join B_temp and H_key, and the result is a set of RSid that his parented exists in B_temp,

4)and use B_temp to represent the new B-tree that construct from the new set;

(6)the final B_temp includes all the resource view ids satisfying the user query

(7)Return all resource view ids in B_temp.

下面以表1中的例子来演示路径查询“ Keyword1/Keyword2” 的处理过程。图4给出了表1对应的数据空间索引EIBH例子。它共包含扩展倒排索引EIL、结合B-树索引和二级索引的混合辅助索引两大部分。

图4

Fig.4

	Figure Option ViewDownloadNew Window
	图4 表1对应的EIBH索引实例Fig.4 EIBH example with respect to Table 1

下面以表1中使用的例子来演示路径查询“ Keyword1/Keyword2” 的处理过程。图4给出了表1对应的数据空间索引EIBH例子。它共包含扩展倒排索引EIL、结合B-树索引和二级索引的混合辅助索引两大部分。

例如, 对于关键字Keywod1来说, 为其建立了B_Keyword1索引和H_Keyword1索引。由于空间限制, 后面讨论中不涉及H_Keyword1索引, 因此, 没有给出H_Keyword1索引的详细内容。同样, 没有给出B_Keyword2的详细内容。

对于查询:Keyword1/Keyword2, 此查询的目的是查找资源视图组件名称为Keyword2且其父资源视图组件名称为Keyword1的资源视图, 或资源视图组件名称为Keyword1且其元组组件中包含属性Keyword2的资源视图。

下面分析如何使用辅助索引处理这个查询。

Step1 建立一个栈Stack, 用来存储关键字。

Step2 首先将路径查询Keywrod1/Keyword2进行分解, 得到关键字Keyword1和Keyword2, 将关键字Keyword2和Keyword1依次压入栈中; 注意, 路径表达式中关键字的进栈顺序是从右到左。

Step3 使用Stack的pop功能, 弹出栈顶的两个元素, 记为Keyword1和Keyword2。接下来搜索扩展倒排列表EI中的关键字列, 得到Keyword1对应的B_Keyword1, Keyword2和对应的H_Keyword2。

Step4 创建一个临时B-树, 记为B_temp。

Step5 连接H_Keyword2和B_Keyword1, 顺序读取H_Keyword2中的每一个ID, 对于读取的每一个ID, 通过搜索B_Keyword1判断是否存在, 如果存在, 则将与ID相对应的子资源视图数组中的资源视图ID插入到B_temp中; 这一步详细过程如下:

读取1, 搜索B_Keyword1, 存在, 则将2, 3, 4, 8逐个插入到B_temp中;

读取2, 搜索B_Keyword1, 不存在;

读取3, 搜索B_Keyword1, 存在, 则将2, 8, 9逐个插入到B_temp中;

读取4, 搜索B_Keyword1, 存在, 则将10, 11, 12逐个插入到B_temp中;

读取8, 搜索B_Keyword1, 不存在;

读取10, 搜索B_Keyword1, 不存在;

读取13, 搜索B_Keyword1, 存在, 则将7, 10逐个插入到B_temp中;

读取15, 搜索B_Keyword1, 存在, 则将11, 13, 30逐个插入到B_temp中;

读取17, 搜索B_Keyword1, 不存在。

Step6 如果栈不为空, 弹出一个栈顶元素key, 搜索EI中的关键字列, 得到key对应的H_key, 接着执行Step7; 如果栈为空, 跳转到Step9。

Step7 创建一颗B_new的新B-树, 连接H_key和B_temp, 顺序读取H_key中的每一个ID, 对于读取的每一个ID, 通过搜索B_temp判断是否存在, 如果存在, 则将与ID相对应的子资源视图数组中的资源视图ID插入到B_new中; H中的每一个ID都判断完后, 删除旧的B_temp, 将B_new改为B_temp。

Step8 重复Step6。

Step9 遍历B_temp, 得到满足条件的资源视图编号(2, 3, 4, 8, 9, 10, 11, 12, 7, 13, 30), 输出每个资源视图编号对应的资源视图。

研究了基于辅助索引的数据空间索引方法, 以支持高效路径查询。针对索引连接存在的问题, 构建了结合B-树索引和二级索引的混合辅助索引。实验结果表明该方法是切实有效的, 且明显优于已有的方法。