第４３ 卷 第１２ 期２０２０ 年１２月计 算机 学 报ＣＨＩＮＥＳＥＪＯＵＲＮＡＬＯＦＣＯＭＰＵＴＥＲＳＶｏｌ．４３Ｎｏ．１２Ｄｅｃ．２０２０基于最大覆盖的代表Ｓｋｙｌｉｎｅ 问题的优化算法研究白 梅 王习特 李冠宇 宁 博 周 新（ 大连海事大学信息科学技术学院 辽宁大连 １１６０００）摘 要 Ｓｋｙｌ ｉｎｅ查询作为多目标决策的重要手段之一， 可以根据用户偏好， 在大量的数据中挖掘出用户真正感兴趣的数据． 然而， 随着维度的增加以及数据分布的原因， 会导致ｓｋｙｌｉ ｎｅ结果数目过多， 查询结果失去意义． 目前， 已有一些工作对代表ｓｋｙｌｉｎｅ 问题进行了研究， 即在全部ｓｋｙｌｉｎｅ结果中选取丨 个最具代表性的ｓｋｙｌｉ ｎｅ元组？ 综合考虑代表ｓｋｙｌ ｉｎｅ的代表性以及稳定性， 本文选取基于最大覆盖的代表ｓｋｙｌｉ ｎｅ问题（＾－Ｍａｘｉ ｍｕｍＣｏｖｅｒａｇｅＳｋｙｌｉｎｅ，々－ＭＣＳ） 问题进行研究． 与之前的Ａ－ＭＣＳ计算方法相比， 本文提出的算法具有更好的效率． 针对ｈＭＣＳ问题， 首先，本文提出了２维上的基于前缀的优化算法ＯＰＡ（Ｏｐｔｉ ｍａｌＰｒｅｆｉｘＡｌｇｏｒｉｔｈｍ） ，ＯＰＡ算法利用前缀支配表， 可以通过少量的加减法运算完成最后的结果计算． 接着， 考虑到多维上ＩＭＣＳ问题是一个ＮＰ－Ｈａｒｄ 问题， 本文提出了优化贪心算法ＯＧＡ和ｅ－ＯＧＡ， ＯＧＡ比基本贪心算法减少了５０％以上的计算量．而ｅ－ＯＧＡ通过引入参数￡ ， 与ＯＧＡ算法相比， 仅牺牲以（１ ＋￡） 的精度， 大大加快了计算效率． 最后， 通过大量的实验验证了本文所提算法ＯＰＡ、 ＯＧＡ和ｅ￣ＯＧＡ的有效性和高效性．关键词 代表ｓｋｙｌｉｎｅ；々－ＭＣＳ； 前缀算法； 贪心算法； 优化算法中图法分类号ＴＰ３０１． ６ＤＯＩ号１０．１ １８９７／ＳＰ． Ｊ．１０１６． ２０２０． ０２２７６ＲｅｓｅａｒｃｈｏｎＯｐｔｉｍｉｚａｔｉｏｎＡｌｇｏｒｉｔｈｍｓｏｆＡ：－ＭａｘｉｍｕｍＣｏｖｅｒａｇｅＳｋｙｌｉｎｅＱｕｅｒｉｅｓＢＡＩＭｅｉＷＡＮＧＸｉ－ＴｅＬＩＧｕａｎ－ＹｕＮＩＮＧＢｏＺＨＯＵＸｉ ｎ＾ＣｏｌｌｅｇｅｏｆＩｎｆｏｒｍａｔ ｉｏｎＳｃｉｅｎｃｅ＾－Ｔｅｃｈｎｏｌ ｏｇｙ＾ＤａｌｉａｎＭａｒｉｔｉｍｅＵｎｉｖｅｒｓｉ ｔｙ＾Ｄａｌｉａｎ＾Ｌｉａｏｎｉｎｇ１１６０００）ＡｂｓｔｒａｃｔＡｓａｎｉ ｍｐｏｒｔａｎｔｏｐｅｒａｔｏｒｆｏｒｍｕｌ ｔｉ－ｃｒｉ ｔｅｒｉａｄｅｃｉ ｓｉ ｏｎｍａｋｉ ｎｇ，ｓｋｙｌ ｉ ｎｅｑｕｅｒｉｅｓｃａｎｆｉ ｎｄｔｈｅｄａｔａｔｈａｔｕｓｅｒｓａｒｅｒｅａｌｌｙｉｎｔｅｒｅｓｔｅｄｉ ｎｆｒｏｍａｌａｒｇｅａｍｏｕｎｔｏｆｄａｔａ．Ｔｈｅｓｋｙｌｉｎｅｃｏｎｓｉｓｔｓｏｆｔｈｅｐｏｉｎｔｓｔｈａｔａｒｅｎｏｔｄｏｍｉ ｎａｔｅｄｂｙｏｔｈｅｒｐｏｉ ｎｔｓ．Ｇｉｖｅｎｔｗｏｐｏｉ ｎｔｓｐ＼ａｎｄｐｚ？ｐ＼ｄｏｍｉ ｎａｔｅｓｐ２ｍｅａｎｓ：ｔｈｅｖａｌｕｅｓｏｆｐ｝ａｒｅａｓｇｏｏｄａｓｏｒｂｅｔｔｅｒｔｈａｎｔｈｏｓｅｏｆｐ２ｉｎａｌ ｌｄｉｍｅｎｓｉ ｏｎｓ，ａｎｄｂｅｔｔｅｒｉ ｎａｔｌｅａｓｔｏｎｅｄｉ ｍｅｎｓｉｏｎ．Ｉｎｍｏｓｔｃａｓｅｓ，ｔｈｅｆｕｌ ｌｓｋｙｌｉ ｎｅｓｅｔｉｓａｇｏｏｄｒｅｃｏｍｍｅｎｄａｔｉｏｎｓｅｔｂｅｃａｕｓｅｔｈｅｔｕｐｌ ｅｓｗｈｉ ｃｈａｒｅｄｏｍｉｎａｔｅｄｂｙｏｔｈｅｒｓａｒｅｆｉｌｔｅｒｅｄｏｕｔ．Ｈｏｗｅｖｅｒ，ｗｉｔｈｔｈｅｉ ｎｃｒｅａｓｅｏｆｄｉ ｍｅｎｓｉ ｏｎａｌ ｉｔｙａｎｄｄｉｓｔｒｉ ｂｕｔｉｏｎｏｆｔｈｅｄａｔａｓｅｔ ，ｔｈｅｎｕｍｂｅｒｏｆｓｋｙｌｉ ｎｅｔｕｐｌｅｓｍａｙｂｅｔｏｏｌａｒｇｅ．Ａｓｔｈｅｒｅｃｏｍｍｅｎｄａｔｉ ｏｎｓｅｔ ，ｔｈｅｆｕｌ ｌｓｋｙｌｉ ｎｅｓｅｔｂｅｃｏｍｅｓｍｅａｎｉ ｎｇｌｅｓｓ．Ｂｅｃａｕｓｅｉｔｉ ｓｉ ｍｐｒａｃｔｉｃａｌｆｏｒｕｓｅｒｓｔｏｃｈｏｏｓｅｓｕｉ ｔａｂｌｅｓｋｙｌ ｉ ｎｅｐｏｉｎｔｓａｆｔｅｒｂｒｏｗｓｉ ｎｇａｌ ｌ ｓｋｙｌｉ ｎｅｐｏｉｎｔｓ．Ｈｅｎｃｅ，ｒｅｃｏｍｍｅｎｄｉｎｇａｆｅｗｒｅｐｒｅｓｅｎｔａｔｉ ｖｅｓｋｙｌｉ ｎｅｐｏｉ ｎｔｓｗｏｕｌｄｂｅｖｅｒｙｈｅｌｐｆｕｌｔｏｕｓｅｒｓ．Ｔｈｅｒｅｈａｖｅｂｅｅｎｓｏｍｅｗｏｒｋｓｆｏｃｕｓｅｄｏｎｒｅｐｒｅｓｅｎｔａｔｉｖｅｓｋｙｌｉ ｎｅｐｒｏｂｌｅｍｓ．Ｃｏｎｓｉｄｅｒｉ ｎｇｔｈｅｒｅｐｒｅｓｅｎｔａｔｉ ｖｅｎｅｓｓａｎｄｓｔａｂｉ ｌ ｉ ｔｙｏｆｒｅｐｒｅｓｅｎｔａｔｉ ｖｅｓｋｙｌ ｉｎｅｓ？ｗｅｃｈｏｏｓｅｔｏｓｔｕｄｙｔｈｅ＾－Ｍａｘｉ ｍｕｍＣｏｖｅｒａｇｅＳｋｙｌｉ ｎｅ（＾－ＭＣＳｆｏｒｓｈｏｒｔ）ｐｒｏｂｌ ｅｍ．Ｇｉ ｖｅｎａｐａｒｅｍａｔｅｒｋｊｔｈｅＡ－ＭＣＳｉｓｔｈｅｓｅｔｗｉ ｔｈｋｓｋｙｌ ｉ ｎｅｐｏｉｎｔｓｗｈｏｓｅｄｏｍｉｎａｎｃｅｓｉｚｅｉ ｓｔｈｅｌａｒｇｅｓｔ．Ｃｏｍｐａｒｅｄｗｉｔｈｔｈｅｐｒｅｖｉｏｕｓ是－ＭＣＳａｌｇｏｒｉｔｈｍｓ， ｔｈｅｐｒｏｐｏｓｅｄａｌｇｏｒｉｔｈｍｓｉ ｎｔｈｉｓｐａｐｅｒｈａｖｅｂｅｔｔｅｒｅｆｆｉｃｉｅｎｃｙ．Ｆｉｒｓｔｌｙ，ｗｅｐｒｏｐｏｓｅａｎｏｐｔｉ ｍｉｚａｔｉｏｎｐｒｅｆｉ ｘ－ｂａｓｅｄａｌｇｏｒｉｔｈｍ（ ＯＰＡ收稿日期： ２０１ ９－０９－０６ ； 在线发布日期： ２０２０－０２－１９． 本课题得到国家自然科学基金项目（６１７０２０７２ ， ６１６０２０７６，６１９７６０３２ ） 、 博士后科学基金面上项目（２０１７Ｍ６２１１２２ ，２０１７Ｍ６１１２１１）、 辽宁省自然科学基金（ ２０１８０５４０００３） 、 中央高校基本科研业务费专项资金（ ３１３２０１９２０２）资助．白 梅， 博士， 副教授， 主要研究方向为数据管理、云计算和数据查询优化． Ｅ－ｍａｉｌ：ｂａｉｍｅｉ ８６１２２ １＠１６３．ｃｏｍ． 王习特， 博士， 副教授， 主要研究方向为大数据管理和并行数据管理． 李冠宇， 博士， 教授， 主要研究领域为智能信息处理和语义物联网． 宁 博， 博士， 副教授， 主要研究方向为数据管理和隐私保护． 周 新， 博士， 讲师， 主要研究方向为数据管理和机器学习．白 梅等： 基于最大覆盖的代表Ｓｋｙｌｉｎｅ 问题的优化算法研究 ２２７７１２ 期ｆｏｒｓｈｏｒｔ）ｆｏｒｔ ｈｅ＾－ＭＣＳｐｒｏｂｌｅｍｉｎ２－ｄｉ ｍｅｎｓｉ ｏｎａｌｄａｔａｓｅｔｓ．Ｕｓｉ ｎｇｔｈｅｐｒｅｆｉ ｘ－ｄｏｍｉ ｎａｎｃｅ－ｔａｂｌｅ，ＯＰＡｃａｎｏｂｔａｉ ｎｔｈｅ＾－ＭＣＳｒｅｓｕｌ ｔｗｉｔｈＯｉ ｋＭ２）ｔｉ ｍｅｓｏｆａｄｄｉ ｔｉｏｎａｎｄｓｕｂｔｒａｃｔｉｏｎｏｐｅｒａｔｉ ｏｎｓ，ｗｈｅｒｅＭｉｓｔｈｅｎｕｍｂｅｒｏｆｆｕｌ ｌｓｋｙｌｉ ｎｅｐｏｉｎｔｓ．Ｓｅｃｏｎｄｌ ｙ，ｃｏｎｓｉ ｄｅｒｔ ｈａｔｔｈｅＭＣＳｐｒｏｂｌｅｍｉｎ＾／－ｄｉｍｅｎｓｉｏｎａｌ（ｉ／＞３）ｄａｔａｓｅｔｓｉ ｓａＮＰ－ｈａｒｄｐｒｏｂｌｅｍ，ｔｗｏｏｐｔｉ ｍａｉ ｚａｔｉ ｏｎｇｒｅｅｇｙａｌｇｏｒｉ ｔｈｍｓＯＧＡａｎｄｅ－ＯＧＡａｒｅｐｒｏｐｏｓｅｄ．ＩｎＯＧＡ，ａｎｉｍｐｒｏｖｅｄｆｏｒｍｕｌ ａｉｓｐｒｏｐｏｓｅｄｔｏｑｕｉｃｋｌｙｃａｌ ｃｕｌａｔｅｔｈｅｄｏｍｉ ｎａｎｃｅｓｉｚｅｏｆａｓｅｔ．Ａｌ ｓｏ，ａｆｉｌ ｔｅｒｉ ｎｇｓｔ ｒａｔｅｇｙｉ ｓｐｒｏｐｏｓｅｄｔｏａｖｏｉ ｄｔｈｅｃａｌ ｃｕｌ ａｔｉ ｏｎｓｏｆｓｏｍｅｒｅｄｕｎｄａｎｔｔｕｐｌ ｅｓ．Ｈｅｎｃｅ， ｃｏｍｐａｒｅｄｗｉｔｈｔｈｅｂａｓｉｃｇｒｅｅｄｙａｌｇｏｒｉｔ ｈｍ，ＯＧＡｒｅｄｕｃｅｓｍｏｒｅｔｈａｎ５０％ｃａｌｃｕｌａｔｉ ｏｎｓａｎｄｈａｖｅｔｈｅｓａｍｅａｃｃｕｒａｃｙ．Ｎｅｘｔ ， ｂｙｉ ｎｔｒｏｄｕｃｉ ｎｇａｐａｒａｍｅｔｅｒｅ， ｔｈｅａｌｇｏｒｉ ｔｈｍｅ－ＯＧＡｉｓｐｒｏｐｏｓｅｄ．Ｔｈｅｃｏｍｐｕｔａｔｉ ｏｎｏｆｅ－〇ＧＡｃａｎｂｅｔｅｒｍｉ ｎａｔｅｄｉ ｎａｄｖａｎｃｅｗｉｔ ｈａｇｕａｒａｎｔｅｅｉ ｎｇａｃｃｕｒａｃｙ．Ｃｏｍｐａｒｅｄｗｉ ｔｈＯＧＡ，ｅ－ＯＧＡｃａｎｇｒｅａｔｌ ｙｓｐｅｅｄｕｐｔｈｅｃａｌ ｃｕｌａｔｉｏｎｅｆｆｉ ｃｉｅｎｃｙｂｙｓａｃｒｉｆｉｃｉｎｇｅ／（１ ＋ｅ）ａｃｃｕｒａｃｙ， ｗｈｅｒｅｅｉｓａｓｍａｌ ｌｖａｌｕｅｇｉ ｖｅｎｂｙｕｓｅｒｓ．Ｆｉｎａｌ ｌ ｙ， ｔｈｅｅｆｆｅｃｔｉｖｅｎｅｓｓａｎｄｅｆｆｉｃｉｅｎｃｙｏｆｔｈｅｐｒｏｐｏｓｅｄａｌｇｏｒｉｔｈｍｓＯＰＡ，ＯＧＡａｎｄｅ－ＯＧＡａｒｅｖｅｒｉ ｆｉｅｄｂｙａｌａｒｇｅｎｕｍｂｅｒｏｆｅｘｐｅｒｉ ｍｅｎｔｓ．Ｉｎｃｏｎｃｌ ｕｓｉ ｏｎ，ｃｏｍｐａｒｅｄｗｉｔｈｔｈｅｐｒｅｖｉｏｕｓａｌｇｏｒｉｔｈｍＰＢＡ，ＯＰＡｈａｓｂｅｔｔｅｒｅｆｆｉｃｉｅｎｃｙａｎｄｔｈｅｓａｍｅａｃｃｕｒａｃｙ，ｂｅｃａｕｓｅｉｔｃａｎｉ ｎｃｒｅａｓｅｔｈｅｒｅｕｓｅｒａｔｅｏｆｔｈｅｒｅｓｕｌｔｓｉｎｔｈｅｐｒｅｆｉ ｘ－ｄｏｍｉ ｎａｎｃｅ－ｔａｂｌｅｓａｎｄｒｅｄｕｃｅｕｎｎｅｓｓａｒｙｃａｌ ｃｕｌ ａｔｉ ｏｎｓｏｆｓｏｍｅｔｕｐｌ ｅｓ．ＣｏｍｐａｒｅｄｗｉｔｈｔｈｅｂａｓｉｃａｌｇｏｒｉｔｈｍＧＡ，ＯＧＡｈａｓｂｅｔｔｅｒｅｆｆｉｃｉｅｎｃｙａｎｄｔｈｅｓａｍｅａｃｃｕｒａｃｙ， ｂｅｃａｕｓｅｉ ｔｃａｎｒｅｕｓｅｔｈｅｐｒｅｖｉ ｏｕｓｃａｌｃｕｌａｔｉ ｏｎｒｅｓｕｌｔｓｔｏｃｏｍｐｕｔｅｔｈｅｄｏｍｉ ｎａｃｅｓｉ ｚｅｏｆａｓｅｔ．Ａｌｓｏ，ｉｔｃａｎａｖｏｉｄｓｏｍｅｕｎｎｅｓｓａｒｙｃａｌｃｕｌａｔｉ ｏｎｓｕｓｉｎｇｔｈｅｆｉｌｔｅｒｉ ｎｇｓｔｒａｔｅｇｉｅｓ．Ｃｏｍｐａｒｅｄｗｉｔｈｅ－ＧＡ， ｅ￣（）ＧＡｈａｓｂｅｔｔｅｒａｃｃｕｒａｃｙｂｙｓａｃｒｉ ｆｉｃｉ ｎｇａｓｍａｌ ｌａｍｏｕｎｔｏｆｒｕｎｎｉ ｎｇｔｉ ｍｅ．Ｃｏｍｐａｒｅｄｗｉ ｔ ｈｔ ｈｅｐｒｅｖｉｏｕｓａｌｇｏｒｉ ｔ ｈｍＲＴ，ｅ－ＯＧＡｈａｓｂｅｔｔｅｒａｃｃｕｒａｃｙａｎｄｂｅｔｔｅｒｔｉ ｍｅｅｆｆｉｃｉｅｎｃｙ．Ｋｅｙｗｏｒｄｓｒｅｐｒｅｓｅｎｔａｔｉ ｖｅｓｋｙｌｉｎｅ；々－ＭＣＳ；ｐｒｅｆｉ ｘａｌｇｏｒｉｔｈｍ；ｇｒｅｅｄｙａｌｇｏｒｉ ｔ ｈｍ；ｏｐｔｉ ｍｉｚａｔｉ ｏｎａｌｇｏｒｉ ｔｈｍｓｉ 引 言随着“大数据”时代的到来， 数据已经成为重要的生产因素． 对海量数据的挖掘和运用， 已成为国内外广大学者的研究重点． 轮廓查询（ ｓｋｙｌｉｎｅｑＵｅｒｙ）［１＿２］作为多目标决策（ Ｍｕｌ ｔｉ－Ｃｒｉ ｔｅｒｉａＤｅｃｉｓｉｏｎ－Ｍａｋｉ ｎｇ，ＭＣＤＭ）手段， 可以通过偏好函数帮助用户从海量信息中提取出有针对性的价值富集， 同时， 轮廓查询还可以快速地确定数据集的帕累托边界（ｐａｒｅｔｏｆｒｏｎｔｉｅｒ）， 这些都使得轮廓查询在许多实际应用中有着非常重要的作用．在介绍轮廓集合的概念之前， 需要先引入支配的概念． 具体地， 给定两个元组久和九，／＞， 支配和指的是： 在所有维度上，九都好于或者等于外； 至少在一个维度上，九要好于九． 为了表述方便， 在本文里， 值越小被认为越“好”． 现实生活中， 所有的数值都可以通过０－１ 标准化？落在［０， １］区间内． 因此，如果某个属性值越大越好， 可以采用ｌ－：ｒ的方法进行转换， 使得转换后的值越小越好． 轮廓集合包含了所有不被其它元组“支配”的元组． 如图１ 所示，一共有１ ６ 条房产记录｛／），，仏，…，九６ ｝． 每一条房产信息包括２ 个维度信息： 与最近的交通站点的距离和每平米单价． 其中， 距离值和价格都通过〇－１ 标准化映射到［〇，１］区间内， 并以“小”值为优． 图中九在两个维度都比九。小， 那么说明九的交通情况和价格都九（ ０．１， ０．６） １．０户２（０．２，０．４ ）０．９０．８／＞３（ ０．３，０．３）０．７久（ ０．３５，０．２ ）０．６窆０．５０．４／＞５（０．６，０．１５ ）久（０．７，０．１ ）０．３０．２ｐ７（ ０．８，０．０５）０．１０． １０．２０．３０．４０．５０．６０．７０． ８０．９１．０距离图１ 轮廓和Ａ 最大覆盖轮廓（々＝３）① ０－１ｆａ； 准化： 也称离差标准化， 它是对原始数据进行线性变换． 使结果落到［〇 ， １］ 区间．２２７８ 计 算机 学 报 ２０２０年比九。好， 则九支配久。． 图中的轮廓集合是｛ 九，办，…，和｝， 其它的房产记录都可以被｛ 九，办，一，和｝ 中的１ 个或多个元组支配．通过上述例子， 可以发现尽管轮廓查询已经大大方便了人们的结果选择， 但是当人们关注的维度较多， 或者关注的数据集较大时， 会造成轮廓元组的数目大大增加［２］． 这时， 整体轮廓集合对于用户的意义将变小， 因此， 通过优中选优， 推荐有限数目的具有代表性的轮廓元组给用户将变得十分必要． 本文主要针对代表轮廓问题进行了研究， 即在整体轮廓中选出具有代表性的有限数目的轮廓元组． 代表轮廓在多目标决策问题上比轮廓集合更具有意义， 尤其适合分布复杂和体量庞大的数据集合， 更加适用在“大数据”时代中．目前， 关于代表轮廓问题［３６］的研究已取得了很多成果． Ｂａｉ 等人［３］和Ｓｏｈｏｌ ｍ等人ｗ提出了基于最大覆盖的代表轮廓问题—＾最大覆盖轮廓々－ＭＣＳ． 具体地， 给定一个参数纟， 从整体轮廓中选出是个轮廓元组， 使得他们可以支配的面积（ 体积或超体积） 达到最大． 如图１ 所示， 图中全体轮廓为｛Ａ，外，…，外｝，当６＝３ 时， ｛／＞１ ， ＞２ ， ？４｝能够支配的区域如图中覆盖所示， 它们的支配面积是０． ０４＋０．０９＋０．５２＝ ０．６５． 其它包含３ 个轮廓元组的集合的支配面积都小于〇．６５， 所以，｛ 九，九，／＞４｝ 就是３－最大覆盖轮廓．正如文献［３－４］ 中提到的， 对比其它代表轮廓，ｈ最大覆盖轮廓更加稳定、计算速度更快、且具有很好的代表性． 但是， 之前设计的ｆ ＭＣＳ算法 在计算过程中， 对于某些必要的中间结果没有进行保留，所以需要大量的重复性计算， 导致算法效率偏低． 且造成每次计算比较复杂， 浪费了大量的算力． 因此，本文设计一种方法， 通过保留最为适合的中间结果，充分复用这些中间结果值， 避免了大量的重复计算，从而加速了ＩＭＣＳ的计算． 归结起来， 本文的主要贡献如下：（１） 针对２ 维数据空间中的ｆＭＣＳ问题， 提出了基于前缀支配表的前缀优化算法ＯＰＡ． 利用优化的求前缀公式， ＯＰＡ可以通过〇（ 々Ｍ２） 次加减法运算完成ＰＭＣＳ的计算， 其中Ｍ是整体ｓｋｙｌｉ ｎｅ 元组的数目．（２） 针对多维数据空间中的ＩＭＣＳ问题， 提出了优化贪心算法ＯＧＡ， 对比基础贪心算法， 在保证相同精确度的前提下减少５０％以上的计算量； 之后， 在ＯＧＡ算法的基础上， 提出了提前截断算法ｅ－ＯＧＡ．与ＯＧＡ算法相比， ｅ－ＯＧＡ通过牺牲以（１ ＋￡） 的精度， 大大提局计算效率．（３） 设计了详细的性能评价实验， 实验结果表明本文所提出的算法〇ＰＡ、ＯＧＡ和ｅ－ＯＧＡ能够分别高效地处理２维和多维空间中的Ａ－ＭＣＳ问题． 与之前算法相比较， 本文提出的算法具有更好的计算效率．本文第２ 节回顾相关工作； 第３ 节介绍最大覆盖代表轮廓ＩＭＣＳ的相关定义； 第４ 节详细描述本文所提出的々－ＭＣＳ的査询算法， 针对２ 维空间， 提出ＯＰＡ算法； 针对多维数据空间， 提出优化贪心算法ＯＧＡ和ｅ－ＯＧＡ； 第５ 节给出实验结果与分析； 第６ 节对全文进行总结．２ 相关工作轮廓查询（ｓｋｙｌｉ ｎｅｑｕｅｒｙ） 的概念最早由Ｂｏｒｚｓｏｎｙｉ等人［１］在２００１ 年提出， 轮廓查询的前身是最大向量问题［７］． 文献［８］对ｓｋｙｌｉ ｎｅ 及其变体查询进行了综述性概括， 包括ｓｋｙｌｉ ｎｅ 查询及其变体查询的相关文献． 与本文关联较大的所有文献都在２．２ 节进行了介绍．２．１ 轮廓查询算法文献［１］中最早提出了两个轮廓查询算法ＢＮＬ和Ｄ＆Ｃ． ＢＮＬ依次扫描全体数据并把不被支配的元组加人到候选集合中， 通过多次迭代求出最终的轮廓集合． Ｄ＆Ｃ算法把全体数据分成多个子集并求出每个子集的子集轮廓， 然后合并所有的子集轮廓得到最终的轮廓集合． ＳＦＳ算法？首先按照单调函数把数据集排序， 使得排在后面的数据不可能支配排在前面的数据， 利用该性质来计算轮廓集合．利用索引， 轮廓查询的效率得到了大大提高．Ｂｉｔｍａｐ算法［１°］首先把每个元组映射成一个ｍ位的矢量， 利用转换后的矢量求解最终的轮廓集合． ＮＮ算法［１ １］和ＢＢＳ算法［１ ２］利用Ｒ－ｔｒｅｅ索引来管理全部的数据元组， ＮＮ利用最近邻来进行过滤求得最终的轮廓集合． ＢＢＳ算法通过访问那些包含最终轮廓元组的Ｒ－ｔｒｅｅ 节点来求得最终的轮廓集合． ＺＢｔｒｅｅ算法［１ ３］采用Ｚ－ｏｒｄｅｒ 索引来管理全体数据， 并利用Ｚ－ｏｒｄｅｒ 之间的顺序过滤， 来计算最终的轮廓结果．此外， 还有很多研究是针对特定环境下的轮廓查询问题． 如数据流上的轮廓查询［１４ １ ５］算法， 旨在解决那些数据频繁更新的多目标决策问题， 适用于股票市场、传感器环境监控方面等． 分布式环境上的白 梅等： 基于最大覆盖的代表Ｓｋｙｌｉ ｎｅ问题的优化算法研究 ２２７９１ ２ 期轮廓查询算法［１ ６ １ ７］， 旨在解决数据体量大的多目标决策问题， 适用于电子商务环境、 传感器网络等数据量大的环境中． 不确定环境上的轮廓查询［１ ８］算法，旨在解决数据值不完全精确环境下的多目标决策问题， 适用于数据范围观测环境中．２． ２ 代表轮廓查询算法随着数据时代的到来， 轮廓查询处理的数据量越来越大， 数据分布越来越复杂， 从而导致了整体轮廓的大小越来越大． 当整体轮廓元组数目过多时， 对整体轮廓的研究意义将变小． 因此， 越来越多的学者致力于代表轮廓［３ ６］的研究．文献［１９－２４］中通过改变支配定义， 来控制最终结果的数目， 选出的结果元组有可能不是传统的轮廓元组． 文献［１９］中提出了ｆ支配的概念， 元组九能够ｔ支配Ａ指的是： 在选中的々 个子维度上， 九支配外． 通过选择合适的子维度就可以控制结果元组的数目． Ｐｅｎｇ等人？针对高维上的 支配ｓｋｙｌｉ ｎｅ问题提出了一种并行解决方法， 利用ＧＰＵ框架来快速计算Ｐ支配ｓｋｙｌ ｉｎｅ 结果． Ｘｉ ａ 等人［２°］提出了ｅ－支配的概念， 元组九能够 支配ｈ指的是： 九每个维度上的值增加ｅ 后， 转换后的九支配外． 通过调整￡ 值， 就能控制结果元组的数目． 信等人 提出了Ｆ支配的概念， 元组九能够 支配／＞２ 指的是：扣每个维度上的值增加＾倍后， 转换后的久支配外．通过调整厂值， 可以控制结果元组的数目． Ｚｈａｎｇ等人［２ ２］提出了圆锥支配的概念， 九能够圆锥支配九指的是： 九与九形成的斜率在圆锥角度范围内． 通过调整圆锥的角度， 就可以调整结果元组的数目．文献［２３］提出了ｔｏｐ－々 轮廓， 每个元组都根据该元组的支配能力（ 即该元组可以支配的其它元组的数目） 进行排序， 选出排在前々 个的元组作为ｔ〇ｐ４轮廓结果返回． 之后， 文献［２４］研究了数据流上的ｔｏｐｉ轮廓问题． 无疑地， 该ｔｏｐ－々 轮廓只考虑了单个元组的支配能力， 没有考虑返回结果的整体支配能力． 更有甚者， ｔｏｐ－々 轮廓选出的代表元组有可能集中在一起， 且不是轮廓元组， 因此， ｔｏｐ－Ａ 轮廓的代表性并不够好．Ｌｉ ｎ等人 提出了基于整体支配数目的代表轮廓ＲＳＰ． ＲＳＰ希望选出々 个轮廓点， 使得选中的是个轮廓点可以支配的元组数目达到最大． 无疑地，ＲＳＰ能保证选中的轮廓元组具有良好的代表性． 但是， ＲＳＰ的稳定性较差， 且计算复杂． 当数据集合变化时， 非轮廓元组会影响ＲＳＰ的结果．Ｔａｏ等人［５］提出了基于距离的代表轮廓ＤＲＳ．ＤＲＳ采用距离来衡量选定集合的代表性． 给定一个有是个轮廓元组的子集Ｋ：， 整体轮廓用ＳＫＹ表示，子集Ｋ的代表因子为￡ｒ（ Ｋ， ＳＫＹ）＝ｍａｘＲＳＫｙ＿Ｋ｛ ｍｉｉｖｅＫ 丨／＞，／／丨 ｝ ， 其中丨丨 是元组ｐ和／／的欧几里德距离． 简单说来， ￡＞（ Ｋ， ＳｉＣＹ）的含义就是选中々个元组， 记录每个未选中的元组距离它最近的选中元组的距离， 其中的最大距离就是Ｋ的距离因子． ＤＲＳ是因子数￡ｒ（ Ｋ， ＳＫＹ） 最小的子集Ｋ． 当某个维度进行缩放的时候， 例如单位由千米变成米，ＤＲＳ的结果会发生变化． 同时， 这种代表轮廓的定义也忽视了轮廓定义的核心， 与支配能力完全无关．另外， 文献［２５－２６］ 中提出了后悔集合的概念．文献［２５］提出了最小后悔代表集合概念， 文中首先定义了后悔的概念， 即针对每个用户， 全集的最高打分函数减去选中子集的最高打分函数就是该集合针对该用户的后悔值， 而后悔率就是后悔值与选中子集打分函数的比值， 最小后悔代表集合就是选中大小为々的子集， 使得所有用户的后悔率的上确界值最小． 文献［２６］提出了Ｉ后悔最小集合， 文中定义了 后悔值为全集中第６ 高的打分函数值减去子集中最高打分函数值． 而ｆ后悔率就是々 后悔值与全集中第々 高的打分函数值的比值 后悔最小集合就是选中大小为ｒ 的子集， 对所有用户的 后悔率的上确界最小． 文献［２５－２６］都以后悔值为目标进行考虑， 这样选中的代表集合与用户在各个维度的打分函数关系十分密切． 文献［２７］中提出了基于意义和多样性的代表轮廓ＳＤＲＳ， 他们希望设定一个合理的参数， 综合考虑多样性和意义． 其中， 多样性采用距离来衡量， 即选择的元组相距越远， 多样性越好． 而选中元组的意义由ｓｉｇｍｏｉｄ 函数来衡量． 文献［２８］中提出了基于点击的代表轮廓， 即对每个轮廓元组都记录一个用户点击它的概率值， 选出々 个轮廓元组， 使得用户点击其中一个元组的概率值达到最大． 上述的几种代表轮廓的定义都忽视了轮廓的核心定义—支配能力， 且它们的计算都是非常复杂的．另外还有很多文献［２９］采用代表轮廓的概念用来过滤， 这些文章中的代表元组的选择标准与本文选定的选择标准都是类似的， 是基于支配面积（体积或者超体积） 的， 但是这些文章都没有给出详细的求解方法， 导致选出的代表轮廓误差太大．①ＰｅｎｇＹ－Ｗ， ＣｈｅｎＷ－Ｍ． Ｐａｒａｌｌｅｌ是－ｄｏｍｉｎａｎｔ ｓｋｙｌｉｎｅ ｑｕｅｒｉｅｓｉｎｈｉｇｈ－ｄｉｍｅｎｓｉｏｎａｌｄａｔａｓｅｔｓ．Ｉｎｆｏｒｍａｔｉ ｏｎＳｃｉｅｎｃｅｓ，ｈｔ ｔｐｓ：／／ｄｏｉ．ｏｒｇ／ｌ〇．１０１６／ｊ． ｉ ｎｓ． ２０１９． ０１． ０３９２２８０ 计 算机 学 报２０２０年与本文最相近的文献是文献［３－４ ， ３０］， 它们研究的都是基于最大覆盖（ 即支配面积、 体积或超体积） 的代表轮廓查询ｔＭＣＳ问题． 文献［４］中只论述了该代表轮廓选取标准的优越性， 没有就ＩＭＣＳ问题给出实际的解决办法． 文献［３］中给出了ＩＭＣＳ问题的详细解决办法， 但是它的处理办法中对计算的复用率不够， 导致算法效率并不够高． 文献［３０］主要针对／ｒ－ＭＣＳ问题的删除鲁棒性问题进行了研究，但是只针对多维贪心算法给出了优化查询算法ＲＴ．ＲＴ采用了Ｌａｚｉ ｅｒ 贪心加速算法［： ｉｌ］的思想， 首先求出一个ｃｏｒｓｅｔ 集合， 而后只在ｃｏｒｅｓｅｔ 集合中进行计算， 不用对全集进行计算．本文针对ｔＭＣＳ问题设计了一种更加灵活、 高效的解决办法， 有效提升了々－ＭＣＳ问题的计算效率．３ 问题描述本文针对基于最大覆盖的代表轮廓查询ｔＭＣＳ问题进行了研究． 为了描述方便， 表１ 中给出了本文的符号定义．表ｉ 符号表示符号 符号含义Ｐ＇， Ｐ２ 数据元组Ｐ 数据集合ＳＫＹ（ Ｐ）／ＳＫＹ 数据集合Ｐ的轮廓集合ｄ 数据集合Ｐ的维度Ｐｘ ｌｉ］ 元组灼在维度／ 上的值ｋ 代表轮廓元组的数目ｋ－ＭＣＳ（ ＳＫＹ） 基于最大覆盖的々－代表轮廓ＤｏｍＳｉｚｅ（Ｓｉ ）／ＤｏｍＳｉ ｚｅｉＳ）元组５，／集合Ｓ的支配（超） 体积／面积Ｉｎｔ Ｓｉｚｅ（ Ｓ） 集合Ｓ所有元组的相交支配（超） 体积／面积Ｉｎｔ Ｓｉｚｅｉ ｓ，＊ Ｓ） 元组＆和集合Ｓ支配面积／ 体积相交部分的大小ｉ－Ｓｅｔ ｓ（． Ｓ） Ｓ中任意／ 个元组组成的所有集合ＰｒｅＳｅｔ （Ｓｉ ） 排在６？， 之前的元组组成的集合ＰｒｅＳｉｚｅ（Ｓ＊ｓ， ） ？ Ｓ对＾的前缀支配面积ＩｎｃｒｅＳｉｚｅｉ ｓ， ？ Ｓ） 元组． 、？， 相对于ｓ的增Ｍ支配体积／面积给定１ 个ｄ维的数据集合Ｐ， 每个数据元组Ｐ可以表示为／＞＝〈／＞［１］，／＞［２］，－ ＂，／＾］〉 ， 且每个维度上的值都以小值为优， 并映射到［〇， １］ 区间内． 通过映射函数， 可以把每个数据在各维度上的值都转化到［〇，１］范围内． 下面． 本文回顾一下轮廓的基本概念．定义１（ 支配［１］） ．给出ｄ维数据集合 ，／＞２ ６／５， 丸支配九（ 记作／＞， ＜内） 需要满足以下两个条件： （ｌ ） Ｖ／ ｅ｛１ ， ２，． ＂， 々｝，／＞， 九［仏（ ２）３） ６｛１，２，—， ｄ）［ｊ］＜／＞２［ｊ］．集合Ｐ中所有不被其它元组支配的元组就组成了Ｐ的轮廓集合， 记作ＳＫＹ（ Ｐ）＝｛ ／＞， 丨 丸，Ｐ， ３ ＾＜九｝， 简写为ＳＫＹ．本文研究的是基于最大覆盖（ 支配面积或体积）的代表轮廓问题ｆＭＣＳ． 在介绍ｆＭＣＳ的标准定义之前， 先介绍如何求解一个集合的支配面积（ 体积） ． 由于每个元组在所有维度上的值都可以标准化到０－１ 范围内， 基于此标准， 下面给出一个ｄ维元组Ｐ的支配大小（ 支配体积或支配面积） ， 记作ｄＪＪ（１—／？［ｚ’］）． 给定一个含有ｗ个元１ ＝ １组的ｄ维集合ｓ＝｛ ｐ丨， 九，…，Ａ， ｝， Ｓ的相交支配大小指的是集合中所有元组共同支配区域的大小， 记ｄ作＾Ｓｚ’２：ｅ（ Ｓ）＝ＪＪ（１—ｍａｘｐｆ（九［ｚ．］） ） ．给定元ｉ＝ｉ组ｆ 和集合Ｓ，ｐ和Ｓ的相交支配大小为能够被ｆ和Ｓ共同支配区域的大小， 记作ＪｍＳｆ＾（ ｐ， Ｓ）．如图２ 中所示， 元组和的支配大小 （九）＝（１—０？２）Ｘ（１—０？４）＝§， ４８？ 集合Ｓｉ＝｛／＞ｉ ，／＞２ ，九｝ 的相交支配区域如图中深色部分所示， 相交支配大小为）＝（１—０？３５）Ｘ（１—０？６）＝０？２６？ 给定集合Ｓ２＝｛ 九，／？２ ｝ 和元组Ａｉ 夕４，Ｓ２） 的大小如图中所有填色部分所示（ １一０． ４）Ｘ（ １—０．３５）＝０．３９．０．８垄０．６＾０． ５０．４０． ２０． １０图２集合的支配大小举例根据文献［３］ 中的定义２， 可以得到一个集合的含有７２ 个元组的ｄ维数据集合Ｓ＝｛ 九，ｐ２，…，Ａ， ｝，Ｓ的支配大小如式（１ ）