栏目文章

Select

1. 集群环境下分布式索引的实现

翁海星, 宫学庆, 朱燕超, 胡华梁

计算机应用 2016, 36 (1): 1-7. DOI: 10.11772/j.issn.1001-9081.2016.01.0001

摘要（897）

PDF （1303KB）（708）

针对分布式存储系统上使用非主键访问数据带来的性能问题,探讨在分布式存储系统上实现索引的相关关键技术。在充分分析分布式存储特征的基础上,提出了分布式索引设计和实现的关键点,并结合分布式存储系统的特点及相关的索引技术,讨论了索引的组织形式、索引的维护和数据一致性等问题;然后基于如上的分析,选择在分布式数据库系统OceanBase开源版本上,设计和实现分布式索引机制,并通过基准测试工具YCSB进行性能测试。实验结果表明,虽然辅助索引会对系统性能产生影响,但因为充分考虑了系统特征及存储特点,在不同数据规模下,该索引都能够将性能影响控制在5%以内。另外,使用冗余列的方式,能进一步将该索引的性能提升100%。

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

Select

2. 基于概率的大数据查询系统——Probery

伍晋博, 宋杰, 张莉, 鲍玉斌

计算机应用 2016, 36 (1): 8-12. DOI: 10.11772/j.issn.1001-9081.2016.01.0008

摘要（696）

PDF （802KB）（424）

针对大数据环境下完整性查询时间代价消耗过高的问题,提出了一种采用近似完整性查询方法的系统——Probery。Probery所采用的近似完整性查询方法不同于传统的近似查询,其近似性主要体现为数据查全的可能性,是一种新型的数据查询方法。Probery首先将存入系统的数据划分为多个数据分段;然后,根据概率放置模型将各个数据分段的数据存储在分布式文件系统中;最后,对于给定的查询条件,Probery采用一种启发式查询方法进行概率查询。通过与其他主流的非关系型数据管理系统的查询性能进行比较,对Probery进行验证,Probery在损失8%查询完整性的情形下,查询时间较HBase相比节约了51%,较Cassandra相比节约了23%,较MongoDB相比节约了12%,较Hive相比节约了3%。实验结果表明,Probery可以适当地损失查询完整性来提高数据的查询性能,具有较好的通用性、适应性和可扩展性。

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

Select

3. 基于Supersonic的并行分组聚集

张兵, 孙辉, 范旭, 李翠平, 陈红, 王雯

计算机应用 2016, 36 (1): 13-20. DOI: 10.11772/j.issn.1001-9081.2016.01.0013

摘要（499）

PDF （1253KB）（329）

针对在分析型联机分析处理(OLAP)应用中频繁出现的数据密集型操作符——分组聚集耗时较多的问题,提出Cache友好的分组聚集算法对该操作进行性能优化。首先,为充分发挥列存储在数据密集型计算方面的优势,采用基于开源的列存储查询执行引擎Supersonic,并在此之上设计Cache友好的分组聚集算法;其次,为加速查询的执行,使用并行技术,将单线程的分组聚集算法改为多线程并行的分组聚集算法。基于Supersonic设计并实现4种并行分组聚集算法:无共享Hash表并行分组聚集(NSHPGA)算法、表锁共享Hash表并行分组聚集(TLSHPGA)算法、桶锁共享Hash表并行分组聚集(BLSHPGA)算法、节点锁共享Hash表并行分组聚集(NLSHPGA)算法,且在不同的分组势集、不同的线程数的情况下,针对上述4种算法做了多组实验。通过对比3种不同粒度的共享Hash表并行分组聚集算法的加速比,得出NLSHPGA算法在加速比和并发度两方面表现最好,部分查询可达到10倍加速比;通过比较NSHPGA算法和NLSHPGA算法的加速比、Cache miss内存使用等情况,得出NLSHPGA算法在分组势集大于8时,加速比超过NSHPGA算法,并且Cache miss更低,使用的内存更少。

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

Select

4. 压缩数据上的关系代数操作算法

丁鑫哲, 张兆功, 李建中, 谭龙, 刘勇

计算机应用 2016, 36 (1): 21-26. DOI: 10.11772/j.issn.1001-9081.2016.01.0021

摘要（619）

PDF （923KB）（374）

