Abstract:

Grid index is often used in the query of top k and skyline in DSMS, but it is coarsegrained. In this paper, we propose a  Reverse Dominant Point Set   ( RDPS )  algorithm which is based on grid index, and prune a number of cells in grid index using the characteristics of RDPS to improve the precision of top k queries, thus accessing the  data set in queries is limited to  the kmax calculating region . So, it reduces the memory usage of grid index and the overhead of queries. Analytical and experimental evidences show the efficiency of the proposed approaches.

Key words: preference topk queries;grid index;reserve dominant point set;data stream