关键词: 不确定数据, 分布式算法, 余弦相似度, 相似性查询

Abstract: Nearest neighbor queries have been used in a wide variety of applications such as collaborative filtering, location-based services and decision support systems. Meanwhile, with the development of entity extraction in Web information, information transformation in privacy protection, text recognition in images, in many fields, uncertain text information is ubiquitous. In the field of information theory, the calculation of textual similarity is transformed to the computation of vector similarity by TF-IDF algorithm, which is rigorous and efficient. However, cosine distance based on TF-IDF does not belong to metric distance function, and it is difficult to build indices on cosine similarity. To this end, this paper studies methods for nearest neighbor queries on uncertain data with cosine similarity constraints. Existing methods are efficient either for numerical data or for certain data, but there is no method that can efficiently support uncertain and character data. So this paper first analyzes the property of cosine similarity to boost up similarity computation. Secondly, this paper proposes an efficient method for similarity queries on uncertain data by transforming cosine similarity computation, and designs an improved tree index for metric space, sMVP-tree (statistic multiple vantage point tree). Lastly, this paper extends the framework to a distributed environment and presents kNN query and RkNN algorithms. The experimental results show that the proposed method is effective and efficient.

Key words: uncertain data, distributed algorithm, cosine similarity, similarity query