船舶進離港行為捕獲算法設計與實現

王永明 饒全成 姚萍

摘要：

針對在設計船舶進離港行為捕獲算法時存在港口范圍難定義、AIS數據的經緯度誤差造成船舶頻繁進出港區邊界等問題，將全球AIS數據與港口數據相結合，設計船舶進離港行為捕獲算法。根據船舶速度、位置、運動特性等信息，實現對船舶進離港、停泊等行為的判斷。利用緯度分桶法、網格法和Kd樹法實現基于船舶位置的港口匹配。實際數據測試表明，網格法的港口匹配時效性最好，每秒可處理約16萬條AIS數據。隨機選取30艘船對算法進行驗證，結果表明船舶軌跡與捕獲到的船舶進離港事件相符。

關鍵詞：

船舶行為; 自動識別系統（AIS）; 港口匹配; 進離港

中圖分類號： U697.1

文獻標志碼： A

Design and implementation of capturing algorithm

for ship entering and leaving port behavior

WANG Yongming1， RAO Quancheng2， YAO Ping2

（1. Navigation College， Dalian Maritime University， Dalian 116026， Liaoning， China;

2. Institute of Computing Technology， Chinese Academy of Sciences， Beijing 100190， China）

Abstract：

In the design process of capturing algorithm for ship entering and leaving port behavior， it is difficult to define port scope， and ships go in and out of port boundary frequently due to latitude and longitude errors of AIS data. To solve these problems， global AIS data and port data are combined to design an algorithm for capturing ship entering and leaving port behavior. The velocity， position and motion characteristics of ships are used to identify ship behaviors such as entering and leaving port， mooring. The latitude point barrel method， the grid method and the Kd tree method are used to realize port match based on ship position. The real data test shows that the grid method is optimal in time and effect for port match， and it can handle about 160 000 messages in 1 s. Thirty ships are selected randomly to verify the algorithm， and the result shows that the ship tracks accord with the events of entering and leaving port of captured ships.

Key words：

ship behavior; automatic identification system （AIS）; port match; entering and leaving port

收稿日期： 2017-05-22

修回日期： 2017-09-20

基金項目： 國家自然科學基金（51309044）

作者簡介：

王永明（1973—）， 男， 安徽壽縣人，高級工程師，博士，研究方向為航運信息化，（E-mail）wangyongming@cttic.cn

0 引 言

船舶軌跡數據是一種典型的時空大數據，各種船舶監測系統（LRIT，VMS，VDR和AIS [1]等）所獲取的船舶軌跡數據記錄了船舶及海上交通的時空變化過程，蘊含了豐富的語義信息。對船舶軌跡數據進行挖掘可發現船舶群體活動的時空特征及演化規律[2]、船舶主航跡帶及其成因等。掌握船舶進離港的規律，對于船舶軌跡的分析[3]具有重要意義。

港口是船舶航行中的關鍵節點，也是整個船舶航行過程中語義信息最豐富的環節。在港船舶會產生包括接受引航、等待、卸貨、裝載、理貨、報關等諸多行為。狹義的船舶進離港就是進港和出港航行，廣義的則是包括船舶進入港區、接受引航、在錨區停留等待、在泊位作業、離開泊位出航、機動航行等的全部過程。對舶舶進離港行為的精細判斷，對于優化港區引航調度、提升港口作業效率具有重大的意義[4]。

快速、準確地挖掘出船舶進離港的行為是對船舶進離港行為捕獲算法的要求。本文將算法分為兩個階段：船舶停泊檢測階段和船舶進離港檢測階段。在船舶停泊檢測階段對船舶的航行與停泊特征進行區分。在船舶進離港檢測階段通過對速度、航向、活動范圍等因素的綜合考慮，捕獲船舶進離港事件。本文采用緯度分桶法、網格法和Kd樹法解決船舶進離港行為捕獲算法中的核心問題：快速找到距離當前船舶最近的港口。通過對港口位置的先驗知識的利用，結合相關的數據結構，不斷提高算法效率。最終發現，用網格法每秒可處理約16萬條數據（目前系統接收的實時AIS數據每秒約3 000條），滿足實時處理的需求。

1 基于AIS數據的船舶進離港

