论文部分内容阅读
传统Top-N查询处理技术尚未融合实体解析,对于具有重复元组的脏数据集,这些技术可能失效。本文给出融合Top-N查询处理和实体解析的五种算法:具有顺序访问和随机访问的TAER算法、限制顺序访问的TAZER算法、仅支持顺序访问的NRAER算法,以及基于学习的LeDer算法和LeMer算法。另外,给出朴素算法作为实验的基准,比较和分析这些算法的性能。
前三种算法不依赖于数据库管理系统(DBMS),而是数据库友好的NoSQL类算法,其索引结构为一些简单的排序列表。对于n维数据集R(tid, A1, A2,…, An)的属性Ai,针对R的所有元组t,将(tid, t[Ai])按属性值t[Ai]排序,得到列表Li。设Q=(q1, q2,…, qn)为一个查询点。算法TAER运用n个列表L1, L2,…, Ln,通过二分查找法定位查询点Q,即确定每个qi在列表Li中的位置,从两个方向找出距离qi较小的元组坐标方向,并以此方向决定有序列表Li顺序访问方向,通过顺序和随机访问得到候选元组,同时进行实时实体解析。算法NRAER同样运用n个列表,定位查询点Q(q1, q2,…, qn);双向搜索查找候选元组。不同的是算法 NRAER 对所有的属性仅进行顺序访问,没有随机访问。算法TAZER运用m个列表L1, L2,…, Lm (1?m 基于学习的算法LeDer运用DBMS,应用学习机制并使用Select-From-Where语句从基础数据库检索候选元组的集合,进而解析候选元组。基于学习的算法LeMer,其基本思想类似于算法 LeDer,但算法 LeMer 从内存中检索候选集。利用学习机制,算法LeDer 和LeMer得到查询点Q的搜索区域S(Q, r),检索出S(Q, r)区域内的元组并将其进行实体解析。
针对低维、中维和高维(2维至120维)数据集进行广泛的实验,运用实验结果对比和分析本文算法的性能,指出各种算法在不同数据集的优势和不足,及其所使用的范围和特征。
前三种算法不依赖于数据库管理系统(DBMS),而是数据库友好的NoSQL类算法,其索引结构为一些简单的排序列表。对于n维数据集R(tid, A1, A2,…, An)的属性Ai,针对R的所有元组t,将(tid, t[Ai])按属性值t[Ai]排序,得到列表Li。设Q=(q1, q2,…, qn)为一个查询点。算法TAER运用n个列表L1, L2,…, Ln,通过二分查找法定位查询点Q,即确定每个qi在列表Li中的位置,从两个方向找出距离qi较小的元组坐标方向,并以此方向决定有序列表Li顺序访问方向,通过顺序和随机访问得到候选元组,同时进行实时实体解析。算法NRAER同样运用n个列表,定位查询点Q(q1, q2,…, qn);双向搜索查找候选元组。不同的是算法 NRAER 对所有的属性仅进行顺序访问,没有随机访问。算法TAZER运用m个列表L1, L2,…, Lm (1?m
针对低维、中维和高维(2维至120维)数据集进行广泛的实验,运用实验结果对比和分析本文算法的性能,指出各种算法在不同数据集的优势和不足,及其所使用的范围和特征。