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

Abstract

BT-Graph (Graph Model based on Ball Tree Structure) 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. Trong bài viết này, chúng tôi đề 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 thuật toán tìm kiếm dựa trên nền tảng CUDA NVIDIA. Các thực nghiệm được triển khai trên hai thuật toán tìm kiếm
k-láng giềng gần nhất và tìm kiếm đường đi 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 tìm kiếm.