Danh sách đen trong lĩnh vực cho vay trực tuyến: Nghiên cứu từ luận văn thạc sĩ khoa học máy tính

Khám phá luận văn thạc sĩ khoa học máy tính về danh sách đen trong cho vay trực tuyến, cung cấp thông tin hữu ích và cảnh báo cần thiết.

• Tác giả: Nguyễn Xuân Vĩnh Hưng
• Người hướng dẫn: PGS. Thoại Nam
• Trường học: Đại học Bách Khoa
• Chuyên ngành: Khoa Học Máy Tính
• Đề tài: Chia Sẻ Danh Sách Đen Trong Lĩnh Vực Cho Vay Trực Tuyến
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2024
• Địa điểm: TP. Hồ Chí Minh

Mục lục chi tiết

• LỜI CÁM ƠN
• TÓM TẮT LUẬN VĂN
• ABSTRACT OF DISSERTATION
• LỜI CAM ĐOAN
• 1. CHƯƠNG 1: GIỚI THIỆU ĐỀ TÀI
• 1.1. Giới thiệu đề tài
• 1.2. Mô tả bài toán
• 1.3. Mục tiêu và nhiệm vụ của luận văn
• 1.4. Giới hạn đề tài
• 1.5. Đóng góp của luận văn
• 1.6. Tóm tắt nội dung
• 2. CHƯƠNG 2: CƠ SỞ KIẾN THỨC
• 2.1. Cấu trúc dữ liệu Bloom Filter
• 2.2. Dương Tính Giả (False Positive) và Số Hàm Băm Tối Ưu K (Optimal K)
• 2.3. Counting Bloom Filter
• 2.4. Dương Tính Giả (False Positive), Số Hàm Băm Tối Ưu (Optimal K), Kích Thước Của Bộ Đếm (Counter Size) và Độ Đếm Tràn (Counter Overflow) của Counting Bloom Filter
• 2.5. Mergeable Counting Bloom Filter
• 2.6. Thêm một phần tử
• 2.7. Truy vấn một phần tử
• 3. CHƯƠNG 3: CÔNG TRÌNH NGHIÊN CỨU LIÊN QUAN
• 3.1. Lamport Clock và Vector Clock
• 4. CHƯƠNG 4: PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ
• 4.1. Xây dựng dữ liệu danh sách đen
• 4.2. Kiến trúc hệ thống
• 4.3. Hiện thực hệ thống
• 4.4. Ngôn ngữ lập trình và nền tảng (framework)
• 4.5. Kết nối hệ thống
• 4.6. Bài toán chuẩn hóa dữ liệu đầu vào
• 4.7. Bảo mật hệ thống
• 4.8. Khả năng chịu lỗi
• 4.9. Bloom Filter Client không gửi danh sách đen đúng thời gian
• 4.10. Bloom Filter Server bị sập
• 4.11. Bloom Filter Client bị sập
• 4.12. Trường hợp dữ liệu danh sách đen lớn
• 4.13. Đánh giá giải pháp
• 4.14. Tập dữ liệu và phương pháp đánh giá
• 4.15. Kết quả và đánh giá
• Tài liệu tham khảo

Tóm tắt

I. Giới thiệu đề tài

Trong bối cảnh hiện nay, ngành tài chính công nghệ (Fintech) đang phát triển mạnh mẽ, đặc biệt là trong lĩnh vực cho vay trực tuyến. Nhu cầu vay vốn của người dân, đặc biệt là nhóm khách hàng yếu thế, ngày càng tăng cao, đặc biệt sau đại dịch COVID-19. Theo thống kê, khoảng 70% người trưởng thành tại Việt Nam có tài khoản ngân hàng, nhưng gần một nửa trong số đó không thể tiếp cận tín dụng. Điều này dẫn đến việc nhiều người phải tìm đến các hình thức vay không chính thống, gây ra nhiều rủi ro tài chính. Danh sách đen trở thành một công cụ quan trọng trong việc thẩm định tín dụng, giúp các công ty tài chính xác định khách hàng có khả năng trả nợ hay không. Tuy nhiên, việc chia sẻ thông tin giữa các công ty tài chính hiện nay vẫn còn nhiều bất cập, thiếu một cơ chế chung để đảm bảo an toàn thông tin khách hàng. Luận văn này nhằm nghiên cứu và phát triển một hệ thống chia sẻ danh sách đen giữa các công ty tài chính, đảm bảo tính bảo mật và hiệu quả.

II. Mô tả bài toán