目前，很少看到有關船舶進離港行為捕獲算法的文獻。在一些根據船舶進離港數據進行研究的文獻[5-6]中，船舶進離港行為捕獲算法非常粗糙，且沒有清晰地展現計算過程。這一方面是因為目前船舶進離港行為判斷算法只在一些航運網站（如國內的寶船網、船訊網，國外的Marine Traffic）上使用，另一方面是因為船舶進離港行為判斷算法有自身的一些難點需要解決。

首先，AIS的航次信息中含有ETA及目的地這兩個字段，即預計到達時間和目的港。最簡單的船舶進離港行為可直接根據其靜態信息（船名、船舶呼號、MMSI、IMO編號等）得到。然而，靜態信息是在設備安裝時由專業技術人員根據船舶國籍證書輸入的，而有些工程師在安裝時沒有嚴格按照相關規則設置靜態信息，各類船舶的操作員均未按規定操作AIS設備，從而造成AIS靜態信息錯誤，無法直接使用。比如，對一張含有635 055條數據的靜態表進行分析發現，船舶MMSI不正常的有27 186條（占4%），呼號不可用的有287 167條（占45%），目的港不可用的有459 998條（占72%），ETA不可用的有507 481條（占80%）。因此，直接根據靜態信息判斷船舶進離港是不可取的。

其次，港口區域較難定義。有的港口比較小，適合用基于港區的位置和大小設置的圓表示。有的港口，如上海港，范圍非常大，包含幾百個泊位和錨區，很難用一個簡單的幾何圖形來描述，則可用自定義的不規則區域來描述。

再次，每新獲取一條AIS數據，算法都會對所有的港口進行遍歷，現階段算法還能勉強滿足系統需要，而一旦有更多的港口數據，用該算法遍歷港口所需要的時間就會增加，難以滿足在線處理的實時性要求。

最后，有些船的AIS信息發送不正常。比如，檢測到某船t1時刻在港口A，t2時刻在港口B，但由于該船主動關閉了AIS，所以其出港口A未被檢測到。這

會對后續利用進離港事件進行分析的其他應用產生影響。本文采取的做法是將此前出港口A事件補全，并給出異常等級參考。

1.1 基于AIS的船舶進離港定義

港口區域一般可被定義成圓形或矩形，相應圓的半徑或矩形的長、寬可以根據港口的大小設置。由于AIS信息中的經緯度有一定的誤差，如果船舶在劃出的港口區域附近連續不斷地發出AIS信息，僅按船舶的位置來匹配港口的位置、計算進離港事件，那么當船舶處于區域邊界時算法會判斷出一系列的進離港事件，從而可能導致利用進離港事件進行分析的其他應用判斷其為異常點，或者至少會受到干擾。因此，只有結合船舶的速度、轉向率、航行狀態等，才能更準確地判斷船舶進離港事件。

很多沿著江河航行的船舶可能實際進入了某港區水域，但沒有發生靠離泊位的行為。如每天經過新加坡港的船舶數量龐大，但很多船舶只是過境通航，并沒有進出新加坡港。

基于以上考慮，本文對船舶進離港的定義為：船舶以低于2 kn 的速度進入港口范圍內，且以高于2 kn的速度離開港口范圍，進入與離開的時間間隔不小于30 min，船舶在港期間活動范圍不大于1 000 m;在此期間，船舶分別發生一次進港和離港事件。港口范圍一般用港口中心經緯度加半徑表示，港口半徑根據其大小進行差異化設置。形狀不規則的港口可用矩形或引入JTS開源模塊來表示。（JTS是加拿大的 Vivid Solutions公司做的一套開放源碼的 Java API，它提供了一套空間數據操作的核心算法。）

1.2

船舶進離港行為時空分析和意義

通過研究船舶進離港行為，可以了解船舶航行規律和港口運作規律[7-8]。基于船舶進離港事件，可以對船舶和港口進行一系列有意義的分析，如統計港口吞吐量、統計全球或所關注港口的船舶進出情況、估算港口的運作效率等，并為決策者提供一定的參考信息。這對貨主選擇效率高的航運公司和航運公司選擇效率高的港口碼頭具有重要參考價值。

目前船舶進離港信息僅掌握在港口經營人手中，是分散且不對外公開的。AIS船位信息是可以通過廣播公開獲得的，利用公開信息辨別進離港事件，在經濟情報獲得、安全情報獲得、適應于大數據時代的數據素材生成方面具有重大意義。

