Metric Trees

Metric tree in an indexing structure that allows for efficient KNN search

Metric tree organizes a set of points hierarchically

  • It's a binary tree: nodes = sets of points, root = all points
  • sets across siblings (nodes on the same level) are all disjoint
  • at each internal node all points are partitioned into 2 disjoint sets

Notation:

  • let N(v) be all points at node v
  • left(v),right(v) - left and right children of v

Splitting a node:

  • choose two pivot points p_l and p_r from N(v)
  • ideally these points should be selected s.t. the distance between them is largest:
    • (p_l,p_r)=\arg \max _{p_l,p_r\in N(v)}\left \| p_1-p_2 \right \|
    • but it takes O(n^2)(where n=\left | N(v) \right |) to find optimal p_l, p_r
  • heuristic:
    • pick a random point p \in N(v)
    • then let p_l be point farthest from p
    • and then let p_r be point farthest from p_l
  • once we have (p_l, p_r) we can partition:
    • project all points onto a line u=p_r-p_l
    • find the median point A along the line u
    • all points on the left of A got to left(v), on the right of A - to right(v)
    • by using the median we ensure that the depth of the tree is O(\log N) where N is the total number of data points
    • however finding the median is expensive
  • heuristic:
    • can use the mean point as well, i.e. A=(p_l+p_r)/2
  • let L be a d-1 dimensional plane orthogonal to u that goes through A
    • this L is a decision boundary - we will use it for querying

After metric tree is constructed at each node we have:

  • the decision boundary L
  • a sphere \mathbb B s.t. all points in N(v) are in this sphere
    • let center(v) be the center of \mathbb B and r(v) be the radius
    • so N(v)\subseteqq \mathbb B(center(v), r(v))

MT-DFS(q) - the search algorithm

  • search in a Metric Tree is a guided Depth-First Search
  • the decision boundary L at each node n is used to decide whether to go left or right
    • if q is in the left , then go to left(v), otherwise - to right(v)
    • (or can project the query point to u, and then check if q< A or not)
  • all the time we maintain x: nearest neighbor found so far
  • let d=\left \| x-q \right \| - distance from best x so far to the query
  • we can use d to prune nodes: we can check if node is good or no point can better than x
    • no point is better than x if \left \| center(r)-q \right \|-r(v)\geqslant d. That means if the hyper-sphere intersects with current candidates sphere

This algorithm is very efficient when dimensionality is \leqslant 30

  • but slows down when it increases

Observation:

  • MT often finds the NN very quickly and then spends 95% of the time verifying that this is the true NN
  • can reduce this time with Spill-Tree
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末懂缕,一起剝皮案震驚了整個濱河市帽撑,隨后出現(xiàn)的幾起案子蝗茁,更是在濱河造成了極大的恐慌递览,老刑警劉巖美尸,帶你破解...
    沈念sama閱讀 222,807評論 6 518
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件扇调,死亡現(xiàn)場離奇詭異蹦掐,居然都是意外死亡丐怯,警方通過查閱死者的電腦和手機蟀伸,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,284評論 3 399
  • 文/潘曉璐 我一進(jìn)店門蚀同,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人啊掏,你說我怎么就攤上這事蠢络。” “怎么了迟蜜?”我有些...
    開封第一講書人閱讀 169,589評論 0 363
  • 文/不壞的土叔 我叫張陵刹孔,是天一觀的道長。 經(jīng)常有香客問我娜睛,道長髓霞,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 60,188評論 1 300
  • 正文 為了忘掉前任畦戒,我火速辦了婚禮方库,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘障斋。我一直安慰自己纵潦,他們只是感情好,可當(dāng)我...
    茶點故事閱讀 69,185評論 6 398
  • 文/花漫 我一把揭開白布垃环。 她就那樣靜靜地躺著邀层,像睡著了一般。 火紅的嫁衣襯著肌膚如雪遂庄。 梳的紋絲不亂的頭發(fā)上寥院,一...
    開封第一講書人閱讀 52,785評論 1 314
  • 那天,我揣著相機與錄音涛目,去河邊找鬼只磷。 笑死,一個胖子當(dāng)著我的面吹牛泌绣,可吹牛的內(nèi)容都是我干的钮追。 我是一名探鬼主播,決...
    沈念sama閱讀 41,220評論 3 423
  • 文/蒼蘭香墨 我猛地睜開眼阿迈,長吁一口氣:“原來是場噩夢啊……” “哼元媚!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 40,167評論 0 277
  • 序言:老撾萬榮一對情侶失蹤刊棕,失蹤者是張志新(化名)和其女友劉穎炭晒,沒想到半個月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體甥角,經(jīng)...
    沈念sama閱讀 46,698評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡网严,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,767評論 3 343
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了嗤无。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片震束。...
    茶點故事閱讀 40,912評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖当犯,靈堂內(nèi)的尸體忽然破棺而出垢村,到底是詐尸還是另有隱情,我是刑警寧澤嚎卫,帶...
    沈念sama閱讀 36,572評論 5 351
  • 正文 年R本政府宣布嘉栓,位于F島的核電站,受9級特大地震影響拓诸,放射性物質(zhì)發(fā)生泄漏侵佃。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 42,254評論 3 336
  • 文/蒙蒙 一奠支、第九天 我趴在偏房一處隱蔽的房頂上張望趣钱。 院中可真熱鬧,春花似錦胚宦、人聲如沸首有。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,746評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽井联。三九已至,卻和暖如春您旁,著一層夾襖步出監(jiān)牢的瞬間烙常,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,859評論 1 274
  • 我被黑心中介騙來泰國打工鹤盒, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留蚕脏,地道東北人。 一個月前我還...
    沈念sama閱讀 49,359評論 3 379
  • 正文 我出身青樓侦锯,卻偏偏與公主長得像驼鞭,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子尺碰,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 45,922評論 2 361

推薦閱讀更多精彩內(nèi)容

  • rljs by sennchi Timeline of History Part One The Cognitiv...
    sennchi閱讀 7,350評論 0 10
  • 隨著年齡的增長挣棕,父母健康的下降译隘,村里一個個老年人的離去,甚至現(xiàn)在還能想到小時候他們叫喊著:孩子洛心,別調(diào)皮固耘,小心過往的...
    攬葉閱讀 180評論 0 0
  • 上小學(xué)的時候,學(xué)校離家遠(yuǎn)词身,父母不放心厅目,讓我每天和同村的同學(xué)小抲一起上學(xué)。 那時候跟現(xiàn)在上午和下午課不一樣法严,而是早中...
    我在乎的僅此而已閱讀 987評論 0 0
  • 5215-謝志剛 轉(zhuǎn)變思維损敷,提高游戲力 英國著名劇作家王爾德曾說:“人生太重要,不要沉重以待渐夸。”工作也是一樣渔欢,不能...
    剽悍的jerry閱讀 219評論 1 1
  • 對于都市崇尚單身的富家子弟坐漏,男人三十是如花的年紀(jì)歇僧,婚姻是阻擋自由的圍墻,然而在農(nóng)村垫挨,二十來歲沒有結(jié)婚就會被家里催婚...
    文案大咖秀閱讀 2,016評論 0 0