Bài toán chia sẻ danh sách đen trong lĩnh vực cho vay trực tuyến được đặt ra nhằm xây dựng một cơ chế chia sẻ dữ liệu giữa các công ty tài chính mà không làm lộ thông tin khách hàng. Hệ thống này sẽ sử dụng cấu trúc dữ liệu Bloom Filter để mã hóa thông tin khách hàng. Mỗi công ty sẽ gửi dữ liệu danh sách đen đã được mã hóa cùng với nhãn thời gian đến các đối tác. Điều này không chỉ giúp tăng cường bảo mật mà còn giảm thiểu thời gian và chi phí trong quá trình thẩm định tín dụng. Một trong những thách thức lớn là đảm bảo rằng hệ thống có thể xử lý khối lượng lớn dữ liệu mà vẫn duy trì hiệu suất cao và độ tin cậy. Việc kiểm tra xem một số điện thoại có nằm trong danh sách đen hay không cần phải được thực hiện một cách nhanh chóng và chính xác.

III. Cơ sở kiến thức

Luận văn này dựa trên các lý thuyết về cấu trúc dữ liệu Bloom Filter và các biến thể của nó như Counting Bloom Filter và Mergeable Counting Bloom Filter. Bloom Filter cho phép kiểm tra sự tồn tại của một phần tử trong tập hợp mà không cần lưu trữ toàn bộ dữ liệu, đồng thời có thể xảy ra trường hợp dương tính giả. Các hàm băm được sử dụng trong Bloom Filter cần được tối ưu hóa để giảm thiểu tỷ lệ dương tính giả. Ngoài ra, lý thuyết về Lamport Clock và Vector Clock sẽ được áp dụng để ghi nhận sự kiện trong hệ thống phân tán, giúp đảm bảo tính đồng bộ và chính xác trong quá trình chia sẻ dữ liệu. Những kiến thức này sẽ tạo nền tảng cho việc xây dựng hệ thống chia sẻ danh sách đen hiệu quả.

IV. Phương pháp giải quyết vấn đề

Để giải quyết bài toán chia sẻ danh sách đen, luận văn sẽ áp dụng các phương pháp nghiên cứu và phát triển hệ thống dựa trên cấu trúc dữ liệu Bloom Filter. Các bước thực hiện bao gồm: 1) Nghiên cứu và phát triển mô hình Bloom Filter và các biến thể của nó. 2) Tính toán các thông số đầu vào cho Bloom Filter như số lượng hàm băm tối ưu và tỷ lệ dương tính giả. 3) Thiết kế kiến trúc hệ thống chia sẻ dữ liệu giữa các công ty tài chính. 4) Hiện thực hóa hệ thống và đánh giá tính đúng đắn của nó. Hệ thống sẽ được kiểm tra khả năng chịu lỗi và bảo mật thông tin, đảm bảo rằng dữ liệu danh sách đen không bị lộ ra ngoài.

V. Kết luận

Luận văn này không chỉ đóng góp vào việc xây dựng một hệ thống chia sẻ danh sách đen trong lĩnh vực cho vay trực tuyến mà còn nâng cao nhận thức về tầm quan trọng của việc bảo mật thông tin khách hàng trong ngành tài chính. Hệ thống được phát triển sẽ giúp các công ty tài chính tối ưu hóa quy trình thẩm định tín dụng, giảm thiểu rủi ro và nâng cao hiệu quả hoạt động. Tuy nhiên, vẫn còn nhiều vấn đề cần giải quyết như cải thiện khả năng mã hóa và bảo mật thông tin. Các nghiên cứu trong tương lai có thể mở rộng sang các lĩnh vực khác trong tài chính công nghệ, nhằm xây dựng một hệ sinh thái tài chính an toàn và hiệu quả hơn.

Nội dung chính

Tổng quan nghiên cứu

Trong bối cảnh phát triển mạnh mẽ của các công ty tài chính công nghệ (Fintech) tại Việt Nam, đặc biệt trong lĩnh vực cho vay trực tuyến, việc quản lý và chia sẻ dữ liệu danh sách đen khách hàng trở thành một thách thức lớn. Theo số liệu của Ngân hàng Nhà nước năm 2020, khoảng 70% người trưởng thành tại Việt Nam có tài khoản ngân hàng, nhưng gần một nửa trong số đó không tiếp cận được tín dụng chính thống. Nhu cầu vay vốn tăng cao, đặc biệt sau đại dịch COVID-19, đã thúc đẩy sự phát triển của các công ty tài chính cho vay trực tuyến nhằm hỗ trợ nhóm khách hàng yếu thế như công nhân, tiểu thương. Tuy nhiên, việc thiếu cơ chế chia sẻ dữ liệu danh sách đen hiệu quả giữa các công ty tài chính dẫn đến rủi ro tín dụng và tăng nợ xấu.

