Izvorni znanstveni članak

https://doi.org/10.17559/TV-20190124092015

An Efficient Top-k Query Scheme Based on Multilayer Grouping

Zongmin Cui ; School of Information Science and Technology, Jiujiang University, No. 551, Qianjin East Road, Jiujiang, Jiangxi 332005, China
Yu Gao ; School of Information Science and Technology, Jiujiang University, No. 551, Qianjin East Road, Jiujiang, Jiangxi 332005, China
Caixue Zhou ; School of Information Science and Technology, Jiujiang University, No. 551, Qianjin East Road, Jiujiang, Jiangxi 332005, China
Guangyong Gao ; School of Computer and Software, Nanjing University of Information Science and Technology, No. 219, Ningliu Road, Nanjing, Jiangsu 210000, China / School of Information Science and Technology, Jiujiang University, No. 551, Qianjin East Road, Jiujiang, Jia
Zhuolin Mei ; School of Information Science and Technology, Jiujiang University, No. 551, Qianjin East Road, Jiujiang, Jiangxi 332005, China
Zongda Wu ; Oujiang College, Wenzhou University, Wenzhou 325035, Zhejiang, China

Sažetak

The top-k query is to find the k data that has the highest scores from a candidate dataset. Sorting is a common method to find out top-k results. However, most of existing methods are not efficient enough. To remove this issue, we propose an efficient top-k query scheme based on multilayer grouping. First, we find the reference item by computing the average score of the candidate dataset. Second, we group the candidate dataset into three datasets: winner set, middle set and loser set based on the reference item. Third, we further group the winner set to the second-layer three datasets according to k value. And so on, until the data number of winner set is close to k value. Meanwhile, if k value is larger than the data number of winner set, we directly return the winner set to the user as a part of top-k results almost without sorting. In this case, we also return the top results with the highest scores from the middle set almost without sorting. Based on above innovations, we almost minimize the sorting. Experimental results show that our scheme significantly outperforms the current classical method on the performance of memory consumption and top-k query.

Ključne riječi

almost minimizing sorting; multilayer grouping; top-k query

Hrčak ID:

226017

URI

https://hrcak.srce.hr/226017

Datum izdavanja:

8.10.2019.

Posjeta: 1.155 *