数据流上动态轮廓查询处理技术的研究

发布时间：2017-07-18 05:09

  本文关键词：数据流上动态轮廓查询处理技术的研究

  更多相关文章： 数据流 动态轮廓 组合式索引 分层次划分 倒排索引

【摘要】：轮廓查询(Skyline)是一种典型的多目标优化问题.动态轮廓查询(Dynamic Skyline)是轮廓查询的一个重要变种,其目标是对于一个给定的查询点q,返回在各维度上最接近q的所有点.对比轮廓查询,动态轮廓查询根据查询点q的位置变动,可以更加灵活地返回查询结果.文中关注数据流上动态轮廓查询处理,此问题在多目标决策方面具有非常重要的应用.为有效地解决该问题,首先提出了一种组合式索引结构来管理数据流上的点,该索引结构包括两个部分:对整体数据使用分层次划分结构进行维护;对子划分内部数据采用倒排索引结构进行维护.该组合式索引结构具有更新快、过滤性能高、适合任意数据分布等优点,可以提高动态轮廓的查询处理效率.然后,基于该组合式索引结构,提出了基础的数据流上动态轮廓查询算法(Basic Dynamic Skyline Query over Data Stream,BDS2).通过维护少量的数据,BDS2可以快速地计算出数据流上的动态轮廓集合.然而BDS2在处理个别更新时,会有较大的时间延迟,为了更稳定地计算数据流上的动态轮廓,避免更新某些点时计算量急剧增加,进一步提出了改进的数据流上动态轮廓查询算法(Improved Dynamic Skyline Query over Data Stream,IDS2).最后,通过一系列的实验验证了文中所提出算法的有效性.
【作者单位】： 东北大学信息科学与工程学院;
【关键词】： 数据流 动态轮廓 组合式索引 分层次划分 倒排索引
【基金】：国家自然科学基金(61100022,61472069) 国家“八六三”高技术研究发展(2012AA011004) 中央高校基本科研业务费专项资金资助项目(N130404014)资助~~
【分类号】：TP391.3
【正文快照】： 1引言 轮廓查询[1-2]作为多目标决策(Multi-Criteria Decision-Making,MCDM)手段,可以通过偏好函数帮助用户从大量信息中提取有用信息,在许多实际应用中都发挥着非常重要的作用.轮廓集合是指所有不被“支配”的点的集合.具体地,给定两个点p1和p2,p1支配p2指的是:在所有维度上

【相似文献】

中国期刊全文数据库 前10条

1 吴恒山,刘兴宇,左琼;一种基于可扩展散列表的倒排索引更新策略[J];计算机工程;2004年08期

2 王冬;左万利;赫枫龄;彭涛;张长利;;一种增量倒排索引结构的设计与实现[J];吉林大学学报(理学版);2007年06期

3 林洁;李丹宁;吴晓;;基于用户的个性化综合倒排索引[J];杭州师范大学学报(自然科学版);2008年03期

4 宁可为;王炜;;基于倒排索引的答疑系统知识库文本研究[J];湖北广播电视大学学报;2010年06期

5 谭斌;丁莎;车念;徐力;聂清彬;谭钱茂;黄翔;;一种面向域的高效倒排索引结构及实时更新[J];四川大学学报(自然科学版);2011年02期

6 杨建武,陈晓鸥;基于倒排索引的文本相似搜索[J];计算机工程;2005年05期

7 邝砾;邓水光;李莹;吴健;吴朝晖;;使用倒排索引优化面向组合的语义服务发现[J];软件学报;2007年08期

8 赵亮;;基于复合结构的高效索引在线更新策略[J];计算机工程;2008年02期

9 吴晓;李丹宁;吕爽;林洁;李丹;;基于综合倒排索引的个性化搜索引擎研究[J];微计算机信息;2008年27期

10 张旭东;孙志明;刘亚宁;单栋栋;闫宏飞;;基于64位体系结构的倒排索引压缩算法[J];计算机工程;2014年02期

中国重要会议论文全文数据库 前4条

1 李栋;史晓东;;对搜索引擎中倒排索引更新策略的研究和改进[A];第二十二届中国数据库学术会议论文集（技术报告篇）[C];2005年

2 刘小珠;孙莎;曾承;彭智勇;;基于缓存的倒排索引机制研究[A];第二十四届中国数据库学术会议论文集（研究报告篇）[C];2007年

3 维尼拉·木沙江;吴俊森;吐尔根·依布拉音;;维吾尔文搜索引擎的倒排索引设计与实现[A];民族语言文字信息技术研究——第十一届全国民族语言文字信息学术研讨会论文集[C];2007年

4 孙宇;刘憬;张宇;刘挺;;基于分词和倒排索引的短文本检索技术的研究与实现[A];黑龙江省计算机学会2007年学术交流年会论文集[C];2007年

中国博士学位论文全文数据库 前1条

1 艾列富;基于内容的大规模图像索引与检索方法研究[D];华中科技大学;2014年

中国硕士学位论文全文数据库 前10条

1 彭雨蒙;基于序列比对的视频指纹检索算法研究[D];电子科技大学;2015年

2 郭争文;基于TermID序列排序的标识符重分配的倒排索引压缩研究[D];北京交通大学;2016年

3 刘兴宇;基于倒排索引的全文检索技术研究[D];华中科技大学;2004年

4 刘红雨;基于倒排索引的微博话题检测[D];哈尔滨工业大学;2013年

5 毛福林;倒排索引压缩算法研究[D];北京交通大学;2015年

6 汪红敏;基于固态硬盘的倒排索引动态更新策略及其优化研究[D];华中科技大学;2013年

7 林洁;基于综合倒排索引的个性化搜索技术研究[D];贵州大学;2008年

8 陈雪帆;基于固态硬盘的倒排索引构建与维护策略研究[D];华中科技大学;2012年

9 吴俊森;维哈柯多语种搜索引擎倒排索引模块的实现[D];新疆大学;2007年

10 潘胜一;基于倒排索引的压缩算法性能研究[D];杭州电子科技大学;2009年

，

本文编号：556106