Luận văn tập trung nghiên cứu và phát triển hệ thống chia sẻ danh sách đen trong lĩnh vực cho vay trực tuyến, sử dụng cấu trúc dữ liệu Bloom Filter và các biến thể cải tiến như Mergeable Counting Bloom Filter để đảm bảo bảo mật thông tin khách hàng và tối ưu hiệu suất truy vấn. Mục tiêu chính là xây dựng kiến trúc hệ thống cho phép các công ty tài chính đối tác chia sẻ dữ liệu danh sách đen một cách an toàn, nhanh chóng, đồng thời giảm thiểu chi phí tích hợp và bảo vệ dữ liệu khỏi các cuộc tấn công mạng.

Phạm vi nghiên cứu tập trung vào dữ liệu danh sách đen số điện thoại khách hàng tại Việt Nam, với thời gian thực hiện từ tháng 9 đến tháng 12 năm 2023. Nghiên cứu có ý nghĩa quan trọng trong việc nâng cao hiệu quả quản lý rủi ro tín dụng, giảm thiểu nợ xấu và thúc đẩy sự phát triển bền vững của ngành tài chính tiêu dùng trực tuyến.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Luận văn dựa trên hai nền tảng lý thuyết chính:

1. Cấu trúc dữ liệu Bloom Filter và các biến thể: Bloom Filter là cấu trúc dữ liệu nén dùng để kiểm tra sự tồn tại của phần tử trong tập hợp với khả năng dương tính giả nhưng không có âm tính giả. Các biến thể như Counting Bloom Filter (CBF) và Mergeable Counting Bloom Filter (mergeCBF) được sử dụng để hỗ trợ thêm, xóa phần tử và hợp nhất dữ liệu từ nhiều nguồn, đồng thời giảm thiểu tỷ lệ dương tính giả và tràn bộ đếm. Các hàm băm như MurmurHash và FNV được áp dụng để đảm bảo phân phối đều và hiệu quả trong Bloom Filter.

2. Thuật toán đồng bộ thời gian trong hệ thống phân tán: Lamport Clock và Vector Clock được sử dụng để đánh dấu thời gian logic cho các sự kiện trong hệ thống phân tán, giúp xác định thứ tự và đồng bộ dữ liệu giữa các công ty tài chính trong mạng lưới chia sẻ. Vector Clock đặc biệt hữu ích trong việc xử lý các sự kiện đồng thời và phát hiện xung đột dữ liệu.

Các khái niệm chính bao gồm: dương tính giả (false positive), số hàm băm tối ưu (optimal k), bộ đếm trong Counting Bloom Filter, tràn bộ đếm (counter overflow), thuật toán virtual-Cuckoo trong mergeCBF, và cơ chế đồng bộ/ bất đồng bộ trong chia sẻ dữ liệu.

Phương pháp nghiên cứu

Nguồn dữ liệu chính là các tập dữ liệu danh sách đen số điện thoại khách hàng từ các công ty tài chính cho vay trực tuyến tại Việt Nam, với ước tính mỗi công ty có khoảng vài triệu phần tử trong danh sách đen. Cỡ mẫu nghiên cứu bao gồm dữ liệu từ khoảng 5 công ty đối tác, tổng số phần tử danh sách đen ước tính lên đến hàng chục triệu.

Phương pháp phân tích bao gồm:

• Tính toán các thông số đầu vào cho Bloom Filter như chiều dài mảng bit, số hàm băm tối ưu dựa trên công thức xác suất dương tính giả.
• Thiết kế và hiện thực kiến trúc hệ thống chia sẻ dữ liệu dựa trên Mergeable Counting Bloom Filter, sử dụng Vector Clock để quản lý thời gian logic.
• Xây dựng mô hình đồng bộ và bất đồng bộ trong trao đổi dữ liệu giữa các công ty qua Message Broker với hàng đợi (queue) để giảm phụ thuộc và tăng khả năng chịu lỗi.
• Đánh giá hiệu suất hệ thống qua các chỉ số như dung lượng dữ liệu, thời gian truy vấn danh sách đen, tỷ lệ dương tính giả và khả năng chịu lỗi khi một hoặc nhiều công ty không gửi dữ liệu kịp thời.

Timeline nghiên cứu kéo dài từ tháng 9 đến tháng 12 năm 2023, bao gồm giai đoạn khảo sát, thiết kế, hiện thực và đánh giá hệ thống.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

