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 条
  • [41] Scalable Top-K Query Processing Using Graphics Processing Unit
    Zhang, Yulin
    Fang, Hui
    Li, Xiaoming
    LANGUAGES AND COMPILERS FOR PARALLEL COMPUTING, LCPC 2017, 2019, 11403 : 240 - 261
  • [42] Efficient top-k query evaluation on probabilistic data
    Re, Christopher
    Dalvi, Nilesh
    Suciu, Dan
    2007 IEEE 23RD INTERNATIONAL CONFERENCE ON DATA ENGINEERING, VOLS 1-3, 2007, : 861 - +
  • [43] Top-k Correlated Subgraph Query for Data Streams
    Pan, Shirui
    Zhu, Xingquan
    Fang, Meng
    2012 21ST INTERNATIONAL CONFERENCE ON PATTERN RECOGNITION (ICPR 2012), 2012, : 2906 - 2909
  • [44] A Top-k query algorithm on uncertain streaming data
    Wang, Ying
    Yu, Jianqiao
    Journal of Computational Information Systems, 2013, 9 (13): : 5273 - 5279
  • [45] Top-k Dominating Queries: an introduction
    Manolopoulos, Yannis
    2015 12th IEEE International Conference on Programming and Systems (ISPS), 2015,
  • [46] Weighted top-k dominating queries on highly incomplete data
    Fattah, H. M. Abdul
    Hasan, K. M. Azharul
    Tsuji, Tatsuo
    INFORMATION SYSTEMS, 2022, 107
  • [47] Top-k Dominating Queries: a Survey
    Tiakas, Eleftherios
    Papadopoulos, Apostolos N.
    Manolopoulos, Yannis
    2015 12TH IEEE INTERNATIONAL CONFERENCE ON PROGRAMMING AND SYSTEMS (ISPS), 2015,
  • [48] Probabilistic Reverse Top-k Query on Probabilistic Data
    Trieu Minh Nhut Le
    Cao, Jinli
    DATABASES THEORY AND APPLICATIONS, ADC 2023, 2024, 14386 : 30 - 43
  • [49] Method for Top-K query on big data in cloud
    Ci, X. (cixiang31415926@126.com), 1600, Chinese Academy of Sciences (25):
  • [50] Continuous Top-k Dominating Queries
    Kontaki, Maria
    Papadopoulos, Apostolos N.
    Manolopoulos, Yannis
    IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, 2012, 24 (05) : 840 - 853