Please wait a minute...
ISSN 1000-1239 CN 11-1777/TP

当期目录

2011年 第48卷 第10期    出版日期:2011-10-15
论文
基于MB-LDA模型的微博主题挖掘
张晨逸, 孙建伶, 丁轶群,
2011, 48(10):  1795-1802. 
摘要 ( 1261 )   HTML ( 17)   PDF (2085KB) ( 1632 )  
相关文章 | 计量指标
随着微博的日趋流行,Twitter等微博网站已成为海量信息的发布体,对微博的研究也需要从单一的用户关系分析向微博本身内容的挖掘进行转变.在数据挖掘领域,尽管传统文本的主题挖掘已经得到了广泛的研究,但对于微博这种特殊的文本,因其本身带有一些结构化的社会网络方面的信息,传统的文本挖掘算法不能很好地对它进行建模.提出了一个基于LDA的微博生成模型MB-LDA,综合考虑了微博的联系人关联关系和文本关联关系,来辅助进行微博的主题挖掘.采用吉布斯抽样法对模型进行推导,不仅能挖掘出微博的主题,还能挖掘出联系人关注的主题.此外,模型还能推广到许多带有社交网络性质的文本中.在真实数据集上的实验表明,MB-LDA模型能有效地对微博进行主题挖掘.
基于计数的数据流频繁项挖掘算法
祝然威 王 鹏 刘马金
2011, 48(10):  1803-1811. 
摘要 ( 561 )   HTML ( 2)   PDF (1963KB) ( 594 )  
相关文章 | 计量指标
挖掘数据流的频繁项已受到广泛关注,经典的频繁项挖掘算法尽管能够比较好地找到频繁项,但对频繁项频数的估计往往存在较大误差.SRoEC(segment rotative efficient count),SReEC(segment reserve efficient count)和RFreq(reserve frequent)算法针对该问题,继承基于计数的算法思想,将计数器进行划分并定义相应的操作,以期提高频数统计准确度并减小“噪音”影响.实验和数据分析表明,这些算法不仅能够保证频数超过阈值的数据项都能被找到,而且大大提高了频繁项频数统计的准确性.在同样空间代价下,算法无论在模拟数据集和真实数据集实验中,都表现出较高的频数准确率、较低的频数偏差率和较高的频数保有率,尤其是数据分布较平缓时,算法优势更加明显.
一种局部相关不确定数据库快照集合上的概率频繁最近邻算法
苗东菁 石胜飞 李建中
2011, 48(10):  1812-1822. 
摘要 ( 327 )   HTML ( 0)   PDF (2885KB) ( 548 )  
相关文章 | 计量指标
局部相关空间不确定数据越来越受到许多实际应用的关注.提出了一种新颖的定义在不确定数据库的多个快照上的概率频繁近邻查询,目的是在多个快照数据上找到以一定概率频繁成为查询点最近邻的那些对象.应用现有的基于传统数据和基于不确定数据上的近邻查询算法直接处理这种查询会产生昂贵的开销.为了很好地解决这一问题,提出了一般的处理框架,其中包括相应的基于切尔诺夫界的过滤方法,以及对于概率质量函数的动态规划算法.给出了分别作用于两个阶段的两个过滤方法.在第1阶段,利用切尔诺夫界的上界推广形式可以过滤大量的候选目标,之后在第2阶段,利用切尔诺夫界的标准形式来进一步过滤候选目标.还讨论了用于处理扩展查询的动态规划算法以及相应的过滤条件.最后,在人工的和真实的数据上都进行了充分的实验,并验证了给出算法的有效性,为进一步的研究工作奠定了基础.
TrSVM:一种基于领域相似性的迁移学习算法
洪佳明 印 鉴 黄 云 刘玉葆 王甲海
2011, 48(10):  1823-1830. 
摘要 ( 768 )   HTML ( 5)   PDF (1417KB) ( 1131 )  
相关文章 | 计量指标
迁移学习是对传统监督学习的扩展,试图利用其他相关领域中的现存数据来帮助完成当前领域的学习任务. 对于归纳式迁移学习算法,当目标领域只有少量数据时,已有的算法容易受到选择性偏差的影响,不能充分发挥相关领域数据的作用. 为解决该问题,提出一种利用领域相似性的新途径:通过定义领域弱相似性的概念,将相似性的约束与目标分类器联系起来,能在训练过程中有效利用相关领域的大量数据,设计出一种基于支持向量机的迁移学习算法TrSVM,并给出求解过程. 在大量数据集上的实验结果表明了新算法的有效性.
一种新的高效图聚集算法
尹 丹 高 宏 邹兆年
2011, 48(10):  1831-1841. 
摘要 ( 699 )   HTML ( 0)   PDF (2148KB) ( 512 )  
相关文章 | 计量指标
图聚集是将一个大规模的图用简洁的并能有效反映原始图的结构和属性信息的小规模图来表示的技术.图聚集在图数据管理、分析和可视化中发挥着重要作用.图聚集方面现有研究结果还很少,也很不系统.其主要不足之处是:1)算法依赖于具体应用;2)算法仅考虑了图的某方面信息,如结构信息或属性信息;3)算法对用户提供的交互和反馈信息的约束很强.针对现有图聚集算法存在的主要不足,提出一种有向图新型图聚集算法,该算法采用一种新的聚集图质量函数,全面刻画了聚集图多样性、覆盖性、简洁性和实用性.该算法使用LSH(locality sensitive Hashing)技术和基于熵的划分技术,保证了聚集图的质量.在真实数据集上进行了大量的实验,验证了算法的有效性.
不确定数据流上的概率反轮廓查询处理
白 梅, 信俊昌, 东 韩, 王国仁,
2011, 48(10):  1842-1849. 
摘要 ( 356 )   HTML ( 1)   PDF (1541KB) ( 419 )  
相关文章 | 计量指标
反轮廓查询在制定有效的市场决策方面具有重要的作用,随着数据流特征和不确定性的表现日益明显,不确定数据流上概率反轮廓查询已经成为一个新的研究课题.为了高效解决不确定数据流上概率反轮廓查询问题,首先,通过对实际应用需求进行分析,提出了不确定数据流上概率反轮廓查询的定义,并根据相关概念,提出了不确定数据流上概率反轮廓查询的索引模型;其次,通过对不确定数据流上概率反轮廓的性质进行深入分析,提出了一种新颖高效的基于R-tree的不确定数据流上概率反轮廓查询算法RT2RS,该算法运用了高效的剪枝策略,避免了大量的无效运算;最后,通过大量的仿真实验对RT2RS性能进行了验证.实验结果表明,RT2RS是解决不确定数据流上概率反轮廓查询的有效方法,大大减少了不确定数据流上概率反轮廓查询的运行时间,能够满足实际应用需求.
不确定图上的kNN查询处理
张应龙, 李翠平, 陈 红, 杜凌霞,
2011, 48(10):  1850-1858. 
摘要 ( 781 )   HTML ( 0)   PDF (1428KB) ( 866 )  
相关文章 | 计量指标
在现实中的许多领域产生大量不确定的图结构的数据,例如分子化合物、蛋白质交互网络等.同时现实中有很多应用例如推荐系统中的推荐过滤、欺诈检测和社会网络的链接预测等,需要查询给定节点的k个最相似节点,针对这一问题,提出了用基于SimRank度量的方法来求解.由于图的动态演变和不确定性导致用现有的SimRank计算方法求k个最近邻的代价昂贵,因此提出一个有效算法,在保证一定准确性的前提下,通过引入路径阈值,算法只需考虑查询点的邻居区域无需考虑整个图从而达到明显的剪枝效果,该方法在确定图和不确定图上都可以适用. 在此基础上为了进一步提高效率,算法在不确定图上引入采样技术.最后从理论、实验说明验证了算法的高效性和有效性.
多时间序列k'/k-支配Skyline查询处理
徐亚军, 王朝坤, 施 炜, 潘 鹏, 魏冬梅,
2011, 48(10):  1859-1870. 
摘要 ( 507 )   HTML ( 1)   PDF (2209KB) ( 355 )  
相关文章 | 计量指标
时间序列是各个领域中大量存在的一类数据,有着极广泛的应用.多时间序列是其中常见的一种数据类型,它从多个角度以单时间序列的形式去描述同一个对象.目前关于时间序列的研究主要集中于单时间序列,而多时间序列的研究工作则相对较少,如多时间序列的查询处理等,但是在实际生活中多时间序列的查询却有着非常广泛的应用.首先定义了多时间序列的支配关系,然后在此基础上给出多时间序列k'/k-支配Skyline查询的定义,并提出了GMS和GMI两种查询算法,对算法的正确性和复杂性也进行了证明和分析.合成数据和真实数据上的大量实验表明,两种算法都可以得到较好的查询结果,而GMI算法的查询效率较GMS算法有很大程度地提升.
面向不确定图的k最近邻查询
张 旭 何向南 金澈清 周傲英
2011, 48(10):  1871-1878. 
摘要 ( 556 )   HTML ( 2)   PDF (1308KB) ( 924 )  
相关文章 | 计量指标
生物网络、社会网络、交际网络等复杂的网络被广泛的研究,由于数据抽出时引入的噪声和错误使这些数据具有不确定性,因此可以对这些应用使用不确定图模型建模,k最近邻查询问题是查询一个图上的距离某个特定点最近的k个邻居节点的问题,它是不确定图上的一个基础问题.设计了一个解决不确定图上最近邻问题的框架,首先定义了一种新颖的不确定图上的k最近邻查询,然后提出了针对该查询的一般处理算法,同时对该算法进行了优化,使算法效率得到极大提高.理论分析和实验结果表明提出的算法能够高效地处理不确定图上的k最近邻查询.
一个基于图的音乐数据模型与查询语言及其实现
欧晓平 王朝坤 彭 卓 仇 萍 白易元
2011, 48(10):  1879-1889. 
摘要 ( 575 )   HTML ( 0)   PDF (1832KB) ( 712 )  
相关文章 | 计量指标
图数据模型广泛应用于各种具有复杂关联数据的领域.针对现有音乐数据模型与查询语言在功能上的缺陷,首先提出了一个基于图的音乐数据模型Gra-MM,用图数据模型对复杂音乐数据进行建模,定义了图逻辑数据结构以及相关的图代数操作,然后给出了建立在Gra-MM之上的音乐数据查询语言Gra-MQL,定义了查询语言的BNF定义.Gra-MQL能够较好地处理音乐数据之间的复杂关联,同时具有音乐元数据检索和音乐内容数据检索能力,从而满足用户对音乐数据不同层次的查询需求,克服了传统图数据查询语言对复杂关联数据的表达能力有限、不能直接应用于音乐内容检索等不足.最后对实现的音乐数据库原型系统进行了介绍,对原型系统进行测试并给出实验数据,证明了模型以及查询语言的可行性.
关系数据库上基于元组组合的关键字查询
陶 岳 何震瀛 张家琪
2011, 48(10):  1890-1898. 
摘要 ( 407 )   HTML ( 1)   PDF (1572KB) ( 506 )  
相关文章 | 计量指标
在传统的关系数据库上进行关键字查询已经成为近来数据库领域的研究热点,现有的工作都是以单个元组作为结果单元来返回.为了满足用户对于返回多元组的要求,提出了基于元组组合的关键字查询的概念,并通过返回元组组合来响应查询.通过对问题的分析得到了一系列启发式剪枝策略,设计了一个综合的优化算法.通过一系列真实数据集和人工数据集上的实验,验证了优化算法在绝大部分情况下比最初的算法在性能上有了显著的提高.
MANET中基于缓存的移动数据查询处理算法的研究
张艳卿 李金宝 郭龙江
2011, 48(10):  1899-1907. 
摘要 ( 307 )   HTML ( 0)   PDF (1615KB) ( 385 )  
相关文章 | 计量指标
针对MANET环境中带宽有限、能量有限、存储有限和链路频繁的断接性等特点,提出了基于缓存的移动数据查询问题,证明该问题是NP完全问题,并给出一个多项式时间的近似算法,即最大节点新覆盖数据算法MD.该算法采用贪心策略,查询新覆盖数据量最大的节点,减少了查询次数,并最大限度地减少了网络中的传输时延.然后在MD算法的基础上,同时考虑了节点新覆盖数据量和链路服务质量问题,提出了一种改进的高效的启发式算法,即基于最大节点DD值的算法MDD,有效地减少了能量消耗,最小化数据传输时延,提高了网络的吞吐量.理论分析及实验结果表明提出的数据查询算法能够充分利用缓存节点的数据信息,较好地完成数据查询工作,有效地减少数据收集时延,提高查询效率.
面向实时定位系统的位置区域索引
郭 超 李 坤 王永炎 刘胜航 王宏安
2011, 48(10):  1908-1917. 
摘要 ( 496 )   HTML ( 0)   PDF (1617KB) ( 341 )  
相关文章 | 计量指标
在移动应用领域中,移动对象实时位置的区域查询在整个系统的分析、决策、预测等方面具有重要的作用.采用射频识别技术进行定位识别的实时定位系统具有对象分布区域化、不同子区域对象分布密度不均匀等特点.基于这些特点,提出了一种新的面向实时定位系统的区域索引机制,用以提高移动对象实时位置的区域查询的性能.该索引机制根据系统中对象的分布情况进行区域划分,利用R树对划分区域进行索引,并根据每个划分子区域对象的分布密度,用不同密度的网格索引位于该区域内部的对象的位置;同时进一步对提出的索引结构进行缓存感知的优化.实验结果表明,当对象分布不均时,该索引具有比R树和网格更优的区域查询性能,同时保持了良好的更新性能.
OAFTL:一种面向企业级应用的高效闪存转换层处理策略
綦晓颖, 汤 显, 梁智超, 孟小峰,
2011, 48(10):  1918-1926. 
摘要 ( 540 )   HTML ( 0)   PDF (1645KB) ( 330 )  
相关文章 | 计量指标
基于NAND闪存的存储设备通过引入闪存转换层来对闪存芯片进行封装,使得闪存存储设备像普通块设备一样使用.闪存转换层算法的性能很大程度上决定了闪存设备的存储性能,已有方法尽管可以在嵌入式环境下正常工作,但当应用到随机访问频繁的企业级应用环境中时存在访问性能低的问题.提出了一种面向企业级应用的闪存转换层算法OAFTL,该算法基于页级地址映射,根据访问操作的类型来组织映射项信息,通过为映射页保留日志信息来缓冲频繁修改的映射信息,以提高闪存读、写性能.实验结果表明,提出的OAFTL算法能够有效地适应企业级工作负载,同已有方法相比,综合读写性能提升了20%以上.
空间数据库中一种自适应的缓存替换策略
陈坤杰 孙未未 朱 良 刘未末
2011, 48(10):  1927-1934. 
摘要 ( 482 )   HTML ( 0)   PDF (1122KB) ( 421 )  
相关文章 | 计量指标
随着近年来空间数据库研究和应用的不断深入,针对空间数据库中数据组织和查询的特征来设计缓存页面替换策略成为一个新的研究问题.Voronoi图是一种重要的空间数据库组织技术,在处理kNN查询时具有非常好的性能.针对Voronoi图组织的空间数据库,首先利用空间局部性提出了一种基于欧氏距离的替换策略,在发生页面失效时选择距离上一次访问页面欧氏距离最远的页面进行替换;进一步,针对不同kNN查询的搜索空间大小差异非常大的特点,在LIRS替换策略基础上提出一种自适应替换策略,通过对HIR页面占缓存比例自动调整来适应不同的查询.综合两者,形成基于欧氏距离的自适应缓存页面替换算法AELIRS.大量实验表明,在缓存大小与搜索空间大范围变动中,AELIRS始终优于其他替换策略.
myBUD中多媒体数据索引CFTree*的研究和实现
张 孝, 孙新云, 刘科研, 琚星星, 王 珊,
2011, 48(10):  1935-1941. 
摘要 ( 476 )   HTML ( 0)   PDF (1633KB) ( 342 )  
相关文章 | 计量指标
图片、音频、视频、网页等非结构化数据的高速增长使得如何高效管理它们成为一大挑战.提出的多媒体数据索引CFTree*是非结构化数据管理系统平台myBUD中对多媒体数据进行管理的具体研究和实现.CFTree*是基于簇特征树的层次树索引结构,可用于基于内容的近似kNN查询.实验表明,基于CFTree*索引结构的近似kNN查询性能比基于顺序扫描的kNN查询有60%左右的提高.与精确kNN相比,基于CFTree*索引的近似kNN查询结果与查询对象的平均相似度略低于精确kNN结果,但结果的多样性则优于精确kNN结果.
列存储数据仓库查询执行中重用缓冲区调度算法
张 琦, 王 梅, 乐嘉锦, 刘国华,
2011, 48(10):  1942-1950. 
摘要 ( 469 )   HTML ( 0)   PDF (1438KB) ( 387 )  
相关文章 | 计量指标
查询的中间结果重用是提高查询效率的重要手段.现有列存储系统主要关注多查询计划间的中间结果重用,忽略了单一查询计划执行过程中大量可重复访问的中间结果.单一查询中的中间结果具有确定性高、结果大小可估计的特征,非常适合作为重用的对象.为此,针对列存储数据仓库单一查询计划执行过程中的中间结果重用问题,提出了一个重用缓冲区空间的调度算法.首先,基于操作结点在给定物理执行计划树中的相对位置及其操作所产生的中间结果的大小对操作结点提出重用度估计模型.其次,设计了基于模型估计结果的缓冲区调度算法.在每一个查询计划的执行过程中,根据其模型估计结果执行缓冲区调度算法,使得其产生的中间结果中更重要的部分能够更久地驻留在内存中,以提升查询性能.在数据仓库基准数据集SSB上的实验结果验证了方法的有效性.
OLAP性能测试方法研究与实现
赵 博 叶晓俊
2011, 48(10):  1951-1959. 
摘要 ( 763 )   HTML ( 5)   PDF (2614KB) ( 524 )  
相关文章 | 计量指标
随着商业智能市场的逐步扩大,联机分析处理(OLAP)系统的使用质量评估已经成为数据库应用的研究热点.作为效用特性的OLAP系统性能评估需要一个性能基准.以OLAP委员会推出的APB-1性能基准为基础,首先设计了面向多维数据库的立方体(Cube)模型以及相应的多维表达式(MDX)查询模板,在Cube模型设计的过程中修改了APB-1基准ROLAP星型模型的不足之处;接着在测试数据一致和测试参数一致的前提下,通过对设计的MOLAP模型查询结果与ROLAP模型查询结果进行对比分析,证明了MOLAP模型及MDX查询模板设计的正确性;然后给出了OLAP性能测试流程,描述了支持ROLAP和MOLAP性能测试的工具框架及其主要模块.最后使用该测试框架在商业数据库管理系统上对ROLAP和MOLAP进行并发查询实践,验证了框架的有效性.提出的方法及技术实现为未来OLAP产品性能的测试和评价提供多维数据模型、业务模型和工具的支持.
一种基于可变步长量化调制的地理数据库水印方法
汪传建, 葛贺飞, 丁 卯, 彭智勇, 彭煜玮, 宋 伟, 王俊舟,
2011, 48(10):  1960-1971. 
摘要 ( 429 )   HTML ( 0)   PDF (2476KB) ( 338 )  
相关文章 | 计量指标
地理数据库是地理信息系统的基础,也是数据生产者的宝贵财富.因此,如何利用数字水印技术保护地理数据库的版权成为一个亟待解决的问题.提出一种高鲁棒的、保持形状的、支持盲检的地理数据库水印方法.利用面类地物的平均特征距离的最高h有效位作为鲁棒地物标识,并将所有地物划分到若干分组中,采用可变步长量化调制方法嵌入水印信息,并通过轻微修改地物的面积体现水印的嵌入.为确保算法的安全性,水印嵌入过程中地物和分组间的归属关系、每个地物上拟嵌入的水印位和相应的步长均基于用户密钥计算得出.实验证明,该方法具有良好的鲁棒性,能有效抵抗平移、旋转、化简、噪音附加、顶点插值、裁剪、元组增加和元组修改攻击.而且,在数据可用性范围内,随着水印强度的增加,算法鲁棒性随之提高.