1. Hiệu quả nén và truy vấn của Mergeable Counting Bloom Filter: Với tổng số phần tử danh sách đen khoảng 5 triệu cho mỗi công ty và 5 công ty tham gia, hệ thống sử dụng mảng bit có chiều dài 71.887.937 và số hàm băm tối ưu là 10, đạt tỷ lệ dương tính giả chỉ khoảng 0,1%. Thời gian truy vấn danh sách đen trung bình dưới 10ms, giảm đáng kể so với phương pháp truyền thống.

2. Khả năng hợp nhất dữ liệu và xóa phần tử: Mergeable Counting Bloom Filter cho phép hợp nhất dữ liệu từ nhiều công ty mà không làm tăng tỷ lệ tràn bộ đếm quá mức, với xác suất tràn bộ đếm dưới 0,01% khi sử dụng 16 mảng bit và bộ đếm 4 bit. Hệ thống cũng hỗ trợ xóa phần tử hiệu quả, giúp cập nhật danh sách đen linh hoạt theo thời gian.

3. Đồng bộ dữ liệu với Vector Clock: Việc áp dụng Vector Clock giúp hệ thống xác định chính xác thứ tự cập nhật danh sách đen giữa các công ty, giảm thiểu xung đột dữ liệu và đảm bảo tính nhất quán. Trong chế độ bất đồng bộ, hệ thống vẫn duy trì hoạt động ổn định khi một công ty không gửi dữ liệu kịp thời, nhờ cơ chế epsilon cho phép sử dụng dữ liệu gần nhất.

4. Tính bảo mật và giảm thiểu rủi ro lộ thông tin: Dữ liệu danh sách đen được mã hóa dưới dạng Bloom Filter, không thể giải mã trực tiếp số điện thoại khách hàng, giúp bảo vệ thông tin cá nhân ngay cả khi dữ liệu bị rò rỉ hoặc tấn công mạng.

Thảo luận kết quả

Kết quả cho thấy việc ứng dụng Mergeable Counting Bloom Filter kết hợp với Vector Clock là giải pháp khả thi và hiệu quả cho bài toán chia sẻ danh sách đen trong lĩnh vực cho vay trực tuyến. So với các phương pháp chia sẻ dữ liệu truyền thống như FTP, REST API hay chia sẻ file CSV qua email, hệ thống mới giảm thiểu đáng kể chi phí tích hợp và thời gian xử lý.

Việc sử dụng cấu trúc dữ liệu Bloom Filter giúp giảm dung lượng lưu trữ và tăng tốc độ truy vấn, đồng thời vẫn đảm bảo tỷ lệ dương tính giả ở mức chấp nhận được. Các thuật toán đồng bộ thời gian trong hệ thống phân tán giúp duy trì tính nhất quán dữ liệu trong môi trường có nhiều thành viên và khả năng chịu lỗi cao.

So sánh với các nghiên cứu trước đây về Bloom Filter trong hệ thống phân tán, luận văn đã mở rộng ứng dụng vào lĩnh vực tài chính tiêu dùng, đồng thời giải quyết các vấn đề thực tiễn như bảo mật dữ liệu và cập nhật danh sách đen linh hoạt. Các biểu đồ thể hiện tỷ lệ dương tính giả theo số hàm băm và kích thước mảng bit, cũng như thời gian truy vấn danh sách đen, minh họa rõ hiệu quả của giải pháp.

Đề xuất và khuyến nghị

1. Triển khai hệ thống chia sẻ danh sách đen dựa trên Mergeable Counting Bloom Filter: Các công ty tài chính nên áp dụng kiến trúc hệ thống đề xuất để nâng cao hiệu quả quản lý rủi ro tín dụng, giảm thiểu nợ xấu. Thời gian triển khai dự kiến trong vòng 6 tháng, với sự phối hợp chặt chẽ giữa các bên.

2. Áp dụng Vector Clock để đồng bộ dữ liệu trong môi trường phân tán: Đề xuất sử dụng Vector Clock làm cơ chế đánh dấu thời gian logic để đảm bảo tính nhất quán và xử lý xung đột dữ liệu hiệu quả. Chủ thể thực hiện là bộ phận công nghệ thông tin của các công ty tài chính.

3. Tăng cường bảo mật dữ liệu danh sách đen: Khuyến nghị mã hóa dữ liệu danh sách đen dưới dạng Bloom Filter để bảo vệ thông tin khách hàng, đồng thời áp dụng các biện pháp bảo mật mạng và kiểm soát truy cập nghiêm ngặt. Thời gian thực hiện liên tục, cần có chính sách giám sát và đánh giá định kỳ.

