- Trang Chủ
- Toán học
- Một cách tiếp cận mới cho bài toán tìm đường đi ngắn nhất trên đồ thị phân tán
Xem mẫu
- ISSN 2354-0575
MỘT CÁCH TIẾP CẬN MỚI CHO BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT
TRÊN ĐỒ THỊ PHÂN TÁN
Nguyễn Thị Huyền, Phạm Đăng Hải
Trường Đại học Bách khoa Hà Nội
Ngày nhận: 17/2/2016
Ngày xét duyệt: 15/3/2016
Tóm tắt:
Gần đây, hiệu quả của việc truy vấn thông tin trên các đồ thị lớn trở thành một chủ đề quan trọng
trong khoa học máy tính. Một câu truy vấn được sử dụng rộng rãi đó là “tìm đường đi ngắn nhất giữa hai
đỉnh của đồ thị”, một bài toán mà có thể được giải bằng một vài thuật toán nổi tiếng như Dijkstra, Johnson,
hay Floyd-Warshall; tuy nhiên, nó là không đơn giản để trả lời câu truy vấn này trên một đồ thị mà dữ liệu
phân tán ở nhiều vị trí khác nhau. Trong bài báo này, chúng tôi đề xuất một cách tiếp cận mới dựa trên
kỹ thuật ước lượng từng phần để giải quyết bài toán tìm đường đi ngắn nhất giữa hai đỉnh trên một đồ thị
phân tán. Chúng tôi chỉ ra rằng thuật toán đề xuất có thể được cài đặt dưới hình thức song song trên nền
tảng MapReduce. Bằng việc sử dụng một tập dữ liệu trong thực tế cho thực nghiệm, chúng tôi tiến hành
thực nghiệm và chỉ ra được thuật toán của chúng tôi có khả năng mở rộng cho các đồ thị lớn trên các hệ
thống phân tán.
Từ khóa: Truy vấn đồ thị, MapReduce, Đường đi ngắn nhất, Đồ thị phân tán, Ước lượng từng phần.
1. Đặt vấn đề • Giải thuật tìm kiếm A*: giải bài toán
Trong các ứng dụng thực tế, bài toán tìm nguồn đơn sử dụng heuristics để tăng tốc độ tìm
đường đi ngắn nhất giữa hai đỉnh của một đồ thị kiếm.
liên thông có một ý nghĩa to lớn. Ví dụ như, bài toán • Thuật toán Floyd-Warshall: giải bài toán
chọn một hành trình tiết kiệm nhất (theo tiêu chuẩn đường đi ngắn nhất cho mọi cặp đỉnh.
hoặc khoảng cách hoặc thời gian hoặc chi phí) trên • Thuật toán Johnson: giải bài toán đường
một mạng giao thông đường bộ, đường thủy hoặc đi ngắn nhất cho mọi cặp đỉnh, có thể nhanh hơn
đường không; bài toán chọn một phương pháp tiết thuật toán Floyd-Warshall trên các đồ thị thưa.
kiệm nhất để đưa ra một hệ thống động lực từ trạng Các thuật toán trên được xây dựng để giải
thái xuất phát đến một trạng thái đích, bài toán lập quyết các bài toán đồ thị tổng quát, ở đó dữ liệu tập
lịch thi công các công đoạn trong một công trình thi trung tại một máy tính đơn nhất. Tuy nhiên, nó là
công lớn, bài toán lựa chọn đường truyền tin với chi không đơn giản để trả lời câu truy vấn này trên một
phí nhỏ nhất trong mạng thông tin, v.v… đồ thị lớn mà dữ liệu phân tán ở nhiều vị trí khác
Bài toán tìm đường đi ngắn nhất có thể phát nhau. Trong bài báo này, chúng tôi đã đề xuất một
biểu dưới dạng hình thức như sau: Cho trước một thuật toán dựa trên kỹ thuật ước lượng từng phần và
đồ thị có trọng số G = (V, E), trong đó V là một tập khai thác nền tảng hỗ trợ xử lý dữ liệu song song
đỉnh, E là một tập cạnh, hãy tìm một đường đi ngắn MapReduce [2] để giải quyết bài toán tìm đường đi
nhất từ đỉnh xuất s ! V đến đỉnh đích t ! V [1]. Bài ngắn nhất nêu trên.
toán đường đi ngắn nhất giữa mọi cặp đỉnh là một
bài toán tương tự, trong đó ta phải tìm các đường đi 2. Cơ bản về thuật toán Dijkstra
ngắn nhất cho mọi cặp đỉnh s và t. Dijkstra là một thuật toán giải quyết bài toán
Trong lý thuyết đồ thị, đã có nhiều thuật toán đường đi ngắn nhất nguồn đơn trong một đồ thị có
được đề xuất đề giải quyết bài toán tìm đường đi hướng, mà trọng số trên các cung không âm [1].
ngắn nhất. Các thuật toán quan trọng nhất giải quyết Thuật toán được xây dựng dựa trên cơ sở
bài toán này bao gồm: gán cho các đỉnh các nhãn tạm thời. Nhãn của mỗi
• Thuật toán Dijkstra: giải bài toán nguồn đỉnh cho biết cận của độ dài đường đi ngắn nhất từ
đơn nếu tất cả các trọng số đều không âm. Thuật s đến nó. Các nhãn này sẽ được biến đổi theo một
toán này có thể tính toán tất cả các đường đi ngắn thủ tục lặp, mà ở mỗi bước lặp có một nhãn tạm
nhất từ một đỉnh xuất phát cho trước s tới mọi đỉnh thời trở thành nhãn cố định. Nếu nhãn của một đỉnh
khác mà không làm tăng thời gian chạy. nào đó trở thành một nhãn cố định thì nó sẽ cho ta
• Thuật toán Bellman-Ford: giải bài toán không phải là cận trên mà là độ dài của đường đi
nguồn đơn trong trường hợp trọng số có thể có giá ngắn nhất từ đỉnh s đến nó. Thuật toán được mô tả
trị âm. cụ thể như sau:
56 Khoa học & Công nghệ - Số 9/Tháng 3 - 2016 Journal of Science and Technology
- ISSN 2354-0575
Thuật toán 1: Thủ tục Dijkstra tìm đường đi Định nghĩa 1: Đồ thị phân tán G = (V, E) là
ngắn nhất từ một đỉnh đến các đỉnh đồ thị bao gồm một tập các đồ thị con từ G1, G2, …,
Gk nằm trên các máy tính khác nhau và một đồ thị
Đầu vào: một đồ thị G = (V, E), đỉnh nguồn s liên kết giữa chúng Gc. Trong đó, một đồ thị con Gi
Đầu ra: độ dài đường đi ngắn nhất từ đỉnh s đến được định nghĩa bởi (Vi , Ei ), với Vi ! V và Ei ! E;
các đỉnh còn lại trong đồ thị đồ thị liên kết Gc = (Vc, Ec ) , ở đó Ec là tập các cạnh
1: for each vertex v in G // khởi tạo kết nối các đồ thị con với nhau (gọi là cạnh liên kết)
2: dist[v] ← ∞; // khởi tạo giá trị và Vc là tập các đỉnh có các cạnh liên kết.
từ s tới đỉnh v = ∞ Ví dụ 1:
3: previous[v] ← null; // đỉnh trước của
đỉnh v
4: dist[source] ← 0; // khoảng cách từ
nguồn tới nguồn
5: while V is not empty do
6: u ← đỉnh có thuộc V có khoảng cách
tới s là nhỏ nhất;
7: V ← V/{u};
8: for each neighbor v of u
9: alt ← dist[u] + dist_between(u, v)
10: if alt < dist[v] then
11: dist[v] ← alt;
12: previous[v] ← u;
13: return previous[ ]; Hình 1. Minh họa đồ thị phân tán
Thuật toán có độ phức tạp là O(n2). Do độ
Hình 1 ở trên là một ví dụ minh họa đồ thị
phức tạp tính toán cao, việc giải bài toán này với
phân tán. Trong ví dụ này, đồ thị phân tán G gồm
tính chất tuần tự gặp phải bất lợi lớn về thời gian
3 đồ thị con G1, G2 và G3 và một đồ thị liên kết Gc
thực hiện chương trình, tốc độ xử lý, khả năng lưu
với các cạnh được vẽ bằng các nét đứt. Trong ví dụ
trữ,... Đặc biệt là trên đồ thị có hàng triệu đỉnh và
này, dữ liệu của mỗi đồ thị con và đồ thị liên kết bao
cạnh mà thời gian chạy phải được rút gọn thì thuật
gồm như sau:
toán tuần tự không thực hiện được.
Bảng 1. Dữ liệu trên các đồ thị con và đồ thị liên kết
Điều này đặt ra yêu cầu phải chia đồ thị cho
một hệ thống phân tán có nhiều máy tính cùng tham Đồ thị Vi Ei
gia tính toán đồng thời, song việc chia đồ thị thành G1 = (V1, E1) {1, 2, 3, 4, 5} {(1,2); (1,3); (1,4);
các đồ thị nhỏ thì việc lưu trữ các đồ thị nhỏ đó trên (2,3); (3,5)}
hệ thống file phân tán và việc sử dụng thuật toán tìm G2 = (V2, E2) {6, 7, 8, 9, {(7,10); (8,6);
đường đi ngắn nhất trên hệ thống phân tán đó trở 10} (8,10); (10,9)}
thành một bài toán với nhiều thách thức.
G3 = (V3, E3) {11, 12, 13, {(11,13); (12,15);
3. Đồ thị phân tán 14, 15, 16} (13,15); (14,16);
Cơ sở dữ liệu phân tán là tuyển tập dữ liệu (15,16)}
có quan hệ logic với nhau, được phân bố trên các Gc = (Vc, Ec) {2, 3, 4, 5, 6, {(3,7); (4,11);
máy tính của một mạng máy tính. Cũng giống như 7, 9, 11, 12, (5,12); (6,2);
cơ sở dữ liệu phân tán, đồ thị phân tán là một tập các 14, 16} (7,14); (9,14)}
đồ thị con liên thông với nhau bởi các cạnh của đồ
thị và các đồ thị này được đặt phân tán trên một hệ 4. Đề xuất thuật toán tìm đường đi ngắn nhất
thống mạng máy tính. trên đồ thị phân tán
Trên thực tế chúng ta thấy, dữ liệu của một Để tìm kiếm đường đi ngắn nhất trên đồ thị
đồ thị G đặc trưng cho một hệ thống có thể được phân tán, chúng tôi đã đề xuất một thuật toán theo
chia ra làm k phần khác nhau nằm ở các máy thuộc kỹ thuật ước lượng từng phần.
các vị trí địa lý khác nhau, ở đó mỗi phần được coi Ước lượng từng phần
là một đồ thị con (sub-graph). Các đồ thị con này Kỹ thuật ước lượng từng phần được đưa ra
liên thông với nhau bởi tập các cạnh của đồ thị. Một trong [3]. Kỹ thuật này trình bày một vài kiểu tối ưu
cách hình thức hóa có thể định nghĩa đồ thị phân hóa chương trình theo những cách đặc biệt nhằm
tán như sau: mục tiêu tăng tốc độ xử lý. Ở đó, một chương trình
Khoa học & Công nghệ - Số 9/Tháng 3 - 2016 Journal of Science and Technology 57
- ISSN 2354-0575
xử lý p được chia ra làm k phần (p1, p2, …,pk) cái của một tình thành có tồn tại các điểm của các tỉnh
mà có thể thực thi riêng rẽ và đảm bảo thực hiện thành lân cận. Một tình huống thực tế là: một người
theo cùng một cách. Một chương trình pi sẽ thực đang ở địa điểm (1) tại Hà Nội muốn đến thăm một
hiện nhanh hơn thực thi chương trình p. Kết quả người bạn ở địa điểm số (16) tại Hải Dương. Trên
của pi là tập con trong kết quả của p. Bằng việc áp thực tế, có rất nhiều tuyến đường từ Hà Nội đến Hải
dụng kỹ thuật ước lượng từng phần này, các công Dương, có tuyến trực tiếp qua hai thành phố, nhưng
trình nghiên cứu trong [4, 5, 6] đã đề xuất các thuật cũng có nhiều tuyến đi liên tỉnh qua Hưng Yên rồi
toán hiệu quả trong việc ước lượng truy vấn trên đồ mới đến Hải Dương. Hãy giúp anh ấy tìm ra một
thị phân tán. tuyến đường ngắn nhất đi từ (1) đến (16) trên hệ
thống dữ liệu đã có. Trong các phần tiếp theo, chúng
Đề xuất thuật toán tôi sẽ tập trung giải quyết bài toán này.
Trong phần này, chúng tôi trình bày đề xuất Một vài quan sát và suy luận:
một thuật toán tìm đường đi ngắn nhất trên đồ thị Như định nghĩa đồ thị phân tán ở trên, mối
phân tán. Ở đây, cách tiếp cận là sử dụng thuật toán liên hệ giữa các đồ thị con được xác định thông qua
Dijkstra kết hợp với kỹ thuật ước lượng từng phần. các đỉnh và cạnh của đồ thị liên kết. Một đỉnh thuộc
Để làm được điều đó, chúng tôi đã nghiên cứu mối đồ thị con này có thể là đỉnh đích của một cạnh mà
liên hệ giữa đường đi ngắn nhất trên toàn bộ đồ thị đỉnh thuộc đồ thị con khác. Tất cả các đỉnh cạnh
và đường đi ngắn nhất trên từng phần đồ thị. Các kỹ như vậy đều thuộc đồ thị liên kết. Để tổng quát hóa
thuật này sẽ được trình bày trong các phần dưới đây. mối quan hệ giữa chúng, chúng tôi đưa ra các định
Định nghĩa 2: Đồ thị phân tán có trọng số là nghĩa sau:
một đồ thị phân tán mà trên các cạnh được gán một Định nghĩa 3: Đỉnh liên kết trong (input
giá trị số (số nguyên hoặc số thực). node) của một đồ thị con Gi = (Vi, Ei), là một đỉnh
Để áp dụng cho bài toán tìm đường đi ngắn thuộc tập đỉnh Vi mà tồn tại ít nhất một cạnh từ một
nhất, chúng tôi sử dụng một đồ thị phân tán có trọng đỉnh thuộc đồ thị con khác đến nó.
số. Bằng cách gán các trọng số vào đồ thị phân tán Định nghĩa 4: Đỉnh ảo ngoài (output node
của Hình 1, chúng ta có một đồ thị phân tán có trọng hay virtual node) của một đồ thị con Gi = (Vi, Ei),
số như trong Hình 2. là một đỉnh không thuộc tập đỉnh Vi nhưng tồn tại ít
nhất một cạnh từ một đỉnh thuộc Vi đến nó.
Từ hai định nghĩa trên, chúng ta có thể đưa
ra mối liên hệ giữa đồ thị G, các đồ thị con Gi và đồ
thị liên kết Gc như sau:
• Vc = U ik= 1 _Vi .in , Vi .out i , trong đó Vi .in là
tập các input node của đồ thị con Gi và Vi .in 3 Vi;
Vi .out là tập các output node của đồ thị con Gi và
Vi .out + Vi = 4;
• Ec = U ik= 1 cEi , trong đó cEi là tập tất cả các
cạnh liên kết thuộc Gi , mỗi cạnh thuộc (v, u) ! cEi
là được xác định bởi v ! Vi .in và u ! Vi .out.
• V = U ik= 1 _Vi i và Vi + Vj = 4 if i ≠ j;
E = E c , _ U ik= 1 Ei i và Ei + Ej = 4 if i ≠ j;
Trên thực tế, dữ liệu lưu trữ ở mỗi máy bao
Hình 2. Ví dụ đồ thị phân tán có trọng số gồm một đồ thị con Gi, một tập các output node
Vi.out và tập các cạnh liên kết cEi . Toàn bộ dữ liệu
Trong Hình 2, các trọng số được đưa vào lưu trên một máy gọi là một mảnh (fragment) của
được xem như độ dài đường đi giữa hai địa điểm đồ thị G, kí hiệu bởi Fi = _Vi , Vi .out, Ei , cEi i ).
(có thể sử dụng đơn vị là kilometer). Như vậy, việc xử lý truy vấn trên mỗi máy nghĩa
là chúng ta đang xử lý trên một mảnh của đồ thị G.
Ví dụ 2: Giả sử chúng ta có một đồ thị phân Bảng 2. Minh họa input và output node của đồ thị
tán có trọng số G như trong Hình 2 là một mạng phân tán
đường của các tỉnh thành. Ở đó, G1, G2, và G3 tương Fi Vi.in Vi.out
ứng 3 tỉnh thành khác nhau lần lượt là Hà Nội,
Hưng Yên và Hải Dương. Dữ liệu mạng đường đi F1 {2} {7, 11, 12}
của các tình thành là rất lớn và được lưu trữ riêng F2 {7} {2, 14}
biệt tại các máy tính khác nhau, có kết nối với nhau
F3 {11, 12, 14} {4}
qua một hệ thống mạng. Trên mỗi mạng đường đi
58 Khoa học & Công nghệ - Số 9/Tháng 3 - 2016 Journal of Science and Technology
- ISSN 2354-0575
Bảng 2 chỉ ra tập các input node và output 8: for each node v ! Vi .in do
node trên các mảnh đồ thị. Tuy nhiên, trong bảng 9: v.pvec ← Dijkstra(Gi, v, Vi .out);
trên có hai giá trị đặc biệt được thêm vào: đỉnh (1) 10: if v.pvec ≠ 4 then
là đỉnh xuất nguồn nên nó được thêm vào danh sách 11: Pi ← v.pvec;
input node của phần đồ thị con chứa nó (G1) và đỉnh 12: return Pi;
(16) là đỉnh đích nên nó được thêm vào danh sách
output node của phần đồ thị con chứa nó (G3).
Thuật toán 2 thực hiện tính toán một phần
Như vậy, chúng ta có câu truy vấn Q(1, 16).
kết quả cho câu truy vấn Q trên một đồ thị con. Đầu
Việc trả lời câu truy vấn Q trên đồ thị G là tương
tiên, (1) khởi tạo tạo Pi là một tập vector rỗng, ở
đương với việc tìm ra một đường đi P(Q) = {v1 -> v2
đó v.pvec ! Pi là một vector đường đi, mỗi phần
-> …-> vn} là đường đi ngắn nhất, trong đó v i ! G
tử v.pvec[u] là một đường đi từ input node v đến
G (i = 1, 2, ..., n), v1 = 1 và vn = 16.
output node u. (2) Sau đó nó thực hiện việc kiểm
Để trả lời câu truy vấn Q trên đồ thị phân tán,
tra đỉnh nguồn và đích để thêm vào tập Vi.in hay
ý tưởng cơ bản của chúng tôi gồm các bước như sau:
Vi.out tương ứng. Cuối cùng, (3) sử dụng thuật toán
Bước 1: Khi nhận được câu truy vấn Q(s, t),
Dijkstra tính toán kết quả đường đi ngắn nhất v.pvec
một máy đóng vai trò là máy chủ điều phối (master)
từ input node v đến các đỉnh output node u ! Vi.out
sẽ gửi Q đến mỗi máy cục bộ (slaver)
như sau: nếu tồn tại sẽ ghi giá trị đường đi X(v,u)
Bước 2: Sau khi nhận được câu truy vấn Q
(khoảng cách ngắn nhất và danh sách các đỉnh đi
từ máy master (M), mỗi máy slaver (Si) sẽ thực hiện
qua theo thứ tự) vào vector v.pvec; ngược lại, nếu
thuật toán Dijkstra tìm đường đi ngắn nhất từ tất
không tồn tại đường đi, giá trị khoảng cách trả về là
các các input node đến output node trên phần đồ
∞ và đường đi bằng 4 thì không thêm vào v.pvec.
thị con Gi tương ứng một cách song song. Điều này
Sau đó thêm v.pvec khác 4 vào Pi .
có nghĩa là chúng ta tìm đường đi ngắn nhất từ các
đỉnh biên ở đồ thị này đến các đỉnh biên thuộc đồ Ví dụ 3:
thị khác, những đỉnh có thể liên kết đồ thị con với Trong ví dụ này, chúng tôi thực hiện thuật
nhau. Trên mỗi slaver Si chúng ta nhận được các toán 2, sử dụng câu truy vấn và các mô tả ở trong
phần kết quả Pi tương ứng. Mỗi đỉnh trong các phần Ví dụ 2. Theo như Thuật toán 2, chúng ta phải thực
kết quả này có thể liên quan đến việc tìm ra kết quả hiện trả lời câu truy vấn Q(1, 16) trên 3 máy cục
cuối cùng cho câu truy vấn Q trên đồ thị G. Trong bộ và nhận về 3 phần kết quả lần lượt là P1, P2, P3.
Pi, mỗi input node v có thể tồn tại đường đi tới một Sau đó tổng hợp thành một đồ thị phụ thuộc và trả
output node u, nhưng ta không biết được u có thể lời câu truy vấn Q trên đồ thị đó. Tuy nhiên, ở đây,
đến được đỉnh đích t hay không. Như vậy, ta có thể chúng tôi chỉ trình bày áp dụng thuật toán đề xuất
biểu diễn Pi bằng một tập các vector đường đi với trên mảnh đồ thị F1. Khởi tạo ta có Pi = 4, Vi.in =
số phần tử là số output node của Gi, ở đó giá trị mỗi {2} và Vi.out = {7, 11, 12}. Trên V1, tồn tại đỉnh
phần tử của vector được định nghĩa bằng đường đi (1) là đỉnh nguồn của câu truy vấn nên đỉnh (1) sẽ
ngắn nhất từ một input node đến một output node được thêm vào Vi.in, khi đó V1.in = {1, 2}; đỉnh
(bao gồm độ dài và đường đi). Bước này được minh (16) không tồn tại trên V1, nên Vi.out giữ nguyên.
họa bởi Thuật toán 2. Sau đó thực hiện Dijkstra tìm đường đi ngắn nhất
Bước 3: Tổng hợp các phần kết quả để xây từ các input node đến output node ta thu được các
dựng lên một đồ thị phụ thuộc trên máy master. Sau vector đường đi như trong Bảng 3.
đó thực hiện thuật toán Dijkstra một lần nữa trên đồ Bảng 3. Kết quả thực hiện câu truy vấn Q trên F1
thị phụ thuộc để tìm ra đường đi ngắn nhất từ đỉnh
s đến đỉnh t. Đây là kết quả cuối cùng cho câu truy v.pvec (7) (11) (12)
vấn Q(s,t) trên đồ thị G. (1).pvec X(1,7) = [3, X(1,11) = [5, X(1,12) = [4,
Thuật toán 2: Thủ tục LocalEval {1, 3, 7}] {1, 4, 11}] {1, 3, 5, 12}]
Đầu vào: mảnh đồ thị Fi và câu truy vấn Q(s, t) (2).pvec X(2,7) = [8, X(2,11) = X(2,12) = [8,
Đầu ra: Tập các vector đường đi Pi {2, 3, 7}] [∞, {4}] {2, 3, 5, 12}]
1: Pi ← 4; Như vậy, P1 gồm 2 vector với 5 giá trị đường
2: if s ! Vi then đi từ các đỉnh input node đến các đỉnh output node.
3: Vi .in ← Vi.in ,{s}; Kết quả này sẽ được gửi tới máy chủ điều phối để
4: if t ! Vi then xây dựng lên đồ thị phụ thuộc. Hoàn toàn tương tự,
5: Vi.out ← Vi .out ,{t}; ta có thể thực hiện tính được các kết quả P2, P3 trên
6: for each node v ! Vi do các mảnh đồ thị F1 và F2 tương ứng như trong Bảng
7: v.visited = false; 4 và Bảng 5.
Khoa học & Công nghệ - Số 9/Tháng 3 - 2016 Journal of Science and Technology 59
- ISSN 2354-0575
Bảng 4. Kết quả thực hiện câu truy vấn Q trên F2
v.pvec (2) (14)
(7).pvec X(7,2) = [∞, {4}] X(7,14) = [2, {7, 14}]
Bảng 5. Kết quả thực hiện câu truy vấn Q trên F3
v.pvec (16)
(11).pvec X(11,16) = [7, {11, 13, 15, 16}]
(12).pvec X(12,16) = [5, {12, 15, 16}]
(14).pvec X(14,16) = [1, {14, 16}]
Sau khi có các kết quả từ P1, P2, và P3 từ
các máy slaver gửi lên, tại máy master tiến hành
Hình 4. Mô hình MapReduce sử dụng để trả lời câu
xây dựng một đồ thị phụ thuộc Gd = (Vd, Ed) như
truy vấn trên đồ thị phân tán
sau: với mỗi X(v,u) của Pi tạo ra hai đỉnh trên đồ thị
phụ thuộc tương ứng Xv và Xu và một cạnh nối giữ
Trong mô hình này, chúng tôi sử dụng một
chúng với trọng số là giá trị khoảng cách của X(v,u).
Job để cài đặt thuật toán. Ở đây, số Map Tasks phụ
Giá trị đường đi của X(v,u) được dùng cho việc truy
thuộc và số phần đồ thị con của bài toán, và chỉ duy
vết đường đi khi cạnh nối Xv và Xu tồn tại trong kết nhất một Reduce Task được sử dụng vào mục đích
quả đường đi ngắn ngất trả lời cho câu truy vấn Q tổng hợp các phần kết quả và tìm ra câu trả lời cuối
trên đồ thị Gd cũng như đồ thị G. cùng cho câu truy vấn Q trên đồ thị G.
Dữ liệu các mảnh đồ thị được lưu trên hệ
thống HDFS của Hadoop gồm k mảnh. Cách thức
hoạt động của mô hình như sau: (1) khi một câu truy
vấn Q(s,t) được đưa ra, máy chủ điều phối (master)
sẽ chuyển nó xuống các slavers (giả sử có k máy
slavers); (2) tại mỗi máy thực thi hàm Map bằng
cách gọi thủ tục LocalEvalMapper, thủ tục này
có nhiệm vụ tìm ra các đường đi ngắn nhất từ các
input node đến các output node bằng cách gọi hàm
LocalEval(Fi , Q) đã trình bày và trả về kết quả là
tập các vector đường đi chứa trong Pi. Kết quả của
mỗi Map Task được ghi xuống hệ thống HDFS và
gửi đến Reduce Task với cùng một khóa K1. Ở đây,
Hình 3. Đồ thị phụ thuộc Gd được tạo ra từ kết quả chúng tôi chọn một giá trị khóa duy nhất nhằm mục
của các Pi đích tất cả các phần kết quả được tập hợp về một
máy để tạo lên một đồ thị phụ thuộc Gd. (3) Sau
Bằng việc sử dụng thuật toán Dijkstra tìm đó, tại máy chủ điều phối sẽ thực hiện hàm Reduce
đường đi ngắn nhất từ đỉnh X1 đến X16 trên đồ thị Gd bằng cách gọi thủ tục EvalReducer, thủ tục này có
ta tìm ra được kết quả đường đi P’ (màu đỏ): X1 -> nhiệm vụ tạo ra một đồ thị phụ thuộc Gd từ các phần
X7 -> X14 -> X16 với độ dài = 6. Tiếp theo, nối các kết quả gửi đến bởi các hàm Map và thực hiện hàm
giá trị đường đi của X(1,7), X(7,14) và X(14,16) theo thứ Dijkstra để tìm đường đi ngắn nhất từ đỉnh nguồn
tự ta tìm được câu trả lời P(Q): 1 -> 3 -> 7 -> 14 -> đến đỉnh đich và trả về kết quả cuối cùng cho câu
16, có độ dài = 6 là kết quả cuối cùng cho câu truy truy vấn Q trên đồ thị G.
vấn Q trên đồ thị G.
5. Thực nghiệm và đánh giá kết quả
Cài đặt bài toán sử dụng MapReduce Thiết lập môi trường thực nghiệm
Trong phần này, chúng tôi trình bày kỹ thuật Các cài đặt sử dụng cho thực nghiệm các
sử dụng MapReduce để cài đặt các thuật toán đề thuật toán trong bài báo này như sau:
xuất. Mô hình sử dụng MapReduce để trả lời câu a) Môi trường thực nghiệm
truy vấn Q trên đồ thị phân tán G được thể hiện Hệ thống Hadoop dùng để thực nghiệm trong
trong Hình 4. bài báo bao gồm 17 máy tính để bàn: một máy được
60 Khoa học & Công nghệ - Số 9/Tháng 3 - 2016 Journal of Science and Technology
- ISSN 2354-0575
dùng làm master node, 16 máy slaver node dùng Thời gian thực hiện ở đây bao gồm cả thời gian khởi
cho việc tính toán tìm ra kết quả của bài toán. Mỗi tạo 1 Job trong Hadoop, ghi/đọc dữ liệu từ HDFS và
máy tính có 2 CPUs và bộ nhớ RAM là 2 GB. Tất cả thời gian chạy thuật toán trả lời câu truy vấn. Chính
các thuật toán trong bài báo được cài đặt bằng Java. vì vậy, ở đây chúng tôi không so sánh về mặt thời
b) Dữ liệu thực nghiệm gian thực hiện giữa thuật toán song song phân tán
Bài báo sử dụng một dữ liệu mạng đường đi với thời gian thuật toán chạy tuần tự trên một máy.
của thành phố New York [7] với kích thước 264.346 Đề xuất này của chúng tôi có ý nghĩa trong việc xử
đỉnh và 733.846 cạnh, trong đó mỗi đỉnh là định danh lý phân tán với dữ liệu lớn, cái mà một máy tính đơn
một địa điểm của thành phố và mỗi cạnh chỉ đường nhất có thể không giải quyết được cả về mặt lưu trữ
đi từ một địa điểm đến một địa điểm khác. Mỗi cạnh và việc xử lý tính toán.
có trọng số là khoảng cánh giữa hai địa điểm.
Để tạo ra các phần đồ thị con khác nhau mà
vẫn đảm bảo tính đúng đắn của dữ liệu, bài báo đã
sử dụng công cụ GraphLab [8] cho việc phân mảnh
đồ thị thành nhiều đồ thị con. Chúng tôi đã chuẩn
bị 4 bộ dữ liệu với số phần đồ thị con lần lượt là 4,
8, 16 và 32.
c) Câu truy vấn
Chúng tôi đã chọn ra ngẫu nhiên một câu
truy vấn: Tìm đường đi ngắn nhất từ đỉnh có mã là
“1” đến đỉnh có mã là “14” trên đồ thị. Câu truy vấn
này tồn tại kết quả một đường đi ngắn nhất với tổng
độ dài = 111751, nó được đưa ra từ kết quả chạy
thuật toán Dijkstra trên đồ thị ban đầu (chưa phân
mảnh). Chúng tôi dùng kết quả này để đối chiếu với
kết quả sinh ra từ thuật toán đề xuất.
d) Kết quả thực nghiệm Hình 5. Kết quả thời gian thực thi câu truy vấn với
Trong phần này, chúng tôi trình bày kết quả số lượng đồ thị con khác nhau
của việc thực hiện câu truy vấn nêu trên và đo lượng
thời gian trả lời câu truy vấn trên môi trường phân 6. Kết luận
tán với các bộ dữ liệu có kích thước khác nhau. Bài báo đã trình bày một cách tiếp cận mới
Hình 5 cho thấy kết quả khi chia đồ thị ra để giải quyết bài toán tìm đường đi ngắn nhất từ một
thành càng nhiều phần đồ thị con và thực hiện thuật đỉnh đến một đỉnh khác trên đồ thị phân tán. Chúng
toán song song trên từng đồ thị con đó thì thời gian tôi đã đưa ra một thuật toán dựa trên kỹ thuật ước
thực hiện thuật toán sẽ giảm dần. Cụ thể khi dữ liệu lượng từng phần và khai thác nền tảng hỗ trợ xử lý
được chia thành 4 phần đồ thị con thì thời gian thực dữ liệu song song phân tán MapReduce. Kết quả
hiện của thuật toán là 200s, khi chia thành 8 phần đồ thực nghiệm trên một dữ liệu đồ thị thực tế đã chỉ ra
thị con thì thời gian thực hiện giảm còn 120s và khi tính hiệu quả trong cách tiếp cận của chúng tôi cho
số đồ thị con là 32 thì thời gian giảm chỉ còn 52s. việc xử lý đồ thị lớn trên môi trường phân tán. Do
e) Phân tích đó, đề xuất này có thể áp dụng cho các ứng dụng
Hình 5 chỉ ra rằng, thời gian trả lời câu truy khác trong thực tế như phân tích mạng xã hội, mạng
vấn sẽ tỉ lệ nghịch với số phần đồ thị con. Thời gian giao thông,..vv. Tiếp theo hướng nghiên cứu này,
giảm nhanh khi tăng số lượng hàm Map dùng cho chúng tôi sẽ tập trung vào các loại bài toán khác
việc tìm kiếm các kết quả từng phần. Ở đây, mỗi trên môi trường phân tán ví dụ như bài toán truy vấn
phần đồ thị con được thực hiện bởi một hàm Map. theo biểu thức chính quy có điều kiện.
Tài liệu tham khảo
[1]. Lê Minh Hoàng, “Chuyên đề Lý thuyết đồ thị”, Đại Học Sư Phạm Hà Nội, 1999-2002
[2]. Dean, Jeffrey, and Sanjay Ghemawat, “MapReduce: Simplified Data Processing on Large
Clusters”, Communications of the ACM 51.1 (2008): 107-113.
[3] N. D. Jones, An Introduction to Partial Evaluation. ACM Computing Surveys (CSUR), 28(3):480–
503, 1996.
[4]. P. Buneman, G. Cong, W. Fan, and A. Kementsietsidis, Using Partial Evaluation in Distributed
Query Evaluation, In Proceedings of the 32nd International Conference on Very Large Databases,
Khoa học & Công nghệ - Số 9/Tháng 3 - 2016 Journal of Science and Technology 61
- ISSN 2354-0575
pages 211–222. VLDB Endowment, 2006.
[5]. W. Fan, J. Li, S. Ma, N. Tang, and Y. Wu, Adding Regular Expressions to Graph Reachability
and Pattern Queries, In Data Engineering (ICDE), 2011 IEEE 27th International Conference on,
pages 39–50. IEEE, 2011.
[6]. W. Fan, X. Wang, and Y. Wu, Performance Guarantees for Distributed Reachability Queries,
Proceedings of the VLDB Endowment, 5(11):1304–1316, 2012.
[7]. Camil Demetrescu. 2014, “9th DIMACS Implementation Challenge: Shortest Paths”, Accessed
January 08, 2016. http://www.dis.uniroma1.it/challenge9/download.shtml
[8]. Low, Yucheng, et al, “Graphlab: A new Framework for Parallel Machine Learning”, arXiv
preprint arXiv:1408.2041 (2014).
A NOVEL APPROACH TO SHORTEST PATH PROBLEM ON DISTRIBUTED GRAPH
Abstract:
Recently, the efficient of query evaluation on big graphs is an important research topic in computer
science. A widely-used query is the shortest path query between two nodes in a graph, which can be
evaluated on a general graph by using a few well-known algorithms such as Dijkstra, Johnson or Floyd-
Warshall; however, it is nontrivial to answer this kind of query in a distributed graph. In this paper, we
propose a novel approach based on the partial evaluation to solve shortest path problem between two
nodes on distributed graph. We show that our algorithm can be readily implemented in the MapReduce
framework, in parallel. Using a real-life data we perform experiments and show that our algorithm is
scalable on large graphs on the distributed systems.
Keywords: Graph Querying, MapReduce, Shorstest Path, Distributed Graph, Partial Evaluation.
62 Khoa học & Công nghệ - Số 9/Tháng 3 - 2016 Journal of Science and Technology
nguon tai.lieu . vn
