TDEP: efficiently processing top-k dominating query on massive data

被引:0
|
作者
Xixian Han
Jianzhong Li
Hong Gao
机构
[1] Harbin Institute of Technology,School of Computer Science and Technology
来源
Knowledge and Information Systems | 2015年 / 43卷
关键词
Massive data; Top-; dominating query; TDEP algorithm; Sorted lists; Early pruning;
D O I
暂无
中图分类号
学科分类号
摘要
In many applications including multicriteria decision making, top-k dominating query is a practically useful tool to return k tuples with the highest domination scores in a potentially huge data space. The existing algorithms, either requiring indexes built on the specific attribute subset, or incurring high I/O cost or memory cost, cannot process top-k dominating query on massive data efficiently. In this paper, a novel algorithm TDEP is proposed to utilize sorted lists built for each attribute with low cost to return top-k dominating result on massive data efficiently. Through analysis, it is found that TDEP can be divided into two phases: growing phase and shrinking phase. In each phase, TDEP retrieves the sorted lists in round-robin fashion and maintains the candidates until the stop condition is satisfied. The theoretical analysis is provided for the execution behavior in two phases. An efficient method is developed to compute the domination scores of tuples with the obtained candidates only. Besides, TDEP adopts early pruning to reduce the number of candidate tuples maintained significantly. The extensive experimental results, conducted on synthetic and real-life data sets, show the significant performance advantage of TDEP over the existing algorithms.
引用
收藏
页码:689 / 718
页数:29
相关论文
共 50 条
  • [1] TDEP: efficiently processing top-k dominating query on massive data
    Han, Xixian
    Li, Jianzhong
    Gao, Hong
    KNOWLEDGE AND INFORMATION SYSTEMS, 2015, 43 (03) : 689 - 718
  • [2] TKAP: Efficiently processing top-k query on massive data by adaptive pruning
    Han, Xixian
    Liu, Xianmin
    Li, Jianzhong
    Gao, Hong
    KNOWLEDGE AND INFORMATION SYSTEMS, 2016, 47 (02) : 301 - 328
  • [3] TKAP: Efficiently processing top-k query on massive data by adaptive pruning
    Xixian Han
    Xianmin Liu
    Jianzhong Li
    Hong Gao
    Knowledge and Information Systems, 2016, 47 : 301 - 328
  • [4] TKEP: An efficient top-k query processing algorithm on massive data
    Han X.-X.
    Yang D.-H.
    Li J.-Z.
    Jisuanji Xuebao/Chinese Journal of Computers, 2010, 33 (08): : 1405 - 1417
  • [5] Supporting early pruning in top-k query processing on massive data
    Han, Xixian
    Li, Jianzhong
    Yang, Donghua
    INFORMATION PROCESSING LETTERS, 2011, 111 (11) : 524 - 532
  • [6] Efficient Top-k Dominating Computation on Massive Data
    Han, Xixian
    Li, Jianzhong
    Gao, Hong
    IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, 2017, 29 (06) : 1199 - 1211
  • [7] An Effective Pruning Scheme for Top-k Dominating Query Processing on Uncertain Data Streams
    Lai, Chuan-Chi
    Fan, Chih-Cheng
    Liu, Chuan-Ming
    2022 IEEE VTS ASIA PACIFIC WIRELESS COMMUNICATIONS SYMPOSIUM, APWCS, 2022, : 104 - 108
  • [8] Sliding window top-k dominating query processing over distributed data streams
    Daichi Amagata
    Takahiro Hara
    Shojiro Nishio
    Distributed and Parallel Databases, 2016, 34 : 535 - 566
  • [9] Sliding window top-k dominating query processing over distributed data streams
    Amagata, Daichi
    Hara, Takahiro
    Nishio, Shojiro
    DISTRIBUTED AND PARALLEL DATABASES, 2016, 34 (04) : 535 - 566
  • [10] An Effective Method for Top-k Dominating Query Processing over Multiple Uncertain Data Streams
    Liu, Chuan-Ming
    Wang, Tien-Chun
    Lai, Chuan-Chi
    Wang, Li-Chun
    2018 27TH WIRELESS AND OPTICAL COMMUNICATION CONFERENCE (WOCC), 2018, : 91 - 95