4. Xây dựng cơ chế đồng bộ và bất đồng bộ linh hoạt: Hệ thống cần thiết kế cơ chế xử lý dữ liệu trong trường hợp một hoặc nhiều công ty không gửi dữ liệu kịp thời, đảm bảo hoạt động liên tục và ổn định. Chủ thể thực hiện là đội ngũ phát triển hệ thống và quản lý dự án.

5. Đào tạo và nâng cao nhận thức cho nhân viên vận hành: Tổ chức các khóa đào tạo về công nghệ Bloom Filter, hệ thống phân tán và bảo mật dữ liệu cho nhân viên kỹ thuật và vận hành để đảm bảo vận hành hệ thống hiệu quả và an toàn.

Đối tượng nên tham khảo luận văn

1. Các công ty tài chính công nghệ (Fintech): Đặc biệt là các đơn vị hoạt động trong lĩnh vực cho vay trực tuyến, có nhu cầu quản lý và chia sẻ dữ liệu danh sách đen để giảm thiểu rủi ro tín dụng và nâng cao hiệu quả thẩm định khách hàng.

2. Nhà phát triển phần mềm và kỹ sư hệ thống phân tán: Những người quan tâm đến ứng dụng cấu trúc dữ liệu Bloom Filter và các thuật toán đồng bộ thời gian trong xây dựng hệ thống phân tán, đặc biệt trong lĩnh vực tài chính.

3. Các nhà nghiên cứu và sinh viên ngành Khoa học Máy tính, Công nghệ Thông tin: Luận văn cung cấp kiến thức chuyên sâu về Bloom Filter, Counting Bloom Filter, Mergeable Counting Bloom Filter, cũng như các thuật toán Lamport Clock và Vector Clock, phù hợp cho nghiên cứu và học tập.

4. Cơ quan quản lý và hoạch định chính sách tài chính: Có thể tham khảo để hiểu rõ hơn về các giải pháp công nghệ hỗ trợ quản lý rủi ro tín dụng trong lĩnh vực tài chính tiêu dùng, từ đó xây dựng các chính sách phù hợp thúc đẩy phát triển ngành.

Câu hỏi thường gặp

1. Bloom Filter là gì và tại sao lại được sử dụng trong chia sẻ danh sách đen?
   Bloom Filter là cấu trúc dữ liệu nén giúp kiểm tra nhanh sự tồn tại của phần tử trong tập hợp với tỷ lệ dương tính giả thấp. Nó được sử dụng để mã hóa danh sách đen nhằm giảm dung lượng lưu trữ và bảo vệ thông tin khách hàng khỏi bị lộ khi chia sẻ giữa các công ty.

2. Mergeable Counting Bloom Filter khác gì so với Bloom Filter truyền thống?
   Mergeable Counting Bloom Filter hỗ trợ thêm, xóa phần tử và hợp nhất dữ liệu từ nhiều nguồn, trong khi Bloom Filter truyền thống chỉ hỗ trợ thêm phần tử và không thể xóa hoặc hợp nhất. Điều này giúp hệ thống cập nhật danh sách đen linh hoạt và hiệu quả hơn.

3. Vector Clock giúp gì trong hệ thống chia sẻ danh sách đen?
   Vector Clock cung cấp cơ chế đánh dấu thời gian logic cho các sự kiện trong hệ thống phân tán, giúp xác định thứ tự và đồng bộ dữ liệu giữa các công ty, giảm thiểu xung đột và đảm bảo tính nhất quán của danh sách đen được chia sẻ.

4. Tỷ lệ dương tính giả trong Bloom Filter có ảnh hưởng thế nào đến hệ thống?
   Tỷ lệ dương tính giả là xác suất hệ thống trả về kết quả sai khi kiểm tra phần tử không tồn tại trong danh sách đen. Tỷ lệ này cần được giữ ở mức thấp (khoảng 0,1%) để đảm bảo độ tin cậy của hệ thống trong việc thẩm định khách hàng.

5. Hệ thống có thể hoạt động thế nào khi một công ty không gửi dữ liệu kịp thời?
   Hệ thống sử dụng cơ chế bất đồng bộ với biến epsilon cho phép sử dụng dữ liệu cập nhật gần nhất của công ty không gửi dữ liệu kịp thời, đảm bảo hoạt động liên tục và ổn định mà không làm gián đoạn quá trình chia sẻ danh sách đen.

Kết luận

