A Survey of Top-k Query Processing Techniques in Relational Database Systems

被引：505

作者：

Ilyas, Ihab F. ^{[1
]}

Beskales, George ^{[1
]}

Soliman, Mohamed A. ^{[1
]}

机构：

[1] Univ Waterloo, Waterloo, ON N2L 3G1, Canada

来源：

ACM COMPUTING SURVEYS | 2008年 / 40卷 / 04期

基金：

加拿大自然科学与工程研究理事会;

关键词：

Algorithms; Design; Experimentation; Performance; Top-k; rank-aware processing; rank aggregation; voting;

D O I：

10.1145/1391729.1391730

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Efficient processing of top-k queries is a crucial requirement in many interactive environments that involve massive amounts of data. In particular, efficient top-k processing in domains such as the Web, multimedia search, and distributed systems has shown a great impact on performance. In this survey, we describe and classify top- k processing techniques in relational databases. We discuss different design dimensions in the current techniques including query models, data access methods, implementation levels, data and query certainty, and supported scoring functions. We show the implications of each dimension on the design of the underlying techniques. We also discuss top- k queries in XML domain, and show their connections to relational approaches.

引用

页数：58

共 70 条

[61]

Theobald M., 2005, VLDB, P625

[62]

TRUCHON M, 1998, CAHIER U LAVAL, V9815

[63] Ranked join indices [J].

Tsaparas, P ;

Palpanas, T ;

Kotidis, Y ;

Koudas, N ;

Srivastava, D .

19TH INTERNATIONAL CONFERENCE ON DATA ENGINEERING, PROCEEDINGS, 2003, :277-288

[64] APPROXIMATE - A QUERY PROCESSOR THAT PRODUCES MONOTONICALLY IMPROVING APPROXIMATE ANSWERS [J].

VRBSKY, SV ;

LIU, JWS .

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, 1993, 5 (06) :1056-1068

[65]

XIN D, 2006, P 32 INT C VER LARG, P235

[66]

Xin Dong, 2007, SIGMOD, P103

[67] CONSISTENT EXTENSION OF CONDORCETS ELECTION PRINCIPLE [J].

YOUNG, HP ;

LEVENGLICK, A .

SIAM JOURNAL ON APPLIED MATHEMATICS, 1978, 35 (02) :285-300

[68]

Yuan Y., 2005, Proceedings of the 31st International Conference on Very Large Data Bases", VLDB '05, P241

[69]

Zhang Z., 2006, SIGMOD C, P359

[70]

[No title captured]

← 1 2 3 4 5 6 7 →