针对在大数据管理中,在压缩的数据上无需解压即可进行相关操作的问题,在数据服从正态分布的前提下,根据列数据存储的特点,提出了一种新的面向列存储的压缩方法——CCA。首先,通过对列数据的长度进行归类;然后,采用抽样的方法获得重复度较高的前缀;最后,使用字典编码进行压缩,提出了列索引(CI)和列实体(CR)作为数据压缩结构来降低大数据存储的空间需求,从而直接有效地在压缩数据上支持选择、投影、连接等基本操作,并实现了基于CCA的数据库原型系统——D-DBMS。理论分析和在1 TB数据上的实验结果表明,该压缩算法能够显著提高大数据的存储效率和数据操作性能,与BAP和TIDC压缩方法相比,在压缩率分别提高了51%、14%;在执行速度上提高了47%、42%。

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

Select

5. 基于划分的增量式字符串相似性连接方法

燕彩蓉, 朱斌, 王健, 黄永锋

计算机应用 2016, 36 (1): 27-32. DOI: 10.11772/j.issn.1001-9081.2016.01.0027

摘要（438）

PDF （890KB）（366）

字符串相似性连接是数据质量管理的基本操作,也是数据价值发现的关键步骤。针对目前已有的方法不能满足面向大数据的增量式处理需求的问题,提出一种面向流式数据的增量式字符串相似性连接方法——Inc-Join,并对方法的索引技术进行了优化。该方法以Pass-Join字符串连接算法为基础,首先,采用字符串划分技术将字符串划分成多个互不相交的子串;然后,建立字符串的反向索引列表并将其作为状态;最后,新增数据只需根据状态进行相似性计算,每次连接操作结束后都对状态进行更新。实验结果表明,Inc-Join方法在不影响连接准确率的同时,有效将长、短字符串重复匹配次数减少为√ n( n是批处理方式的匹配次数)。实验对3种数据集进行处理,发现使用批处理方式进行相似性连接的响应时间是Inc-Join的1至4.7倍,并呈现急剧递增的趋势;而且优化后Inc-Join方法的响应时间最小只占优化前的3/4,并随处理数据的增多所占比例越来越小。同时优化后的Inc-Join不需要保存状态,再一次减小了算法执行的时间和空间开销。

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

Select

6. 基于深度表示模型的移动模式挖掘

陈勐, 禹晓辉, 刘洋

计算机应用 2016, 36 (1): 33-38. DOI: 10.11772/j.issn.1001-9081.2016.01.0033

摘要（422）

PDF （960KB）（499）

针对时空轨迹中位置顺序和时间对于理解用户移动模式的重要性,提出了一种新的用户轨迹深度表示模型。该模型考虑到时空轨迹的特点:1)不同的位置顺序表示不同的移动模式;2)轨迹有周期性并且在不同的时间段有变化。首先,将两个连续的位置点组合成位置序列;然后,将位置序列和对应的时间块组合成时间位置序列,作为描述轨迹特征的基本单位;最后,利用深度表示模型为每个序列训练特征向量。为了验证深度表示模型的有效性,设计实验将时间位置序列向量应用到用户移动模式发现中,并利用Gowalla签到数据集进行了实验评测。实验结果显示提出的模型能够发现"上班""购物"等明确的模式,而Word2Vec很难发现有意义的移动模式。

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

Select

7. 基于Markov模型与轨迹相似度的移动对象位置预测算法

宋路杰, 孟凡荣, 袁冠

计算机应用 2016, 36 (1): 39-43. DOI: 10.11772/j.issn.1001-9081.2016.01.0039

摘要（794）

PDF （939KB）（640）

针对低阶Markov模型预测精度较差,以及多阶Markov模型预测稀疏率高的问题,提出一种基于Markov模型与轨迹相似度(MMTS)的移动对象位置预测算法。该方法借鉴了Markov模型思想对移动对象的历史轨迹进行建模,并将轨迹相似度作为位置预测的重要因素,以Markov预测模型的预测结果集作为预测候选集,结合相似度因素得出最终预测结果。实验结果表明,与 k阶Markov模型相比,该方法的预测性能不会随着训练样本大小及阶数 k的变化受到很大的影响,并且在大幅降低 k阶Markov模型预测稀疏率的同时将预测精度平均提高了8%以上。所提方法不仅解决了 k阶Markov模型的预测稀疏率高及预测精度不足的问题;同时提高了预测的稳定性。

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