• Luận văn đã phát triển thành công hệ thống chia sẻ danh sách đen trong lĩnh vực cho vay trực tuyến dựa trên cấu trúc dữ liệu Mergeable Counting Bloom Filter và thuật toán Vector Clock.
• Hệ thống đảm bảo bảo mật thông tin khách hàng, giảm thiểu chi phí tích hợp và tăng hiệu suất truy vấn danh sách đen với tỷ lệ dương tính giả thấp khoảng 0,1%.
• Kiến trúc hệ thống hỗ trợ cả chế độ đồng bộ và bất đồng bộ, tăng khả năng chịu lỗi và tính ổn định trong môi trường phân tán.
• Các giải pháp đề xuất có thể ứng dụng rộng rãi trong các công ty tài chính công nghệ, góp phần nâng cao hiệu quả quản lý rủi ro tín dụng và giảm nợ xấu.
• Bước tiếp theo là triển khai thực tế hệ thống tại các công ty tài chính, đồng thời nghiên cứu mở rộng ứng dụng cho các loại dữ liệu khác và nâng cao bảo mật.

Hành động khuyến nghị: Các tổ chức tài chính và nhà phát triển công nghệ nên phối hợp triển khai và đánh giá hệ thống để tận dụng tối đa lợi ích từ nghiên cứu này, góp phần phát triển ngành tài chính tiêu dùng trực tuyến bền vững.

Trích đoạn nội dung tài liệu

Chương 1 GIỚI THIỆU ĐỀ TÀI: giới thiệu về hiện trạng của ngành tài chính, cụ thể là cho vay tiêu dùng, cho vay trực tuyến và nhu cầu thực tế trong việc chia sẻ dữ liệu danh sách đen mô tả bài toán chia sẻ danh sách đen trong lĩnh vực cho vay trực tuyến. − Chương 2 CƠ SỞ KIẾN THỨC: là các cơ sở lý thuyết mà học viên sử dụng trong luận văn này, bao gồm các lý thuyết cơ bản về Bloom Filter, các thuộc tính của Bloom Filter và biến thể cải tiến khác của Bloom Filter là Counting Bloom Filter hay Mergeable Counting Bloom Filter, các hàm băm được sử dụng trong Bloom Filter, lý thuyết về Lamport Clock và Vector Clock. 7 − Chương 3 CÁC CÔNG TRÌNH NGHIÊN CỨU LIÊN QUAN: nói về các công trình nghiên cứu liên quan tới Bloom Filter. Từ đó các cải tiến của cấu trúc dữ liệu mới lần lượt ra đời, và đó cũng là cơ sở quan trọng cho ứng dụng của tác giả trong luận văn.

− Chương 4 PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ: Chương 4 nói cụ thể về các mô hình đề xuất của học viên cho bài toán chia sẻ danh sách đen. − Chương 5 KẾT LUẬN: Tổng kết các đóng góp của luận văn, các vấn đề còn tồn tại của bài toán chia sẻ danh sách đen đồng thời nói về khả năng phát triển trong tương lai. 8 Chương 2 CƠ SỞ KIẾN THỨC 2. Cấu trúc dữ liệu Bloom Filter Cấu Trúc Dữ Liệu Bloom Filter là một cấu trúc dữ liệu đã nén để trả lời nhanh cho câu hỏi, phần tử này có nằm trong tập hợp không? Kết quả là có thể là “có” hoặc có thể hoặc không.

Tức là BloomFilter có thể dương tính giả (false positive) nhưng không thể có trường hợp âm tính giả (false negative). Bloom Filter bao gồm một mảng bit B có chiều dài m. Khi khởi tạo, giá trị của mỗi bit trong mảng là 0. Khi mã hoá thông tin thành viên e, e sẽ được sẽ được mã hoá bởi k hàm băm độc lập nhau:.

Vùng giá trị trả về của hàm băm sẽ là chính là chỉ mục được dùng trong mảng bit B. , sẽ được bật thành 1. Và những bit đó sẽ được gọi là bit thành viên (membership bit).1: Mã hoá các phần tử a, b,c vào Bloom Filter với số hàm băm bằng 3 2. Dương Tính Giả (False Positive) và Số Hàm Băm Tối Ưu K (Optimal K) Cho m là chiều dài của mảng bit.

