栏目文章

Select

1. 轻量级大数据运算系统Helius

丁梦苏, 陈世敏

计算机应用 2017, 37 (2): 305-310. DOI: 10.11772/j.issn.1001-9081.2017.02.0305

摘要（986）

PDF （943KB）（903）

针对Spark数据集不可变，以及Java虚拟机（JVM）依赖环境引起的代码执行、内存管理、数据序列化/反序列化等开销过多的不足，采用C/C++语言，设计并实现了一种轻量级的大数据运算系统——Helius。Helius支持Spark的基本操作，同时允许数据集整体修改；同时，Helius利用C/C++优化内存管理和网络传输，并采用stateless worker机制简化分布式计算平台的容错恢复过程。实验结果显示：5次迭代中，Helius运行PageRank算法的时间仅为Spark的25.12%~53.14%，运行TPCH Q6的时间仅为Spark的57.37%；在PageRank迭代1次的基础上，运行在Helius系统下时，master节点IP接收和发送数据量约为运行于Spark系统的40%和15%，而且200 s的运行过程中，Helius占用的总内存约为Spark的25%。实验结果与分析表明，与Spark相比，Helius具有节约内存、不需要序列化和反序列化、减少网络交互以及容错简单等优点。

参考文献 | 相关文章 | 多维度评价

Select

2. 面向海量交通数据的HBase时空索引

房俊, 李冬, 郭会云, 王嘉怡

计算机应用 2017, 37 (2): 311-315. DOI: 10.11772/j.issn.1001-9081.2017.02.0311

摘要（999）

PDF （814KB）（739）

针对HBase无法直接建立时空索引所带来的交通数据查询性能问题，基于HBase行键设计了面向海量交通数据的HBase时空索引。首先利用Geohash降维方法将二维空间位置数据转化为一维编码，再与时间维度进行组合；然后根据组合顺序的不同，提出了四种结构模型，分别讨论了模型的具体构成以及交通数据查询中的适应面；最后提出了相应的时空索引管理算法及基于Hbase时空索引的交通数据查询方法。通过实验验证了提出的HBase时空索引结构能有效提升海量交通数据的区域查询性能，并比较了四种时空索引结构在不同数据规模、不同查询半径以及不同时间范围的查询性能，量化验证了不同索引结构在交通数据查询中的适应场景。

参考文献 | 相关文章 | 多维度评价

Select

3. 基于差分隐私的频繁序列模式挖掘算法

李艳辉, 刘浩, 袁野, 王国仁

计算机应用 2017, 37 (2): 316-321. DOI: 10.11772/j.issn.1001-9081.2017.02.0316

摘要（1094）

PDF （1179KB）（853）

针对当数据集含有敏感信息时，直接发布频繁序列模式本身及其支持度计数都有可能泄露用户隐私信息的问题，提出一种满足差分隐私（DP）的频繁序列模式挖掘（DP-FSM）算法。该算法利用向下封闭性质生成候选序列模式集，基于智能截断方法从候选模式中挑选出频繁的序列模式，最后采用几何机制对所选出模式的真实支持度添加噪声进行扰动。另外，为了提高挖掘结果的可用性，设计了一个阈值修正的策略来减小挖掘过程中的截断误差和传播误差。理论分析证明了该算法满足ε-差分隐私。实验结果表明了该算法在拒真率（FNR）和相对支持度误差（RSE）两个指标上明显低于对比算法PFS²，有效地提高了挖掘结果的准确度。

参考文献 | 相关文章 | 多维度评价

Select

4. 领域驱动的高效用co-location模式挖掘方法

江万国, 王丽珍, 方圆, 陈红梅

计算机应用 2017, 37 (2): 322-328. DOI: 10.11772/j.issn.1001-9081.2017.02.0322

摘要（561）

PDF （1053KB）（609）

空间并置（co-location）模式是指其实例在空间邻域内频繁共现的空间特征集的子集。现有的空间co-location模式挖掘的有趣性度量指标，没有充分地考虑特征之间以及同一特征的不同实例之间的差异；另外，传统的基于数据驱动的空间co-location模式挖掘方法的结果常常包含大量无用或是用户不感兴趣的知识。针对上述问题，提出一种更为一般的研究对象——带效用值的空间实例，并定义了新的效用参与度（UPI）作为高效用co-location模式的有趣性度量指标；将领域知识形式化为三种语义规则并应用于挖掘过程中，提出一种领域驱动的多次迭代挖掘框架；最后通过大量实验对比分析不同有趣性度量指标下的挖掘结果在效用占比和频繁性两方面的差异，以及引入基于领域知识的语义规则前后挖掘结果的变化情况。实验结果表明所提出的UPI度量是一种兼顾频繁和效用的更为合理的度量指标；同时，领域驱动的挖掘方法能有效地挖掘到用户真正感兴趣的模式。

参考文献 | 相关文章 | 多维度评价

Select

5. 基于中医方剂数据库的Top-Rank- k频繁模式挖掘算法

秦琦冰, 谭龙

计算机应用 2017, 37 (2): 329-334. DOI: 10.11772/j.issn.1001-9081.2017.02.0329

摘要（775）

