Sliding window top-k dominating query processing over distributed data streams

详细信息    查看全文

• 作者：Daichi Amagata ; Takahiro Hara ; Shojiro Nishio
• 刊名：Distributed and Parallel Databases
• 出版年：2016
• 出版时间：December 2016
• 年：2016
• 卷：34
• 期：4
• 页码：535-566
• 全文大小：2,192 KB
• 刊物类别：Computer Science
• 刊物主题：Database Management
  Data Structures
  Information Systems Applications and The Internet
  Operating Systems
  Memory Structures
  
• 出版者：Springer Netherlands
• ISSN：1573-7578
• 卷排序：34

文摘

Preference query processing is important for a wide range of applications involving distributed databases, such as network monitoring, web-based systems, and market analysis. In such applications, data objects are generated frequently and massively, which presents an important and challenging problem of continuous query processing over distributed data stream environments. A top-k dominating query, which has been receiving much research attention recently, returns the k data objects that dominate the highest number of data objects in a given dataset, and due to its dominance-based ranking function, we can easily obtain superior data objects. An emerging requirement in distributed stream environments is an efficient technique for continuously monitoring top-k dominating data objects. Despite of this fact, no study has addressed this problem. In this paper, therefore, we address the problem of continuous top-k dominating query processing over distributed data stream environments. We present two algorithms that monitor the exact top-k dominating data and efficiently eliminate unqualified data objects for the result, which reduces both communication and computation costs. In addition to these algorithms, we present an approximate algorithm that further reduces both communication and computation costs. Extensive experiments on both synthetic and real data have demonstrated the efficiency and scalability of our algorithms.KeywordsTop-k dominating queriesMulti-dimensional dataDistributed data streams