[請益] 2D封包分類使用fractional cascading
http://netgroup.polito.it/teaching/trc/papers/1998-RangeMatching.pdf
請問一下，有人有讀過這篇PAPER嗎?
在5.1部分有提到可以運用cascading技巧，使得搜尋時間減為O(ls+log n)
整整讀了兩個禮拜也研究不出來，
圖五的部份paper上提到運用複製技巧，就是將level i+1 複製其point到level i
所以再search level i+1只需花費O(1)
但是照paper那種方法 實在是推不出O(ls+log n)
因為還要再加上ls個O(1) (ls為number of possible prefix lengths)
所以現在我想法是不要用paper的search方法
也不需要運用到複製，觀察出在search每個level時 之間有什麼關聯性
也就是說search第i+1層時候，或許在search第i層就已經有得到了一些資訊
以致於search時間才會減為(ls+log n)
但是....我真的卡住了，實在是推出不來O(ls+log n)
因為對fractional cascading也不是很清楚，查了一下，有看到一張瀑布的圖片
所以是在search的時候Y軸範圍會越縮越小嗎?可是套用到圖5就不會解釋了
有前輩能指點一下嗎= = 真的快被這篇搞到瘋了(最近都有想休學的念頭出現= =)
嚴重懷疑自己是不是不適合讀研究所
--
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.118.2.133