TY - GEN
T1 - Global Top-k aggregate queries based on x-tuple in uncertain database
AU - Liu, Dexi
AU - Wan, Changxuan
AU - Xiong, Naixue
AU - Park, Jong Hyuk
AU - Yeoe, Sang Soo
PY - 2010
Y1 - 2010
N2 - A Top-k aggregate query, which is a powerful technique when dealing with large quantity of data, ranks groups of tuples by their aggregate values and returns k groups with the highest aggregate values. However, compared to Top-k in traditional databases, queries over uncertain database are more complicated because of the existence of exponential possible worlds. As a powerful semantic of Top-k in uncertain database, Global Top-k return k highest-ranked tuples according to their probabilities of being in the Top-k answers in possible worlds. We propose a x-tuple based method to process Global Top-k aggregate queries in uncertain database. Our method has two levels, group state generation and G-x-Top-k query processing. In the former level, group states, which satisfy the properties of x-tuple, are generated one after the other according to their aggregate values, while in the latter level, dynamic programming based Global x-tuple Top-k query processing are employed to return the answers. Comprehensive experiments on different data sets demonstrate the effectiveness of the proposed solutions.
AB - A Top-k aggregate query, which is a powerful technique when dealing with large quantity of data, ranks groups of tuples by their aggregate values and returns k groups with the highest aggregate values. However, compared to Top-k in traditional databases, queries over uncertain database are more complicated because of the existence of exponential possible worlds. As a powerful semantic of Top-k in uncertain database, Global Top-k return k highest-ranked tuples according to their probabilities of being in the Top-k answers in possible worlds. We propose a x-tuple based method to process Global Top-k aggregate queries in uncertain database. Our method has two levels, group state generation and G-x-Top-k query processing. In the former level, group states, which satisfy the properties of x-tuple, are generated one after the other according to their aggregate values, while in the latter level, dynamic programming based Global x-tuple Top-k query processing are employed to return the answers. Comprehensive experiments on different data sets demonstrate the effectiveness of the proposed solutions.
KW - Dynamic programming algorithm
KW - G-x-top-k queries
KW - Global Top-k aggregate queries
KW - Uncertain database
UR - http://www.scopus.com/inward/record.url?scp=77954807797&partnerID=8YFLogxK
U2 - 10.1109/WAINA.2010.183
DO - 10.1109/WAINA.2010.183
M3 - Conference contribution
AN - SCOPUS:77954807797
SN - 9780769540191
T3 - 24th IEEE International Conference on Advanced Information Networking and Applications Workshops, WAINA 2010
SP - 814
EP - 821
BT - 24th IEEE International Conference on Advanced Information Networking and Applications Workshops, WAINA 2010
T2 - 24th IEEE International Conference on Advanced Information Networking and Applications Workshops, WAINA 2010
Y2 - 20 April 2010 through 23 April 2010
ER -