Đồ Án Nghiên cứu bộ lọc Bloom Filter và ứng dụng_HVKế toán (TM+chương trình)

1. Tên đề tài :
Nghiên cứu bộ lọc Bloom Filter và ứng dụng.
2. Các số liệu ban đầu: Dựa trên nhiệm vụ được giao và các tài liệu tham khảo .
3. Nội dung bản thuyết minh
Mở đầu
Chương 1: Lý thuyết về bộ lọc Bloom.
Chương 2: Khớp tiền tố dài nhất sử dụng bộ lọc Bloom.
Chương 3: Phân loại gói tin sử dụng bộ lọc Bloom.
Chương 4: Khai phá phần tử phổ biến trong luồng dữ liệu sử dụng ESBF theo mô hình Damped.
Chương 5: Cài đặt chương trình.
Kết luận.
Tài liệu tham khảo.
4. Số lượng, nội dung bản vẽ A0 và các sản phẩm cụ thể (nếu có):
.
.




LỜI NÓI ĐẦU
Internet là một kho dữ liệu khổng lồ, mọi người có thể tìm được bất kỳ thông tin nào về khoa học, sức khoẻ, đời sống, tin tức, .và cả việc thông tin liên lạc qua thư điện tử, chat, Với những ưu điểm lớn của World Wide Web, số lượng người sử dụng, máy chủ, các mạng con kết nối vào Internet ngày tăng với tốc độ chóng mặt. Điều đó cũng đồng nghĩa với việc lưu lượng lưu thông trên mạng ngày càng tăng lên và dường như quá tải. Để giải quyết vấn đề đó, những nghiên cứu cả về phần cứng và phần mềm không ngừng được nêu ra nhằm tăng tốc độ truyền tải trên mạng, tăng tốc độ xử lý của các thiết bị mạng Việc sử dụng mạng Internet ngày càng phổ biến thì cũng càng đặt nhiều vấn đề mới hơn như vấn đề an ninh mạng, vấn đề bảo mật thông tin trên mạng
Bộ lọc Bloom do Burton Bloom đưa ra năm 1970 đã cho thấy được hiệu quả của nó trong việc góp phần giải quyết một số vấn đề về tốc độ và thời gian xử lý với cơ sở dữ liệu trên mạng. Chính vì thế bộ lọc Bloom ngày càng được sử dụng rộng rãi trong rất nhiều ứng dụng mạng: định tuyến IP, phân loại gói tin, chia sẽ bộ nhớ cache trong mạng per to per, IP traceback, khai phá phần tử phổ biến trong luồng dữ liệu, phát hiện sự xâm nhập trong hệ thống an ninh mạng . Bộ lọc Bloom cũng rất hiệu quả trong việc xử lý với cơ sở dữ liệu nói chung nên thực sự rất hữu ích trong rất nhiều ứng dụng thực tế khác.
Trong đồ án tốt nghiệp của mình, em chọn đề tài là “Nghiên cứu bộ lọc Bloom Filter và ứng dụng” gồm 3 nội dung chính:
Lý thuyết về bộ lọc Bloom
Tìm hiểu một số ứng dụng của bộ lọc Bloom: khớp tiền tố dài nhất, phân loại gói tin và khai phá phần tử phổ biến sử dụng ESBF theo mô hình Damped.
Cài đặt chương trình minh họa.
Em xin chân thành cảm ơn thầy giáo Thiếu tá – TS. Nguyễn Mạnh Hùng cùng các thầy cô trong Bộ môn Công nghệ phần mềm, và Khoa CNTT đã tận tình hướng dẫn, chỉ bảo và tạo mọi điều kiện giúp đỡ em hoàn thành tốt đồ án này.




MỤC LỤC
LỜI NÓI ĐẦU
08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200330031003600390037003200320033000000
Chương 1: LÝ THUYẾT VỀ BỘ LỌC BLOOM

1.1 Giới thiệu
1.2 Cấu trúc bộ lọc Bloom cơ bản
1.3 Cơ chế hoạt động của bộ lọc Bloom
1.4 Ước lượng sai số
1.5 Bộ lọc Bloom đếm (counting Bloom Filters)
1.6 Lựa chọn hàm băm
1.6.1 Hàm băm sử dụng phương pháp chia.
1.6.2 Hàm băm sử dụng phương pháp nhân

Chương 2:
KHỚP TIỀN TỐ DÀI NHẤT SỬ DỤNG BỘ LỌC BLOOM

2.1 Định tuyến IP của router
2.1.1 Thiết bị định tuyến router
2.1.2 Bảng định tuyến
2.2 Thuật toán khớp tiền tố cổ điển
2.3 Khớp tiền tố dài nhất sử dụng bộ lọc Bloom
2.3.1 Giới thiệu 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200330031003600390037003200340030000000
2.3.2 Cấu trúc cơ bản
2.3.3 Hoạt động
Chương 3:
PHÂN LOẠI GÓI TIN SỬ DỤNG BỘ LỌC BLOOM

3.1 Khái niệm về phân loại gói tin
3.2 Chức năng của bộ lọc Bloom trong phân loại gói tin
3.3 Thuật toán tích chéo cổ điển
3.4 Thuật toán tích chéo đa tập con
3.5 Thuật toán tìm kiếm không gian bộ mức xếp chồng
3.5.1 Phương pháp gom nhóm không chồng nhau (Overlap-free)
3.5.2 Bản đồ bit NLT và bản đồ bit PL/NL
3.5.3 Sơ đồ dòng của thuật toán
3.6 Thuật toán Tích chéo và trộn NLT (NLT Merging and Crossproduct – NLTMC)
Chương 4:
KHAI PHÁ PHẦN TỬ PHỔ BIẾN TRONG LUỒNG DỮ LIỆU SỬ DỤNG ESBF THEO MÔ HÌNH DAMPED
08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200330031003600390037003200350035000000
4.1 Định nghĩa luồng dữ liệu và phần tử phổ biến
4.2 Mô hình Damped
4.3 Bộ đếm phân rã theo thời gian
4.4 ESBF 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200330031003600390037003200350039000000
4.5 Thuật toán MIBFD

Chương 5: CÀI ĐẶT CHƯƠNG TRÌNH

5.1 Giao diện chính
5.2 Chương trình cài đặt bộ lọc Bloom cơ bản
5.3 Chương trình cài đặt thuật toán khớp tiền tố dài nhất
5.4 Chương trình cài đặt bài toán phân loại gói tin 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200330031003600390037003200360035000000
5.4.1 Thuật toán tích chéo cổ điển
5.4.2 Thuật toán tích chéo đa tập con
5.4.3 Thuật toán tìm kiếm không gian NLT
5.4.4 Thuật toán tích chéo và trộn NLT
5.4.5 So sánh các thời gian xử lý của các thuật toán
5.5 Chương trình cài đặt bài toán khai phá phần tử phổ biến

08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200330031003600390037003200370031000000
KẾT LUẬN

TÀI LIỆU THAM KHẢO