在經濟情報獲得方面，通過船舶進離港行為將船舶整個航程進行切分，結合船舶檔案、船型、吃水、靠泊時間等，能夠對貿易量做比較精準的推測，進而掌握大宗貨物的流向，分析宏觀經濟。同時，通過分析船舶進離港行為，挖掘船舶航行規律，可以評估航運公司、港口運營效率。

在安全情報獲得方面，船舶進離港行為分析可以推廣到進離區域分析。對于一些關鍵區域、作業平臺區域、敏感對峙區域等進行進離區域分析，能夠有效地追蹤和甄別潛在的海上犯罪和敵對力量，包括海上走私、海上賭博、海上販毒、圍攻海上作業平臺以及海盜等。

在生成適應于大數據時代的數據素材方面，可以增加語義、切割航線段。水上交通與陸上交通不同，其語義信息并不豐富，目前在大數據時代也沒有很好的辦法來套用如機器學習、深度學習之類的方法。船舶進離港事件將航線段進一步切分成帶有語義標記的航行事件，使得船舶航行不再是一系列軌跡點記錄，而是一系列帶有語義信息的事件，這一系列事件可以作為高階處理方法的素材。

2 船舶進離港行為捕獲算法

在船舶靜態AIS信息不可用的情況下，為快速得到船舶進離港事件，可對船舶動態AIS信息進行充分挖掘。綜合考慮船舶的速度、位置、運動特征等，在線檢測出全球船舶進離港事件。

船舶在到港時會低速進入港區，低速到達錨地，等待有可用的泊位（并持續一段較長時間）。其間，船舶的活動范圍有限。本文對低速閾值、活動范圍閾值給出了經驗值，并依據此經驗值檢測船舶進離港事件。

為快速得到船舶所在的港口，先對全球港口在地理位置上進行預處理，構造相關的數據結構，使得查詢船舶所處港口的速度得到大幅提升，從而滿足在線檢測的需求。

2.1 數據預處理

AIS信息在傳輸過程中會出現一定的錯誤，因此在

輸入AIS數據前，需要對其進行預處理，刪除明顯錯誤的AIS數據，如：經度的正常范圍為-180°～180°，緯度的正常范圍為-90°～90°，不在此范圍內的AIS數據都會被刪除。[9]

2.2 船舶進離港行為捕獲算法設計

對某單船的速度進行研究，其速度隨時間的變

化大致如圖1所示。T1時刻船舶進港，T1～T2時間

圖1 單船速度變化示意圖

圖2 船舶進離港行為捕獲

算法流程

內船舶低速在港區內移動，T2時刻船舶離港。根據船舶速度和活動范圍可判斷出船舶航行狀態的變化，再結合船舶和港口的位置即可對船舶進離港行為作出判斷。

在線船舶進離港行為捕獲算法分為兩個階段：（1）根據船舶速度、活動范圍、軌跡點數等判斷其是否發生停泊事件;（2）結合全球港口信息，檢測船舶停泊事件是否為船舶進離港事件。算法流程見圖2。

根據上述分析設計出船舶停泊事件檢測的流程，見圖3。

算法維護每條船的低速軌跡序列，根據每條實時的AIS數據：若船舶速度低于給定的閾值，則將該船加入到相應的序列;若船舶速度高于閾值，則認為該船是從停泊狀態轉到航行狀態，是一個可能的停泊結束事件。若確實存在該船的低速軌跡點序列，則此軌跡點序列的首尾軌跡點被認為是停泊事件的起訖點。為能夠判斷準確，接著加入平均速度、活動范圍等信息進行進一步確認。首先判斷該船的低速軌跡序列的點數是否大于設定的閾值，以免低速軌跡序列點數太少，給停泊事件檢測造成誤差。若點數符合要求，則求出軌跡序列平均速度，若平均速度大于等于閾值，則認為停泊狀態可信度不高。最后，求出軌跡點序列的最大、最小經緯度，即將該船的活動范圍看成一個矩形，將矩形對角線的一半作為該船的活動半徑。若此活動半徑在設定的閾值范圍內，則可判斷這是一個停泊事件。

圖3 船舶停泊事件檢測流程

將軌跡點序列起訖點的AIS信息字段中的定位時間分別設為停泊事件的起止時間，并將平均速度、活動半徑等參數記錄到該船停泊事件中。在上述計算平均速度和活動半徑的過程中，為確保準確性，省略了軌跡點序列前后的部分軌跡點，僅將中間數據質量更高的軌跡點序列用于計算，以進一步提高船舶停泊事件的可信度。

