距離檢測文章

18/18附錄１對聚類點集近似最鄰近搜索的分析SongriｔＭａneewongｖaｔana和DａvidM．Ｍount摘要最鄰近搜索是最基本的計算問題.給定D維空間中的一個點集，它包含n個數據點,最鄰近搜索要解決的問題是用一個數據結構對這些點進行處理,以便給出一個查詢點時,我們可以高效地在數據集中找到與該點距離最近的點。因為數據集可能很大，所以我們更關注數據結構所占的存儲空間，希望將其控制在Ｏ（ｄｎ）。一種較為流行的用于最鄰近搜索的數據結構是ｋd樹及其變體，這項技術的基本思想是將分級的分解空間放進一個盒子中。在建立這種數據結構時的一個重要的問題是分割算法的選擇，分割算法決定了分割維和用于空間分割的超平面.分割算法的選擇在很大程度上決定了數據結構的效率,當數據點和查詢點都聚集在低維子空間時，這點體現的尤為明顯。這是因為較高的聚集性會讓子劃分生成長寬比極高的盒子。我們將兩種可選的分割策略與眾所周知的優(yōu)化ｋｄ樹策略進行了對比。第一種叫做滑動中點分割策略。它試圖尋求一種平衡，以使得子劃分產生的盒子有一個長寬比的上限，且每個盒子中都含有數據點。第二種被稱為最小不確定性分割策略,它是一種基于詢問的搜索方式。這種策略中，我們除了要給出數據點集外，還要給出一個訓練查詢集,用于預處理。策略中使用了一種簡單的貪心算法，以期選擇的分割平面能在對訓練集查找最鄰近點時使得平均不確定性的總和最小。在產生的一系列點集和查詢集上,我們進行了實驗，將這兩種策略與優(yōu)化kd樹策略進行了比較，并給對實驗結果進行了分析。我們論證了：對于聚類數據和查詢集的近似最鄰近查詢，這兩種算法的效率較標準的kd樹有顯著提高。1。介紹最鄰近查詢需要解決的是這樣一個問題：我們給定集合S,它含有度量空間X中的n個點。我們要對這n個點進行處理，以便對給定的任意點ｑ（q∈X)我們都能很快的找到S中距離它最近的點。最鄰近查詢在很多領域中都有應用,比如知識發(fā)現、數據挖掘、模式識別和分類、機器學習、數據壓縮、多媒體數據庫、文件恢復、統(tǒng)計等等。對于度量空間,我們有許多種選擇。我們始終假定空間為Rd,即d維空間，空間中的距離采用閔可夫斯基Lm距離進行度量。對于任意整數m≥1，Rd中任意兩點p＝(p１，ｐ2…，pｄ)、ｑ=（q１,q２,…,ｑd）的距離被定義為∑１≤i≤d|pi—qｉ｜m的ｍ次方根。L1，L2和Ｌ∞分別被稱為：曼哈頓距離，歐氏距離和最大距離。我們將主要的焦點集中在數據結構上。因為數據集可能很大,我們將其做一下限制，只考慮數據空間程線性增長的情況.在眾多方法之中,最流行的是基于分等級分解空間的方法。在這個領域中,最根本的工作是由Fｒiｅdman，Bｅntleｙ和Finkel完成的。他們指出通過使用kd樹，可以將固定維數空間中可預計其分布的數據的空間復雜度控制在O（n)，查詢的時間復雜度控制在O（logn）.對于這一問題,可選擇的方法有許多種。但是，所有已知的方法都存在這樣一個缺陷：當空間維數增加的時候，運行時間或空間復雜度將隨之以指數倍增長。我們試圖找到一種高效的算法，即使在最糟的情況下，它也會有較低的空間復雜度和較短的查詢時間，但事實證明,想要獲得這樣的算法是很困難的，但這同時也告訴我們尋找近似的最近臨是解決問題的一條出路。設S為Rd中的點集，查詢點q為Rｄ中任意一點,假定ε>０，如果ｄｉst(ｐ，q)≤（1＋ε）dｉst（ｐ＊,q）成立,我們就說點p是點q的近似最近臨。換句話說，ｐ是在相對誤差ε內的真實最近臨。最近,人們已經對近似最近臨問題進行了深入的研究。較有代表性的算法包括：Beｒn［Ber9３］，Aｒya和Mｏｕnt[AM9３ｂ］，Aｒya等人[AMＮ+98］,Kｌeiｎｂerg［Ｋle97］,Clarkson[Cla９４］，Ｃhan［Cha97］，Indｙk和Mｏtwａni［IM98］以及Kushｉleｖｉｔz，Ostroｖskｙ和Ｒaｂani［KOR98].本文中，我們以分級空間分解特別是kd樹為基礎，將數據結構的大小限定在O（dn)。這是因為在種數據結構較為簡單而且應用廣泛。kｄ樹是一種二元樹，它依靠垂直于坐標軸的分割超平面將多維空間劃分為多級子空間。我們將在下一節(jié)對這個問題進行深入的探討.設計kｄ樹的一個關鍵問題是分割超平面的選擇。Frieｄmａn，Ｂentlｅy和Fｉｎｋel提出了一種分割策略:假設點集在第k維上有最大的延展度，則將過第ｋ維中點且垂直于第k維坐標軸的平面作為分割超平面。他們將用這種方法得到的樹稱為優(yōu)化kd樹，我們把用這種方法叫作標準分割策略.另一種較為普遍的方法是利用包含點集的盒子形狀(而非點集的分布）對點集劃分。這種策略將垂直于盒子最長邊且過最長邊中點的平面作為分割超平面。我們將其稱為中點分割策略。以分級空間分解為基礎,人們把出了許多用于最近臨查詢的數據結構。Yiａnilos引入了vp樹。它不像kd樹那樣用一個平面去分割點集，而是利用一個稱為優(yōu)勢點的數據點作為超球面的中心，將空間分為兩部分。有一些基于Ｒ樹及其變體的數據結構被應用于數據庫領域.比如X樹,它通過避免高度堆疊提高了R*樹的性能。類似的例子還有SＲ樹.ＴＶ樹在處理高維高間時使用了較為獨特的方法。它通過維護一系列活躍維達到了降維的目的。當一個節(jié)點中的數據點共享了一個活動維上的相同的坐標時，該維將被列為無效，活躍維集合也將隨之改變.在這篇文章中我們研究了另外兩種分割策略的的性能，并且將其與以往的ｋｄ樹分割策略進行了比較。第一種策略叫做“滑動中點",它是由Mount和Arya針對近似最近臨搜索提出的，并應用于ANN函數庫中。將這種方法引入函數庫是為了更好的處理高聚性數據集。這種策略采用一種較為簡單的方法來更正標準ｋd樹分割策略中的一個嚴重缺陷。這個缺陷在于，當高聚性的數據點存在于低維子空間時，采用標準kｄ樹分割策略對點集進行劃分將會產生許多長寬比極高的盒子,這些盒子會使查詢時間大大延長.“滑動中點"策略起初也是沿盒子的最長邊進行簡單的中點分割，但是,如果分割產生的任何子盒中不含數據點,該策略將使分割面沿點集沿伸方向滑動，直到遇到第一個數據點為止.在3.1節(jié)中我們將對這種分割策略進行詳細描述并對其特性做出分析.第二種策略叫做“最小不確定性”分割策略，它是一項基于詢問的技術。建樹時不僅要給出數據點集,還要選出一些示例性的查詢點，這些點被稱為訓練點。建樹時，算法應用了一種啟發(fā)式的貪心算法，它試圖使對訓練集的查詢時間最小。給定一個查詢點集，我們將最鄰近查詢算法的每一步看作一張雙向連通的圖,稱之為候選圖，它的頂點代表了所有的數據點和查詢點,圖中與查詢點緊挨著的數據子集可能就是該查詢點的最鄰近點?！白钚〔淮_定”策略在執(zhí)行的每一步選出一個分割平面,盡可能多地刪除候選圖中剩余的邊。在3．２節(jié)中,我們對這種策略進行了更為詳細的描述。我們在執(zhí)行這兩種策略的同時也執(zhí)行了標準ｋd樹分割策略。在產生的一系列有著各種分布的低維聚類數據上，我們對這些算法進行了比較.我們相信這種類型的聚類數據在實際應用中的較為普遍的。我們使用手工合成的數據作為與基準數據的一個對比，以便于對我們聚類數據的密度和維數進行調整。我們的結果表明，對于低維聚類數據集，這兩種算法的效率較標準的kd樹有顯著提高。以下的篇章是這樣組織的，在下一章中我們展示了ｋd樹的背景信息以及它是怎樣執(zhí)行最鄰近查詢的。在第3節(jié)中，我們對兩個新的分割策略進行了描述.第四章，主要是對實驗及結果的展示。２。背景在這節(jié)里我們描述了kd樹是如何執(zhí)行精確或近似的最鄰近查詢的。Benｔley將kd樹作為一種在高維空間中通用的二元搜索樹［Beｎ75］。Kｄ樹的每一個的節(jié)點可以看作是一個多維矩形，我們將基稱為盒子.根節(jié)點是一個包含了所有數據點的矩形。其余的節(jié)點代表了包含數據點子集的矩形。（在兩個矩形邊界上的點可以認為是包含在其中任何一個矩形中）.如果節(jié)點中的數據點個數小于一個被稱為bucｋｅtｓｉzｅ的閾值，這個點就被稱為葉節(jié)點，這些數據點就存儲在葉節(jié)點中.否則，建立算法就選擇一個分割超平面，它垂直于其中一個坐標軸，并且貫穿整個盒子。有許多分割策略可以用于超平面的選擇。我們將在下面對此進行更詳細的討論。超平面將盒子劃分為兩個子矩形，相當于是當前節(jié)點的兩個孩子節(jié)點,盒子中的數據點屬于哪個孩子節(jié)點,取決于數據點在超平面的哪一側。樹中的每個內部節(jié)點都與它的分割超平面相關。Ｆrｉdｍan，Benｔley和Fiｎkel［FBＦ７7］給出了一種用kd樹尋找最鄰近數據點的算法。他們所介紹了下面的分割策略，我們將面稱為“標準分割策略”。對每個內部節(jié)點，我們將沿著點集的最大延展度方向選擇分割平面,并使其垂直于某個坐標軸。分割點被選在中點,這樣分割后形成的兩個子集中含有的數據點數基本相同。最終得到的樹的大小為O（n）,高度為Ｏ(logn）。Whｉｔe和Jain[WJ96］提出了另一種方法，稱為VAM分割，兩種方法采用的基本思想是一致的,但后者是將具有最大差異度的維定為分割維。我們用一種簡單的遞歸算法對查詢進行回答。在最基本的情況下,當算法執(zhí)行到葉節(jié)點時,它會對葉中的每個數據點與查詢點間的距離進行計算。最小的距離值將被保存。當我們到達內部節(jié)點時,算法首先決定查詢點位于超平面的哪一側。查詢點必須離即將被訪問的孩子較近。算法遞歸地訪問這個孩子。當返回時，算法判斷盒子中另一個孩子與查詢點的距離是否比當前最小距離要近,如果是，些也對這個孩子進行遞歸訪問.當搜索返回到根時，我們就能得到最鄰近點了。一個重要的觀察結論是:對于任何查詢點，算法將訪問每一個與查詢點距離小與最鄰近點的葉節(jié)點。要對這種近似最鄰近查詢進行概括是較為簡單的。設ε為允許的誤差邊界。在處理內部節(jié)點時，當且僅當先前距離較遠的孩子節(jié)點與查詢點的距離是當前最小距離的１／（1+ε）時，我們才對這個孩子節(jié)點進行訪問.Araｙ等人證明了這個過程的正確性。他們也展示了這種通用的算法是如何計算出k個精確或者近似鄰近點的。Arya和Mounｔ［AＭ９3a］提出了一些對這種算法的改進。第一種叫作“增量距離計算”。這是一種可以用于任何Mｉnkowski距離計算的方法.除了分割超平面，樹的每一個內部節(jié)點還存儲了相關的盒子的信息。算法并不計算真正的距離，而是使用距離的平方。當算法執(zhí)行到內部節(jié)點時，它計算查詢點與相關盒子的平方距。他們指出在固定的時間內（不依賴維數),用這個信息計算出與每了孩子節(jié)點對應的盒子的平方距是完全可能的。他們還展示了一種叫作“優(yōu)先搜索”的方法，這種方法使用堆,按照距離增加的順序訪問每個葉節(jié)點，而非按照樹結構遞歸地訪問。另外一種眾所周知的用于最近鄰查詢的算法叫作部分距離計算［ＢG85，Sｐr91］。當計算查詢點與數據點距離時，如果各平方量的和超過了當前最近點與查詢點距離的平方,那么停止對該距離的計算.對近似最鄰近查詢,Aｒya等人發(fā)現,對于任何一種基于分解空間的近似最鄰近查詢,都有兩條重要的性質。(1）平衡：樹的高度應該為O（logn),其中n是數據點的個數.(2）長寬比界限:樹的葉節(jié)點的長寬比應該有一個限界，這意味著每個葉節(jié)點的最長邊與最短邊的比值應該有一個固定的上限值.在這兩條規(guī)則的基礎上，他們又指出，最臨近查詢可以將數據節(jié)構的大小控制在O（dn)，將執(zhí)行時間控制在O（logn）。不幸的是，對于ｋd樹而言，這兩條性質不總是同時成立，特別是當數據點的分布特別集中時.Ａrya等人提出了一種更復雜一些的數據結構,叫做“balanceｄbｏx-dｅcoｍpositiｏn”樹,它可以同時滿足這兩條性質。這了證時他們的理論，這種額外的復雜性看來是有必要的，并且他們的實驗也證明了當數據集是低維子空間上的高聚性數據時這種復雜性是很重要的。一個有趣但又實際的問題是，是否存在一種算法,它有著kd樹的簡單，又能對實際中的高聚分布的數據提供高效的搜索. 固定長寬比的上限,對高效搜索來說是充分非必要條件。一種更準確的應于他們的實驗結果的條件被稱為“pａcｋｉngｃonｓtｒainｔ”。定義一個半徑為r的球為點集的中心?！皃aｃｋｉngconstraint”表明與球相交的盒子的個數是有限的。PａｃkinｇConstraｉnｔ：大小至少為s的與半徑為r的球相交的葉節(jié)點的個數是有上限的，它受限于的r/s,但不依賴于ｎ。如果樹的盒子有長寬比限制,那么它一定滿足“pacｋingｃonstraint”.Aｒya等人指出，如果滿足“pａcｋingcoｎｓtraｉnt",那么這個盒子數只取決于維數和ε。標準分割策略的不足在于它不能控制盒子的長寬比，因此不能完全滿足“paｃｋingｃonsｔraｉnt".附錄2AｎalysisoｆAｐｐroｘimａt(yī)ｅＮearestＮeｉghｂorＳｅaｒchiｎgwithCluｓterｅdPoｉntSetsSongritMａneewongvatanaanｄDavidＭ.ＭouｎtAbstraｃtNｅaｒestｎeighｂｏｒsearchingisａfundａｍenｔalcompｕtaｔｉoｎalproblｅm．Aｓｅｔofndａt(yī)apｏｉntsisgiveｎｉｎreａld-dimeｎｓiｏnａlspaｃe,andtｈｅprobｌeｍｉstｏprepｒoceｓｓtｈesｅpｏinｔsintoadａt(yī)asｔｒucture,sotｈａt(yī)givenaqueｒypｏｉnｔ,ｔheｎｅaｒｅsｔdatapoｉnttｏｔhｅｑuｅrｙpointｃanｂeｒeｐoｒｔeｄeffｉcｉeｎtly。Beｃａusｅdataseｔｓcａnbｅｑuitelarｇe,wearepriｍarｉlyｉnteresteｄiｎdatastructｕｒｅｓtｈatｕseｏnlyO（dｎ）stｏrａｇe.Apoｐｕlarclassofdaｔastｒuctureｓfornearestneiｇhｂｏrsｅarｃhiｎgiｓthekd－tｒeeaｎdvariａｎtｓbａsｅdonhieｒaｒｃhicａllyｄeｃomposinｇsｐaｃeiｎtorｅｃtanｇｕlarcelｌｓ．Aｎimportantquestionｉnｔhｅcｏnｓtｒuctionoｆsｕｃhdatａstｒuｃturesｉsthｅchoｉceofaｓplitｔingmeｔhｏd，whｉｃhdeterminesthedimensｉonanｄspｌittingｐlanetobeｕsedatｅａcｈstaｇeofｔhedecomｐoｓition。Thiｓchoｉｃｅofsplitｔｉｎgmｅthoｄcａｎhaveａｓigni_cａntinflueｎceonｔhee_cｉencｙofthedaｔastructure.Thｉｓisespeciaｌlｙtruewhendataａｎdquｅｒｙｐointsａｒeｃlusｔｅrｅdinｌｏwｄimeｎsionalsubｓpａceｓ。Thisｉｓbecauseｃlusｔeringcａnleadtosubｄiviｓionsｉnwhicｈｃelｌshａveveryhighａspectratｉos.Wecoｍpａretｈewell-kｎownoptimｉｚeｄｋd-trｅeｓｐliｔｔingmｅｔhodagａinｓtｔwoaltｅrnativesplｉttingmethｏｄs．Thefiｒst，calledｔhesｌidｉng-mｉｄpoｉnｔmethoｄ,wｈiｃhａt(yī)ｔemptstobａlancetｈegoaｌsofproducingsubdivisiｏｎcｅlｌsｏfbounｄｅｄaspectratiｏ，whilenoｔproduｃinganyｅｍptyｃeｌｌs。Ｔhesecond,calｌｅdthｅminimum—amｂiguitymeｔｈｏdｉｓａquｅrｙ-baｓedaｐpｒoaｃh。Inaddｉtｉontｏthedaｔapoinｔｓ，ｉtisalｓogiｖeｎaｔraiｎｉnｇsetofquerｙpoｉntsfｏrpｒeｐrｏｃｅｓｓing．Ｉtemｐlｏysaｓimｐlegreｅｄyalgorｉｔｈmtoｓｅlectthｅｓplittingｐlａnｅｔhaｔmiｎｉmiｚesｔｈeaｖerａｇｅａmountｏfambiguityinthecｈｏiceofthenｅareｓtneｉｇｈｂorｆoｒthetrainiｎｇｐoints。Wｅpｒoｖideａnempｉrｉcalaｎalyｓｉｓcｏmparingtheｓeｔwometｈoｄsaｇaiｎstｔhｅoｐｔimiｚedｋｄ-tｒｅeconstructionfoｒanumberofsynｔhｅticalｌygenerateddataaｎｄquerysets。Wedemoｎstｒatetｈａt(yī)forclustereddataandｑuerｙsets，theｓealgorithmscanproｖｉdesigｎi_cａntｉmprｏｖemeｎtsｏｖｅrtheｓtandaｒｄkｄ-treeconsｔｒucｔｉonforaｐproximaｔenｅareｓｔｎeighborsearｃｈing．1.IｎｔｒoductioｎNeaｒesｔneighborsearｃｈingisthefｏlｌowingｐrobｌｅm：wｅaregivｅnaｓｅtSoｆnｄaｔaｐｏiｎtsinａmeｔrｉcspace,Ｘ，andarｅａskedtｏprｅpｒocessｔhｅｓepoｉntssothａt(yī),ｇivenanyquｅrｙｐoｉntq∈X，thedaｔapoｉｎtnearesｔtｏqcａｎbｅrepoｒtedｑuickly.Nearestｎeighborｓearcｈinghａsapplicａt(yī)ionsinmａnyareas，incluｄｉｎgｋｎowledgediscoveryanddatamining［ＦPSＳＵ9６],patteｒnrecｏgnitionanｄｃｌaｓ-sifiｃａt(yī)ｉon[CＨ67,DH73]，machｉnelearnｉｎｇ［CS93],datacomｐrｅssiｏn［GＧ92]，ｍｕltiｍediaｄataｂａses［FSＮ+95]，ｄｏｃumentreｔriｅval［DＤF+90］，ａｎｄstatistｉcｓ［DW82］.Ｔherearemanｙpｏssiblecｈoicesofｔhｅmetriｃｓpaｃe。ＴhｒoughoutwｅwillassｕmethatｔhespaceｉｓRd，reａld—ｄimensioｎalspacｅ，whｅredistａncesａremeasuredusingaｎｙMiｎkowｓkiLmdisｔanｃemetｒiｃ．Foranyiｎｔegerm≥１,tｈeＬｍ—dｉsｔancebｅtweｅｎｐｏｉntsp=(p１，p2…,pｄ）aｎdq＝(ｑ1，q2，…，qd）inRdisｄeｆiｎedtobethｅm－thｒootof∑1≤i≤ｄ｜pi-ｑi｜ｍ。TheL１,L２,andＬ∞mｅtriｃsaｒetｈewell-knｏwnManhａt(yī)ｔaｎ,Eｕcｌideanaｎdmaxmetｒｉcｓ，respectively.Ourprimaｒｙfoｃusｉsｏｎdataｓｔructurｅsthaｔａｒesｔoｒedinmaiｎmemory。Sincedatasetscaｎbelarｇe,welimitourselvｅstｏconｓiｄｅratiｏnofdａt(yī)aｓtructureｓwhosetｏｔａｌspaｃｅgｒowsｌineａrlｙwitｈdandn。Ａｍｏngｔｈemosｔpopulａｒmetｈodsarｅｔhｏseｂasｅdonｈierarchiｃaｌdecomｐositioｎsofspace.ThesｅｍｉnalworｋiｎtｈisaｒeaｗasbyFrieｄman,Bｅntｌey，aｎdFinkel[ＦBF7７]ｗｈoｓhowedthatO(ｎ）spaceandＯ(lｏgn）qｕerytimeaｒeａｃhievablefｏｒfixeddimｅnsiｏnaｌsｐaｃesintheexpeｃtｅdcasefoｒdatadistｒibｕtionsoｆｂoundeddensitythrougｈthｅuｓeofkd—tｒｅｅs。Theｒｅhavｅｂeｅnnuｍｅｒousｖariationsonthiｓthｅme。Hｏwｅver，allｋnownｍetｈodｓsuffeｒｆroｍthefactthatａsdimｅnsioninｃreａses,eitｈerruｎｎiｎgtimeｏrspaceincｒeaｓeｅxpoｎentiａllywｉｔhdimｅnｓion。Tｈｅdifficultyofobtainingalgｏrithmsｔhaｔａreｅ＿cientｉnｔheｗｏｒｓtcaｓewitｈresｐecttｏbotｈｓｐaceandquｅrytｉmesｕｇgｅｓtstｈealternaｔiveprｏbleｍoffindingaｐｐｒｏximａt(yī)enｅarｅｓtneighｂｏrs.ＣonｓｉdｅrａsetSｏfdａt(yī)apoiｎtsｉnRdaｎdaｑuｅrypoｉntq∈Ｒd.Givenε>0,ｗesaｙthaｔapｏintp∈Sisa（1＋ε）-approxｉmateｎeaｒestneigｈｂoroｆqｉｆdist（p,q)≤(1＋ε）dｉｓt（p＊,ｑ）wheｒep＊isthｅｔruenｅareｓtneｉghｂoｒtoｑ。Inoｔherwords,ｐｉswｉthinrｅlatｉveｅrroｒεoftｈetrｕｅnｅａrestnｅiｇhｂｏr.Theappｒoｘimaｔeneａreｓｔneigｈborｐｒoblemｈasｂeenheａvilｙsｔudiedｒｅｃeｎtlｙ．ExamplｅsincluｄeａｌｇoriｔhｍsbyBern［Ber93］，ArｙaandMount［AM９3b],Ａｒyａ,etａl．［AMN＋98],Ｃlarkson[Clａ９4］，Ｃhaｎ［Ｃha９7]，Kleiｎbeｒg［Kle97］，IndｙkandMｏｔwani［IM98]，ａndＫushileviｔz，OｓtrovskｙaｎｄRabaｎi[KOR98］．InthisstuｄywｅrｅstrｉctattｅｎtiontoｄatastructuresofsｉzｅＯ（dn)bａsedonhｉｅrarchicａlspatialdecompｏsitions，aｎｄｔheｋd-trｅｅiｎparticular.Inｌargｅpartthｉsｉｓｂｅｃauseｏfthesimplｉcityandwidesｐreadpoｐulａrityofthisdataｓtructure.Akd—treｅisbinarytreeｂａｓｅdonａhieｒarchicaｌｓubｄivisｉoｎｏｆsｐacｅbysplittｉnｇhｙperplanesthaｔarｅｏrthogonａltothｅcoorｄinateaxes［ＦBF7７］。Ｉtisdescribedfuｒtｈerｉntｈeｎextsectioｎ．Akeyiｓsuｅinthedeｓignofｔhekd－treeisthechｏiceofｔheｓpｌｉttinghyperplane.Ｆriｅdman，Ｂenｔley,aｎdFinｋelｐropｏsedasplｉttｉnｇmethｏｄbasedonsｅｌectiｎｇtｈeｐlaneorｔhｏgｏnalｔothemedｉａｎcoordinateaｌongwｈicｈtｈepointshａveｔhｅgｒｅatestspread。Ｔｈeｙcａlledｔhｅresulｔingtrｅｅanopti—miｚedｋｄ-treｅ,aｎdheｎcefｏrｔhｗecaｌltｈeｒｅｓultiｎgsplｉttinｇｍethodtｈestandaｒdsplittｉｎgmethod。Anotheｒcｏmmonaｌteｒnaｔｉveｕsｅstheshａｐeoftｈecｅｌl,ｒatｈerｔhａnthｅdistrｉbutionoｆtｈedａｔapoints．Itsplｉtseachｃellthroughitsｍidpoinｔｂｙahyperplaneorｔhogoｎaltｏitslonｇestsidｅ。Wｅcallthiｓthemｉdpｏintsｐlｉtmｅthod．Anuｍbｅｒｏfoｔhｅrdatａsｔｒuｃturesfｏrｎeａrｅstnｅighboｒsearchingbａseｄonhｉｅｒaｒｃhicalｓpatｉaldｅｃomｐosｉtionshavebeeｎｐroposｅd。Yianｉlosintroｄuceｄtheｖp－ｔｒee［Yiａ９3］。Rａｔherthanusiｎｇanaxiｓ—ａlｉｇｎedplａneｔｏｓplitaｎｏdeaｓｉnkd-tree，ｉtusesadatａpoinｔ,caｌledthｅvaｎｔageｐoint，asthecenteｒofａｈyperspheretｈａｔpａｒtiｔionstheｓpａcｅintotｗorｅgions．Therehasａlｓobeenｑuiｔeabitoｆiｎｔereｓｔfｒｏmthe_elｄofdａｔabases.Thereａｒeseveｒaldａt(yī)astrucｔuresfｏｒdatabaseaｐｐlicationsbａsｅdonR-tｒeｅｓａnｄｔheiｒｖarｉants［ＢKSS90，SRＦ87]。Forexample,theX—tree［BＫＫ96]iｍｐrovestｈepｅrfｏｒmanｃeoftheR＊—treebyavｏｉｄinghighovｅｒlaｐ.ＡnothｅrexampleistheSＲ—tree[KS9７］。ＴｈｅTV—tree［LJF９4]ｕseｓａdｉfferentmetｈerｄtodeａlwｉthhｉｇhｄimｅnsｉonalspaces.Itｒｅｄucｅsｄｉmensionａｌiｔybymainｔainingａｎumberoｆactiｖedｉmｅnsiｏnｓ。Whenaｌldataｐointｓinaｎｏdesｈａretｈesamecｏｏrdｉnａt(yī)eoｆanactivedｉmensｉｏn，thatｄimeｎｓioｎｗillｂｅdｅａcｔiｖａt(yī)eｄandｔhesｅtｏｆactiｖedｉmensioｎssｈifts.Iｎthｉspapｅrweｓtudyｔheｐｅrformancｅoftwootｈeｒspliｔｔiｎｇmｅｔhodｓ，andｃｏｍpareｔｈｅmaｇainstｔｈekｄ—trｅespｌｉttingmethｏd。Ｔhｅfirst,calｌedslｉdｉng－midpoint，ｉsaｓpliｔtiｎｇmethｏｄthａt(yī)waｓintrodｕceｄbyMouｎtaｎdArｙaintheＡNNｌｉbraryforａpproximatenearestneighｂoｒsｅarching［MＡ97］.Thiｓmetｈｏdwasintrodｕcedintotｈｅlibrａryinorｄerｔobetterｈanｄｌehighｌyclusｔｅrｅddatasｅｔs.Wｅknoｗｏfnoanaｌｙsiｓ(eｍpiriｃalorｔhｅorｅｔicaｌ)ofｔhismethod.Ｔhismeｔhｏｄwａsdesignedasaｓiｍpｌetｅchniqueｆoraddｒｅsｓｉｎgoneoftｈemostｓerｉｏuｓflawsintｈeｓtanｄａｒdｋd-treesｐｌｉtｔinｇmethod。Theflａwiｓｔhatwheｎtｈｅｄatapoｉｎtsarehｉgｈlycluｓterｅｄinlowdimeｎsiｏnａlsｕbspaces,ｔｈｅnthestanｄaｒdkd－trｅespｌittｉnｇmeｔｈｏdmaｙprｏducｅhｉgｈｌyｅlonｇａt(yī)ｅdceｌlｓ,aｎｄtheseｃanleａdｔoslｏwｑuerｙｔiｍeｓ．Thissｐlitｔiｎｇmethoｄsｔartsｗithａｓiｍplemidpｏintｓpliｔoｆtheｌｏnｇestsidｅoｆtｈｅcｅｌl，butiftｈｉssｐlitｒesｕltsｉnｅiｔｈersｕｂｃellcontａiｎingnｏｄaｔapoints,ittranslａｔes（or“slides”）ｔhespｌitｔingplaneintheｄirｅｃｔionｏfthepoinｔsuｎｔｉlhiｔtingthefirrｓtdａt(yī)ａpｏiｎｔ。IｎSecｔion3。1wｅdｅscｒiｂetｈisｓｐlittingmethodaｎｄanaｌyzesomeofｉｔsｐｒｏperties．Theseｃoｎdsplittinｇmethod,calｌeｄmｉｎimｕｍ—aｍbiguity,isaquery-ｂaｓｅdtechｎique.Tｈeｔｒeeｉsgｉvｅｎnｏtonlythedatａｐoinｔs,bｕｔaｌｓoａｃoｌlectiｏnｏfsａmpleｑuerｙｐoints，calｌedtｈetｒaｉｎingpoｉntｓ。Ｔheａlgoｒithmapｐlｉｅsagreｅdyheｕｒisticｔobuildtｈｅtreeinａnａt(yī)ｔemptｔoｍiｎimｉzethｅexpectedqueｒytimeｏnthｅtrainｉｎgpoints.Wemodｅlqｕeryprocessiｎgastheprｏbｌｅmofeliｍiｎａt(yī)inｇdatapoｉntsfrｏmｃonsidｅrationasthepossiblecａndidatesforthｅneaｒｅｓｔnｅighbｏr。Giveｎａcolleｃtｉonoｆqueryｐoiｎts，wｅcaｎmｏdelanyｓtageｏftｈeneａｒestｎｅigh-boｕraｌｇorｉtｈmasａｂipartiｔegrapｈ，calledtｈeｃａndidategraph，whoseｖerticescorrespoｎdｔoｔheunionoｆthedatapoｉｎｔｓandthequeｒｙｐoiｎts，andｉnwhicｈｅaｃｈquｅrｙpｏintisadjaｃｅnttothesｕbｓｅｔofdataｐoiｎtsthatmigｈｔbeｉtsnearestｎeiｇhbｏr.Theｍｉnｉmum-ambiｇuiｔysｅlｅctsｔｈesｐlitｔinｇpｌanｅａｔeａcｈstagethａt(yī)ｅｌiｍｉnatｅstｈｅmaximumnumbeｒofremａiningedgesinthｅcandｉdateｇraph。IｎSectiｏｎ３．2wedｅscrｉｂｅthissｐlittinｇmethodingrｅaｔerｄetail。Weimｐlｅmentedtｈeｓetwｏｓplｉｔtingｍethoｄｓ，alｏｎｇwithｔhestandａrdkd-ｔreｅsplitｔingmethod．Wecｏmpａreｄtｈemｏnanumberofsyｎthetiｃaｌｌygenｅrａt(yī)edpoｉｎｔdistributiｏnｓ，whiｃhｗｅredesigneｄtｏmｏdellｏw－dimenｓioｎalcluｓｔeｒinｇ。Ｗebelieｖｅthiｓtypeoｆclusｔeringisｎotｕncommoninｍａnyappliｃationdatasets［JＤ88］。Weusedsynthｅticｄatasets,aｓopposedｔoｓｔaｎdaｒdｂenchｍaｒｋs，sothaｔｗecouldaｄｊusｔthｅstrenｇthandｄiｍｅnｓionaｌｉｔyoｆthecluｓtering。Ourrｅsｕｌｔssｈ－ｏwｔhaｔtｈesｅnewsplittｉnｇmethodscaｎprovidｅsiｇni＿caｎtimprovemｅntsovｅrthｅstandardｋd-treesｐlｉｔtｉｎｇmｅｔhodfordaｔａsetsｗitｈloｗ-diｍensiｏｎalclusteｒ-ｉng．Ｔhereｓtoｆｔhepapeｒｉsorｇanizｅｄaｓfolｌｏws。Inｔhenextｓｅｃtionｗeprｅseｎtbackgrｏuｎｄinforｍationoｎtheｋd－treeandhoｗtoperfｏrｍnearestnｅiｇｈbｏrsｅa-rchesinｔhistｒee．InSectiｏn3wepresenttheｔｗonewspｌitｔiｎgmethoｄs.ＩnSection4wedescribeourimpleｍｅｎtatiｏnaｎｄprｅsentourempiｒicａlresｕlts．２。BaｃkgroundＩnthissｅｃtｉonweｄescrｉｂｅhｏwｋd-treeｓａｒｅuseｄfｏｒperformiｎgexacｔandapｐｒｏxｉmateneａreｓtnｅｉghbｏrsearcｈing.Ｂentleｙｉnｔｒｏducedtheｋｄ—treeasageｎ－ｅralizａt(yī)iｏnｏｆtｈebinaｒysearchｔreeｉnhｉｇｈerｄiｍｅnｓiｏns［Bｅn７5］。Eaｃｈｎodeｏｆthｅｔｒeeisimpliｃitlyassociaｔedwithaｄ—dimeｎsionａｌｒｅcｔangle，ｃａllediｔｓcell.Therootnodｅiｓaｓsociａt(yī)ｅｄｗｉtｈtheboundｉｎgrectanｇｌe，whichｅｎcloseｓａlloftｈｅｄａt(yī)ａpoｉnts。Eacｈｎｏdｅiｓaｌｓoiｍｐliciｔlyassｏciateｄwｉththesubｓetofdataｐoinｔｓtｈａt(yī)lｉeｗｉｔhｉnｔhisrectanｇle。（Datapｏintslyingｏnｔheｂoｕｎdarybｅtweentｗoｒecｔａnglｅs,mａybeassｏciａt(yī)edwiｔheither。）Iｆｔｈenumberofpｏｉnｔｓaｓsｏcｉatｅdｗithａnodｅfaｌlsbelowａgｉventｈresｈolｄ,calledthebｕｃkeｔsｉze,thentｈisnodeiｓaleaf，andthｅsepoinｔsareｓtoreｄｗithｔhelｅaf。（Iｎourｅxperｉmeｎtsweusedabｕcketsiｚｅofoｎe.)Othｅrwise,theconstrｕctionalｇorithｍｓeｌｅctsasｐｌiｔｔinghyp—ｅrplane，whｉchｉsorｔhｏｇonａltoonｅoｆｔhecｏordiｎaｔeaxesaｎdpａssｅsthrouｇhthｅcｅｌl．Tｈｅｒeaｒｅanｕmbｅｒofsplｉttｉnｇmetｈodｓtｈatmaｙbeusedfoｒchｏosinｇthｉshｙperｐｌanｅ。Wewｉlｌdｉsｃuｓsthesｅiｎgreaｔerdetailbelow．Thｅhyperplanesuｂdｉ-ｖidestheassociａt(yī)ｅdｃellintotｗｏsubrectaｎｇｌes,wｈｉcharethenasｓociateｄｗｉthｔhechｉldrenoｆthisnode,ａndthepointｓaresuｂdｉvidedａmongthesｅcｈildｒｅｎaccｏrdiｎgtowhｉｃhsｉdeoｆtｈehyperplaneｔｈｅylie．Eａchｉnternalnｏdeoｆtｈetreeｉsassｏciaｔedwitｈitsspliｔtinghｙpｅrplaｎe（whicｈmaybｅgivenastｈｅｉｎdｅｘoftｈeoｒthｏgｏｎalaｘisanｄａｃuttingvalｕealｏngｔhisaxis)．Friedｍan，BeｎtleyandFinkel[FBF７７］pｒｅsentanalgorithmto＿ndthenｅａr－estneighboｒusｉｎgtｈekd－tｒeｅｓ。Theyiｎtroduｃetheｆoｌｌowingsｐｌittｉngmetｈod,whiｃhwecalｌｔhestandardsplittｉnｇｍetｈｏｄ.Forｅachinteｒnalnｏde,thｅspｌittiｎｇhyperpｌaｎeischosｅｎtｏbｅortｈoｇonａltotheaxｉｓａｌongwhｉcｈthepointｓhavetｈeｇrｅatesｔspread(di＿erenceofmaｘｉmumandmiｎiｍum）.Thｅsｐlｉttingｐｏｉnｔｉsch—ｏsenatthemｅdiancooｒｄinａｔe，ｓotｈatｔhetｗoｓubｓetsoｆｄａt(yī)apoｉｎtｓhａｖenｅarly—quａlsizes．TheｒesultｉngtreehasO（n)sizeａｎdＯ（logn)ｈeｉght．WｈiteandJaｉn［ＷJ96]ｐroposedanaltｅｒｎative，caｌｌedtheＶＡM—split，wｉthｔhｅｓamｅbasicidｅa，buttｈesｐｌitｔinｇdimｅｎsionｉsｃhosｅntｏbｅthｅoｎewiththemaximumvariａnce．Querｉesａreaｎswｅrｅｄbyasimplｅrｅcursivｅalgｏrithm。Inthebasisｃasｅ，whenｔｈeａlｇｏrithｍarrivｅsataleａfｏftｈetreｅ，iｔｃoｍpuｔesthedistanceｆromｔhequerypointtoeachｏｆthedatapｏｉntｓassociaｔedｗithｔhisnode。Ｔhesmaｌleｓtsuchdist-tanceｉsｓaved．Ｗhenａrrｉviｎｇataninｔernａlnodｅ，iｔ＿rstdｅｔｅrｍinesthesideｏftheassociatedｈｙperplaｎeｏnｗhicｈtheｑｕerｙpoｉntliｅs.Ｔhｅｑｕｅrypointｉsnece—ssarilyclｏsｅrtothischild’sｃｅll．Thesearｃhreｃursivelyｖｉsitｓthisｃhild.Onretu-rnｉngfromthｅseａrｃh，ｉtｄetｅｒmineswheｔhｅrthecellassoｃｉatedｗｉtｈtheｏtheｒcｈiｌｄｉｓcｌosertoｔheｑuerypoｉntthanthｅclｏseｓtpoiｎtｓeensoｆar。Ifｓｏ，ｔhenｔhｉschiｌｄisalｓｏｖisitedrecuｒsively.Whentｈｅsｅａrchrｅｔurnsfromtherooｔ，thｅclｏs-ｅstpoinｔseｅnｉsｒeturｎed.Ａｎｉｍｐｏrtanｔobservatiｏnisthatfoｒeaｃｈqｕｅｒypoｉnt，eveｒyｌeafｗhosｅdistancefromtheqｕerypointisｌeｓstｈantheneａrｅｓtneighｂｏrwillｂｅviｓiｔedbythealgoriｔｈm。Iｔｉｓaneasymatteｒｔoｇeｎeralｉzethｉｓｓeaｒcｈａlgｏrithｍfｏransｗeringapｐroｘ—iｍateｎeaｒestnｅighbｏrquｅrｉes。Letεdenｏtetｈeａllowｅｄerrｏｒbound。Ｉnthｅｐｒocessingoｆaninternａlｎode,thefurtｈercｈilｄisvisitedonlyｉfitsdistａnｃefromtｈｅquerypoinｔislｅｓstｈａｎｔhedｉstaｎcetotheclosｅｓtpoｉnｔｓofar,ｄｉvideｄｂｙ（1+ε）。Arｙaｅｔal．[AMN＋98］ｓhowｔhｅcorreｃtｎessofｔhｉｓproｃｅdure。Tｈeyalｓｏshowｈｏｗtogeneralizｅthｅsｅaｒchａlgｏriｔｈｍforcｏmputingthek—clｏsｅstneighbors，eitherｅxactｌyｏrａpprｏｘimately.AryaandMounｔ［ＡＭ93a]propoｓedanuｍｂｅroｆｉmproveｍentsｔothisbasiｃａlgｏrithm.Tｈefirstｉscallediｎcｒemｅnｔaldiｓtancｅcaｌculaｔioｎ.ThｉｓtｅｃｈniquｅｃａnbeａppliedforａnyＭinkowskｉmetｒic.Inadditiontosｔorｉngthｅsplitｔinghypｅｒplanｅ,eachinteｒｎalnｏｄeｏfｔhetreealｓosｔorestheexｔｅnｔｓofａssociateｄcellprｏｊecｔedorthｏgｏｎallyonｔoiｔｓsplｉｔtｉnｇaxis.Thealｇorithｍdoｅsnｏtmain－ｔａintruediｓｔaｎces,butinstead（fortheEｕclideanmetｒic）maｉｎｔaiｎｓsquareddiｓtａｎceｓ.Whenthｅalｇｏriｔhmarriｖesatanｉnternaｌnodｅ,iｔmaintaiｎsthesquａreｄｄiｓtaｎｃefｒomtheｑuerypoiｎｔtoｔheasｓｏciatｅdcell。Thｅｙshｏｗｔhａｔincｏｎstanｔｔｉmｅ（indeｐenｄｅntofdｉmensiｏn)iｔispossiblｅtouseｔhisinformationtｏcoｍputｅtｈeｓｑuarｅdｄiｓtancｅtoｅaｃhｏｆｔhｅchｉldren’ｓｃｅlｌ。Thｅyaｌsoｐresentedamｅthｏｄｃalledｐrｉｏritysearｃｈ,whｉchｕsesａheapｔovisｉｔtheleavesofthｅtｒeｅinｉncｒeas—ｉngorderoｆdisｔaｎcｅｆromtｈequerypoinｔ,ratｈeｒthanｉnthereｃursiveｏrｄerdｉcａ—tatｅdｂythestｒuctuｒeｏfthetree.Yetanotｈｅrｉmproveｍeｎtisａwｅｌl－knowｎteｃh-ｎiquefｒomｎｅarestnｅｉghbｏrseaｒchｉnｇ，caｌledpaｒtialdistａnｃecａlcｕｌatｉon[BG85,Spｒ９１］。Wｈencoｍputiｎgｔhedistａncebｅtｗeentｈｅqｕerypoiｎtandadaｔａpoint，ｉｆtheaｃcｕmｕｌaｔedｓumofsquａredcｏmｐonenｔｓeverｅxｃeeｄsthesqｕaredｄistａncetothｅｎｅaｒestpointsｏfar，thｅntheｄiｓｔａｎcecomｐuｔaｔionistermｉnated．Oneoｆｔheimｐｏｒtaｎtelｅmentsofａppｒoximateneａreｓtｎeｉghborsｅarｃhinｇ,whｉｃｈｗａsｏbseｒvｅdｂyAｒyａｅtal。［ＡMＮ+９８]，isthatｔheｒeａretwoiｍpｏrtantｐｒｏpｅｒtiesofａnｙdａｔastruｃｔureforaｐproximａt(yī)ｅneａｒｅsｔneighｂorseａrchinｇbａs-edｏnspatialdｅcomposition．Balanc