1、區(qū)域搜索問題和眾多的實(shí)際應(yīng)用有著緊密的聯(lián)系,例如地理信息系統(tǒng)、計算幾何、計算機(jī)圖形學(xué)、空間數(shù)據(jù)庫和時間序列數(shù)據(jù)庫等系統(tǒng),其實(shí)日常生活中也不乏眾多例子.區(qū)域搜索問題有著豐富的內(nèi)容,該文主要通過一些典型實(shí)例來介紹區(qū)域搜索問題.一般來說,討論的問題或者定義在群上,或者定義在半群上.該文詳細(xì)描述了OLAP上的區(qū)域和查詢和區(qū)域最大值查詢兩個典型的例子,前者的運(yùn)算是定義在群上,而后者的運(yùn)算是定義在半群上的.該文的貢獻(xiàn),主要是用基于壓縮的方法來研究一

2、維空間中的區(qū)域最大值問題.設(shè)計了兩種PHB數(shù)據(jù)結(jié)構(gòu)來存儲預(yù)處理數(shù)據(jù),一個用分層的數(shù)組,另一個用分層的van Emde Boas樹.這兩種數(shù)據(jù)結(jié)構(gòu)的平均空間復(fù)雜度都是線性的,后者是前者的一個改進(jìn).基于前一個數(shù)據(jù)結(jié)構(gòu)的查詢算法的平均時間復(fù)雜度是O(log log n),而另一個的最壞查詢時間復(fù)雜度是O(log log n).最后,該文總結(jié)了區(qū)域搜索算法設(shè)計的一些技巧和一些比較深刻或者是比較新的結(jié)果,并根據(jù)大量的參考文獻(xiàn)例舉了幾個值得關(guān)注的研