國立臺灣大學電信工程學研究所林宗男2006-07-262018-07-052006-07-262018-07-052005-07-31http://ntur.lib.ntu.edu.tw//handle/246246/20316本研究計畫對於如何衡量搜尋網路效能的諸多重要議題做深入思考。現有的評量 標準可能會對於搜尋的效能做出偏頗的結論，或是對於演算法的設計提供錯誤的方 向。因此，我們定義一個統一的準則，稱之為「搜尋效能」(Search Efficiency, SE)， 以綜合廣泛的方式來處理搜尋效能的問題。SE 的目標在於更充分的描述搜尋網路效能 的特性，並對未來的設計提供方向。我們首先在一個理想的網路拓墣，strictly binary tree，藉由分析SE 在兩種典型的搜尋方法，包括breadth first search 以及random walk，來驗證SE 的正確性。另外，基於各種不同的網路狀況，我們進一步展現SE 在 真實世界網路拓墣，power-law random graph，描述效能特性的能力。最後，基於SE 的分析，我們設計一個演算法，dynamic search。Dynamic search 展現出的優異性能， 對於SE 提供未來搜尋網路設計方向的能力做出絕佳示範。This project deliberates on various critical aspects in evaluating searching networks. Existing metrics either draw biased conclusions regarding search performance or provide wrong guidelines for algorithm design. We, therefore, define a unified criterion, Search Efficiency (SE), to objectively address search performance in a comprehensive manner. The goal of SE is to better characterize performance of searching networks than existing metrics do as well as to guide the design of future ones. We first validate the correctness of SE in performance evaluation in an ideal graph, strictly binary tree, by analyzing SE for two typical search methods, breadth first search and random walk. We further show its strength in performance characterization in the real-world topology, power-law random graph, under various network conditions. We finally design an algorithm, dynamic search, based on SE analysis. Its proved outstanding performance demonstrates the strength of SE to provide guidance for the future design of searching networks.application/pdf1073965 bytesapplication/pdfzh-TW國立臺灣大學電信工程學研究所組合數學圖形理論決定型網路計算法CombinatoricsGraph theoryDeterministic network calculusreporthttp://ntur.lib.ntu.edu.tw/bitstream/246246/20316/1/932213E002057.pdf