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

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

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

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

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