三維空間索引結(jié)構(gòu)—LABB樹的研究.pdf

1、索引結(jié)構(gòu)是逆向工程中的重要問題，索引結(jié)構(gòu)的性能決定著空間數(shù)據(jù)的存儲、管理和查詢效率。目前索引結(jié)構(gòu)主要分為靜態(tài)索引和動態(tài)索引，靜態(tài)索引不具備數(shù)據(jù)動態(tài)管理能力而且運算效率低、系統(tǒng)消耗資源高；動態(tài)索引結(jié)構(gòu)完善了數(shù)據(jù)動態(tài)存儲和管理，但仍然存在空間利用率低、自適應(yīng)性差等問題。
　　本文基于R*-樹在逆向工程中的應(yīng)用進(jìn)行研究和優(yōu)化，針對上述問題提出一種基于遺傳算法優(yōu)化的最小包圍盒算法及聚類分簇算法的三維LABB(Local Approxima

2、te Bounding Box)樹索引結(jié)構(gòu)，有效減少結(jié)點的重疊度和死區(qū)的體積，提高結(jié)點的內(nèi)聚性和索引結(jié)點分裂的自適應(yīng)性，優(yōu)化分裂結(jié)果，提高索引結(jié)構(gòu)的查詢效率，主要研究內(nèi)容及成果如下：
　　1)提出一種遺傳算法與O’Rourke的最小包圍盒算法結(jié)合的近似最小包圍盒優(yōu)化求解算法，將包圍盒體積函數(shù)作為目標(biāo)函數(shù)，設(shè)定適應(yīng)度函數(shù)和編碼方案，通過各參數(shù)算子的設(shè)置使迭代過程快速收斂到最優(yōu)解獲得最小包圍盒，解決了時間復(fù)雜度過大、求解效率過低等問題

3、。
　　2)針對k-均值容易陷入局部最優(yōu)解和需要手動輸入?yún)?shù)的問題，基于遺傳算法的全局搜索能力彌補k-均值的缺陷，提出了基于遺傳多目標(biāo)優(yōu)化的結(jié)點自適應(yīng)聚類算法。基于遺傳多目標(biāo)優(yōu)化的方法求解不同簇數(shù)下的全局最優(yōu)分裂解，即得到節(jié)點分裂的Pareto最優(yōu)解集，并以結(jié)點MBR(Minimum Bounding Rectangle)的重疊度與MBR的體積之和分別作為主要、次要評價標(biāo)準(zhǔn)從Pareto最優(yōu)解集中選出偏好解，將其視為索引結(jié)構(gòu)的最優(yōu)