表1 P0與P1的比較邏輯

當得到船舶停泊事件后，結合全球港口信息可得到船舶進離港事件。船舶停泊檢測流程輸出的結果為船舶停泊對象STOP，屬性包括活動半徑、中心經緯度、停泊起始時刻、停泊結束時刻等。計算出此中心與最近的港口P1的距離，且判斷此距離是否小于設定的閾值（此閾值反映港口區域的大小）。系統維護一張全局在港船舶列表，列表的鍵為船舶MMSI，

值為對應的停泊港口P0。同時，每個港口各自維護一張在港船舶列表，列表的鍵為船舶MMSI，值為停泊對象STOP。比較P0與P1的關系，可得到船舶的進離港事件。比較邏輯如表1所示，其中p0和p1為具體的港口。

當P1和P0均為NULL時，說明船A正處于動力航行狀態。

當P1為NULL，P0不為NULL時，說明船A之前在港口p0內，當前不在任何港口內，表明船A已經離開港口p0。

當P1不為NULL，P0為NULL時，說明船A之前未到任何港口，當前在港口p1內，表明船A已經進入港口p1。

當P1和P0均不為NULL時，若P1=P0則說明船舶停泊在p1內，若P1≠P0則說明船A此刻進入p1，之前某一時刻離開p0。離開p0事件并不是此時發生的，而是之前某一時刻發生的，但由于該船的AIS信息異常，如該船主動關閉AIS發射器，所以該船的離港事件未能被及時檢測到。若需要區分此類事件，可對其做相應的異常標記。

船舶進離港事件檢測流程見圖4。船舶在港口內可能會在錨地與泊位間移動，每次移動均會產生停泊事件，即系統可能會檢測到多次停泊事件。對于這種情況，只需更新當前港口內對應于該船的STOP對象的停泊結束時間。當檢測到進港事件時，向全局在港船舶列表中增加相對應的船舶與所停泊港口的鍵值對，同時向發生船舶停泊事件的港口所維護的在港船舶列表中添加船舶與STOP對象的鍵值對;當檢測到離港事件時，則需要刪掉相應的鍵值對。

船舶進離港行為捕獲算法偽代碼如下：

輸入：船舶STOP對象數據流

輸出：船舶進離港事件流

Init HashMap<Ship，PORT>m;//所有在港船舶

Init HashMap<Ship，STOP>s;//每個港口維護的在港船舶

For stop in STOP_stream：

Ship ship = new Ship（stop）;

Port P1 = CurInPort（ship）; //當前距離最近港口

If （Dist（P1， ship） > DistThreshold） continue;

Port P0 = m.get（ship）; //全局表中所對應港口

if（P1==NULL && P0==NULL） nothing to do;

Else if （P1==NULL && P0！=NULL）

generateEvent（ship， P0， departure）; //離港

m.remove（ship）; //維護所有在港船舶

P0.s.remove（ship）; //維護P0的在港船舶

Else if （P1！=NULL && P0==NULL）

generateEvent（ship， P1， In）//進港

m.put（ship， P1）;

P1.s.add（ship， stop）;

Else if （P1！=NULL && P0！=NULL）

if （P1==P0） upDateEndTime（P0， stop）;

Else //先離港，再進港

generateEvent（ship， P0， departure）;

m.remove（ship）;

P0.s.remove（ship）;

generateEvent（ship， P1， In）;

m.put（ship， P1）;

P1.s.add（ship， stop）;

End

圖4 船舶進離港事件檢測流程

從上述偽代碼可看出，通過系統所維護的全局在港船舶列表，可以快速找到P0，要得到P1則需要通過實時計算當前距船舶最近的港口，因此計算的快慢決定了算法的效率。提高算法效率的核心在于如何快速找到與當前船舶距離最近的港口。

3 基于船舶位置的港口匹配方法

基于當前船舶位置，設計緯度分桶法、網格法和Kd樹法等3種算法對港口進行快速檢索。這3種算法均利用港口的先驗地理信息，將全球港口存儲到特定的數據結構中，以加快查詢與當前船舶最近的港口的速度。

圖5 緯度分桶法桶編號示意圖

3.1 算法介紹

緯度分桶法：根據緯度將全球港口劃分到180個桶中。算法根據AIS中的緯度字段快速定位船舶所在的緯度桶，遍歷相鄰的3個緯度桶。緯度分桶法桶編號示意圖見圖5。

