The approximate nearest neighbor(ANN) search over high dimensional data has become an unavoidable service for online applications. Fast and high-quality results of unknown queries are the largest challenge that most algorithms faced with. Locality Sensitive Hashing(LSH) is a well-known ANN search algorithm while suffers from inefficient index structure, poor accuracy in distributed scheme. The traditional index structures have most significant bits(MSB) problem, which is their indexing strategies have an implicit assumption that the bits from one direction in the hash value have higher priority. In this thesis, we propose a new content-based index called Random Draw Forest(RDF), which not only uses an adaptive tree structure by applying the dynamic length of compound hash functions to meet the different cardinality of data, but also applies the shuffling permutations to solve the MSB problem in the traditional LSH-based index. To raise the accuracy in the distributed scheme, we design a variable steps lookup strategy to search the multiple step sub-indexes which are most likely to hold the mistakenly partitioned similar objects. By analyzing the index, we show that RDF has a higher probability to retrieve the similar objects compare to the original index structure. In the experiment, we first learn the performance of different hash functions, then we show the effect of parameters in RDF and the performance of RDF compared with other LSH-based methods to meet the ANN search. / Thesis / Master of Science (MSc)

No description available.

近十年內網際網路迅速興起並蓬勃發展，對我們生活的各個層面造成劇烈的影響，並掀起電子商務的熱潮。目前最引人注目的焦點是B2B，利用網路的特性來降低成本，縮短供應鏈，加速產品生命週期。產業已注意到協同商務中之供應網絡管理，並探討企業問之商務管理所需之方法與資訊技術，以尋求新的企業營運模式。在相關發展中，WWW上之商務資料交換，更是目前發展之重點，我們的終極目標是一個跨產業且進入門檻小的全球性交易平台，ebXML因其可能帶來跨產業協同商務之平台架構逐成為產業矚目之對象。 另一個網路所帶來的問題是資訊爆炸。當人們才剛開始享受網路世界的多采多姿，馬上卻又得面臨資訊氾濫的夢魘。如何利用智慧型的方法，提昇搜尋的效率與提高資訊的效果，是我們所關心的。搜尋引擎的演算法發展已到極致，但在搜尋策略的輔助上仍有發展的空間。 本研究回顧電子商務的緣由與發展，提出web service輿ebMXL應用的跨產業網路交易平台，並設計以5W1H的方式儲存專家經驗與策略，透過查詢擴充的機制，達成搜尋策略與結果的改善，並在這個電子商務架構平台的註冊機制與儲存庫(registry/repository)上運作，讓代理人理解企業之需求與期望，進而完成企業間交易夥伴的尋找，以達成動態供應鏈之實現。 關鍵字：XML，ebXML，web service，UDDI，註冊機制與儲存庫，資訊檢索，搜尋策略，5W1H，後設資料 / Starting from the concept of B2B e-commerce in general, the aim of this thesis is to propose and test a method for supporting trading partners' matching, in particulars those who follows ebXML. In the first place, this research presents a study of the areas where XML may have significant contributions. To avoid falling into pitfalls that works in e-commerce have experienced, we ought to understand the evolution of e-commerce so that the target supports can be derived from learned lessons. With these caveats in mind, the next step is to clarify the characteristics and requirements of a generic B2B framework. Base on the aforementioned survey, the framework of ebXML can be clarified, which is considered as the State-of-Art e-business technology. To reach this, this research is to address not only the problem domain and original concepts but also technology requirements. The ebXML architecture as well as relevant initiatives, viz. SOAP, WSDL and UDDI are then examined to search for potential ebXML-based solutions. In a comparison to RosettaNet, ebXML can provide more efficient and effective searches and matches of trading partners on electronic market place. Among others, the author emphasizes the research into a hybrid of ebXML and so-called web based service technologies. To realize this concept, a searching and matching mechanism with aids of expert's strategies based on 5WIH knowledge schema is carried out in this research. Last but not least, 5W1H knowledge schema is applied, another word serves as metadata, to organize and store expert's heuristic and intelligence in so-called strategy base, so that this work can use the expert's strategy for expanding the keywords to refine user queries in the run-time and thus provide a more efficient and effective matching results. Keyword: XML, ebXML, web service, UDDI, registry/repository, information retrieval, searching strategy, 5W1H, metadata