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 条
  • [31] Efficient processing of top-k dominating queries in distributed environments
    Daichi Amagata
    Yuya Sasaki
    Takahiro Hara
    Shojiro Nishio
    World Wide Web, 2016, 19 : 545 - 577
  • [32] Efficient Distributed Top-k Query Processing with Caching
    Ryeng, Norvald H.
    Vlachou, Akrivi
    Doulkeridis, Christos
    Norvag, Kjetil
    DATABASE SYSTEMS FOR ADVANCED APPLICATIONS, PT II, 2011, 6588 : 280 - 295
  • [33] Distributed Top-k Query Processing on Multi-dimensional Data with Keywords
    Amagata, Daichi
    Hara, Takahiro
    Nishio, Shojiro
    PROCEEDINGS OF THE 27TH INTERNATIONAL CONFERENCE ON SCIENTIFIC AND STATISTICAL DATABASE MANAGEMENT, 2015,
  • [34] Efficient processing of top-k dominating queries in distributed environments
    Amagata, Daichi
    Sasaki, Yuya
    Hara, Takahiro
    Nishio, Shojiro
    WORLD WIDE WEB-INTERNET AND WEB INFORMATION SYSTEMS, 2016, 19 (04): : 545 - 577
  • [35] Examining the Additivity of Top-k Query Processing Innovations
    Mackenzie, Joel
    Moffat, Alistair
    CIKM '20: PROCEEDINGS OF THE 29TH ACM INTERNATIONAL CONFERENCE ON INFORMATION & KNOWLEDGE MANAGEMENT, 2020, : 1085 - 1094
  • [36] Uncertain top-k query processing in distributed environments
    Xite Wang
    Derong Shen
    Ge Yu
    Distributed and Parallel Databases, 2016, 34 : 567 - 589
  • [37] Top-k query processing for replicated data in mobile peer to peer networks
    Sasaki, Yuya
    Hara, Takahiro
    Nishio, Shojiro
    JOURNAL OF SYSTEMS AND SOFTWARE, 2014, 92 : 45 - 58
  • [38] Effective and efficient top-k query processing over incomplete data streams
    Ren, Weilong
    Lian, Xiang
    Ghazinour, Kambiz
    INFORMATION SCIENCES, 2021, 544 : 343 - 371
  • [39] Efficient Top-k Retrieval on Massive Data
    Han, Xixian
    Li, Jianzhong
    Gao, Hong
    IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, 2015, 27 (10) : 2687 - 2699
  • [40] Efficient Top-k Retrieval on Massive Data
    Han, Xixian
    Li, Jianzhong
    Gao, Hong
    2016 32ND IEEE INTERNATIONAL CONFERENCE ON DATA ENGINEERING (ICDE), 2016, : 1496 - 1497