n là tổng số phần tử trong tập hợp và k là tổng số hàm băm. Vậy Xác suất của 1 bit vẫn bằng 0 sau khi đã thêm vào n phần tử là: (2.1) Vậy xác suất bit đó là 1 là: (2.2) 10 Vậy một đối tượng bất kỳ, và chưa được mã hóa trong Bloom Filter , thì xác suất mà tất cả bit ở chỉ mục trả của hàm băm H của đối tượng trả về được bật là: (2.3) Trong đó là hằng số tự nhiên Euler. Rõ ràng, tỷ lệ dương tính giả sẽ giảm khi độ dài của mảng m tăng, và giảm khi số lượng phần tử n được thêm vào Bloom Filter tăng. Để tìm ra số hàm băm tối ưu, ta có thể lấy đạo hàm công thức 2.3 theo k, cho vế bên trái bằng 0 và giải phương trình.5) Khi số hàm k* được sử dụng, ta thay vào hàm tính dương tính giả công thức2.3 sẽ là fB*: (2.6) Trong đó: - là số lượng hàm băm.

- là số lượng hàm băm tối ưu. - là chiều dài của mảng bit - là tổng số phần tử đã được mã hóa trong Bloom Filter. - là hằng số tự nhiên Euler. - là tỷ lệ dương tính giả.

11 - là tỷ lệ dương tính giả khi số hàm băm tối ưu được sử dụng. Counting Bloom Filter Việc loại bỏ một phần tử trong Bloom Filter là không thể. Bởi vì mỗi bit bằng 1 sẽ được sử dụng chung bởi các phần tử khác nhau. Ta không thể đơn giản gán bit thành 0 được vì nó dẫn tới việc lược bỏ một phần tử khác.

Counting Bloom Filter dùng một mảng của bộ đếm (counter) C với chiều dài l. Mỗi bộ đếm trong mảng đều được khởi tạo là 0. Cũng giống như Bloom Filter truyền thống, chúng ta mã hoá một phần tử e bằng k hàm băm. Mỗi hàm băm sẽ trả về giá trị từ 0 tới l - 1 là chỉ mục của trong mảng bộ đếm C.

Chúng ta sẽ tăng giá trị của bộ đếm tại vị trí của số đếm lên 1.2: Mã hoá các phần tử a, b,c vào Counting Bloom Filter với số hàm băm bằng 3 Khi muốn xoá một phần tử e khỏi tập hợp, chúng ta cũng băm phần tử đó và có tập giá trị các chỉ mục. ta sẽ giảm giá trị tại các vị trí số đếm xuống 1. Khi kiểm tra một phần tử bất kỳ e’ có nằm trong Counting Bloom Filter không, ta cũng băm đối tượng thành bằng k hàm băm. Sau đó 12 kiểm tra giá trị tại các vị trí do hàm băm trả về trong mảng C có khác 0 hay không? Nếu tất cả đều khác 0, thì có thể kết luận đối tượng đó nằm trong tập hợp.

Dương Tính Giả (False Positive), Số Hàm Băm Tối Ưu (Optimal K), Kích Thước Của Bộ Đếm (Counter Size) và Độ Đếm Tràn (Counter Overflow) của Counting Bloom Filter Cho là chiều dài của mảng bộ đếm, là tổng số phần tử đã được mã hả trong Counting Bloom Filter tập hợp và là số hàm băm. Cùng phương pháp phân tích như phần 2.2, ta có xác xuất 1 phần tử trong mảng số là 0 sau khi đã thêm n phần tử là: (2.7) Vậy xác suất phần tử đó đó khác 0 là: 1- (2.8) Vậy với một đối tượng bất kỳ, và không nằm trong Counting Bloom Filter, thì xác suất mà tất cả các số ở chỉ mục được hàm băm trả về lớn hơn 0 là: (2.9) Trong đó, là hằng số Euler số tự nhiên. Từ hàm số trên, ta sẽ tính số hàm băm tối ưu k* như phương pháp ở chương 2.2 , ta lấy đạo hàm của 3.11) Trong đó là logarit cơ số tự nhiên Euler. Khi số hàm k* được sử dụng, ta thay vào hàm tính dương tính giả sẽ là fC*: (2.12) Trong đó: - là số lượng hàm băm.

- là số lượng hàm băm tối ưu. - là chiều dài của mảng bộ đếm - là tổng số phần tử đã được mã hóa trong Bloom Filter. - là hằng số tự nhiên Euler. - là tỷ lệ dương tính giả.

- là tỷ lệ dương tính giả khi số hàm băm tối ưu được sử dụng. Như vậy, Counting Bloom Filter có cùng tỷ lệ dương tính giả với Bloom Filter truyền thống. Bộ Đếm trong Counting Bloom Filter là được chỉ định trước và có giới hạn. Tất cả đều có cùng độ dài cố định.

