I. Giới thiệu đề tài
Luận văn tập trung nghiên cứu cấu trúc chỉ mục TS-Tree áp dụng cho dữ liệu chuỗi thời gian với độ đo xoắn thời gian động (DTW). Dữ liệu chuỗi thời gian đóng vai trò quan trọng trong nhiều lĩnh vực như khoa học, kinh tế và tài chính. Bài toán tìm kiếm tương tự trên dữ liệu chuỗi thời gian đòi hỏi các cấu trúc chỉ mục hiệu quả để tăng tốc độ truy xuất và độ chính xác. Các cấu trúc chỉ mục truyền thống như R-Tree* có hạn chế khi xử lý dữ liệu nhiều chiều và sử dụng độ đo Euclid. TS-Tree được đề xuất như một giải pháp tối ưu, kết hợp với độ đo DTW để cải thiện hiệu suất tìm kiếm.
1.1. Mục tiêu nghiên cứu
Mục tiêu chính của luận văn là nghiên cứu và so sánh hiệu quả của cấu trúc chỉ mục TS-Tree với R-Tree* khi áp dụng độ đo DTW. TS-Tree được kỳ vọng sẽ cải thiện tốc độ tìm kiếm và độ chính xác trong bài toán tìm kiếm tương tự trên dữ liệu chuỗi thời gian.
1.2. Phạm vi nghiên cứu
Luận văn giới hạn nghiên cứu trong việc áp dụng độ đo DTW và các kỹ thuật như PAA để thu giảm số chiều dữ liệu. Các cấu trúc chỉ mục được so sánh là R-Tree* và TS-Tree, với mục đích đánh giá hiệu quả trong bài toán so trùng mẫu.
II. Cơ sở lý thuyết
Luận văn trình bày các lý thuyết nền tảng về dữ liệu chuỗi thời gian, độ đo DTW, và các cấu trúc chỉ mục như R-Tree* và TS-Tree. Độ đo DTW là phương pháp tính khoảng cách linh hoạt, phù hợp với dữ liệu chuỗi thời gian có chiều dài khác nhau. R-Tree* là cấu trúc chỉ mục không gian phổ biến, nhưng có hạn chế khi xử lý dữ liệu nhiều chiều. TS-Tree được thiết kế để khắc phục các hạn chế này, đặc biệt khi kết hợp với độ đo DTW.
2.1. Dữ liệu chuỗi thời gian
Dữ liệu chuỗi thời gian là chuỗi các giá trị được ghi nhận theo thời gian, thường xuất hiện trong các ứng dụng như y tế, tài chính và năng lượng. Đặc điểm chính của dữ liệu chuỗi thời gian là tính nhiều chiều và độ dài biến đổi.
2.2. Độ đo DTW
Độ đo DTW cho phép tính khoảng cách giữa hai chuỗi thời gian có độ dài khác nhau bằng cách tìm đường xoắn tối ưu. Phương pháp này phù hợp với dữ liệu chuỗi thời gian vì nó linh hoạt trong việc so sánh các mẫu có hình dạng tương tự nhưng khác biệt về thời gian.
III. Cấu trúc chỉ mục TS Tree
TS-Tree là cấu trúc chỉ mục được thiết kế để hỗ trợ hiệu quả bài toán tìm kiếm tương tự trên dữ liệu chuỗi thời gian. TS-Tree sử dụng các thành phần như separators và quantization để tổ chức dữ liệu. Cấu trúc này cho phép tăng tốc độ tìm kiếm và cải thiện độ chính xác khi kết hợp với độ đo DTW.
3.1. Thành phần của TS Tree
TS-Tree bao gồm các thành phần như separators để phân tách dữ liệu và quantization để rời rạc hóa dữ liệu. Các thành phần này giúp tối ưu hóa quá trình tìm kiếm và lưu trữ dữ liệu.
3.2. Thao tác trong TS Tree
Các thao tác chính trong TS-Tree bao gồm chèn, xóa và tìm kiếm. TS-Tree được thiết kế để hỗ trợ các thao tác này một cách hiệu quả, đặc biệt khi áp dụng độ đo DTW.
IV. Thực nghiệm và đánh giá
Luận văn tiến hành thực nghiệm để so sánh hiệu quả của TS-Tree và R-Tree* khi áp dụng độ đo DTW. Kết quả thực nghiệm cho thấy TS-Tree có hiệu suất vượt trội trong việc tăng tốc độ tìm kiếm và cải thiện độ chính xác. Các bộ dữ liệu được sử dụng bao gồm dữ liệu chứng khoán, năng lượng và điện não đồ.
4.1. Kết quả thực nghiệm
Kết quả thực nghiệm cho thấy TS-Tree có thời gian lập chỉ mục và truy vấn nhanh hơn so với R-Tree*. Đặc biệt, TS-Tree giảm đáng kể số lần truy xuất nút trong quá trình tìm kiếm.
4.2. Đánh giá hiệu quả
TS-Tree được đánh giá là cấu trúc chỉ mục hiệu quả hơn trong việc xử lý dữ liệu chuỗi thời gian nhiều chiều và áp dụng độ đo DTW. Kết quả này mở ra hướng nghiên cứu mới trong việc cải tiến các cấu trúc chỉ mục cho dữ liệu chuỗi thời gian.
V. Kết luận và hướng phát triển
Luận văn kết luận rằng TS-Tree là cấu trúc chỉ mục hiệu quả cho bài toán tìm kiếm tương tự trên dữ liệu chuỗi thời gian khi áp dụng độ đo DTW. TS-Tree không chỉ cải thiện tốc độ tìm kiếm mà còn nâng cao độ chính xác so với R-Tree*. Hướng phát triển tiếp theo là nghiên cứu các phương pháp tối ưu hóa TS-Tree và áp dụng vào các ứng dụng thực tế.
5.1. Kết quả đạt được
Luận văn đã nghiên cứu và so sánh thành công hiệu quả của TS-Tree và R-Tree* trong bài toán tìm kiếm tương tự trên dữ liệu chuỗi thời gian.
5.2. Hướng phát triển
Hướng phát triển tiếp theo bao gồm tối ưu hóa TS-Tree và áp dụng vào các lĩnh vực như y tế, tài chính và năng lượng để khai thác tiềm năng của dữ liệu chuỗi thời gian.
