第３９卷 第１０期
２０１６年１０月计 算 机 学 报ＣＨＩＮＥＳＥＪＯＵＲＮＡＬＯＦＣＯＭＰＵＴＥＲＳＶｏｌ．３９Ｎｏ．１０Ｏｃｔ．２０１６
收稿日期：２０１５-０４-０７；在线出版日期：２０１５-１０-１３．本课题得到国家自然科学基金（６１１０００２２，６１４７２０６９）
、国家“八六三”高技术研究发展计划项目基金（２０１２ＡＡ０１１００４）、中央高校基本科研业务费专项资金资助项目（Ｎ１３０４０４０１４）资助．白 梅，女，１９８６年生，
博士研究生，主要研究方向为流数据管理和不确定数据管理．Ｅ-ｍａｉｌ：ｂａｉｍｅｉ８６１２２１＠１６３．ｃｏｍ．信俊昌，男，１９７７年生，
博士，副教授，主要研究方向为分布式数据管理与传感数据集成．王国仁，男，１９６６年生，博士，教授，博士生导师，主要研究领域为数据库、大数据管理．王习特，男，１９８７年生，博士研究生，中国计算机学会（ＣＣＦ）会员，主要研究方向为大数据管理．数据流上动态轮廓查询处理技术的研究
白梅 信俊昌 王国仁 王习特
（东北大学信息科学与工程学院 沈阳 １１０００４）
摘 要 轮廓查询（Ｓｋｙｌｉｎｅ）是一种典型的多目标优化问题．动态轮廓查询（ＤｙｎａｍｉｃＳｋｙｌｉｎｅ）
是轮廓查询的一个重要变种，其目标是对于一个给定的查询点q ，返回在各维度上最接近q 的所有点．对比轮廓查询，动态轮廓查询根据
查询点q 的位置变动，
可以更加灵活地返回查询结果．文中关注数据流上动态轮廓查询处理，此问题在多目标决策方面具有非常重要的应用．为有效地解决该问题，首先提出了一种组合式索引结构来管理数据流上的点，该索引结
构包括两个部分：
对整体数据使用分层次划分结构进行维护；对子划分内部数据采用倒排索引结构进行维护．该组合式索引结构具有更新快、过滤性能高、适合任意数据分布等优点，可以提高动态轮廓的查询处理效率．然后，基于
该组合式索引结构，提出了基础的数据流上动态轮廓查询算法（ＢａｓｉｃＤｙｎａｍｉｃＳｋｙｌｉｎｅＱｕｅｒｙｏｖｅｒＤａｔａＳｔｒｅａｍ，
ＢＤＳ２）．通过维护少量的数据，ＢＤＳ２可以快速地计算出数据流上的动态轮廓集合．
然而ＢＤＳ２在处理个别更新时，会有较大的时间延迟，为了更稳定地计算数据流上的动态轮廓，避免更新某些点时计算量急剧增加，进一步提出了改进的数据流上动态轮廓查询算法（ＩｍｐｒｏｖｅｄＤｙｎａｍｉｃＳｋｙｌｉｎｅＱｕｅｒｙｏｖｅｒＤａｔａＳｔｒｅａｍ，ＩＤＳ２）．
最后，通过一系列的实验验证了文中所提出算法的有效性．
关键词 数据流；动态轮廓；组合式索引；分层次划分；倒排索引
中图法分类号ＴＰ３９１ DOI 号１０．１１８９７／ＳＰ．Ｊ．１０１６．２０１６．０２００７
Research on D y namic Sk y line Q uer y Processin g over Data Streams
ＢＡＩＭｅｉ ＸＩＮＪｕｎ-Ｃｈａｎｇ ＷＡＮＧＧｕｏ-Ｒｅｎ ＷＡＮＧＸｉ-Ｔｅ
（Colle g e o f In f ormation Ｓcience &Ｅn g ineerin g ，Northeastern Universit y ，Ｓhen y an g １１０００４）
Abstract Ｓｋｙｌｉｎｅｑｕｅｒｙｉｓａｔｙｐｉｃａｌｍｕｌｉｔ-ｏｂｊｅｃｔｉｖｅｏｐｔｉｍｉｚａｔｉｏｎｐｒｏｂｌｅｍ．ＤｙｎａｍｉｃＳｋｙｌｉｎｅｉｓａｎｉｍｐｏｒｔａｎｔｖａｒｉａｎｔｏｆｓｋｙｌｉｎｅｏｐｅｒａｔｏｒ．Ｇｉｖｅｎａｑｕｅｒｙｐｏｉｎｔq ，ｄｙｎａｍｉｃｓｋｙｌｉｎｅｑｕｅｒｙｃａｎｒｅｔｕｒｎｔｈｅｔｕｐｌｅｓｗｈｉｃｈａｒｅｃｌｏｓｅｔｏq ｉｎａｌｌｔｈｅｄｉｍｅｎｓｉｏｎｓ．Ｃｏｍｐａｒｉｎｇｗｉｔｈｔｈｅｓｋｙｌｉｎｅｑｕｅｒｙ，ｄｙｎａｍｉｃｓｋｙｌｉｎｅｃａｎｒｅｔｕｒｎｔｈｅｒｅｓｕｌｔｆｌｅｘｉｂｌｙｂｙｃｈａｎｇｉｎｇｌｏｃａｔｉｏｎｓｏｆｔｈｅｑｕｅｒｙｐｏｉｎｔq ．Ｉｎｔｈｉｓｐａｐｅｒ，ｗｅｆｏｃｕｓｏｎｔｈｅｄｙｎａｍｉｃｓｋｙｌｉｎｅｑｕｅｒｙｐｒｏｂｌｅｍｏｖｅｒｔｈｅｄａｔａｓｔｒｅａｍ，ｗｈｉｃｈｐｌａｙｓａｖｅｒｙｉｍｐｏｒｔａｎｔｒｏｌｅｉｎｔｈｅｍｕｌｔｉ-ｃｒｉｔｅｒｉａｄｅｃｉｓｉｏｎｍａｋｉｎｇ．Ｔｏｓｏｌｖｅｔｈｉｓｐｒｏｂｌｅｍｅｆｆｉｃｉｅｎｔｌｙ，ｆｉｒｓｔｌｙ，ｗｅｐｒｏｐｏｓｅａｃｏｍｂｉｎｅｄｉｎｄｅｘｓｔｒｕｃｔｕｒｅｔｏｍａｎａｇｅｔｈｅｄａｔａｉｎｔｈｅｄａｔａｓｔｒｅａｍ．Ｔｈｅｃｏｍｂｉｎｅｄｉｎｄｅｘｓｔｒｕｃｔｕｒｅｃｏｎｔａｉｎｓｔｗｏｐａｒｔｓ：ｔｈｅｗｈｏｌｅｄａｔａａｒｅｍａｎａｇｅｄｂｙａｈｉｅｒａｒｃｈｉｃａｌｄｉｖｉｓｉｏｎｓｔｒｕｃｔｕｒｅ；ｔｈｅｄａｔａｉｎｔｈｅｌｅａｆｄｉｖｉｓｉｏｎａｒｅｍａｎａｇｅｄｂｙａｎｉｎｖｅｒｔｅｄｉｎｄｅｘｓｔｒｕｃｔｕｒｅ．Ｔｈｉｓｃｏｍｂｉｎｅｄｉｎｄｅｘｓｔｒｕｃｔｕｒｅｈａｓｓｏｍｅａｄｖａｎｔａｇｅｓ，ｓｕｃｈａｓｂｅｕｐｄａｔｅｄｆａｓｔ，ｈａｖｅｈｉｇｈｆｉｌｔｅｒｉｎｇｃａｐａｃｉｔｙａｎｄｂｅｓｕｉｔａｂｌｅｆｏｒａｒｂｉｔｒａｒｙｄａｔａｄｉｓｔｒｉｂｕｔｉｏｎｓ．Ｉｔｃａｎａｃｃｅｌｅｒａｔｅｔｈｅｓｐｅｅｄｏｆｕｐｄａｔｅｏｐｅｒａｔｉｏｎｏｖｅｒｔｈｅｄａｔａｓｔｒｅａｍａｎｄｉｍｐｒｏｖｅｔｈｅｐｅｒｆｏｒｍａｎｃｅｏｆｄｙｎａｍｉｃｓｋｙｌｉｎｅｃａｌｃｕｌａｔｉｏｎ．Ｓｅｃｏｎｄｌｙ，ｂａｓｅｄｏｎｔｈｉｓｃｏｍｂｉｎｅｄｉｎｄｅｘ，ｗｅｐｒｏｐｏｓｅ
ｔｈｅｂａｓｉｃｄｙｎａｍｉｃｓｋｙｌｉｎｅｑｕｅｒｙａｌｇｏｒｉｔｈｍｏｖｅｒｄａｔａｓｔｒｅａｍｓ（ＢＤＳ２ｆｏｒｓｈｏｒｔ）
，ｗｈｉｃｈｃａｎｑｕｉｃｋｌｙ万方数据