Giả sử, mỗi bộ đếm có t bit. Giá trị của bộ đếm là từ khoảng tới. Nếu giá trị bộ đếm đang là và ta mã hoá một phần tử mới, bộ đếm sẽ tăng lên 1, tràn bộ đếm (counter overflow) sẽ xảy ra. Nếu giá trị càng nhỏ, thì việc tràn bộ đếm sẽ xảy ra thường xuyên hơn.

Tuy nhiên nếu giá trị lớn sẽ tốn bộ nhớ. Cho là một biến ngẫu nhiên là giá trị của bộ đếm sau n lần thêm phần tử vào BloomFilter, sẽ tuân theo phân phối xác suất Binomial: .13) 14 Ở đây, được xác định bởi công thức: (2.14) Xác suất để bộ đếm lớn hơn hoặc bằng giá trị y là: (2.15) Trong đó: là giai thừa giảm dần : (2. Ta có thể giới hạn bằng: (2.17) Xác suất bất kỳ bộ đếm c nào mà lớn hơn hoặc bằng y sẽ là: (2.18) Và khi số hàm băm tối ưu k* (công thức 2.11) được áp dụng thì ta có: 15 (2.19) Ý nghĩa các ký hiệu trong phần 2.4 : - là xác suất để điều kiện đó xảy ra. - là chiều dài của mảng bộ đếm.

- là giai thừa của biến x. - là hằng số tự nhiên Euler. - là logarit cơ số tự nhiên e. - là tổng số phần tử có trong Bloom Filter.

- là phép tổng. Trong thực tế, nếu tràn bộ đệm xảy ra, ta vẫn có thể giữ giá trị của bộ đếm. Nhưng qua quá nhiều phân tử, có thể dẫn tới tình huống tỷ lệ dương tính giả cao. Mergeable Counting Bloom Filter Nếu chúng ta sử dụng Bloom Filter, thì việt kết hợp hai hay nhiều vector khá đơn giản, chỉ cần OR bit tương đương trong vector.

Tuy nhiên, Counting Bloom Filter (CBF) không hỗ trợ việc kết hợp hai vectors dữ liệu do CBF không lưu thông tin về hai phần hay nhiều phần tử trùng nhau. Nếu chúng ta có 2 CBF là CBF1và CBF2. Khi hợp CBF1 và CBF2, ta sẽ cộng từng phần tử i của mảng bộ đếm CBF1 và CBF2. Nếu có quá nhiều phần tử trùng trong cả hai CBF trên thì có thể dẫn bộ đếm tràn.

Để giải quyết vấn đề này, Wengjin Liu và nhóm tác giả đã đưa ra giải pháp Mergeable Counting Bloom Filter (mergeCBF), dựa trên sử dụng thuật toán xếp lịch Cuckoo. Ý tưởng của mergeCBF là tách các mảng bộ đếm (counter array) thành một nhóm các mảng bit và sắp xếp các mảng theo một thứ tự cố định để ghi nhận những phần tử đã được thêm vào. 16 Cấu trúc của mergeCBF: - hàm băm, số lượng hàm băm tối ưu theo công thức 2. - Một nhóm gồm mảng bit , trong đó là giá trị lớn nhất của bộ đếm.

- Một mảng là orBarr, là kết quả or của nhóm các mảng bit ở trên. Dùng để tăng hiệu quả của việc truy vấn. MergeCBF không chỉ hỗ trợ delete, thêm phần tử mới, xóa phần tử mà còn hỗ trợ việc hợp giữa hai hay nhiều mergeCBF khác nhau nếu có chung hàm băm và chiều dài mảng bit. Thêm một phần tử Để thêm một phần tử vào mergeCBF, ta không chỉ băm phần tử đó bằng k hàm băm mà còn phải sắp xếp các và chọn mảng bit nào để chứa các giá trị trả về của hàm băm.

Để đảm bảo việc xếp các bit vào mảng bit một cách ít đụng độ và hiệu quả, nhóm tác giả dùng giới thiệu một thuật toán lấy ý tưởng từ thuật toán Cuckoo Hash tên là thuật toán sắp xếp virtual-Cuckoo. Ý tưởng của thuật toán Cuckoo hash là tìm ra vị trí của phần tử trong mảng, nếu vị trí ô trong mảng đã có một phần tử chiếm dụng, chúng ta sẽ đẩy phần tử đã có ra khỏi ô đó, chèn phần tử mới vào ô hiện tại, tìm một vị trí mới cho phần tử cũ. Quá trình này tiếp diễn cho tới khi không còn đụng độ nửa. Cuckoo Hash đảm bảo việc sử dụng bộ nhớ một cách hiệu quả vì nó khuyến khích nhiều ô trong mảng được sử dụng hơn.