计算机研究与发展
計算機研究與髮展
계산궤연구여발전
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
2003年
8期
1209-1215
,共7页
算法%相似性搜索%度量空间%数据库%数据挖掘
算法%相似性搜索%度量空間%數據庫%數據挖掘
산법%상사성수색%도량공간%수거고%수거알굴
相似性搜索是从数据库中检索出同给定数据对象相似的数据对象,已有的基于R-tree的相似性搜索,当搜索空间的维的个数较小时效率较高,但当搜索空间的维的个数较大时则效率很低 .针对此问题,提出了新的度量空间分割方法和索引结构pgh-tree,利用数据对象与很少几个固定参考对象的距离之差进行数据分割和索引,产生一个平衡的索引树 .在此基础上,提出了新的算法,利用查询数据对象与固定参考对象的距离之差过滤掉大部分的不相关数据,具有较小的I/O代价和距离计算复杂性,平均复杂性为θ(n0.58),是目前复杂性最小的相似性搜索算法 .另外还讨论了基于pgh-tree的最近相邻点搜索策略 .
相似性搜索是從數據庫中檢索齣同給定數據對象相似的數據對象,已有的基于R-tree的相似性搜索,噹搜索空間的維的箇數較小時效率較高,但噹搜索空間的維的箇數較大時則效率很低 .針對此問題,提齣瞭新的度量空間分割方法和索引結構pgh-tree,利用數據對象與很少幾箇固定參攷對象的距離之差進行數據分割和索引,產生一箇平衡的索引樹 .在此基礎上,提齣瞭新的算法,利用查詢數據對象與固定參攷對象的距離之差過濾掉大部分的不相關數據,具有較小的I/O代價和距離計算複雜性,平均複雜性為θ(n0.58),是目前複雜性最小的相似性搜索算法 .另外還討論瞭基于pgh-tree的最近相鄰點搜索策略 .
상사성수색시종수거고중검색출동급정수거대상상사적수거대상,이유적기우R-tree적상사성수색,당수색공간적유적개수교소시효솔교고,단당수색공간적유적개수교대시칙효솔흔저 .침대차문제,제출료신적도량공간분할방법화색인결구pgh-tree,이용수거대상여흔소궤개고정삼고대상적거리지차진행수거분할화색인,산생일개평형적색인수 .재차기출상,제출료신적산법,이용사순수거대상여고정삼고대상적거리지차과려도대부분적불상관수거,구유교소적I/O대개화거리계산복잡성,평균복잡성위θ(n0.58),시목전복잡성최소적상사성수색산법 .령외환토론료기우pgh-tree적최근상린점수색책략 .
