基于Skyline的搜索结果排序方法

doi:10.11772/j.issn.1001-9081.2015.04.1154

计算机应用 ›› 2015, Vol. 35 ›› Issue (4): 1154-1158.DOI: 10.11772/j.issn.1001-9081.2015.04.1154

基于Skyline的搜索结果排序方法

尹文科, 吴姗姗, 丁峰, 荀智德

信息系统工程重点实验室, 南京 210007

收稿日期:2014-10-30 修回日期:2015-01-07 出版日期:2015-04-10 发布日期:2015-04-08
通讯作者: 尹文科
作者简介:尹文科(1987-),男,安徽滁州人,工程师,博士,主要研究方向:信息检索; 吴姗姗(1981-),女,江苏南京人,高级工程师,硕士,主要研究方向:海量数据管理; 丁峰(1968-),男,江苏扬州人,研究员级高级工程师,硕士,主要研究方向:信息服务; 荀智德(1988-),男,江苏徐州人,工程师,硕士,主要研究方向:数据挖掘。

Skyline based search results sorting method

YIN Wenke, WU Shanshan, DING Feng, XUN Zhide

Science and Technology on Information Systems Engineering Laboratory, Nanjing Jiangsu 210007, China

Received:2014-10-30 Revised:2015-01-07 Online:2015-04-10 Published:2015-04-08

摘要/Abstract

摘要：

针对现有垂直搜索引擎的排序结果存在多样性差和冗余度高的问题,提出了一种基于Skyline的搜索结果排序方法。该方法通过计算搜索结果的轮廓等级、支配度和覆盖度作为排序依据,并且为加快轮廓等级和支配度的计算,使用了一种基于Bitmap的轮廓等级和支配度计算算法。实验结果表明,该方法的排序结果具有低冗余度和高多样性的优点,并且具有更快的轮廓等级和支配度计算速度。

关键词: Skyline, 轮廓等级, 支配度, 覆盖度, Bitmap

Abstract:

Concerning the high redundancy and low diversity of search result sorting in current vertical search engines, a skyline based search results sorting method was proposed. The search results were sorted in accordance with skyline level, domination degree and coverage. In order to reduce the time cost, a Bitmap based skyline level and domination degree computing algorithm was proposed. The experimental results show that the proposed method can achieve better performance in terms of search results diversity with low redundancy, and has faster calculation speed in skyline level and domination degree calculation.

Key words: Skyline, skyline level, domination degree, coverage, Bitmap

中图分类号:

TP301.6

尹文科, 吴姗姗, 丁峰, 荀智德. 基于Skyline的搜索结果排序方法[J]. 计算机应用, 2015, 35(4): 1154-1158.

YIN Wenke, WU Shanshan, DING Feng, XUN Zhide. Skyline based search results sorting method[J]. Journal of Computer Applications, 2015, 35(4): 1154-1158.

参考文献

[1] ZHANG M, HURLEY N. Avoiding monotony: improving the diversity of recommendation lists[C]// Proceedings of the 2008 ACM Conference on Recommender Systems. New York: ACM Press, 2008: 123-130.
[2] CLARKE C L A, KOLLA M, CORMACK G V, et al. Novelty and diversity in information retrieval evaluation[C]// Proceedings of the 31st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New York: ACM Press, 2008: 659-666.
[3] ZHANG Y, CALLAN J, MINKA T. Novelty and redundancy detection in adaptive filtering[C]// Proceedings of the 25th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New York: ACM Press,2002: 81-88.
[4] AGRAWAL R, GOLLAPUDI S, HALVERSON A, et al. Diversifying search results[C]// Proceedings of the Second ACM International Conference on Web Search and Data Mining. New York: ACM Press, 2009: 5-14.
[5] BORZSONYI S, KOSSMANN D, STOCKER K. The skyline operator [C]// Proceedings of the 17th International Conference on Data Engineering. Piscataway: IEEE Press, 2001: 421-430.
[6] CHOMICKI J, GODFREY P, GRYZ J. Skyline with presorting[C]// Proceedings of the 19th International Conference on Data Engineering. Piscataway: IEEE Press, 2003: 717-816.
[7] TAN K L, ENG P K, OOI B C. Efficient progressive skyline computation[C]// VLDB 2001: Proceedings of the 27th International Conference on Very Large Data Bases. San Francisco: Morgan Kaufmann Publishers, 2001: 301-310.
[8] KOSSMANN D, RAMSAK F, ROST S. Shooting stars in the sky: an online algorithm for skyline queries[C]// VLDB 2002: Proceedings of the 28th International Conference on Very Large Data Bases. San Francisco: Morgan Kaufmann Publishers, 2002: 275-286.
[9] PAPADIAS D, TAO Y, FU G, et al. An optimal and progressive algorithm for skyline queries[C]// SIGMOD 2003: Proceedings of the 2003 ACM SIGMOD International Conference on Management of data. New York: ACM Press, 2003: 467-478.
[10] ROCHA-JUNIOR J B, VLACHOU A, DOULKERIDIS C, et al. Efficient execution plans for distributed skyline query processing[C]// Proceedings of the 14th International Conference on Extending Database Technology. New York: ACM Press, 2011: 271-282.
[11] HUANG Z, JENSEN C S, LU H, et al. Skyline queries against mobile lightweight devices in MANETs[C]// ICDE 2006: Proceedings of the 22nd International Conference on Data Engineering. Piscataway: IEEE Press, 2006:66.
[12] WANG S, VU Q H, OOI B C, et al. Skyframe: a framework for skyline query processing in peer-to-peer systems[J]. The VLDB Journal, 2009, 18(1): 345-362.
[13] CHAUDHURI S, DALVI N N, KAUSHIK R. Robust cardinality and cost estimation for skyline operator[C]// ICDE 2006: Proceedings of the 22nd International Conference on Data Engineering. Washington, DC: IEEE Computer Society, 2006: 64.
[14] VLACHOU A, DOULKERIDIS C, KOTIDIS Y, et al. SKYPEER: efficient subspace skyline computation over distributed data[C]//ICDE 2007: Proceedings of the 23rd IEEE International Conference on Data Engineering. Piscataway: IEEE Press,2007: 416-425.
[15] PEI J, FU A W C, LIN X, et al. Computing compressed multidimensional skyline cubes efficiently[C]// ICDE 2007: Proceedings of the 23rd IEEE International Conference on Data Engineering. Piscataway: IEEE Press, 2007: 96-105.
[16] DING X, JIN H. Efficient and progressive algorithms for distributed skyline queries over uncertain data[J]. IEEE Transactions on Knowledge and Data Engineering, 2012, 24(8): 1448-1462.

基于Skyline的搜索结果排序方法

Skyline based search results sorting method

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 7

编辑推荐

Metrics

[1]	张书旋, 康海燕, 闫涵. 基于Skyline计算的社交网络关系数据隐私保护[J]. 计算机应用, 2019, 39(5): 1394-1399.
[2]	左开中, 尚宁, 陶健, 王涛春. 两层传感网隐私保护的不完全数据Skyline查询协议[J]. 计算机应用, 2017, 37(6): 1599-1604.
[3]	周涛, 陆惠玲, 马苗, 杨鹏飞. 基于一致度、覆盖度和包含度的感兴趣区域不一致性决策算法[J]. 计算机应用, 2015, 35(10): 2803-2807.
[4]	张效娟李伟. 可信可控网络中跨自治域的流合作测量模型[J]. 计算机应用, 2011, 31(09): 2304-2312.
[5]	谈嵘顾君忠林欣陈鹏. 基于用户隐私保护的区域多对象聚集问题[J]. 计算机应用, 2011, 31(09): 2389-2394.
[6]	崔斌卢阳 . 基于不确定数据的查询处理综述[J]. 计算机应用, 2008, 28(11): 2729-2731.
[7]	李茹，赵小东，吕国英，褚诚缘. 专家系统规则库覆盖度量的研究及实践[J]. 计算机应用, 2005, 25(02): 283-285.