%0 Journal Article
%T An Algorithm Based on RGH-Tree for Similarity Search Queries<br>基于广义超曲面树的相似性搜索算法
%A ZHANG Zhao-gong
%A LI Jian-zhong
%A <br>张兆功
%A 李建中
%J 软件学报
%D 2002
%I 
%X Similarity search is a very important problem in data mining. It retrieves similar objects in database and finds proximity between objects. It can be applied to image/picture databases, spatial databases, and time-series databases. For Euclid space (a special metric space), similarity search algorithms based on R-tree are efficient in low-dimensional space, but degenerate into linear scan for high-dimensional space. This phenomenon is called dimensionality curse. This paper presents a new partition and index method of metric space, rgh-tree which distributes and partitions objects by using distance information if objects with rew fixed reference. It produces a balance tree with no data overlay. In addition, an algorithm based on rgh-tree, which is suitable for similarity search in metric space, is presented in this paper. The algorithm overcomes the shortcomings of the exiting algorithms, which has less I/O cost and times of computing distance, with average complexity o(n0.58).
%K algorithm
%K similarity search query
%K metric space
%K database<br>算法
%K 相似性搜索
%K 度量空间
%K 数据库
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=7735F413D429542E610B3D6AC0D5EC59&aid=211474AD19C80CE6&yid=C3ACC247184A22C1&vid=FC0714F8D2EB605D&iid=F3090AE9B60B7ED1&sid=F3D9B969D1F8BD1F&eid=64CE2972A4410367&journal_id=1000-9825&journal_name=软件学报&referenced_num=2&reference_num=13