於機率性資料庫中選擇具影響力物件之技術

Abstract

In this dissertation, we study how to select influential objects in probabilistic databases. For an uncertain dataset with probabilistic attribute values, we would like to tell which objects can best improve query or mining results if we can acquire their exact attribute values. The problem is explored on both clustering and the Probabilistic k-Nearest-Neighbor (k-PNN) query. We carefully define the metrics for evaluating the quality of the results of clustering and k-PNN query, and then we design algorithms to find the solutions according to the metrics correspondingly. For the k-PNN query, we provide optimal solutions of acquisition for nearest-neighbor query (1-PNN), and we propose a scalable algorithm solving the acquisition for k-PNN query with k > 1. Besides, for a social network dataset with edge probabilities, we would like to tell which neighboring nodes of the query node can best help gather specific information if these nodes are asked. We carefully formulate the problem according to the motivated scenario, and the proposed approach considers both the strength and the diversity of a node’s influence. We conduct experiments on various datasets, and the experimental results demonstrate the effectiveness and the efficiency of the proposed approaches.