臺灣博碩士論文加值系統

本論文結合Bloom Filter與類神經網路概念提出整數型 Bloom Filter，其目的在於識別碼之多屬性成員查詢。識別碼成員查詢之應用甚廣且通常可以使用傳統二位元Bloom Filter 作為查詢方法。近年來，由於網際網路上之資料量遽增，多屬性成員查詢開始受到學者重視，因據此可提高網路運算效能。傳統的Bloom Filter如果實作為多層或分段的模式可以達成多屬性查詢的效果；然而，卻會導致運算效能降低與誤判率提高等缺點。本論文所提以整數資料型態為基礎之Bloom Filter，配合類神經網路之重複訓練方式，嘗試克服上述缺點，訓練演算法具有動態新增及刪除樣本之特色。實驗使用之兩組資料分別為模擬之(1)台灣小客車車牌號碼與(2)電子郵件帳號。實驗結果顯示在適當條件下，對於誤判率具有優異的表現，運算呈現穩定且高效能。未來研究將進行非字串形資料包含影像與聲紋之應用。

This thesis proposes Integer Bloom Filter for multi-attribute membership querying of identifiers, which combines the concepts of Bloom Filters and artificial neutral networks. Membership querying of identifiers has been applied on a wide range of categories, and normally this type of problem could be dealt with by employing traditional binary-based Bloom Filters. Recently, as the data amount on the internet has been dramatically increased, multi-attribute membership querying has started to be emphasized by researchers because computational effectiveness can be enhanced with such a technique. Traditional Bloom Filters with multi- layer or segment implementations are capable of solving this problem; however, such implementations could result in lower computational effectiveness and higher error rates. In this thesis, a novel type of Bloom Filter with integer data is developed in an attempt to resolve the problems stated above, where the training process of artificial neural networks is incorporated. The proposed training algorithm is associated with both insertion and deletion operations, which is critical in achieving the goals of this thesis. Two experimental data were simulated including (1) car license plates in Taiwan and (2) email accounts. The results show, with appropriate parameter settings, the error rates could be controlled under a satisfactory level with intact computational effectiveness. Future research will be focused on non-string data patterns including images and voice signals.

摘要 i
ABSTRACT ii
誌謝 iii
目錄 iv
表目錄 v
圖目錄 vi
第一章 緒論 1
第一節 研究背景動機 1
第二節 研究目的與方法 2
第三節 研究範圍與限制 5
第二章 文獻探討 6
第一節 Bloom Filter發展與類型 6
第二節 多屬性查詢的發展 8
第三章 整數資料型態Bloom Filter演算法 12
第一節 整數單元的屬性與結構 14
第二節 樣本前處理程序 19
第三節 屬性標記決策模型 25
第四節 網路訓練學習程序 29
第四章 模式實驗與研究探討 36
第一節 樣本類型適應性實驗 36
第二節 多屬性效能評估實驗 40
第五章 結論與未來研究方向 48
第一節 研究結果與討論 48
第二節 未來研究方向與建議 49
參考文獻 50
附錄 A 樣本類型適應性實驗：樣本A(車牌號碼) 54
附錄 B 樣本類型適應性實驗：樣本B(電子郵件信箱) 59
附錄 C 多屬性效能評估實驗：樣本A(車牌號碼) 64
附錄 D 多屬性效能評估實驗：樣本B(電子郵件信箱) 67
附錄 E 樣本刪除可靠度實驗：樣本A(車牌號碼) 70
附錄 F 樣本刪除可靠度實驗：樣本B(電子郵件信箱) 74