Select

8. 基于手机轨迹数据的人口流动分析

孔扬鑫, 金澈清, 王晓玲

计算机应用 2016, 36 (1): 44-51. DOI: 10.11772/j.issn.1001-9081.2016.01.0044

摘要（485）

PDF （1202KB）（568）

随着通信技术的发展和智能手机的普及,运营商基站所采集的大规模手机轨迹数据在城市规划、人口迁移等领域中发挥了重要价值。针对城市人口流动问题,提出一种利用手机轨迹数据的基于轨迹行为特征的人口流动判定(MF-JUPF)算法。首先,可对手机轨迹数据进行数据预处理,以提取用户活动轨迹;然后根据进出城市的行为模式提取重要特征,再根据真实标注数据集合利用多种分类模型进行参数训练;最后,根据模型训练结果判定用户轨迹是否为进出城市行为。所提系统使用MapReduce框架进行数据分析,以提高性能和可扩展性。基于真实数据集合的实验结果表明,对于进出城市的判定,该方法的准确率和召回率可达80%以上,与基于信号消失时长的人口流动判定(SD-JUPF)算法相比,在判定进入城市的准确率上提高了19.0%,召回率提高了13.9%;在判定离开城市的准确率上提高了17.3%,召回率提高了6.1%。相比非过滤算法,根据手机轨迹数据特点进行的数据过滤算法可减少处理时间36.1%以上。理论分析和实验结果表明MF-JUPF方法精度高,可扩展性好,因此对城市规划等领域有重要应用价值。

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

Select

9. 基于贝叶斯模型的多标签分类算法

张洛阳, 毛嘉莉, 刘斌, 吴涛

计算机应用 2016, 36 (1): 52-56. DOI: 10.11772/j.issn.1001-9081.2016.01.0052

摘要（682）

PDF （869KB）（686）

针对二元关联法(BR)未考虑标签之间相关性,容易造成分类器输出在训练集中不存在或次数较少标签的不足,提出了基于贝叶斯模型的多标签分类算法(MLBM)和马尔可夫型多标签分类算法(MMLBM)。首先,建立仿真模型分析BR算法的不足,考虑到标签的取值应由属性置信度和标签置信度共同决定,提出MLBM。其中,通过传统的分类算法计算获得属性置信度,以及通过训练集得到标签置信度。然后,考虑到MLBM在计算属性置信度时必须考虑所有已分类的标签,分类器的性能容易受无关或弱关系的标签影响,所以使用马尔可夫模型简化置信度的计算提出了MMLBM。理论分析和仿真实验表明,与BR算法相比,MMLBM的平均分类精度在emotions数据集上提高约4.8%,在yeast数据集上提高约9.8%,在flags数据集上提高约7.3%。实验结果表明,当数据集中实例的标签基数较大时,相对于BR算法,MMLBM的准确性有较大的提升。

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

Select

10. 基于画面组单元时序控制算法的H.264实时流关键帧预处理

杜聃, 冯丽君, 刘胤田

计算机应用 2016, 36 (1): 57-60. DOI: 10.11772/j.issn.1001-9081.2016.01.0057

摘要（422）

PDF （802KB）（309）

网络带宽特别是上行带宽受限情况下,基于H.264高压缩率的网络音视频通话或视频会议普遍会出现不同程度的丢包现象,从而造成流媒体播放的花屏等质量问题,影响视频通话或视频会议的效果。针对上述问题,提出了基于关键帧预处理的实时流媒体播放质量控制方法。该方法采用单元时序控制算法对视频关键坏帧进行实时侦测和取舍,进而减少花屏情况。使用该方法将降低后处理计算的时空成本,并提高流媒体播放的流畅性。通过原始帧播放、后处理播放、关键帧预处理播放3种处理方法的实验对比,证明基于播放单元时序控制算法的实时流媒体播放器,不但明显提高了播放的流畅性,播放后处理的计算复杂度也降低了40%以上。结果表明,该方法对提高播放质量、减少花屏情况有着突出的效果。

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

栏目文章信息