距離檢測(cè)文章

18/18附錄１對(duì)聚類(lèi)點(diǎn)集近似最鄰近搜索的分析SongriｔＭａneewongｖaｔana和DａvidM．Ｍount摘要最鄰近搜索是最基本的計(jì)算問(wèn)題.給定D維空間中的一個(gè)點(diǎn)集，它包含n個(gè)數(shù)據(jù)點(diǎn),最鄰近搜索要解決的問(wèn)題是用一個(gè)數(shù)據(jù)結(jié)構(gòu)對(duì)這些點(diǎn)進(jìn)行處理,以便給出一個(gè)查詢(xún)點(diǎn)時(shí),我們可以高效地在數(shù)據(jù)集中找到與該點(diǎn)距離最近的點(diǎn)。因?yàn)閿?shù)據(jù)集可能很大，所以我們更關(guān)注數(shù)據(jù)結(jié)構(gòu)所占的存儲(chǔ)空間，希望將其控制在Ｏ（ｄｎ）。一種較為流行的用于最鄰近搜索的數(shù)據(jù)結(jié)構(gòu)是ｋd樹(shù)及其變體，這項(xiàng)技術(shù)的基本思想是將分級(jí)的分解空間放進(jìn)一個(gè)盒子中。在建立這種數(shù)據(jù)結(jié)構(gòu)時(shí)的一個(gè)重要的問(wèn)題是分割算法的選擇，分割算法決定了分割維和用于空間分割的超平面.分割算法的選擇在很大程度上決定了數(shù)據(jù)結(jié)構(gòu)的效率,當(dāng)數(shù)據(jù)點(diǎn)和查詢(xún)點(diǎn)都聚集在低維子空間時(shí)，這點(diǎn)體現(xiàn)的尤為明顯。這是因?yàn)檩^高的聚集性會(huì)讓子劃分生成長(zhǎng)寬比極高的盒子。我們將兩種可選的分割策略與眾所周知的優(yōu)化ｋｄ樹(shù)策略進(jìn)行了對(duì)比。第一種叫做滑動(dòng)中點(diǎn)分割策略。它試圖尋求一種平衡，以使得子劃分產(chǎn)生的盒子有一個(gè)長(zhǎng)寬比的上限，且每個(gè)盒子中都含有數(shù)據(jù)點(diǎn)。第二種被稱(chēng)為最小不確定性分割策略,它是一種基于詢(xún)問(wèn)的搜索方式。這種策略中，我們除了要給出數(shù)據(jù)點(diǎn)集外，還要給出一個(gè)訓(xùn)練查詢(xún)集,用于預(yù)處理。策略中使用了一種簡(jiǎn)單的貪心算法，以期選擇的分割平面能在對(duì)訓(xùn)練集查找最鄰近點(diǎn)時(shí)使得平均不確定性的總和最小。在產(chǎn)生的一系列點(diǎn)集和查詢(xún)集上,我們進(jìn)行了實(shí)驗(yàn)，將這兩種策略與優(yōu)化kd樹(shù)策略進(jìn)行了比較，并給對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行了分析。我們論證了：對(duì)于聚類(lèi)數(shù)據(jù)和查詢(xún)集的近似最鄰近查詢(xún)，這兩種算法的效率較標(biāo)準(zhǔn)的kd樹(shù)有顯著提高。1。介紹最鄰近查詢(xún)需要解決的是這樣一個(gè)問(wèn)題：我們給定集合S,它含有度量空間X中的n個(gè)點(diǎn)。我們要對(duì)這n個(gè)點(diǎn)進(jìn)行處理，以便對(duì)給定的任意點(diǎn)ｑ（q∈X)我們都能很快的找到S中距離它最近的點(diǎn)。最鄰近查詢(xún)?cè)诤芏囝I(lǐng)域中都有應(yīng)用,比如知識(shí)發(fā)現(xiàn)、數(shù)據(jù)挖掘、模式識(shí)別和分類(lèi)、機(jī)器學(xué)習(xí)、數(shù)據(jù)壓縮、多媒體數(shù)據(jù)庫(kù)、文件恢復(fù)、統(tǒng)計(jì)等等。對(duì)于度量空間,我們有許多種選擇。我們始終假定空間為Rd,即d維空間，空間中的距離采用閔可夫斯基Lm距離進(jìn)行度量。對(duì)于任意整數(shù)m≥1，Rd中任意兩點(diǎn)p＝(p１，ｐ2…，pｄ)、ｑ=（q１,q２,…,ｑd）的距離被定義為∑１≤i≤d|pi—qｉ｜m的ｍ次方根。L1，L2和Ｌ∞分別被稱(chēng)為：曼哈頓距離，歐氏距離和最大距離。我們將主要的焦點(diǎn)集中在數(shù)據(jù)結(jié)構(gòu)上。因?yàn)閿?shù)據(jù)集可能很大,我們將其做一下限制，只考慮數(shù)據(jù)空間程線性增長(zhǎng)的情況.在眾多方法之中,最流行的是基于分等級(jí)分解空間的方法。在這個(gè)領(lǐng)域中,最根本的工作是由Fｒiｅdman，Bｅntleｙ和Finkel完成的。他們指出通過(guò)使用kd樹(shù)，可以將固定維數(shù)空間中可預(yù)計(jì)其分布的數(shù)據(jù)的空間復(fù)雜度控制在O（n)，查詢(xún)的時(shí)間復(fù)雜度控制在O（logn）.對(duì)于這一問(wèn)題,可選擇的方法有許多種。但是，所有已知的方法都存在這樣一個(gè)缺陷：當(dāng)空間維數(shù)增加的時(shí)候，運(yùn)行時(shí)間或空間復(fù)雜度將隨之以指數(shù)倍增長(zhǎng)。我們?cè)噲D找到一種高效的算法，即使在最糟的情況下，它也會(huì)有較低的空間復(fù)雜度和較短的查詢(xún)時(shí)間，但事實(shí)證明,想要獲得這樣的算法是很困難的，但這同時(shí)也告訴我們尋找近似的最近臨是解決問(wèn)題的一條出路。設(shè)S為Rd中的點(diǎn)集，查詢(xún)點(diǎn)q為Rｄ中任意一點(diǎn),假定ε>０，如果ｄｉst(ｐ，q)≤（1＋ε）dｉst（ｐ＊,q）成立,我們就說(shuō)點(diǎn)p是點(diǎn)q的近似最近臨。換句話說(shuō)，ｐ是在相對(duì)誤差ε內(nèi)的真實(shí)最近臨。最近,人們已經(jīng)對(duì)近似最近臨問(wèn)題進(jìn)行了深入的研究。較有代表性的算法包括：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].本文中，我們以分級(jí)空間分解特別是kd樹(shù)為基礎(chǔ)，將數(shù)據(jù)結(jié)構(gòu)的大小限定在O（dn)。這是因?yàn)樵诜N數(shù)據(jù)結(jié)構(gòu)較為簡(jiǎn)單而且應(yīng)用廣泛。kｄ樹(shù)是一種二元樹(shù)，它依靠垂直于坐標(biāo)軸的分割超平面將多維空間劃分為多級(jí)子空間。我們將在下一節(jié)對(duì)這個(gè)問(wèn)題進(jìn)行深入的探討.設(shè)計(jì)kｄ樹(shù)的一個(gè)關(guān)鍵問(wèn)題是分割超平面的選擇。Frieｄmａn，Ｂentlｅy和Fｉｎｋel提出了一種分割策略:假設(shè)點(diǎn)集在第k維上有最大的延展度，則將過(guò)第ｋ維中點(diǎn)且垂直于第k維坐標(biāo)軸的平面作為分割超平面。他們將用這種方法得到的樹(shù)稱(chēng)為優(yōu)化kd樹(shù)，我們把用這種方法叫作標(biāo)準(zhǔn)分割策略.另一種較為普遍的方法是利用包含點(diǎn)集的盒子形狀(而非點(diǎn)集的分布）對(duì)點(diǎn)集劃分。這種策略將垂直于盒子最長(zhǎng)邊且過(guò)最長(zhǎng)邊中點(diǎn)的平面作為分割超平面。我們將其稱(chēng)為中點(diǎn)分割策略。以分級(jí)空間分解為基礎(chǔ),人們把出了許多用于最近臨查詢(xún)的數(shù)據(jù)結(jié)構(gòu)。Yiａnilos引入了vp樹(shù)。它不像kd樹(shù)那樣用一個(gè)平面去分割點(diǎn)集，而是利用一個(gè)稱(chēng)為優(yōu)勢(shì)點(diǎn)的數(shù)據(jù)點(diǎn)作為超球面的中心，將空間分為兩部分。有一些基于Ｒ樹(shù)及其變體的數(shù)據(jù)結(jié)構(gòu)被應(yīng)用于數(shù)據(jù)庫(kù)領(lǐng)域.比如X樹(shù),它通過(guò)避免高度堆疊提高了R*樹(shù)的性能。類(lèi)似的例子還有SＲ樹(shù).ＴＶ樹(shù)在處理高維高間時(shí)使用了較為獨(dú)特的方法。它通過(guò)維護(hù)一系列活躍維達(dá)到了降維的目的。當(dāng)一個(gè)節(jié)點(diǎn)中的數(shù)據(jù)點(diǎn)共享了一個(gè)活動(dòng)維上的相同的坐標(biāo)時(shí)，該維將被列為無(wú)效，活躍維集合也將隨之改變.在這篇文章中我們研究了另外兩種分割策略的的性能，并且將其與以往的ｋｄ樹(shù)分割策略進(jìn)行了比較。第一種策略叫做“滑動(dòng)中點(diǎn)",它是由Mount和Arya針對(duì)近似最近臨搜索提出的，并應(yīng)用于ANN函數(shù)庫(kù)中。將這種方法引入函數(shù)庫(kù)是為了更好的處理高聚性數(shù)據(jù)集。這種策略采用一種較為簡(jiǎn)單的方法來(lái)更正標(biāo)準(zhǔn)ｋd樹(shù)分割策略中的一個(gè)嚴(yán)重缺陷。這個(gè)缺陷在于，當(dāng)高聚性的數(shù)據(jù)點(diǎn)存在于低維子空間時(shí)，采用標(biāo)準(zhǔn)kｄ樹(shù)分割策略對(duì)點(diǎn)集進(jìn)行劃分將會(huì)產(chǎn)生許多長(zhǎng)寬比極高的盒子,這些盒子會(huì)使查詢(xún)時(shí)間大大延長(zhǎng).“滑動(dòng)中點(diǎn)"策略起初也是沿盒子的最長(zhǎng)邊進(jìn)行簡(jiǎn)單的中點(diǎn)分割，但是,如果分割產(chǎn)生的任何子盒中不含數(shù)據(jù)點(diǎn),該策略將使分割面沿點(diǎn)集沿伸方向滑動(dòng)，直到遇到第一個(gè)數(shù)據(jù)點(diǎn)為止.在3.1節(jié)中我們將對(duì)這種分割策略進(jìn)行詳細(xì)描述并對(duì)其特性做出分析.第二種策略叫做“最小不確定性”分割策略，它是一項(xiàng)基于詢(xún)問(wèn)的技術(shù)。建樹(shù)時(shí)不僅要給出數(shù)據(jù)點(diǎn)集,還要選出一些示例性的查詢(xún)點(diǎn)，這些點(diǎn)被稱(chēng)為訓(xùn)練點(diǎn)。建樹(shù)時(shí)，算法應(yīng)用了一種啟發(fā)式的貪心算法，它試圖使對(duì)訓(xùn)練集的查詢(xún)時(shí)間最小。給定一個(gè)查詢(xún)點(diǎn)集，我們將最鄰近查詢(xún)算法的每一步看作一張雙向連通的圖,稱(chēng)之為候選圖，它的頂點(diǎn)代表了所有的數(shù)據(jù)點(diǎn)和查詢(xún)點(diǎn),圖中與查詢(xún)點(diǎn)緊挨著的數(shù)據(jù)子集可能就是該查詢(xún)點(diǎn)的最鄰近點(diǎn)。“最小不確定”策略在執(zhí)行的每一步選出一個(gè)分割平面,盡可能多地刪除候選圖中剩余的邊。在3．２節(jié)中,我們對(duì)這種策略進(jìn)行了更為詳細(xì)的描述。我們?cè)趫?zhí)行這兩種策略的同時(shí)也執(zhí)行了標(biāo)準(zhǔn)ｋd樹(shù)分割策略。在產(chǎn)生的一系列有著各種分布的低維聚類(lèi)數(shù)據(jù)上，我們對(duì)這些算法進(jìn)行了比較.我們相信這種類(lèi)型的聚類(lèi)數(shù)據(jù)在實(shí)際應(yīng)用中的較為普遍的。我們使用手工合成的數(shù)據(jù)作為與基準(zhǔn)數(shù)據(jù)的一個(gè)對(duì)比，以便于對(duì)我們聚類(lèi)數(shù)據(jù)的密度和維數(shù)進(jìn)行調(diào)整。我們的結(jié)果表明，對(duì)于低維聚類(lèi)數(shù)據(jù)集，這兩種算法的效率較標(biāo)準(zhǔn)的kd樹(shù)有顯著提高。以下的篇章是這樣組織的，在下一章中我們展示了ｋd樹(shù)的背景信息以及它是怎樣執(zhí)行最鄰近查詢(xún)的。在第3節(jié)中，我們對(duì)兩個(gè)新的分割策略進(jìn)行了描述.第四章，主要是對(duì)實(shí)驗(yàn)及結(jié)果的展示。２。背景在這節(jié)里我們描述了kd樹(shù)是如何執(zhí)行精確或近似的最鄰近查詢(xún)的。Benｔley將kd樹(shù)作為一種在高維空間中通用的二元搜索樹(shù)［Beｎ75］。Kｄ樹(shù)的每一個(gè)的節(jié)點(diǎn)可以看作是一個(gè)多維矩形，我們將基稱(chēng)為盒子.根節(jié)點(diǎn)是一個(gè)包含了所有數(shù)據(jù)點(diǎn)的矩形。其余的節(jié)點(diǎn)代表了包含數(shù)據(jù)點(diǎn)子集的矩形。（在兩個(gè)矩形邊界上的點(diǎn)可以認(rèn)為是包含在其中任何一個(gè)矩形中）.如果節(jié)點(diǎn)中的數(shù)據(jù)點(diǎn)個(gè)數(shù)小于一個(gè)被稱(chēng)為bucｋｅtｓｉzｅ的閾值，這個(gè)點(diǎn)就被稱(chēng)為葉節(jié)點(diǎn)，這些數(shù)據(jù)點(diǎn)就存儲(chǔ)在葉節(jié)點(diǎn)中.否則，建立算法就選擇一個(gè)分割超平面，它垂直于其中一個(gè)坐標(biāo)軸，并且貫穿整個(gè)盒子。有許多分割策略可以用于超平面的選擇。我們將在下面對(duì)此進(jìn)行更詳細(xì)的討論。超平面將盒子劃分為兩個(gè)子矩形，相當(dāng)于是當(dāng)前節(jié)點(diǎn)的兩個(gè)孩子節(jié)點(diǎn),盒子中的數(shù)據(jù)點(diǎn)屬于哪個(gè)孩子節(jié)點(diǎn),取決于數(shù)據(jù)點(diǎn)在超平面的哪一側(cè)。樹(shù)中的每個(gè)內(nèi)部節(jié)點(diǎn)都與它的分割超平面相關(guān)。Ｆrｉdｍan，Benｔley和Fiｎkel［FBＦ７7］給出了一種用kd樹(shù)尋找最鄰近數(shù)據(jù)點(diǎn)的算法。他們所介紹了下面的分割策略，我們將面稱(chēng)為“標(biāo)準(zhǔn)分割策略”。對(duì)每個(gè)內(nèi)部節(jié)點(diǎn)，我們將沿著點(diǎn)集的最大延展度方向選擇分割平面,并使其垂直于某個(gè)坐標(biāo)軸。分割點(diǎn)被選在中點(diǎn),這樣分割后形成的兩個(gè)子集中含有的數(shù)據(jù)點(diǎn)數(shù)基本相同。最終得到的樹(shù)的大小為O（n）,高度為Ｏ(logn）。Whｉｔe和Jain[WJ96］提出了另一種方法，稱(chēng)為VAM分割，兩種方法采用的基本思想是一致的,但后者是將具有最大差異度的維定為分割維。我們用一種簡(jiǎn)單的遞歸算法對(duì)查詢(xún)進(jìn)行回答。在最基本的情況下,當(dāng)算法執(zhí)行到葉節(jié)點(diǎn)時(shí),它會(huì)對(duì)葉中的每個(gè)數(shù)據(jù)點(diǎn)與查詢(xún)點(diǎn)間的距離進(jìn)行計(jì)算。最小的距離值將被保存。當(dāng)我們到達(dá)內(nèi)部節(jié)點(diǎn)時(shí),算法首先決定查詢(xún)點(diǎn)位于超平面的哪一側(cè)。查詢(xún)點(diǎn)必須離即將被訪問(wèn)的孩子較近。算法遞歸地訪問(wèn)這個(gè)孩子。當(dāng)返回時(shí)，算法判斷盒子中另一個(gè)孩子與查詢(xún)點(diǎn)的距離是否比當(dāng)前最小距離要近,如果是，些也對(duì)這個(gè)孩子進(jìn)行遞歸訪問(wèn).當(dāng)搜索返回到根時(shí)，我們就能得到最鄰近點(diǎn)了。一個(gè)重要的觀察結(jié)論是:對(duì)于任何查詢(xún)點(diǎn)，算法將訪問(wèn)每一個(gè)與查詢(xún)點(diǎn)距離小與最鄰近點(diǎn)的葉節(jié)點(diǎn)。要對(duì)這種近似最鄰近查詢(xún)進(jìn)行概括是較為簡(jiǎn)單的。設(shè)ε為允許的誤差邊界。在處理內(nèi)部節(jié)點(diǎn)時(shí)，當(dāng)且僅當(dāng)先前距離較遠(yuǎn)的孩子節(jié)點(diǎn)與查詢(xún)點(diǎn)的距離是當(dāng)前最小距離的１／（1+ε）時(shí)，我們才對(duì)這個(gè)孩子節(jié)點(diǎn)進(jìn)行訪問(wèn).Araｙ等人證明了這個(gè)過(guò)程的正確性。他們也展示了這種通用的算法是如何計(jì)算出k個(gè)精確或者近似鄰近點(diǎn)的。Arya和Mounｔ［AＭ９3a］提出了一些對(duì)這種算法的改進(jìn)。第一種叫作“增量距離計(jì)算”。這是一種可以用于任何Mｉnkowski距離計(jì)算的方法.除了分割超平面，樹(shù)的每一個(gè)內(nèi)部節(jié)點(diǎn)還存儲(chǔ)了相關(guān)的盒子的信息。算法并不計(jì)算真正的距離，而是使用距離的平方。當(dāng)算法執(zhí)行到內(nèi)部節(jié)點(diǎn)時(shí)，它計(jì)算查詢(xún)點(diǎn)與相關(guān)盒子的平方距。他們指出在固定的時(shí)間內(nèi)（不依賴(lài)維數(shù)),用這個(gè)信息計(jì)算出與每了孩子節(jié)點(diǎn)對(duì)應(yīng)的盒子的平方距是完全可能的。他們還展示了一種叫作“優(yōu)先搜索”的方法，這種方法使用堆,按照距離增加的順序訪問(wèn)每個(gè)葉節(jié)點(diǎn)，而非按照樹(shù)結(jié)構(gòu)遞歸地訪問(wèn)。另外一種眾所周知的用于最近鄰查詢(xún)的算法叫作部分距離計(jì)算［ＢG85，Sｐr91］。當(dāng)計(jì)算查詢(xún)點(diǎn)與數(shù)據(jù)點(diǎn)距離時(shí)，如果各平方量的和超過(guò)了當(dāng)前最近點(diǎn)與查詢(xún)點(diǎn)距離的平方,那么停止對(duì)該距離的計(jì)算.對(duì)近似最鄰近查詢(xún),Aｒya等人發(fā)現(xiàn),對(duì)于任何一種基于分解空間的近似最鄰近查詢(xún),都有兩條重要的性質(zhì)。(1）平衡：樹(shù)的高度應(yīng)該為O（logn),其中n是數(shù)據(jù)點(diǎn)的個(gè)數(shù).(2）長(zhǎng)寬比界限:樹(shù)的葉節(jié)點(diǎn)的長(zhǎng)寬比應(yīng)該有一個(gè)限界，這意味著每個(gè)葉節(jié)點(diǎn)的最長(zhǎng)邊與最短邊的比值應(yīng)該有一個(gè)固定的上限值.在這兩條規(guī)則的基礎(chǔ)上，他們又指出，最臨近查詢(xún)可以將數(shù)據(jù)節(jié)構(gòu)的大小控制在O（dn)，將執(zhí)行時(shí)間控制在O（logn）。不幸的是，對(duì)于ｋd樹(shù)而言，這兩條性質(zhì)不總是同時(shí)成立，特別是當(dāng)數(shù)據(jù)點(diǎn)的分布特別集中時(shí).Ａrya等人提出了一種更復(fù)雜一些的數(shù)據(jù)結(jié)構(gòu),叫做“balanceｄbｏx-dｅcoｍpositiｏn”樹(shù),它可以同時(shí)滿(mǎn)足這兩條性質(zhì)。這了證時(shí)他們的理論，這種額外的復(fù)雜性看來(lái)是有必要的，并且他們的實(shí)驗(yàn)也證明了當(dāng)數(shù)據(jù)集是低維子空間上的高聚性數(shù)據(jù)時(shí)這種復(fù)雜性是很重要的。一個(gè)有趣但又實(shí)際的問(wèn)題是，是否存在一種算法,它有著kd樹(shù)的簡(jiǎn)單，又能對(duì)實(shí)際中的高聚分布的數(shù)據(jù)提供高效的搜索. 固定長(zhǎng)寬比的上限,對(duì)高效搜索來(lái)說(shuō)是充分非必要條件。一種更準(zhǔn)確的應(yīng)于他們的實(shí)驗(yàn)結(jié)果的條件被稱(chēng)為“pａcｋｉngｃonｓtｒainｔ”。定義一個(gè)半徑為r的球?yàn)辄c(diǎn)集的中心?！皃aｃｋｉngconstraint”表明與球相交的盒子的個(gè)數(shù)是有限的。PａｃkinｇConstraｉnｔ：大小至少為s的與半徑為r的球相交的葉節(jié)點(diǎn)的個(gè)數(shù)是有上限的，它受限于的r/s,但不依賴(lài)于ｎ。如果樹(shù)的盒子有長(zhǎng)寬比限制,那么它一定滿(mǎn)足“pacｋingｃonstraint”.Aｒya等人指出，如果滿(mǎn)足“pａcｋingcoｎｓtraｉnt",那么這個(gè)盒子數(shù)只取決于維數(shù)和ε。標(biāo)準(zhǔn)分割策略的不足在于它不能控制盒子的長(zhǎng)寬比，因此不能完全滿(mǎn)足“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(cuò)ｓｐ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ｒｅe(cuò)constructionfoｒ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ｅe(cuò)spｌｉ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ｅe(cuò)spｌ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ｅe(cuò)xpectedqueｒ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