Albus, J. S. (1975). A New Approach to Manipulator Control: The Cerebellar Model Articulation Controller (CMAC). Transaction ASME Journal of Dynamic Systems, Measurement and Control 97, 220-227.
Albus, J. S. (1975). Data Storage in the Cerebellar Model Articulation Controller. Transaction ASME Journal of Dynamic Systems, Measurement and Control 97, 228-233.
Albus, J. S., (1979). A Model of the Brain for Robot Control. BYTE, 4(7), 54-95.
Bin, X. & Yu, H. (2010), Using Parallel Bloom Filters for Multiattribute Representation on Network Services. IEEE Transactions on parallel and distributed systems, 21(1), 20-32.
Bloom, B. (1970). Space/time tradeoffs in hash coding with allowable errors. Commun. ACM, 13(7), 422–426.
Cheng, H. Y. & Ma, H. (2011), Fast Approach to Simultaneously Determine Existence & Classification for String Patterns in a Payload. E -Business & E –Government 2011 International Conference, 1-4.
Cheng, H. Y. & Ma, H. (2013). Membership Classification using Integer Bloom Filter, The 12th IEEE/ACIS International Conference on Computer & Information Science (ICIS 2013), 385-390.
Cohen, S. & Matias, Y. (2003). Spectral bloom filters. (2003). In Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data 241-252.
Czerwinski , S., Zhao, B., Hodes, T., Joseph, A. & Katz, R. (1999). An architecture for a secure service discovery service. Proc. Fifth Annu. Int. Conf. Mobile Computing and Networks (MobiCOM’99), 24–35.
Dan, L., Cao, P., Almeida, J., & Broder, A. (2000). Summary cache: A scalable wide-area web cache sharing protocol. IEEE/ACM Transaction. Networking, 8(3), 281-293.
Dharmapurikar, S., Krishnamurthy P., Sproull, T. & Lockwood, J. W. (2003). Deep packet inspection using parallel Bloom filters. In 11th IEEE Symposium on High Performance Interconnects, 44-51.
Fan, L., Cao, P., Almeida, J. & Broder, A. Z. (2000). Summary cache: A scalable wide-area web cache sharing protocol. IEEE/ACM Transactions on Networking (TON) archive, 8(3), 281-293.
Ficara, D., Pietro, A. D., Giordano, S., Procissi, G. & Vitucci, F. (2010). Enhancing counting Bloom filters through Huffman-coded multilayer structures. IEEE/ACM Trans. on Networking, 18(6), 1977-1987.
Guo, D., Wu, J., Chen, H., & Luo, X. (2010). The Dynamic Bloom Filters, IEEE Transaction on Knowledge & Data Engineering. 22(1), 120-133.
Hao, F., Kodialam, M., & Lakshman, T. V. (2007). Building high accuracy bloom filters using partitioned hashing. In Proc. of the 2007 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, 277-288.
Hao, F., Kodialam, M., Lakshman, T.V. & Song, H. (2012). Fast Dynamic Multiple-Set Membership Testing Using Combinatorial Bloom Filters. IEEE/ACM Transactions on Networking, 20(1), 295-304.
Iiguni, Y. (1996). Hierarchical Image Coding via Cerebellar Model Arithmetic Computers. IEEE Transaction on Image Processing, 5(10), 1393-1401.
Ker, J. S., Kuo, Y. H., Wen, R. C., & Liu, B. D. (1997). Hardware Implementation of CMAC Neural Network with Reduce Storage Requirement. IEEE Transaction on Neural Networks, 8(6), 1545-1556.
Kirsch, A. & Mitzenmacher, M. (2006). Distance-sensitive bloom filters. In Proc. the 8th Workshop on Algorithm Engineering & Experiments (ALENEX06).
Kubiatowicz, J., Bindel, D., Chen, Y., Czerwinski, S., Eaton, P., Geels, D., Gummadi, R., Rhea, S., Weatherspoon, H., Weimer, W., Wells, C. & Zhao B. (2000). OceanStore: An architecture for global-scale persistent storage. Proc. ASPLOS, 190–201.
Kumar, A., Xu, J., Wang, J., Spatschek, O. & Li, L. (2004). Space-code bloom filter for efficient per-flow traffic measurement. In Proc. 23rd IEEE INFOCOM, 1762-1773.
Kumar, S. & Crowley, P. (2005). Segmented hash: an efficient hash table implementation for high performance networking subsystems. ANCS '05 Proceedings of the 2005 ACM symposium on Architecture for networking & communications systems, 91–103.
Laufer, R. P., Velloso, P. B. & Duarte, O. C. M. B. (2005). Generalized bloom filters. Technical Report Research Report GTA-05-43.
Ma, H. & Cheng, H. Y. (2010). A High-Efficiency Querying Algorithm for Multi-Attribute Text String Identifiers. International Conference on Engineering & Business Management, 1826-1829.
Ma, H. & Cheng, H. Y. (2010). Multi-attribute Bloom Filter Query Scheme. The 2010 International Conference in Management Sciences & Decision Making, 471-478.
Ma, H. & Cheng, H. Y. (2013). A two-layer scheme for membership & classification querying. Kybernetes, 42(1), 82-93.
Ma, H. & Tsai, T. F. (2009). Fast Determining Existence of Text Strings in a Large Dataset Using CMAC Mapping. International Journal of Information & Management Sciences, 20(4), 589-601.
Ma, H. (2008), Fast Blocking of Undesirable Web Pages on Client PC by Discriminating URL using Neural Networks. Expert Systems With Applications, 34(2), 1533-1540.
Mark C. J. & Steffan, J. G. (2011). Understanding bloom filter intersection for lazy address-set disambiguation. SPAA '11 Proceedings of the 23rd ACM symposium on Parallelism in algorithms & architectures, 345-354.
Mitzenmacher, M. (2002). Compressed Bloom Filters. IEEE/ACM TRANSACTIONS ON NETWORKING, 10(5).
Moraru, I. & Andersen, D. G. (2012). Exact Pattern Matching with Feed-Forward Bloom Filters. Journal of Experimental Algorithmics, 17(3).
Priya A. G. A. & Lim H. (2010). Hierarchical packet classification using a Bloom filter and rule-priority tries. Computer Communications, 33(10), 1215-1226.
Rousskov, A. & Wessels, D. (1998). Cache digests. Computer Netw. ISDN System, 30(22–23), 2155–2168.
Sarang, D., Michael, A. & John, L. (2004). Design and Implementation of a String Matching System for Network Intrusion Detection using FPGA-based Bloom Filters. Washington University Dept. of Computer Science and Engineering : Technical Report WUCS-2004-012.
Snoeren, A. C., Partridge, C., Sanchez, L. A., Jones, C. E., Tchakounito, F., Kent, S. T. & Strayer,W. T. (2001). Hash-based IP traceback. Proc. SIGCOMM, 3–14.
Yu, H. & Mahapatra, R. H. (2011). A Power and Throughput-Efficient packet Classifier with n Bloom Filters. IEEE Trans. On Computers, 60(8), 1182-1193.