網格法[10]：在緯度分桶的基礎上，對經度也劃分桶，形成網格，見圖6。將全球港口劃分到1°×1°的網格中。算法根據AIS中的經度、緯度字段快速定位船舶所在網格，遍歷相鄰9個網格中的所有港口，找到距離當前船舶最近的港口。一般1°×1°的網格邊長約為60 n mile（約110 km），遠遠超過港區大小。因此，其他網格中的港口與該船的距離必然大于設定距離閾值，不合要求，即其他網格中的港口與該船的距離不用計算。

圖6 網格法網格編號示意圖

Kd樹[11-12]法：Kd樹（多維二叉搜索樹）是由Bentley于1975年提出的。通常用Kd樹做數據索引和查詢。Kd樹通過把一個空間劃分成多個不相交的子空間來組織k維空間中的點集，其中小于等于劃分值的點劃分到左子樹，大于劃分值的點劃分到右子樹。Kd樹本質上是一種二元搜索樹，它用超平面把空間劃分成若干子區間來對數據進行搜索，從而可以高效地找到某一點的最近鄰。將全球港口按照經緯度劃分存儲到一棵二叉樹中的步驟：首先，將所有港口按經度排序，取排在中間的港口作為第1個節點插入Kd樹;然后，將余下的港口按緯度排序，取排在中間的港口作為第2個節點插入Kd樹;重復上述步驟，最終所建的二叉樹是一棵高度平衡的二叉樹。找到Kd樹中某船的最近鄰，即距離該船最近的港口。

3.2 算法分析

前述3種算法都利用港口的地理信息預先構建了一張“表”，在實時查詢與某船距離最近的港口時，利用這張“表”加快查詢的速度。因此，港口在“表”中分布得越均勻，查詢的速度越快。目前系統中港口總數為7 805個。

用緯度分桶法劃分的桶中的港口數分布見圖7。由圖7可知：大部分港口集中在小部分緯度桶中;從第120號到第150號的桶中的港口總數為4 904個，占系統中港口總數的62.8%。這說明港口在緯度桶中的分布極不均勻。

圖7 用緯度分桶法劃分的桶中港口數分布

用網格法劃分的網格中的港口數分布見圖8。由圖8可知，3.4%的網格中的港口總數占系統中港口總數的90%。與緯度分桶法一樣，網格中的港口數分布極不均勻。

圖8 用網格法劃分的網格中的港口數分布

圖9 Kd樹法劃分效果

Kd樹法的劃分效果見圖9。豎直線為豎直劃分（根據X坐標劃分），水平線為水平劃分（根據Y坐標劃分）。由圖9可知，Kd樹法劃分出的空間并不均勻，地圖下方的空白較多，空間較大，而地圖中部空間小且子空間排列緊密。

現實世界中的港口分布并不均勻，因此在用緯度分桶法和網格法劃出的桶和網格中的港口分布也不均勻。在極端情況下，所有的港口都聚集在一個桶或一個網格中，計算效率退化為與暴力解法的計算效率相等。

下面具體分析算法的時空復雜度。設港口數為M，待計算AIS信息條數為N。用緯度分桶法設置的桶的數量為D，而用網格法設置的網格數為D0·D1。

對于緯度分桶法和網格法，建“表”的時間分別花在定位港口所對應的桶和網格上。因此，時間復雜度均為O（M），空間復雜度則除了要存儲每個港口還要存儲桶或網格，故分別為O（D+M）和

O（D0·D1+M）。對于Kd樹法，建“表”的插入時間為log2M，因此總的建表時間為O（Mlog2M），空間復雜度則為O（M）。

在查找時間方面，假定AIS數據均勻分布，每個桶或網格被查找到的概率相等。對于緯度分桶法，M個港口均勻分布在D個桶中，查找時間復雜度為O（（1+M/D）·N）。對于網格法，M個港口均勻分布在D0·D1個網格中，查找時間復雜度為O（（1+M/（D0·D1））·N）。對于Kd樹法[13]，平均復雜度為O（（Mlog2M）·N），在最差的情況下要遍歷到每個港口，因此，在最差的情況下時間復雜度為O（M·N）。

3.3 運行效率測試與分析

為了測試3種算法在真實數據中的表現，選取全球2015年10—12月的AIS數據。在硬件平臺為Xeon（R） CPU E3-1200（@3.10 GHz），內存8 GB，軟件為Windows 7 x64和JRE 1.7.0的試驗環境下

