Cải thiện tốc độ tìm kiếm của mô hình đồ thị BT-Graph dựa trên nền tảng CUDA

K b v c s k tì tr đ v B d đ v đ [ [ tr h lu N h V r p ỷ yếu Hội nghị Q CẢI T 3 Khoa Công TÓM TẮ alltree, giúp m à không gian đ húng tôi đề xuấ ong hóa thuật -láng giềng gầ m kiếm. Từ khóa BT-Gra úc balltree [2 ề xuất bán kín ị trí địa lý lớ T-Graph. Ngày n ụng đòi hỏi c ộ phức tạp củ à xử lý tuần t Trong b ồ thị BT-Gra 15] [16] [26]. 23] [24] [25] Bài viế ên mô hình. ình đồ thị BT ận. CUDA VIDIA. CUD iệu suất tính t GPUs [ ới số lượng l ộng rãi trong hỏng như: mô uốc gia lần thứ HIỆN TỐ Lư 2 Vụ K nghệ thông lhhuong T - BT-Graph ô hình hóa hệ t ịa lý tìm kiếm t một hướng tiế toán tìm kiếm n nhất và tìm k - CUDA, BT-G ph (Graph M 1] [11]. BT-G h hoạt động n và không A) ay, việc sử d ần phải xử lý a mô hình đồ ự trên CPU [1 ài viết này, c ph bằng phươ Các thực ngh và tìm kiếm đ t được chia th Phần thứ hai -Graph dựa tr [26] là một A cung cấp k oán bằng các 6] [16] [28] h ớn các lõi GP xử lý song s phỏng khí h VIII về Nghiên cứ C ĐỘ T DỰA ơng Hoàng 1 Trung hoa học, Công tin và Truyền @ctu.edu.vn, (Graph Model hống mạng giá mở rộng thì c p cận mới tron dựa trên nền t iếm đường đi n raph, vị trí địa odel based on raph không c cho các cảm b gian địa lý tì Hình 1. A) Tậ ụng Graphic song song. N thị. Đã có nh ] [2] [3] [7] [ húng tôi đề x ng pháp song iệm được tri ường đi ngắn ành năm phần trình bày về ên nền tảng C mô hình lập hả năng kết h h khai thác sứ ỗ trợ đa luồng Us cung cấp ong. GPUs đ ậu, dịch bệnh u cơ bản và ứng ÌM KIẾM TRÊN Hướng1, Ngu tâm Công ngh nghệ và Mô thông, Nhóm nhthanh@{m based on Ball m sát các bẫy đ ần phải cải thi g việc cải thiện ảng CUDA NV gắn nhất dựa lý, mạng giám I. G Ball Tree St hỉ giúp mô h iến tự động, m m kiếm mở r B) p hợp điểm, B) Processing U goài ra GPUs iều nghiên cứ 10]. uất một hướn song hóa th ển khai dựa t nhất [5] [9] [ . Phần thứ nh CUDA NVID UDA. Phần II. C trình và là m ợp giữa kiến c mạnh của đ khổng lồ - n một khả năng ược sử dụng , dụng Công nghệ CỦA MÔ NỀN TẢN yễn Hải Tha ệ phần mềm, i trường, Bộ G nghiên cứu li oet.gov.vn, mo Tree Structure) èn tự động và ện tốc độ tìm k tốc độ tìm kiếm IDIA. Các thự trên mô hình đ sát bẫy đèn tự IỚI THIỆU ructure) [11] ình hóa hệ th à còn hỗ trợ ộng thì cần p Cấu trúc Balltr nits (GPUs) cũng hỗ trợ t u về việc cho g tiếp cận mớ uật toán tìm k rên hai thuật 17] [18] [27] ất giới thiệu IA. Phần thứ thứ tư trình b UDA NVIDIA ột nền tảng trúc phần cứn ơn vị xử lý đồ hiều lõi, với s xử lý dữ liệ để giải quyết thông tin (FAIR) HÌNH Đ G CUDA nh2, Huỳnh X Đại học Cần iáo dục và Đ ên ngành DR et.edu.vn}, h là một mô hìn hỗ trợ tìm kiếm iếm của mô hì của mô hình c nghiệm được ồ thị BT-Graph động, song son là một mô hìn ống mạng giá tìm kiếm vị tr hải cải tiến t C) ee, C) Mô hình [28] đóng vai ốt trong việc thấy hiệu suấ i trong việc c iếm dựa trên toán: tìm kiếm [29]. về mô hình B ba trình bày ày về các thực tính toán son g và phần m họa – Graph ố lượng lên đ u song song, nhiều vấn đề ; Hà Nội, ngày 9 Ồ THỊ B uân Hiệp3 Thơ ào tạo Việt N EAM-CTU/IR xhiep@ctu.ed h đồ thị được x vị trí địa lý. K nh đồ thị BT-G đồ thị BT-Grap triển khai trê và cho thấy sự g. h đồ thị được m sát các bẫy í địa lý [11]. ốc độ tìm ki đồ thị BT-Gra trò quan trọ xử lý đồ thị m t cao giữa xử ải thiện tốc đ nền tảng GP k-láng giền T-Graph và tì về cải thiện t nghiệm. Phầ g song được ềm. CUDA có is Processing ến hàng trăm chính vì điều phức tạp tro -10/7/2015 T-GRAP am D, Đại học C u.vn ây dựng dựa tr hi số lượng vị t raph. Trong b h bằng phương n hai thuật toá cải thiện tốt xây dựng dự đèn tự động Tuy nhiên, kh ếm của mô h ph ng trong xử l à không cần lý song song ộ tìm kiếm củ Us CUDA N g gần nhất [8 m kiếm vị trí ốc độ tìm kiế n cuối cùng l phát triển bở khả năng tăn Units (GPUs) lõi và hàng n đó GPUs đượ ng mô hình h H ần Thơ ên cấu trúc trí địa lý lớn ài viết này, pháp song n tìm kiếm về thời gian a trên cấu bằng cách i số lượng ình đồ thị ý các ứng phải giảm trên GPUs a mô hình VIDIA [6] ] [13] [19] địa lý dựa m của mô à phần kết i Công ty g đáng kể . gàn luồng. c sử dụng óa và mô Ls c A [ tự tr k v n v tr B tr t m G n ương Hoàng Hướ CUDA ong. Cả CPU ác tính toán s III. CẢ . Thuật toán Tìm kiế 11] được thể động tại mộ uy vấn q tron iếm giải thuậ ề Q chứa k vị út đang xét B à cập nhật lại ái và con phả Tuy nh TS. Ngoài ra ường hợp giả Trường ảng CUDA (g ột thực hiện PU. Module hất (gần nhất ng, Nguyễn Hải cung cấp một và GPU đều ong song sẽ d I THIỆN TỐ tìm kiếm k-l m k-láng giề hiện như là ph t không gian đ g V, k là số đ t sẽ tính toán trí có cùng đ lớn hơn D, b Q. Trường h i. Chi tiết giả iên, khi số lượ khi số lượng i quyết bài to hợp một chú ọi tắt là BF-k tính toán son hai thực hiện ) – Thực hiện Thanh, Huỳnh X tập hợp các t tham gia vào o GPU xử lý Hình 3 C ĐỘ TÌM áng giềng gầ ng gần nhất ương pháp tì ịa lý xác địn iểm gần nhất lại Q. Tại mỗ iều kiện gần n ỏ qua B và trả ợp ba nếu B l i thuật được m ng vị trí địa điểm truy vấ án tìm kiếm k ng tôi đề xuấ NNCUDA) g song khoản sắp xếp các k tại CPU. uân Hiệp Hình 2. hư viện mở rộ quá trình tính với bộ nhớ riê . GPU và CU KIẾM CỦA n nhất của m trên mô hình m kiếm k vị t h. Với V là tậ cần tìm. Quá i nút B đang hất của truy kết quả là Q à một nút tro ô tả như tron lý lớn và khô n lớn cũng c -láng giềng g t sử dụng thu [2] [3] [8] [10 g cách từ điểm hoảng cách tí Lưu đồ xử lý ng hỗ trợ lập toán. Các tín ng biệt. DA giao tiếp MÔ HÌNH Đ ô hình đồ thị đồ thị BT-Gr rí địa lý gần n p hợp các vị t trình tìm kiếm xét, giải thuậ vấn q. Trường . Trường hợp ng, gọi đệ quy g [11]. ng gian tìm k ần phải cải th ần nhất bằng p ật toán vét cạ ] [19] [23] [2 truy vấn đế nh toán được của CUDA trình viên tro h toàn tuần tự với bộ cấp ph Ồ THỊ BT-G BT-Graph dự aph (Search b hất được áp d rí địa lý (bẫy được bắt đầ t thực hiện m hợp một nếu hai nếu B là n thuật toán tì iếm mở rộng iện tốc độ tìm hương pháp n áp dụng cho 5] và được c n tất cả các đ theo thứ tự tă ng việc phát t sẽ được thực át bộ nhớ RAPH DỰA a trên CUDA ased on BT- ụng trên hệ t đèn), Q chứa u từ nút gốc, ột trong ba trư khoảng cách út lá, duyệt q m kiếm cho h thì cần cải th kiếm. Vì vậ song song hóa tìm kiếm k- ài đặt với hai iểm trong tập ng dần và chọ riển các thuật thi trên CPU TRÊN CUD Graph, viết t hống mạng c các điểm láng trong suốt qu ờng hợp, cu từ điểm truy ua tất cả các đ ai nút con củ iện tốc độ tìm y, chúng tôi đ . láng giềng dự module chín dữ liệu – Th n ra k-khoản 73 toán song , trong khi A ắt là BTS) ác bẫy đèn giềng của á trình tìm ối cùng trả vấn q đến iểm x ∈ B a B là con kiếm của ề xuất hai a trên nền h. Module ực hiện tại g cách nhỏ 7 C th B t x t đ b 4 Trường UDA xử lý [ uật 2. . Thuật toán Thuật t ìm kiếm đườn ây dựng trên oán. Có hai n ược đánh dấu ản: khởi tạo ( Giải th 1. 2. 3. 4. 5. 6. 7. 8. hợp hai chún 4]. Phương ph Hìn Giải thuật 2 / 1. T 2. T 3. S / 4. V 5. T 6. T 7. S tìm kiếm đư oán Dijkstra [ g đi sao cho c cơ sở gán cho hãn là cố định là nhãn cố đị Initialization) CẢI THIỆN uật 1: BF-kN //Xử lý tại Nạp dữ liệu Thiết lập ch Sao chép dữ //Xử lý tại G Tính toán k Sao chép dữ //Xử lý tại C Sắp xếp các Lấy ‘k’ kho Giải phóng g tôi đề xuất áp này chúng h 4. BTSCUD : BTSCUDA /Xử lý tại CP ạo cấu trúc c ạo mảng chứ ao chép cây /Xử lý tại GP ới mỗi điểm ìm kiếm trên rả kết quả là ao chép kết q ờng đi ngắn n 5] [26] là thu hi phí duyệt t các đỉnh của và tạm thời nh sẽ cho kết , tìm giá trị nh TỐC ĐỘ TÌM NCUDA CPU vào bộ nhớ d ỉ số k liệu từ CPU PU hoảng cách từ liệu từ GPU PU khoảng cách ảng cách đầu bộ nhớ CUD với mỗi lần t tôi gọi là BT A với mỗi đi U ây T a các điểm tru T và mảng qA U truy vấn cây T với ph danh sách k-l uả tất cả danh hất của mô h ật toán tìm k ừ đỉnh bắt đầ đồ thị các nh . Ở mỗi bước quả là đường ỏ nhất (Extra KIẾM CỦA MÔ ùng chung vào GPU điểm truy vấ về CPU tính được the tiên thể hiện A hực hiện BTS SCUDA. Ý t ểm truy vấn s y vấn qArrra rrray từ CPU ương pháp BF áng giềng gần sách k-láng ình đồ thị B iếm đường đi u đến đỉnh kết ãn tạm thời. C lặp sẽ thay đ đi ngắn nhất ct_Min) và cậ HÌNH ĐỒ THỊ B n q đến tất cả o thứ tự tăng cho các điểm trên một điể ưởng thuật to ẽ do một luồn y vào GPU S nhất của mỗ giềng tìm đượ T-Graph dựa ngắn nhất bằ thúc là nhỏ n ác nhãn này ổi một nhãn t từ đỉnh tới nú p nhật giá trị T-GRAPH DỰA điểm v ∈ V dần gần nhất m truy vấn th án được thể h g trong CUD i điểm truy vấ c từ GPU về trên CUDA ng phương p hất. Thuật to được thay đổ ạm thời thành t đó. Thuật to (UpdateCost) TRÊN NỀN TẢ ì sẽ do một lu iện trong hìn A xử lý n CPU háp duyệt qu án Dijkstra tu i theo mỗi bư nhãn cố địn án bao gồm b . NG CUDA ồng trong h 4 và giải a đồ thị và ần tự được ớc lặp tính h. Một nút a bước cơ L lu U ương Hoàng Hướ Để son ồng trong CU pdateCost đư H Quá trìn ng, Nguyễn Hải g song hóa th DA. Quá trì ợc cài đặt bằn ình 5. Lưu đ h cấp phát bộ Thanh, Huỳnh X Giải thuậ 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. uật toán Dijk nh xử lý song g CUDA. ồ song song t nhớ GPUs c Hình 6. Cấp uân Hiệp t 3: Thuật to //Initial foreach v ∈ d[v end d[S] Q ← while Q ≠ ∅ //Extract_ u ← { v: v if (d[u] = break; Remove u //UpdateC foreach (u if ((d[u d[v] end end stra, chúng tô song được th huật toán Dijk ho các cạnh c phát bộ nhớ l án Dijkstra V do ] ← ∞ ← 0 V do Min ∈ Q ^ ∀w ∈ ∞) then from Q ost , v) ∈ V do ] + c(u, v)) < d ← d[u] + c(u, i đề xuất mỗ ể hiện như lư stra trên mô h ủa đồ thị BT- ưu trữ cho mô Q, d[v] ≤ d[w [v]) then v) i cạnh của đồ u đồ ở hình 5 ình đồ thị BT Graph được th hình đồ thị B ] } thị BT-Grap . Trong đó, h -Graph sử dụ ể hiện như hì T-Graph h sẽ tương ứn ai bước Extra ng CUDA nh 6. 75 g với một ct_Min và 76 CẢI THIỆN TỐC ĐỘ TÌM KIẾM CỦA MÔ HÌNH ĐỒ THỊ BT-GRAPH DỰA TRÊN NỀN TẢNG CUDA Thuật toán Dijkstra cài đặt với CUDA (gọi tắt là DijkstraCUDA) được thể hiện như sau: Giải thuật 4: Thuật toán DijkstraCUDA Bước 1: 1. Khởi tạo ma trận trọng số, điểm bắt đầu và kết thúc Bước 2: 2. Cấp phát bộ nhớ trong CUDA tương ứng với số cạnh của mô hình đồ thị BT-Graph Bước 3: 3. Sao chép dữ liệu từ CPU sang GPU Bước 4: 4. Tìm kiếm đỉnh u tự do sao cho chi phí đi từ đỉnh xuất phát S đến u là nhỏ nhất 5. Nếu không tìm thấy u thỏa điều kiện trên thì thoát: + Hoặc là tìm thấy đường đi. + Hoặc không tìm thấy đường đi. 6. Nếu tìm thấy đỉnh u thỏa điều kiện, dùng đỉnh u xét các đỉnh tự do khác. 7. Dùng CUDA để cấp các luồng cho việc thực hiện tính toán giữa đỉnh u và các đỉnh còn lại. Bước 5: 8. Sao chép dữ liệu từ GPU về CPU Bước 6: 9. Giải phóng CUDA IV. THỰC NGHIỆM Trong phần thực nghiệm này chúng tôi tiến hành so sánh tốc độ tìm kiếm trên mô hình đồ thị BT-Graph giữa thuật toán tuần tự trên CPU và thuật toán song song trên CUDA. Máy tính được sử dụng cho phần thực nghiệm này là Desktop (Intel Core i3-3220 3.3 GHz, bộ nhớ 4GB DDR3, card đồ họa NVIDIA GeForce GTX 660 với bộ nhớ 2GB GDDR5) chạy hệ điều hành Ubuntu 14.04 64 bits. A. Dữ liệu thực nghiệm Dữ liệu sử dụng cho thực nghiệm được chia làm hai loại, loại một dùng cho thực nghiệm tìm kiếm k-láng giềng và loại hai dùng cho tìm kiếm đường đi ngắn nhất Dijkstra. Các dữ liệu được sinh ra ngẫu nhiên từ chương trình thực nghiệm. Cấu trúc thông tin của dữ liệu loại một bao gồm hai danh sách. Danh sách thứ nhất chứa các điểm dữ liệu ban đầu gồm ba cột và số dòng là tùy chọn. Mỗi dòng mô tả thông tin một điểm dữ liệu. Cột một chứa tên của điểm dữ liệu, cột hai chứa giá trị x trong không gian hai chiều và cột ba chứa giá trị y trong không gian hai chiều. Danh sách thứ hai chứa các điểm truy vấn cũng gồm ba cột và số dòng là tùy chọn. Mỗi dòng mô tả thông tin một điểm truy vấn. Cột một chứa tên của điểm dữ liệu, cột hai và cột ba chứa giá trị x và y trong không gian hai chiều. Cấu trúc thông tin của dữ liệu loại hai dùng để mô tả số đỉnh, cạnh và thông tin các cạnh của mô hình đồ thị BT- Graph. Dòng thứ nhất chứa hai giá trị, số đỉnh và số cạnh của mô hình đồ thị BT-Graph. Các dòng còn lại, mỗi dòng chứa ba giá trị - đỉnh đầu, đỉnh cuối và trọng số của cạnh được tạo bởi hai đỉnh đó. B. Công cụ thực nghiệm và phương pháp thực nghiệm Trong thực nghiệm này, chúng tôi đã xây dựng một công cụ dựa trên nền tảng NetGen [14] với tên gọi là: GLS (Geographical Location Search) [11], cho phép xây dựng mô hình đồ thị BT-Graph [28] dựa trên tập dữ liệu cho trước. Ngoài ra, chương trình còn cho phép tính toán, thực thi chương trình CUDA thông qua thư viện DLL&C của Smalltalk và so sánh thời gian thực thi của các thuật toán. Trong cùng một thuật toán và một tập dữ liệu, chúng tôi tiến hành thực thi chương trình nhiều lần và lấy kết quả trung bình về thời gian thực thi của thuật toán đó nhằm mục đích để thu được kết quả tương đối chính xác. C. So sánh hiệu suất của thuật toán tìm kiếm k-láng giềng Yêu cầu đặt ra cho phần thực nghiệm này là so sánh được tốc độ tìm kiếm của thuật toán kNN truyền thống [11] trên mô hình đồ thị BT-Graph và thuật toán kNN dựa trên CUDA [26]. Thực nghiệm được tiến hành trên tập dữ liệu được mô tả như trong phần dữ liệu thực nghiệm. Chúng tôi tiến hành thực thi chương trình 10 lần trên mỗi thuật toán và lấy giá trị trung bình theo thời gian thực thi. Kết quả thực nghiệm của chương trình sau khi đã lấy trung bình được thể hiện như trong bảng 1. Trong đó, N là số lượng điểm dữ liệu ban đầu, Q là số lượng điểm truy vấn. Lương Hoàng Hướng, Nguyễn Hải Thanh, Huỳnh Xuân Hiệp 77 Bảng 1. Bảng so sánh tốc độ thực thi của các thuật toán (Đơn vị tính bằng mili giây) N =10000 với Q= 10000 N = 100000 với Q=100000 kNN BT-Graph 179.46 17898.13 BF-kNNCUDA 123.47 5440.29 BTSCUDA 1.12 53.478 Hình 7. Biểu đồ so sánh tốc độ thực thi của ba thuật toán Dựa vào bảng thực nghiệm 1 và biểu đồ so sánh ở hình 7, chúng ta thấy rằng thuật toán BF-kNNCUDA cải thiện tốc độ tìm kiếm hơn gấp khoảng 2.37 lần so với thuật toán kNN BT-Graph. Trong khi đó thuật toán BTSCUDA cải thiện tốc độ gấp khoảng 247.46 lần so với thuật toán kNN BT-Graph và cải thiện tốc độ gấp khoảng 105.98 lần so với BF-kNNCUDA. D. So sánh hiệu suất của thuật toán tìm kiếm đường đi ngắn nhất Yêu cầu đặt ra cho phần thực nghiệm này là so sánh được tốc độ tìm kiếm của thuật toán Dijkstra truyền thống trên mô hình đồ thị BT-Graph và thuật toán DijkstraCUDA. Trong phần này, chúng tôi vẫn tiến hành thực thi chương trình 10 lần cho từng thuật toán và sau đó lấy kết quả trung bình trên tổng số lần thực thi đó. Dữ liệu đầu vào là tập dữ liệu được mô tả như trong phần dữ liệu thực nghiệm. Sau đó xây dựng ma trận trọng số trên mô hình đồ thị BT-Graph. Tiến hành tìm kiếm trên ma trận trọng số đó bằng hai phương pháp: tuần tự và song song với CUDA. Kết quả đầu ra của chương trình là thời gian thực thi của hai phương pháp. Kết quả thực nghiệm với số lượng đỉnh của đồ thị khác nhau được thể hiện như bảng 2. Bảng 2. Thể hiện kết quả thực nghiệm của hai thuật toán (Đơn vị tính là mili giây) 1000 3000 5000 7000 9000 11000 13000 15000 Dijkstra 47 413 1116 2173 3641 5422 7545 10111 DijkstraCUDA 189 753 1498 2120 3130 4338 5414 7118 Hình 8. Biểu đồ so sánh tốc độ thực thi của thuật toán Dijkstra trên CPU và GPU Từ bảng thực nghiệm 2 và biều đồ so sánh thuật toán Dijkstra trên CPU và GPU trong hình 8, ta thấy khi số lượng đỉnh trong một đồ thị nhỏ và nằm trong khả năng xử lý của CPU thì khi đó CPU sẽ có thời gian thực thi nhanh hơn so với GPU. Nguyên nhân là do phải sao chép dữ liệu từ CPU sang GPU và tiến hành xử lý tính toán sau đó sao chép kết quả 0 5000 10000 15000 20000 N= 10000 và Q=10000 N=100000 và Q=100000 So sánh tốc độ thực thi của ba thuật toán kNN BT-Graph BF-kNNCUDA BTSCUDA 0 5000 10000 15000 So sánh thời gian thực thi của thuật toán Dijkstra trên CPU và GPU Dijkstra DijkstraCUDA 78 CẢI THIỆN TỐC ĐỘ TÌM KIẾM CỦA MÔ HÌNH ĐỒ THỊ BT-GRAPH DỰA TRÊN NỀN TẢNG CUDA ngược về GPU. Tuy nhiên, khi số lượng đỉnh của một đồ thì đủ lớn, thì chúng ta có thể thấy thời gian xử lý của GPU được cải thiện đáng kể. Cụ thể như trong như trong bảng 2 và hình 8, khi số lượng đỉnh nhỏ hơn 9000 thì CPU xử lý nhanh hơn GPU. Nhưng khi số lượng đỉnh đủ lớn (lớn hơn 9000) thì tốc độ của GPU nhanh hơn so với CPU. V. KẾT LUẬN BT-Graph (Graph Model based on Ball Tree Structure) [11] là một mô hình đồ thị được xây dựng dựa trên cấu trúc balltree, giúp mô hình hóa hệ thống mạng giám sát các bẫy đèn tự động và hỗ trợ tìm kiếm vị trí địa lý. Khi số lượng vị trí địa lý lớn và không gian địa lý tìm kiếm mở rộng thì cần phải cải thiện tốc độ tìm kiếm của mô hình đồ thị BT-Graph. Chính vì vậy chúng tôi đã đề xuất một hướng tiếp cận mới trong cải thiện tốc độ tìm kiếm của mô hình đồ thị BT-Graph bằng phương pháp song song hóa dựa trên nền tảng CUDA. Trên nền tảng CUDA, chúng tôi đã tiến hành song song hóa hai thuật toán tìm kiếm của mô hình đồ thị BT- Graph – BF-kNNCUDA, BTSCUDA và DijkstraCUDA. Từ đó, công cụ GLS được tạo ra nhằm xây dựng mô hình đồ thị BT-Graph, đồng thời cho phép tính toán hiệu suất hoạt động của các thuật toán và đưa ra kết quả so sánh. Kết quả thực nghiệm cho thấy việc song song hóa thuật toán tìm kiếm của mô hình đồ thị BT-Graph cho một kết quả tốt về thời gian tìm kiếm. Trong thời gian tới, chúng tôi sẽ tiến hành song song hóa toàn bộ quá trình xây dựng mô hình đồ thị BT-Graph nhằm tiếp tục cải thiện tốc độ trong toàn bộ quá trình xây dựng mô hình. VI. TÀI LIỆU THAM KHẢO [1] Andrew O. Finley, Ronald E. McRoberts, “Efficient k-nearest neighbor searches for multi-source forest attribute mapping”, Remote Sesing of Environment (Volume 112, Issue 5), pp. 2203-2211, 2008. [2] Carlo del Mundo, Mariam Umar, “A Mixed Hierarchical Algorithm for Nearest Neighbor Search”, 2013. [3] Deepika Verma, Namita Kakkar, Neha Mehan, “Comparison of Brute-Force and K-D tree Algorithm”, International Journal of Advanced Research in Computer and Communication Engineering (Volume 3, Issue 1), 2014. [4] Dr. Mohammed Otair, “APPROXIMATE K-NEAREST NEIGHBOUR BASED SPATIAL CLUSTERING USING K-D TREE”, Internaltional Journal of Database Management Systems (Volume 5, Issue 1), pp. 97, 2013. [5] E. W. Dijkstra, “A note on two problems in connexion with graphs”, Numerische Mathematik (volume 1, Issue 1), pp. 269-271, 1959. [6] Ebook: CUDA, [7] Fabian Gieseke, Justin Heinermann, Cosmin Oancea, Christian Igel, “Buffer k-d Trees: Processing Massive Nearest Neighbor Queries on GPUs”, Proceeding of The 31st Internaltional Conference on Machine Learning, pp. 172-180, 2014. [8] Graham Nolan, “Improving the k-Nearest neighbour Algorithm with CUDA”, Technical report, School of CSSE, The University of Western Australia, 2009. [9] Gunjan Singla, Amrita Tiwari, Dhirendra Pratap Singh, “New Approach for Graph Algorithms on GPU using CUDA”, Internaltion Journal of Computer Application (Volume 72, Issue 18), pp. 38-42, 2013. [10] Kimikazu Kato, Tikara