Ranking-k: effective subspace dominating query algorithm

doi:10.11772/j.issn.1001-9081.2015.01.0108

Journal of Computer Applications ›› 2015, Vol. 35 ›› Issue (1): 108-114.DOI: 10.11772/j.issn.1001-9081.2015.01.0108

Previous Articles Next Articles

Ranking-k: effective subspace dominating query algorithm

LI Qiusheng¹, WU Yadong¹, LIN Maosong², WANG Song^2,3, WANG Haiyang¹, FENG Xinmiao¹

1. School of Computer Science and Technology, Southwest University of Science and Technology, Mianyang Sichuan 621010, China;
2. School of Information Engineering, Southwest University of Science and Technology, Mianyang Sichuan 621010, China;
3. Institute of Electronic Engineering, China Academy of Engineering Physics, Mianyang Sichuan 621010, China

Received:2014-08-08 Revised:2014-09-23 Online:2015-01-01 Published:2015-01-26

有效的子空间支配查询算法——Ranking-k

李秋生¹, 吴亚东¹, 林茂松², 王松^2,3, 王海洋¹, 冯鑫淼¹

1. 西南科技大学计算机科学与技术学院, 四川绵阳621010;
2. 西南科技大学信息工程学院, 四川绵阳621010;
3. 中国工程物理研究院电子工程研究所, 四川绵阳621010

通讯作者: 吴亚东
作者简介:李秋生(1989-),男,山东菏泽人,硕士研究生,主要研究方向:科学可视化、信息可视化;吴亚东(1979-),男,河南周口人,教授,博士,CCF会员,主要研究方向:图像图形处理、可视化技术;林茂松(1964-),男,安徽全椒人,教授,博士,CCF会员,主要研究方向:图像图形处理、虚拟现实;王松(1989-),男,安徽桐城人,博士研究生,CCF会员,主要研究方向:基于内容的图像、视频检索及可视化;王海洋(1990-),男,河南驻马店人,主要研究方向:科学计算可视化;冯鑫淼(1991-),女,四川绵阳人,硕士研究生,主要研究方向:增强现实.
基金资助:
国家自然科学基金资助项目(61303127);国家科技支撑计划项目(2013BAH32F02,2013BAH32F03);国防重点学科实验室项目(13zxnk12);四川省教育厅重点项目(13ZA0169);四川省苗子工程资助项目(2014-043);西南科技大学研究生创新基金资助项目(14ycx057).

Abstract

Abstract:

Top-k dominating query algorithm requires high consumption of time and space to build combined indexes on the attributes, and the query accuracy is low for the data with same attribute values. To solve these problems, a Ranking-k algorithm was given in this paper. The proposed Ranking-k algorithm is a new subspace dominating query algorithm combining the B⁺-trees with probability distribution model. Firstly, the ordered lists for each data attribute were constructed by the B⁺-trees. Secondly, the round-robin scheduling algorithm was used to scan ordered attribute lists satisfying skyline criterion. Some candidate tuples were generated and k end tuples were obtained. Thirdly, the dominated scores of end tuples were calculated by using the probability distribution model according to the generated candidate tuples and end tuples. Through iterating the above process, the optimal query results were obtained. The experimental results show that the overall query efficiency of the proposed Ranking-k algorithm is improved by 94.43% compared with the Basic-Scan Algorithm (BSA) and by 7.63% compared with the Differential Algorithm (DA), and the query results of Ranking-k algorithm are much closer to theoretical values in comparison of the Top-k Dominating with Early Pruning (TDEP) algorithm, BSA and DA.

Key words: Top-k dominating, subspace, Ranking-k algorithm, sorted list, round-robin scheduling algorithm

摘要：

针对Top-k dominating查询算法需要较高的时空消耗来构建属性组合索引,并且在相同属性值较多情况下的查询结果准确率低等问题,提出一种通过B⁺-trees和概率分布模型相结合的子空间支配查询算法——Ranking-k算法.首先,采用B⁺-trees为待查找数据各属性构建有序列表;然后,采取轮询调度算法读取skyline准则涉及到的有序列表,生成候选元组并获得k组终结元组;其次,根据生成的候选元组和终结元组,采用概率分布模型计算终结元组支配分数.迭代上述过程优化查询结果,直到满足条件为止.实验结果表明:Ranking-k与基本扫描算法(BSA)相比,查询效率提高了94.43%;与差分算法(DA)相比,查询效率提高了7.63%;与早剪枝Top-k支配(TDEP)算法、BSA和DA相比,查询结果更接近理论值.

关键词: Top-k dominating, 子空间, Ranking-k算法, 有序列表, 轮询调度算法

CLC Number:

LI Qiusheng, WU Yadong, LIN Maosong, WANG Song, WANG Haiyang, FENG Xinmiao. Ranking-k: effective subspace dominating query algorithm[J]. Journal of Computer Applications, 2015, 35(1): 108-114.

李秋生, 吴亚东, 林茂松, 王松, 王海洋, 冯鑫淼. 有效的子空间支配查询算法——Ranking-k[J]. 计算机应用, 2015, 35(1): 108-114.

References

[1] FAGIN R, LOTEM A, NAOR M. Optimal aggregation algorithms for middleware [C]// PODS'01: Proceedings of the Twentieth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. New York: ACM, 2001: 102-113.
[2] VAGELIS H, NICK K, PAPAKONSTANTINOU Y. PREFER: a system for the efficient execution of multi-parametric ranked queries [C]// Proceeding of the 2001 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2001: 259-270.
[3] BORZSONYI S, KOSSMANN D, STOCKER K. The skyline operator [C]// Proceedings of the 17th International Conference on Data Engineering. Piscataway: IEEE, 2001: 421-430.
[4] PAPADIAS D, TAO Y, FU G, et al. Progressive skyline computa- tion in database systems [J]. ACM Transactions on Database Systems, 2005, 30(1): 41-82.
[5] YIU M, MAMOULIS N. Efficient processing of Top-k dominating queries on multi-dimensional data [C]// VLDB'07: Proceedings of the 33rd International Conference on Very Large Data Bases. [S.l.]: VLDB Endowment, 2007: 483-494.
[6] YIU M, MAMOULIS N. Multi-dimensional Top-k dominating que-ries [J]. The International Journal on Very Large Data Bases, 2009, 18(3): 695-718.
[7] KONTAKI M, PAPADOPOULOS Y. Continuous Top-k dominating queries [J]. IEEE Transactions on Knowledge and Data Engineering, 2010, 24(5): 840-853.
[8] ZHANG W, LIN X, ZHANG Y, et al. Threshold-based probabilistic Top-k dominating queries [J]. The International Journal on Very Large Data Bases, 2010, 19(2): 283-305.
[9] TIAKAS E, PAPADOPOULOS A N, MANOLOPOULOS Y. Pro-gressive processing of subspace dominating queries [J]. The International Journal on Very Large Data Bases, 2011, 20(6): 921-948.
[10] HAN X, YANG D, LI J. An efficient Top-k dominating algorithm on massive data title [J]. Chinese Journal of Computers, 2013,33(8): 1405-1417.(韩希先,杨东华,李建中.TKEP:海量数据上一种有效的Top-k查询处理算法[J].计算机学报,2013,33(8): 1405-1417.)
[11] TAO Y, XIAO X, PEI J. SUBSKY: efficient computation of skylines in subspaces [C]// Proceedings of the 22nd International Conference on Data Engineering. Piscataway: IEEE, 2006: 65-76.
[12] XIA T, ZHANG D. Refreshing the sky: the compressed skycube with efficient support for frequent updates [C]// Proceedings of the 2006 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2006: 491-502.
[13] YUAN Y, LIN X, LIU Q, et al. Efficient computation of the skyline cube [C]// Proceedings of the 31st International Conference on Very Large Data Bases. [S.l.]: VLDB Endowment, 2005: 241-252.
[14] TAO Y, XIAO X, PEI J. Efficient skyline and Top-k retrieval in subspaces [J]. IEEE Transactions on Knowledge and Data Engineering, 2007, 19(8): 1072-1088.
[15] ZHANG Z, LU H, OOI C, et al. Understanding the meaning of a shifted sky: a general framework on extending skyline query [J]. The International Journal on Very Large Data Bases, 2010, 19(2): 181-201.

Ranking-k: effective subspace dominating query algorithm

有效的子空间支配查询算法——Ranking-k

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	XIE Yu, JIANG Yu, LONG Chaoqi. Extended isolation forest algorithm based on random subspace [J]. Journal of Computer Applications, 2021, 41(6): 1679-1685.
[2]	LIN Junchao, WAN Yuan. Self-adaptive multi-measure unsupervised feature selection method with structured graph optimization [J]. Journal of Computer Applications, 2021, 41(5): 1282-1289.
[3]	LYU Jia, XIAN Yan. Co-training algorithm combining improved density peak clustering and shared subspace [J]. Journal of Computer Applications, 2021, 41(3): 686-693.
[4]	ZHU Yuna, ZHANG Yutao, YAN Shaoge, FAN Yudan, CHEN Hantuo. Protocol identification approach based on semi-supervised subspace clustering [J]. Journal of Computer Applications, 2021, 41(10): 2900-2904.
[5]	WANG Lijuan, CHEN Shaomin, YIN Ming, XU Yueying, HAO Zhifeng, CAI Ruichu, WEN Wen. Improved block diagonal subspace clustering algorithm based on neighbor graph [J]. Journal of Computer Applications, 2021, 41(1): 36-42.
[6]	HUANG Xueyu, XU Haote, TAO Jianwen. Multi-source adaptation classification framework with feature selection [J]. Journal of Computer Applications, 2020, 40(9): 2499-2506.
[7]	LI Xingfeng, HUANG Yuqing, REN Zhenwen. Joint low-rank and sparse multiple kernel subspace clustering algorithm [J]. Journal of Computer Applications, 2020, 40(6): 1648-1653.
[8]	CHENG Yusheng, SONG Fan, WANG Yibin, QIAN Kun. Multi-label feature selection algorithm based on conditional mutual information of expert feature [J]. Journal of Computer Applications, 2020, 40(2): 503-509.
[9]	ZENG Meng, NING Bin, CAI Zhihua, GU Qiong. Hyperspectral band selection based on deep adversarial subspace clustering [J]. Journal of Computer Applications, 2020, 40(2): 381-385.
[10]	TAN Yao, RAO Wenbi. Heterogeneous compound transfer learning method for video content annotation [J]. Journal of Computer Applications, 2018, 38(6): 1547-1553.
[11]	ZHANG Leyuan, LI Jiaye, LI Pengqing. Low rank non-linear feature selection algorithm [J]. Journal of Computer Applications, 2018, 38(12): 3444-3449.
[12]	YUAN Haojie, SUN Guiling, XU Yi, ZHENG Bowen. Face recognition based on complement null-space and nearest space distance [J]. Journal of Computer Applications, 2017, 37(5): 1475-1480.
[13]	FANG Ning, ZHOU Yu, YE Qingwei, LI Yugang. Modal parameter identification of vibration signal based on unsupervised learning convolutional neural network [J]. Journal of Computer Applications, 2017, 37(3): 786-790.
[14]	CHENG Lingfang, YANG Tianpeng, CHEN Lifei. Soft subspace clustering algorithm for imbalanced data [J]. Journal of Computer Applications, 2017, 37(10): 2952-2957.
[15]	WU Jieqi, LI Xiaoyu, YUAN Xiaotong, LIU Qingshan. Parallel sparse subspace clustering via coordinate descent minimization [J]. Journal of Computer Applications, 2016, 36(2): 372-376.