Recently, large uncertain databases have attracted much attention in many applications, including data management, data integration, social media and security investigation and so on. K-Rank queries, according to matching scores, are an important tool for exploring large uncertain data sets. Few algorithms have been developed to solve this problem. In spite of these works, developing more efficient algorithm is on demand. The problem can be represented as a model of n tuples consist of m instances, and each query-tuple randomly instantiates into one or more tuples based on a set of multi-alternative instances. In this paper, we present an effective backtracking-based algorithm, called Fast Multi-Objective Optimization (FMOO) algorithm. It is able to find K-Rank queries on uncertain databases with efficient memory usage and time complexity O(knlogn), whereas all existing algorithms run in quadratic space and time complexity. Experimental evaluation on synthetic data with theoretical analysis have been provided to demonstrate the efficiency of the new algorithm.
展开▼