對3種算法進行效率測試。分別使用1萬條、5萬

條、10萬條、50萬條、100萬條、500萬條、1 000萬條

圖10 系統采用3種算法處理

AIS數據所耗費的時間

AIS數據作為測試集，分別記錄系統采用3種算法處理完所有數據所耗費的時間（均取3次試驗的平均值）。試驗結果見圖10。

從圖10可以看出，3種算法的時間效率均與AIS數據數量呈線性關系。從圖10中還可以看出：網格法的效率最高;Kd樹法由于每次進行最近鄰查詢都要進行多次距離計算，所以其算法效率較低;緯度分桶法和網格法都天然地減少了待查詢的港口數量，因此效率都較Kd樹法高。

4 船舶進離港行為捕獲算法正確性驗證

為驗證系統所捕獲到的進離港事件的正確性，隨機選取客船、貨船和漁船各10艘進行對比分析。圖11所示為其中1艘MMSI為235000864的客船的歷史軌跡（數據來源于寶船網）。從數據庫中查詢到系統捕獲到的進離港事件，見圖12。比較圖11

圖11 某客船的歷史軌跡

圖12 捕獲到的某客船的進離港事件

與12可知該客船先后經過港口LOCHMADDY，UIG，TARBERT，系統捕獲到了相應的進離港事件。所選取的其他客船、貨船和漁船的進離港事件也均被正確捕獲，這里不再贅述。

隨機抽取的船舶軌跡與系統捕獲到的船舶進離港事件能很好地吻合，表明船舶進離港捕獲算法能正確捕獲船舶的進離港事件。

5 結束語

在線船舶進離港捕獲算法存在港口范圍難定義、AIS信息中的經緯度誤差造成的船舶頻繁進出港區邊界等問題。本文為解決這些問題做了有效嘗試，首次在全球港口數據庫上對全球AIS數據進行試驗。試驗結果表明，網格法在船舶進離港行為捕獲算法中取得了最高的時間效率，具有實際應用的價值。由于現實世界的港口分布并不均勻，未來可以考慮分區域來劃分網格，以達到更高的時間效率。

如果能夠捕獲全球船舶的進離港事件，用統一的船舶進離港事件格式表示，就能為后續用更高階的方法來發現知識規律提供極大的便利。

參考文獻：

[1]趙學俊， 董曉永， 趙麗寧. AIS與船舶航行安全[J]. 世界海運， 2003， 26（2）： 24-26.

[2]何時浩. 基于AIS信息的船舶航跡動態行為分析技術研究[J]. 科技視界， 2017（1）： 232，238.

[3]朱姣， 劉敬賢， 陳笑， 等. 基于軌跡的內河船舶行為模式挖掘[J]. 交通信息與安全， 2017， 35（3）： 107-116.

[4]劉滿娜. 基于AIS的港口監控與分析系統的設計與實現[D]. 北京： 北京郵電大學， 2011.

[5]向哲， 施朝健， 胡勤友， 等. 利用AIS數據計算港口間競爭度的方法[J]. 上海海事大學學報， 2016， 37（1）： 60-64.DOI：10.13340/j.jsmu.2016.01.011.

[6]劉茹茹， 洪鋒， 劉傳洋. 基于AIS信息的船舶抵離港頻數的統計[J]. 電腦知識與技術， 2014， 10（13）： 3160-3161.

[7]洪曙東. AIS在港口調度管理應用的研究[J]. 中國港口， 2010（7）： 51-52.

[8]張建雄. 基于AIS的港口船舶動態統計系統[J]. 中國水運， 2015（2）： 56-57.

[9]潘家財， 姜青山， 邵哲平. 船舶會遇的時空數據挖掘算法及應用[J]. 中國航海， 2010， 33（4）： 57-60.

[10]韓家煒， 坎伯. 數據挖掘： 概念與技術[M]. 北京： 機械工業出版社， 2001： 100-103.

[11]BENTLEY J L. Multidimensional binary search trees used for associative searching[J]. Communications of the ACM， 1975， 18（9）： 509-517.

[12]唐寧九， 游洪躍， 朱宏， 等. 數據結構與算法分析[M]. 成都： 四川大學出版社， 2006.

[13]SEDGEWICK R. Algorithms[M]. Chennai Area， India： Pearson Education India， 1988.