Bài viết 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 đề xuất một hướng tiếp cận mới trong việc 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 tìm kiếm dựa trên nền tảng CUDA. | Kỷ yếu Hội nghị Q K Quốc gia lần thứ VIII về Nghiên cứ cơ bản và ứng dụng Công nghệ thông tin (FAIR) Hà Nội, ngày 9 ứu ệ ); 9-10/7/2015 CẢI T THIỆN TỐ ĐỘ T KIẾM CỦA MÔ HÌNH Đ THỊ B T-GRAP ỐC TÌM M Ô ĐỒ PH DỰA TRÊN NỀN TẢN CUDA A NG A Lư ương Hoàng Hướng1, Ngu uyễn Hải Tha 2, Huỳnh X anh Xuân Hiệp3 1 Trung tâm Công ngh phần mềm, Đại học Cần Thơ hệ 2 Vụ K Khoa học, Công nghệ và Môi trường, Bộ Giáo dục và Đ tạo Việt N g G Đào Nam 3 Khoa Công nghệ thông tin và Truyền thông, Nhóm nghiên cứu li ngành DR g n m iên REAM-CTU/IR Đại học Cần Thơ RD, C lhhuong g@, nhthanh@{, mo }, h hxhiep@ TÓM TẮ - BT-Graph (Graph Model based on Ball Tree Structure) là một mô hìn đồ thị được x dựng dựa tr cấu trúc ẮT h l ) nh xây rên balltree, giúp mô hình hóa hệ t b thống mạng giá sát các bẫy đèn tự động và hỗ trợ tìm kiếm vị trí địa lý. K số lượng vị trí địa lý lớn ám đ m Khi t và không gian đ lý tìm kiếm mở rộng thì cần phải cải thi tốc độ tìm kiếm của mô hì đồ thị BT-G v địa iện k ình Graph. Trong bài viết này, b chúng tôi đề xuấ một hướng tiế cận mới tron việc cải thiện tốc độ tìm kiếm của mô hình đồ thị BT-Grap bằng phương pháp song c ất ếp ng n ếm ph g song hóa thuật toán tìm kiếm dựa trên nền t s tảng CUDA NV VIDIA. Các thự nghiệm được triển khai trê hai thuật toá tìm kiếm ực ợc ên án k-láng giềng gần nhất và tìm k k kiếm đường đi n ngắn nhất dựa trên mô hình đồ thị BT-Graph và cho thấy sự cải thiện tốt về thời gian đ h ự tì kiếm. ìm Từ khóa - CUDA, BT-G a Graph, vị trí địa lý, mạng giám sát bẫy đèn tự động, song son a m ự ng. I. GIỚI THIỆU G U BT-Gra (Graph M aph Model based on Ball Tree St n tructure) [11] là một mô hìn đồ thị được xây dựng dự trên cấu nh c ựa tr balltree [2 [11]. BT-G rúc 21] Graph không c giúp mô hình hóa hệ th chỉ h hống mạng giá sát các bẫy đèn tự động bằng cách ám y đề xuất bán kín hoạt động cho các cảm b tự động, mà còn hỗ trợ tìm kiếm vị tr địa lý [11]. Tuy nhiên, kh số lượng đ nh biến m ợ trí hi tốc vị trí địa lý
