ĐÁNH GIÁ CÁC GIAO THỨC CÂY TRUY VẤN DỰA TRÊN TRI THỨC VỚI CÁC PHÂN BỐ THẺ RFID KHÁC NHAU

jos.hueuni.edu.vn Tập 134, Số 2A, 2025 121 (a) (b) Hình 1. So sánh số khe xung đột của các thuật toán QT, KQT, HQT, QTKS và QTKS_TE: (a) phân bố đồng nhất; (b) phân bố không đồng nhất Kết quả cho thấy các thuật toán cây truy vấn dựa trên tri thức luôn tạo ra số khe xung đột thấp hơn so với QT, nhờ khai thác “tri thức” về cơ sở dữ liệu thẻ, miền phân bố và số lượng thẻ mà đầu đọc có được, qua đó tránh được nhiều nút xung đột khi duyệt cây. Trong nhóm này, QTKS_TE đạt số khe xung đột thấp nhất, đặc biệt hiệu quả khi số thẻ xuất hiện xấp xỉ số thẻ trong cơ sở dữ liệu, do vừa xây dựng cây truy vấn trên cơ sở dữ liệu thẻ, vừa ước tính được số thẻ cần truy vấn; mức “tri thức” càng cao thì truy vấn càng hiệu quả. Tuy nhiên, khi so sánh hai dạng phân bố, QTKS_TE có thể tạo ra số khe xung đột khá cao trong một số trường hợp phân bố không đồng nhất. Hiệu suất của QTKS_TE phụ thuộc chặt chẽ vào cấu trúc cây được xây dựng và vị trí thực tế của các thẻ xuất hiện trong vùng đọc; nếu phân bố thẻ buộc thuật toán phải duyệt qua hầu hết các nút của cây để truy vấn hết thẻ, số khe xung đột của QTKS_TE sẽ khó được giảm xuống. 3.2 So sánh số khe nhàn rỗi Đối với các cải tiến của thuật toán QT được công bố trước đây, việc giảm số khe xung đột thường đi kèm với việc tăng số khe nhàn rỗi (idle slots). Tuy nhiên, với các thuật toán dựa trên tri thức, số khe nhàn rỗi có xu hướng biến thiên khác nhau, như thể hiện ở Hình 2. KQT có số khe nhàn rỗi cao hơn QT. Về bản chất, KQT thực hiện QT độc lập trên từng khoảng được chia. Nếu việc chia khoảng chính xác (mỗi khoảng xấp xỉ có một thẻ), KQT đạt hiệu

quả tốt; ngược lại, khi một khoảng không chứa thẻ nào hoặc chứa nhiều hơn một thẻ, KQT lại hoạt động tương tự QT trong khoảng đó, dẫn đến xuất hiện thêm các khe nhàn rỗi so với QT. Đối với HQT, do lựa chọn bit truy vấn “tốt nhất” dựa trên entropy, hầu như không xuất hiện khe nhàn rỗi.