Xử lý đồ thị lớn trên môi trường phân tán sử dụng Mapreduce

- NGUYỄN THỊ HUYỀN XỬ LÝ ĐỒ THỊ LỚN TRÊN MÔI TRƢỜNG PHÂN TÁN SỬ DỤNG MAPREDUCE LUẬN VĂN THẠC SĨ KỸ THUẬT CÔNG NGHỆ THÔNG TIN NGƢỜI HƢỚNG DẪN KHOA HỌC: TS PHẠM ĐĂNG HẢI HÀ NỘI - 2016 Xử lý đồ thị lớn trên môi trƣờng phân tán sử dụng MapReduce LỜI CẢM ƠN Để hoàn thành luận văn tốt nghiệp “Xử lý đồ thị lớn trên môi trường phân tán sử dụng MapReduce”, lời đầu tiên em xin gửi lời cảm ơn sâu sắc nhất tới TS Phạm Đăng Hải, ngƣời đã hƣớng dẫn và chỉ bảo em tận tình trong suốt thời gian làm khóa luận.
- Em xin chân thành cảm ơn PGS.TS Huỳnh Quyết Thắng, PGS.TS Nguyễn Đức Nghĩa, TS Cao Tuấn Dũng đã cung cấp cho em các kiến thức nền tảng về xử lý dữ liệu trên môi trƣờng phân tán, lý thuyết đồ thị để em thực hiện đề tài này.
- Học viên Nguyễn Thị Huyền Xử lý đồ thị lớn trên môi trƣờng phân tán sử dụng MapReduce LỜI CAM ĐOAN Với mục đích học tập, nghiên cứu để nâng cao trình độ chuyên môn nên tôi đã làm luận văn này một cách nghiêm túc và hoàn toàn trung thực.
- Hà Nội, tháng 04 năm 2016 Học viên Nguyễn Thị Huyền Xử lý đồ thị lớn trên môi trƣờng phân tán sử dụng MapReduce MỤC LỤC DANH MỤC CÁC KÝ HIỆU, CÁC TỪ VIẾT TẮT.
- 2 DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ.
- 7 CHƢƠNG 1: TỔNG QUAN VỀ XỬ LÝ ĐỒ THỊ LỚN.
- Giới thiệu về đồ thị và đồ thị lớn.
- Định nghĩa đồ thị và đồ thị lớn (Big Graph.
- Đồ thị có trọng số và đƣờng đi.
- Nghiên cứu về các ứng dụng của bài toán xử lý đồ thị lớn.
- Những thách thức trong xử lý đồ thị lớn.
- Phân tích đồ thị lớn.
- Nén đồ thị.
- Trực quan hóa đồ thị.
- Một số kỹ thuật và công cụ xử lý đồ thị lớn.
- 23 CHƢƠNG 3: PHÂN TÍCH ĐỒ THỊ LỚN VỚI MAPREDUCE.
- Tổng quan về vấn đề phân tích đồ thị.
- Khai phá đồ thị (Graph Mining.
- 28 Xử lý đồ thị lớn trên môi trƣờng phân tán sử dụng MapReduce 3.2.1.
- Các nghiên cứu liên quan đến khai phá đồ thị.
- So khớp đồ thị (Graph Matching.
- Truy vấn đồ thị (Graph Querying.
- 37 CHƢƠNG 4: ỨNG DỤNG MAPREDUCE GIẢI QUYẾT BÀI TOÁN TÌM ĐƢỜNG ĐI NGẮN NHẤT TRÊN ĐỒ THỊ PHÂN TÁN.
- Đồ thị phân tán.
- Đề xuất thuật toán tìm đƣờng đi ngắn nhất trên đồ thị phân tán.
- Nó nằm trong chuẩn defacto cho kết nối giữa các nút chạy một chƣơng trình song song trên bộ nhớ chia sẻ đƣợc phân phối SSH Secure Shell Giao thức kết nối mạng có tính bảo mật cao HDFS Hadoop Distributed File System Hệ thống tệp tin phân tán của Hadoop MR Map Reduce Mô hình lập trình Map Reduce AI Artificial Intelligence Trí tuệ nhân tạo MDL Minimum Description Length Nguyên tắc chiều dài mô tả tối thiểu DBMS Database Management System Hệ quản trị cơ sở dữ liệu SQL Structured Query Language Ngôn ngữ truy vấn mang tính cấu trúc.
- Xử lý đồ thị lớn trên môi trƣờng phân tán sử dụng MapReduce 2 DANH MỤC CÁC BẢNG Bảng 4.1: Dữ liệu trên các đồ thị con và đồ thị liên kết.
- 45 Bảng 4.2: Minh họa input và output node của đồ thị phân tán.
- 52 Xử lý đồ thị lớn trên môi trƣờng phân tán sử dụng MapReduce 3 DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ Hình 1.1: Phân loại đồ thị.
- 10 Hình 1.2: Đồ thị có trọng số.
- 11 Hình 1.3: Nén đồ thị.
- 21 Hình 2.4: Tiến trình xử lý các cặp key-value MapReduce.
- 22 Hình 4.1: Minh họa đồ thị phân tán.
- 44 Hình 4.2: Ví dụ đồ thị phân tán có trọng số.
- 46 Hình 4.3: Đồ thị phụ thuộc Gd đƣợc tạo ra từ kết quả của các Pi.
- 52 Hình 4.4: Mô hình MapReduce trong trả lời câu truy vấn trên đồ thị phân tán.
- 53 Hình 4.5: Thời gian thực thi câu truy vấn với số lƣợng đồ thị con khác nhau.
- 56 Xử lý đồ thị lớn trên môi trƣờng phân tán sử dụng MapReduce 4 MỞ ĐẦU 1.
- Lý do chọn đề tài Cơ sở khoa học: Khái niệm về đồ thị lớn xuất hiện ở khắp mọi nơi từ các mạng xã hội và các mạng điện thoại di động đến các mạng sinh học và World Wide Web.
- Khai thác đồ thị lớn dẫn đến nhiều ứng dụng thú vị bao gồm cả an ninh mạng, phát hiện gian lận, tìm kiếm Web, hệ gợi ý, và nhiều hơn nữa.
- Việc xử lý và phân tích dữ liệu đồ thị lớn dựa trên những nghiên cứu trong nhiều lĩnh vực bao gồm khoa học máy tính, thống kê, toán học, kỹ thuật dữ liệu, nhận dạng mẫu, trực quan hóa, trí tuệ nhân tạo, học máy, và tính toán hiệu năng cao.
- Mô hình MapReduce: là một mô hình lập trình giúp các ứng dụng có thể xử lý nhanh một lƣợng lớn dữ liệu trên các máy phân tán hoạt động song song, độc lập với nhau từ đó giúp rút ngắn thời gian xử lý toàn bộ dữ liệu.
- MapReduce làm đơn giản hoá các giải thuật tính toán phân tán.
- Với MapReduce, ta chỉ cần cung cấp hai hàm Map và Reduce cùng với một số thành phần xử lý dữ liệu đầu vào.
- Do vậy, các nhà phát triển ứng dụng phân tán có thể tập trung nhiều hơn cho phần logic của ứng dụng, bỏ qua các chi tiết phức tạp của việc phân tán xử lý.
- Sự ra đời của MapReduce đã mở ra cho các doanh nghiệp cơ hội xử lý các nguồn dữ liệu đồ sộ với chi phí thấp và thời gian nhanh hơn.
- Với việc áp dung MapReduce, Amazon có thể xử lý đƣợc các file log phát sinh trong quá trình bán hàng trên mạng, phục vụ cho việc dự đoán xu hƣớng mua hàng của khách hàng, các sản phẩm đang đƣợc mua nhiều v.v… Facebook có thể xử lý đƣợc khối lƣợng Xử lý đồ thị lớn trên môi trƣờng phân tán sử dụng MapReduce 5 hơn 10 tỷ hình ảnh mà họ đang lƣu trữ để rút trích các thông tin về kích thƣớc hình ảnh, phát hiện các hình ảnh xấu.
- Cơ sở thực tiễn: Trên thế giới hiện nay dữ liệu đồ thị đang đƣợc tạo ra với tốc độ chƣa từng có.
- Ví dụ, Facebook tải 60 terabyte dữ liệu mới mỗi ngày đƣợc coi là một đồ thị lớn với hơn 1,5 tỷ đỉnh tƣơng ứng với số lƣợng ngƣời dùng tính đến năm 2015.
- Yahoo đã có một đồ thị 1,4 tỷ nút Web tại 2002.
- Microsoft đã có 1,15 tỷ cặp truy vấn URL vào năm 2009 và Google xử lý 20 petabyte mỗi ngày.
- Với hơn 30 triệu ngƣời dùng Internet và hơn 15 triệu ngƣời dùng Mobile Internet vào năm 2012, điều này làm cho Việt Nam đang đứng trƣớc một cơ hội vô cùng lớn về khai thác dữ liệu đồ thị lớn.
- Vì vậy việc nghiên cứu để xử lý dữ liệu đồ thị lớn sao cho hiệu quả là hết sức thiết thực.
- Vì những lý do trên mà tôi chọn đề tài “Xử lý đồ thị lớn trên môi trường phân tán sử dụng MapReduce” làm đề tài luận văn của mình.
- Mục đích nghiên cứu  Nghiên cứu đƣợc một số vấn đề trong xử lý đồ thị lớn (Big Graph.
- Vấn đề liên quan đến truy vấn dữ liệu trên đồ thị lớn.
- Xử lý đồ thị lớn trên môi trƣờng phân tán sử dụng MapReduce 6 - Vấn đề về công nghệ, công cụ xử lý Big Graph.
- Nghiên cứu về Hadoop/MapReduce - Tổng quan về Hadoop/MapReduce - Cách thức giải quyết bài toán với MapReduce  Giải quyết bài toán tìm đƣờng đi ngắn nhất trên đồ thị phân tán sử dụng Mapreduce.
- Đối tƣợng nghiên cứu  Nghiên cứu tìm hiểu lý thuyết về đồ thị, đồ thị lớn.
- Nghiên cứu tổng quan về Hadoop/MapReduce trong xử lý dữ liệu phân tán  Nghiên cứu vấn đề về công nghệ, công cụ xử lý Big Graph.
- Áp dụng giải quyết bài toán tìm đƣờng đi ngắn nhất trên đồ thị phân tán.
- Phạm vi nghiên cứu  Tổng quan về lý thuyết đồ thị, đồ thị lớn  Mô hình lập trình MapReduce  Phân tích đồ thị lớn với MapReduce  Ứng dụng MapReduce giải quyết bài toán tìm đƣờng đi ngắn nhất trên đồ thị phân tán.
- Phƣơng pháp nghiên cứu  Nghiên cứu tài liệu khoa học về xử lý đồ thị lớn.
- Xử lý đồ thị lớn trên môi trƣờng phân tán sử dụng MapReduce 7  Nghiên cứu lý thuyết về đồ thị, đồ thị lớn.
- Nghiên cứu về các ứng dụng của việc khai thác và xử lý đồ thị lớn.
- Nghiên cứu về xử lý đồ thị phân tán với MapReduce ứng dụng giải quyết bài toán tìm đƣờng đi ngắn nhất trên đồ thị phân tán.
- Những luận điểm cơ bản và đóng góp mới của đề tài Đề tài đã trình bày đƣợc một cách tiếp cận mới để giải quyết bài toán tìm đƣờng đi ngắn nhất từ một đỉnh đến một đỉnh khác trên đồ thị phân tán.
- Đề tài đã đề xuất một thuật toán dựa trên kỹ thuật ƣớc lƣợng từng phần và khai thác nền tảng hỗ trợ xử lý dữ liệu song song phân tán MapReduce.
- Xử lý đồ thị lớn trên môi trƣờng phân tán sử dụng MapReduce 8 CHƢƠNG 1: TỔNG QUAN VỀ XỬ LÝ ĐỒ THỊ LỚN 1.1.
- Giới thiệu về đồ thị và đồ thị lớn Đồ thị dễ dàng tìm thấy ở khắp mọi nơi trong cuộc sống hàng ngày của chúng ta nhƣ.
- Cấu trúc của Protein (Protein structure) Một dữ liệu lớn ngày nay trên các hệ thống mạng đều có thể biểu diễn dƣới dạng các đồ thị & mối quan hệ của chúng theo.
- Liên kết, kết nối vật lý - Kết nối giữa các mạng trong lớp mạng - Mối quan hệ trong mạng xã hội - Siêu lien kết giữa các trang web - Các tƣơng tác phức tạp giữa các thực thể… Những đồ thị trên chứa đựng những thong tin giá trị cho việc ứng dụng vào hệ thống mạng nhƣ - Những phát hiện từ cộng đồng, những điểm chung - Phân lớp - Những hệ thống đƣợc đƣa ra theo ƣu tiên nào đó - Tìm kiếm trên mạng - P2P (điểm tới điểm) tìm kiếm & lấy dữ liệu - Tin cậy & uy tín… Nhìn chung, đồ thị có tính bao quát hơn từng đối tƣợng, tuần tự, cây, mạng nói chung.
- Đồ thị giải quyết đƣợc nhiều vấn đề có độ tính toán phức tạp cao.
- Xử lý đồ thị lớn trên môi trƣờng phân tán sử dụng MapReduce 9 1.1.1.
- Định nghĩa đồ thị và đồ thị lớn (Big Graph) Định nghĩa 1.1.
- Đồ thị là một cấu trúc rời rạc gồm các đỉnh và các cạnh nối các đỉnh đó đƣợc mô tả hình thức: G = (V, E), trong đó V gọi là tập các đỉnh (vertices) và E gọi là tập các cạnh (edges).
- Có nhiều loại đồ thị khác nhau biểu diễn cho những đối tƣợng khác nhau và trong các ứng dụng khác nhau.
- Ngƣời ta phân loại đồ thị dựa trên đặc điểm của các cạnh nối [1].
- Cho đồ thị G = (V, E).
- Đồ thị G đƣợc gọi là đơn đồ thị nếu giữa hai đỉnh u, v của V có nhiều nhất là 1 cạnh trong E nối từ u tới v.
- Đồ thị G đƣợc gọi là đa đồ thị nếu giữa hai đỉnh u, v của V có thể có nhiều hơn 1 cạnh trong E nối từ u tới v.
- Đồ thị G đƣợc gọi là đồ thị vô hướng nếu các cạnh trong E là không định hƣớng, tức là cạnh nối hai đỉnh u, v bất kỳ cũng là cạnh nối hai đỉnh v, u.
- Đồ thị G đƣợc gọi là đồ thị có hướng nếu các cạnh trong E là có định hƣớng, có thể có cạnh nối từ đỉnh u tới đỉnh v nhƣng chƣa chắc đã có cạnh nối từ đỉnh v tới đỉnh u.
- Trong đồ thị có hƣớng, các cạnh đƣợc gọi là các cung.
- Đồ thị vô hƣớng cũng có thể coi là đồ thị có hƣớng nếu nhƣ ta coi cạnh nối hai đỉnh u, v bất kỳ tƣơng đƣơng với hai cung (u, v) và (v, u).
- Xử lý đồ thị lớn trên môi trƣờng phân tán sử dụng MapReduce 10 Hình 1.1: Phân loại đồ thị Mặc dù chƣa có một khái niệm chính xác về đồ thị lớn (Big Graph) nhƣng chúng ta có thể khái quát rằng thuật ngữ “đồ thị lớn” chỉ các đồ thị mà dữ liệu của nó gồm tập các đỉnh và cạnh (có thể gồm cả nhãn của đỉnh hay cạnh) với số lƣợng lớn lên đến hàng triệu đơn vị (ví dụ mạng xã hội Facebook đƣợc xem nhƣ một đồ thị lớn với hơn 1.5 tỷ đỉnh tƣơng ứng với số lƣợng ngƣời dùng tính đến 12/2015).
- Sự phức tạp trong cấu trúc của đồ thị lớn khiến cho các thuật toán đồ thị truyền thống không xử lý đƣợc hoặc xử lý với một hiệu năng thấp.
- Từ đó, đồ thị lớn đặt ra các thách thức cho việc lƣu trữ, phân tích, trực quan hóa và truy vấn.
- Bởi vậy, gần đây nhiều nhà nghiên cứu đã tập trung vào các giải pháp, thuật toán để giải quyết vấn đề của đồ thị lớn, một trong các nền tảng phải kể đến là MapReduce (chi tiết về MapReduce đƣợc trình bày ở Chƣơng 2) 1.1.2.
- Đồ thị có trọng số và đƣờng đi Định nghĩa 1.6.
- Đồ thị có trọng số là đồ thị mà mỗi cạnh của nó đƣợc gán cho tƣơng ứng với một số (nguyên hoặc thực).
- Số gán cho mỗi cạnh của đồ thị đƣợc gọi là trọng số của cạnh.
- Hình 2 sau đây minh họa cho một đồ thị có trọng số.
- Xử lý đồ thị lớn trên môi trƣờng phân tán sử dụng MapReduce 11 Hình 1.2: Đồ thị có trọng số Định nghĩa 1.7.
- Cho đồ thị có trọng số G=(V, E).
- Nghiên cứu về các ứng dụng của bài toán xử lý đồ thị lớn Đồ thị lớn đƣợc sử dụng để giải quyết các bài toán trong nhiều lĩnh vực khác nhau.
- Chẳng hạn, chúng ta có thể phân biệt các hợp chất hoá học hữu cơ khác nhau với cùng một công thức phân tử nhƣng khác nhau về cấu trúc phân tử nhờ đồ thị.
- Chúng ta có thể xác định xem hai máy tính trong mạng có thể trao đổi thông tin đƣợc với nhau hay không nhờ mô hình đồ thị của mạng máy tính.
- Đồ thị có trọng số

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt