Optimizing Distributed Top-k Queries

被引：0
作者：
Neumann, Thomas [1 ]
Bender, Matthias [1 ]
Michel, Sebastian [2 ]
Schenkel, Ralf [1 ]
Triantafillou, Peter [3 ,4 ]
Weikum, Gerhard [1 ]
机构：
[1] Max Planck Inst Informat, Saarbrucken, Germany
[2] Ecole Polytech Fed Lausanne, Lausanne, Switzerland
[3] Univ Patras, Patras, Greece
[4] RACTI, Patras, Greece
来源：
WEB INFORMATION SYSTEMS ENGINEERING - WISE 2008, PROCEEDINGS | 2008年 / 5175卷
关键词：
D O I：
暂无
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
Top-k query processing is a fundamental building block for efficient ranking in a large number of applications. Efficiency is a central issue, especially for distributed settings, when the data is spread across different nodes in a network. This paper introduces novel optimization methods for top-k aggregation queries in such distributed environments that can be applied to all algorithms that fall into the frameworks of the prior TPUT and KLEE methods. The optimizations address 1) hierarchically grouping input lists into top-k operator trees and optimizing the tree structure, and 2) computing data-adaptive scan depths for different input sources. The paper presents comprehensive experiments with two different real-life datasets, using the ns-2 network simulator for a packet-level simulation of a large Internet-style network.
引用
收藏
页码：337 / +
页数：3
相关论文
共 24 条
[1]   Reducing network traffic in unstructured P2P systems using Top-k queries [J].
Akbarinia, Reza ;
Pacitti, Esther ;
Valduriez, Patrick .
DISTRIBUTED AND PARALLEL DATABASES, 2006, 19 (2-3) :67-86
[2]  
Balke WT, 2005, PROC INT CONF DATA, P174
[3]  
Brijs T., 1999, P 5 ACM SIGKDD INT C, P254, DOI 10.1145/312129.312241
[4]  
Cao P., 2004, P 23 ANN ACM S PRINC, P206, DOI [10.1145/1011767.1011798, DOI 10.1145/1011767.1011798]
[5]  
Chang K. C.-C., 2002, PROC ACM SIGMOD INT, P346
[6]  
Das G., 2006, P 32 INT C VER LARG, P451
[7]  
DAS G, 2007, VLDB, P183
[8]  
Dubinko M, 2006, P 15 INT C WORLD WID, P193
[9]   Optimal aggregation algorithms for middleware [J].
Fagin, R ;
Lotem, A ;
Naor, M .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2003, 66 (04) :614-656
[10]  
GAROFALAKIS M, 2005, IEEE DATA ENG B, V28
123