Layered Indices for Probabilistic Top-k Queries
Yan Jia · Journal of Chinese Computer Systems · 2011
Query processing on uncertain data has been a recent hot topic in the database community because of its wide range of applications.Probabilistic top-k queries have multiple query semantics because they rank data according to both scoring function and probability.As a class of I/O intensive queries,the probabilistic top-k queries need general indexing techniques to improve the query efficiency.Starting from the analysis of the nature of probabilistic top-k queries,this paper proposes two layered indices based on the concept of skyline and dominating frequency respectively.Both theoretical analysis and experimental results have shown that both indices can be used by the probabilistic top-k queries which meet the specific natures to improve the I/O efficiency,and the index based on dominating frequency is more robust than the one based on skyline.