幾何區(qū)域查詢算法的研究.pdf

1、幾何區(qū)域查詢問題是計算幾何領(lǐng)域的一個重要研究內(nèi)容，它來源于數(shù)據(jù)庫和地理信息系統(tǒng)應(yīng)用的需求而產(chǎn)生并迅速發(fā)展，同時在計算機圖形學(xué)、模式識別等領(lǐng)域得到了廣泛的應(yīng)用。該問題往往是某一領(lǐng)域中的關(guān)鍵性子問題，如光線追蹤、隱藏面消除、相交性判定、相似性查詢、最近鄰查詢等。 數(shù)據(jù)查詢的實質(zhì)是對數(shù)據(jù)的分類索引的過程，一般分為兩類：一類是對數(shù)據(jù)空間的分割，將整個數(shù)據(jù)空間遞歸劃分為一系列子空間；另一類是將高維空間中的數(shù)據(jù)對象映射到一維空間中，然后利用

2、一維空間中數(shù)據(jù)間的有序性高效的處理數(shù)據(jù)。 本文主要做了以下工作： 1.凹顧了計算幾何及幾何區(qū)域查詢的相關(guān)理論、常見的區(qū)域查詢類型以及國內(nèi)外的研究現(xiàn)狀。從數(shù)學(xué)理論的角度出發(fā)，利用代數(shù)學(xué)中半群的概念，在加權(quán)意義下給出了區(qū)域查詢問題統(tǒng)一的理論模型，并利用耗費函數(shù)作為衡量算法效率的計算模型，為區(qū)域查詢算法的提出、實現(xiàn)及復(fù)雜度分析提供了理論依據(jù)和判斷準(zhǔn)則。 2.對正交區(qū)域查詢問題的一些經(jīng)典數(shù)據(jù)組織結(jié)構(gòu)的構(gòu)建思想、查詢算法及

3、實現(xiàn)方法做了詳細(xì)分析和研究，這是進行算法改進和創(chuàng)新的基礎(chǔ)和依據(jù)。 3.根據(jù)數(shù)據(jù)對象多個屬性間重要性的差異，采用“粗篩”與“細(xì)篩”相結(jié)合，層次化的查詢結(jié)構(gòu)對數(shù)據(jù)空間進行了分割。首先，對數(shù)據(jù)對象進行大尺度的粗選，排除大量無關(guān)數(shù)據(jù)；其次，采用較小的尺度進一步縮小可選集的范圍；最后，采用精確的查詢。具體來講，為了獲得較高的查詢和動態(tài)更新效率并且提高數(shù)據(jù)組織的靈活性，采用了以地址方式存儲數(shù)據(jù)的鏈表結(jié)構(gòu)作為基本數(shù)據(jù)載體；為了實現(xiàn)不同尺度的分

4、割，采用了改進的1-3確定性跳躍表；由于鏈表是一種線性存儲結(jié)構(gòu)較難用于高維數(shù)據(jù)對象，為此采用了將一維鏈表映射到高維空間的辦法實現(xiàn)了層次化數(shù)據(jù)結(jié)構(gòu)，使其成為適應(yīng)高維空間區(qū)域查詢的索引結(jié)構(gòu)。該結(jié)構(gòu)繼承了跳躍表的優(yōu)點。利用確定性跳躍表來代替高度遞歸的區(qū)域查詢樹，該結(jié)構(gòu)既實現(xiàn)了對k維空間區(qū)域查詢的高效性，又規(guī)避了跳躍表結(jié)構(gòu)本身的缺點。本文給出了該結(jié)構(gòu)的完整定義，并給出了該結(jié)構(gòu)的實現(xiàn)算法以及建立在該結(jié)構(gòu)之上的查詢、插入和刪除算法。通過對計算模型分