PDF （854KB）（500）

为降低中医（TCM）方剂频繁模式挖掘过程中对经验参数的依赖，提高挖掘结果的准确性，针对中医方剂的数据特点，提出一种基于带权无向图的Top-Rank-k频繁模式挖掘算法。该算法可以直接挖掘出频繁k-itemset（k≥3）而无需产生1-itemset和2-itemset，并随之快速回溯到核心药物组合的频繁项集所对应的方剂信息；此外，采用一种动态位向量（DBV）的压缩机制对无向图中边的权重进行压缩存储，以有效地提高算法的空间存储效率。分别对中医方剂数据集、真实数据集（Chess、Pumsb和Retail）和合成数据集（T10I4D100K和Test2K50KD1）进行测试和比较，结果表明该算法与iNTK和BTK相比具有更高的时间和空间效率，而且也可以应用于其他类型的数据集。

参考文献 | 相关文章 | 多维度评价

Select

6. 基于多样化top- k shapelets转换的时间序列分类方法

孙其法, 闫秋艳, 闫欣鸣

计算机应用 2017, 37 (2): 335-340. DOI: 10.11772/j.issn.1001-9081.2017.02.0335

摘要（711）

PDF （920KB）（581）

针对基于shapelets转换的时间序列分类方法中候选shapelets存在较大相似性的问题，提出一种基于多样化top-k shapelets转换的分类方法DivTopKShapelet。该方法采用多样化top-k查询技术，去除相似shapelets，并筛选出最具代表性的k个shapelets集合，最后以最优shapelets集合为特征对数据集进行转换，达到提高分类准确率及时间效率的目的。实验结果表明，DivTopKShapelet分类方法不仅比传统分类方法具有更高的准确率，而且与使用聚类筛选的方法（ClusterShapelet）和shapelets覆盖的方法（ShapeletSelection）相比，分类准确率最多提高了48.43%和32.61%；同时在所有15个数据集上均有计算效率的提升，最少加速了1.09倍，最高可达到287.8倍。

参考文献 | 相关文章 | 多维度评价

Select

7. 路网中位置不确定的二元反 kNN查询

徐伟, 李文根, 张毅超, 关佶红

计算机应用 2017, 37 (2): 341-346. DOI: 10.11772/j.issn.1001-9081.2017.02.0341

摘要（613）

PDF （877KB）（523）

针对路网限制和物体位置的不确定性，提出了路网中位置不确定的二元反kNN查询（PBRkNN），旨在查找一组位置不确定的点，使得每个不确定点的kNN包含给定查询点的概率大于一个阈值。为了解决该问题，首先提出一种基于Dijkstra进行剪枝处理的基本算法，即PE算法；接着在PE算法的基础上通过预处理计算出每个点的kNN从而加快查询速度，即PPE算法；而为了进一步减小PPE算法中范围查询的开销，提出PPEE算法，利用网格索引来索引范围查询中要查询的不确定空间点，从而提升算法的效率。最后，在北京和加州路网数据集上进行了大量实验，结果表明通过一些预处理的策略确实可以有效地处理路网中位置不确定的二元反kNN查询。

参考文献 | 相关文章 | 多维度评价

Select

8. 基于查询概率的位置隐私保护方法

赵大鹏, 宋光旋, 靳远远, 王晓玲

计算机应用 2017, 37 (2): 347-351. DOI: 10.11772/j.issn.1001-9081.2017.02.0347

摘要（807）

PDF （1008KB）（644）

现有的隐私保护技术较少考虑到查询概率、map数据、信息点（POI）语义等边信息，攻击者可以将边信息与位置数据相结合推断出用户的隐私信息，为此提出一种新的方法ARB来保护用户的位置隐私。该方法首先把空间划分为网格，根据历史查询数据计算出处于不同网格区域的用户提交查询的概率；然后结合相应单元格的查询概率来生成用户匿名区域，从而保护用户的位置隐私信息；最后采用位置信息熵作为隐私保护性能的度量指标。在真实数据集上与已有的两种方法进行对比来验证隐私保护方法的性能，结果显示该方法具体有较好的隐私保护效果和较低的时间复杂度。

参考文献 | 相关文章 | 多维度评价

Select

9. 高效的多关键词匹配最优路径查询算法KSRG

金鹏飞, 牛保宁, 张兴忠

计算机应用 2017, 37 (2): 352-359. DOI: 10.11772/j.issn.1001-9081.2017.02.0352

摘要（541）

PDF （1293KB）（575）

为改进基于关键词的最优路径查询算法，在大规模图以及多查询关键词下复杂度过高与可扩展性不足的缺陷，依据查询关键词序列构建候选路径的策略提出一种高效查询算法。该算法在路径构建过程中优先满足查询关键词的全包含条件，以关键词引导下的路径拓展替代盲目的邻边拓展，从而高效地构建候选路径；通过变量缩放与无效路径裁剪，将问题求解复杂度由阶乘级转化为多项式级，进一步降低算法复杂度，提升可扩展性。通过四组图数据集下的实验，验证了算法在查询效率与可扩展性上的提升。

参考文献 | 相关文章 | 多维度评价

栏目文章信息