Tóm tắt Luận án Một số kỹ thuật dự báo vị trí và truy vấn các đối tượng chuyển động trong cơ sở dữ liệu không gian-thời gian

rả lời truy vấn một cách chính xác. 1.2.3. Vấn đề về lập chỉ mục Số lượng các đối tượng chuyển động trong CSDL có thể rất lớn. Do vậy chúng ta cần phải lập chỉ mục cho thuộc tính vị trí. Việc sử dụng cách lập chỉ mục trực tiếp cho thuộc tính không gian như thông thường là không thể được do việc thay đổi liên tục giá trị của thuộc tính này sẽ dẫn đến cũng phải lập lại chỉ mục cho nó một cách liên tục. 1.2.4. Vấn đề về tính không chắc chắn/không chính xác Vị trí của đối tượng chuyển động trong CSDL về cơ bản là không chính xác với vị trí thực tế của nó bất kể chính sách cập nhật vị trí của đối tượng vào CSDL. Tính không chắc chắn vốn có này có ý nghĩa khác nhau cho mô hình cơ sở dữ liệu, truy vấn và lập chỉ mục. Vì sự không chắc chắn trong cơ sở dữ liệu vị trí, sẽ có thêm hai kiểu ngữ nghĩa trong truy vấn là “CÓ THỂ” và “CHẮC CHẮN”. Dù tính không chắc chắn đã được nghiên cứu rộng rãi, việc xây dựng mô hình mới và khả năng không gian-thời gian cho các đối tượng chuyển động vẫn cần phải xem xét lại các giải pháp hiện có. Kết luận chương Chương 1 đã giới thiệu các vấn đề cơ bản về CSDL các đối tượng chuyển động. MODB là dạng thu gọn của CSDL không gian-thời gian, trong đó chỉ quan tâm đến các điểm chuyển động mà không xét đến các đối tượng khác. Các vấn đề còn tồn tại cần giải quyết trong CSDL các đối tượng chuyển động cũng được tổng hợp lại. Các chương tiếp theo nghiên cứu sinh sẽ trình bày các nghiên cứu của mình, góp phần giải quyết một số vấn đề này. 8 Chương 2. DỰ ĐOÁN VỊ TRÍ CỦA ĐỐI TƯỢNG CHUYỂN ĐỘNG Trong chương này, nghiên cứu sinh sẽ trình bày hai phương pháp dự đoán vị trí của đối tượng chuyển động, được đề xuất nhằm góp phần giải quyết vấn đề mô hình hóa vị trí trong MODB. Phương pháp thứ nhất là dự đoán vị trí theo hàm chuyển động chỉ hiệu quả với dự đoán ở tương lai gần. Phương pháp thứ hai là dự đoán theo hành vi của đối tượng tiếp cận theo hướng sử dụng khai phá luật kết hợp của các mẫu hình di chuyển của đối tượng, dự đoán được vị trí ở những thời điểm xa hiện tại với độ chính xác tương đối cao. Kết hợp hai phương pháp này sẽ đem lại hiệu quả tốt hơn cho truy vấn trong toàn hệ thống. 2.1. Dự đoán vị trí của đối tượng dựa theo hàm chuyển động Các hàm chuyển động có thể chia thành hai dạng sau: - Hàm tuyến tính: mô tả chuyển động theo đường thẳng - Hàm phi tuyến: mô tả chuyển động theo đường cong bất kỳ 2.1.1. Dự đoán dựa theo hàm tuyến tính Cho một đối tượng có vị trí l0 tại thời điểm t0 có vận tốc v0. Mô hình chuyển động tuyến tính sẽ dự đoán vị trí của đối tượng tại thời điểm tq bởi biểu thức: l(tq)=l0 + v0 * (tq-t0) trong đó l và v là các véc-tơ n chiều Với mô hình tuyến tính, việc tính toán vị trí của đối tượng chuyển động ở thời điểm tiếp theo rất nhanh chóng. Tuy nhiên, với nhiều bài toán thực tế, độ chính xác này thường không cao do đối tượng có thể di chuyển trong mạng lưới giao thông đô thị phức tạp và có rất nhiều yếu tố ảnh hưởng đến véc tơ vận tốc (độ lớn và hướng) của đối tượng. 2.1.2. Dự đoán dựa theo hàm phi tuyến Trong thực tế, chuyển động của các đối tượng thường là phi tuyến. Với mô hình này, chuyển động của đối tượng được biểu diễn bởi các 9 hàm toán học phức tạp hơn vì vậy độ chính xác dự đoán sẽ cao hơn mô hình tuyến tính. Hàm chuyển động đệ quy và ma trận chuyển động Sử dụng hàm chuyển động đệ quy là phương pháp dự đoán vị trí từ những vị trí trước đó trong quá khứ. Phương pháp này biểu diễn vị trí l của đối tượng tại thời điểm t (ký hiệu lt) dưới dạng biểu thức sau: 𝑙𝑡 = ∑𝑐𝑖 ∗ 𝑙𝑡−𝑖 𝑓 𝑖=1 trong đó ci là ma trận hệ số và f là số tối thiểu các vị trí gần nhất để tính được các phần tử của tất cả ci. Xét đối tượng O trong không gian n chiều. Tại thời điểm ti và ti+1 (0 < i < q), q là thời điểm truy vấn, vị trí của O được biểu diễn lần lượt bởi các véc tơ Pi và Pi+1 như sau: 𝑃𝑖⃗⃗ = (𝑝𝑖,1, 𝑝𝑖,2, , 𝑝𝑖,𝑛) và 𝑃𝑖+1⃗⃗ ⃗⃗ ⃗⃗ ⃗⃗ = (𝑝𝑖+1,1, 𝑝𝑖+1,2, , 𝑝𝑖+1,𝑛) Véc tơ dịch chuyển của O từ thời điểm ti đến ti+1, ký hiệu 𝑖⃗⃗⃗ , được mô tả như sau: 𝑖⃗⃗⃗ = (𝑖,1, 𝑖,2, , 𝑖,𝑛) = 𝑃𝑖+1⃗⃗ ⃗⃗ ⃗⃗ ⃗⃗ − 𝑃𝑖⃗⃗ Do đó muốn tính 𝑃𝑖+1⃗⃗ ⃗⃗ ⃗⃗ ⃗⃗ ta cần xác định véc tơ dịch chuyển 𝑖⃗⃗⃗ . Có một số kỹ thuật dự đoán theo hàm chuyển động đệ quy hay được sử dụng như SMA và EWMA. Chúng sử dụng các vị trí trong quá khứ của đối tượng để xác định véc tơ dịch chuyển, từ đó dự đoán vị trí của đối tượng ở các thời điểm tiếp theo. Kỹ thuật dự đoán theo trung bình động đơn giản - SMA Biểu thức tính i,k theo SMA (Simple Moving Average) như sau: Kỹ thuật dự đoán theo trung bình động trọng số mũ - EWMA 10 Biểu thức tính EWMA như sau: Kỹ thuật dự đoán vị trí đối tượng theo mô hình W-EWMA Nhằm làm giảm khối lượng tính toán không cần thiết, nghiên cứu sinh đề xuất kỹ thuật dự đoán đặt tên là W-EWMA (Window Exponentially Weighted Moving Average). Theo kỹ thuật này thay vì tính tất cả các j,k, chỉ tính w bước gần nhất trước đó. Biểu thức (2-10) tính W-EWMA như sau: Giải thuật tính toán theo kỹ thuật W-EWMA như dưới đây: Algorithm Cal_W-EWMA Input: 𝑃𝑖 = {𝑝𝑖,1, 𝑝𝑖,2, , 𝑝𝑖,𝑛} Output: 𝑃𝑖+1 = {𝑝𝑖+1,1, 𝑝𝑖+1,2, , 𝑝𝑖+1,𝑛} 1. w ← a; ← b // initialization w 2. Sd = 0; Sa = 0 // initialization Sd, Sa 3. FOR EACH pi,k IN Pi 4. FOR j = i-w to i-1 // windowed 5. j,k = pj,k – pj-1,k calculate  6. Sd ← Sd + i-1-j * j,k 7. Sa ← Sa + i-1-j 8. END FOR 9. pi+1,k = pi,k + Sd/Sa 10. END FOR 11. 𝑃𝑖+1 ← {𝑝𝑖+1,1, 𝑝𝑖+1,2, , 𝑝𝑖+1,𝑛} 12. RETURN Pi+1 Algorithm End. 11 Trong kỹ thuật này, độ phức tạp thuật toán là O(n*w), với n là số chiều của không gian dữ liệu, w là hằng số xác định trước bằng công thức (2-10a) w = S/(v*f), Trong đó S là độ dài trung bình của các tuyến đường trên bản đồ (m), v là vận tốc di chuyển trung bình (m/s), f là tần suất cập nhật dữ liệu (s). Các kết quả thực nghiệm trên cho thấy, kỹ thuật dự đoán vị trí của đối tượng theo mô hình W-EWMA cho kết quả khá chính xác với thời gian tính toán nhanh hơn theo mô hình EWMA hay SMA. Giá trị w có thể lựa chọn khởi tạo giá trị ban đầu theo công thức (2-10a) và điều chỉnh lại cho hợp lý trong quá trình sử dụng hệ thống. Giá trị nên lựa chọn theo từng loại ngữ cảnh hay ứng dụng cụ thể: nhỏ phù hợp hơn với những ứng dụng mà đối tượng di chuyển với hướng và vận tốc ít biến đổi (phương tiện hàng hải, hàng không) còn lớn lại dễ thích nghi với những ứng dụng mà đối tượng di chuyển với hướng và vận tốc hay thay đổi (phương tiện đường bộ). 2.2. Dự đoán dựa trên hành vi của đối tượng 2.2.1. Luật kết hợp Luật kết hợp là một biểu thức có dạng: XY, trong đó X và Y là tập các mục cùng xuất hiện trong một bộ cho trước [1]... 2.2.2. Thuật toán phân cụm dựa trên mật độ DBSCAN Thuật toán phân cụm dựa trên mật độ thông dụng nhất là thuật toán DBSCAN, cho phép tìm các đối tượng mà có số đối tượng láng giềng lớn hơn một ngưỡng tối thiểu. Một cụm được xác định bằng tập tất cả các đối tượng liên thông mật độ với các láng giềng của nó [22]... 2.2.3. Mẫu hình di chuyển Trong thực tế chuyển động của đối tượng thường có tính chu kỳ theo một mẫu hình (pattern) nào đó. Ví dụ như con người đi làm hàng 12 ngày theo một tuyến đường định trước. Phương tiện giao thông công cộng có lịch trình, tuyến đường và điểm đỗ cố định Định nghĩa 3.1 [Điểm dừng] Điểm dừng là một phần quan trọng trong quỹ đạo mà đối tượng không có dịch chuyển rõ ràng trong một khoảng thời gian nhất định. Điểm dừng được mô tả bởi một kiểu đặc trưng không gian với khoảng thời gian xác định (không rỗng). Định nghĩa 3.2 [Di chuyển] Di chuyển từ điểm dừng l1 đến l2 được ký hiệu l1  l2 là một phần của quỹ đạo trong khoảng thời gian xác định được giới hạn bởi hai điểm dừng liên tiếp l1 và l2 trong đó các điểm dừng này không bị trùng về mặt thời gian. Định nghĩa 3.3 [Quỹ đạo] Quỹ đạo P là một danh sách sắp thứ tự của các điểm dừng và các di chuyển. P thường được biểu diễn như sau: P = {(l0, l1, , ln-1)} trong đó li (0 ≤ i < n) biểu diễn đối tượng tại vị trí li ở thời điểm i. Định nghĩa 3.4 [Độ hỗ trợ của di chuyển] Cho X={P1, P2,, Pn} là tập các quỹ đạo; Trong đó mỗi quỹ đạo Pi (0 < i  n) được định nghĩa như định nghĩa 3.3 ở trên. Độ hỗ trợ của di chuyển AB, ký hiệu là sup(AB), là tỉ số của các quỹ đạo Pi trong X mà có chứa di chuyển AB trên tổng số quỹ đạo có trong X. sup(AB) = |{P ∈ X |AB ∈ P| |X| Trong đó ký hiệu |Z| biểu diễn số phần tử có trong tập Z. Định nghĩa 3.5 [Mẫu hình di chuyển] Một di chuyển được gọi là mẫu hình di chuyển nếu độ hỗ trợ s của nó lớn hơn hoặc bằng một ngưỡng cho trước gọi là minsup. Định nghĩa 3.6 [Mẫu hình quỹ đạo] 13 Quỹ đạo P được gọi là mẫu hình quỹ đạo nếu nó được biểu diễn dưới dạng của một luật kết hợp đặc biệt: P: 𝑅𝑡1 𝑗1  𝑅𝑡2 𝑗2   𝑅𝑡𝑚 𝑗𝑚 𝑐 → 𝑅𝑡𝑛 𝑗𝑛 với ràng buộc về thời gian: t1 < t2 < < tm < tn Tham số c là độ chắc chắn hay xác xuất biểu thị khả năng xảy ra. Định nghĩa 3.7 [Truy vấn tương lai] Truy vấn tương lai là truy vấn dự đoán không gian-thời gian thỏa mãn điều kiện sau: tq  tc + d Trong đó tq là ký hiệu thời gian tại thời điểm truy vấn, tc là ký hiệu thời gian hiện thời và d là thời gian ở tương lai thỏa mãn: tq < T, 0 < d < T (T là ngưỡng thời gian truy vấn) 2.2.4. Khai phá mẫu hình di chuyển Khai phá mẫu hình di chuyển đã được nghiên cứu và có một số kết quả nhất định. Các nghiên cứu này bao gồm các nhóm sau: (1) Biến đổi dữ liệu thô: Dữ liệu thô được xấp xỉ và chuyển đổi thành một định dạng phân tích. (2) Chỉ mục: Kalniset và đồng nghiệp sử dụng một chỉ số lưới Gt tại mỗi thời điểm t để lưu trữ dữ liệu tại thời điểm đó. Sau đó áp dụng thuật toán phân cụm dựa trên mật độ DBSCAN trên các chỉ số lưới Gt để xác định các cụm tại thời điểm t. (3) Tiếp cận kiểu Apriori: Cách tiếp cận kiểu Apriori có thể được áp dụng để khai phá các mẫu hình quỹ đạo một cách hiệu quả. Một vấn đề trong việc dự đoán vị trí đối tượng dựa theo mẫu hình là làm thế nào để xác định được mẫu hình dựa trên thông tin về vị trí của nó trong quá khứ. Một số nghiên cứu cho rằng có thể làm được bằng cách khai phá mẫu hình. Tuy nhiên để thu được mẫu hình cần một lượng rất lớn dữ liệu lịch sử của đối tượng để 14 tiến hành khai phá. Điều này cũng có nghĩa là số lượng mẫu hình phát hiện được cũng sẽ rất lớn. Vì vậy cần có phương pháp để tổ chức các mẫu hình này để trả lời các truy vấn dự đoán vị trí một các hiệu quả. Nhằm góp phần giải quyết vấn đề này, nghiên cứu sinh đề xuất sử dụng khung quy trình khai phá mẫu hình di chuyển và lưu trữ trong CSDL không gian như hình dưới đây. Hình 2.9. Quy trình khai phá mẫu hình di chuyển Quy trình này được phân thành 3 mức: dữ liệu, trích chọn mẫu hình và mô hình hóa mẫu hình. (1) Ở mức dữ liệu, trong CSDL lưu trữ cả dữ liệu địa lý và dữ liệu quỹ đạo chuyển động của đối tượng. (2) Ở mức trích chọn mẫu hình, dữ liệu được làm sạch và chuyển đổi thành định dạng chuẩn (tiền xử lý) để chuẩn bị cho bước khai phá dữ liệu. Ở mức này, dữ liệu cũng được chuyển đổi thành định dạng đầu vào theo yêu cầu của các thuật toán khai phá. (3) Ở bước khai phá dữ liệu, người sử dụng có thể xác định các tham số khai phá như độ hỗ trợ tối thiểu để có thể trích chọn chỉ các đặc trưng thỏa mãn ràng buộc. Sau khai phá chúng ta có các mẫu hình di chuyển và sẽ được mô hình hóa cho bước dự đoán vị trí về sau. Cơ sở dữ liệu Địa lý Cơ sở dữ liệu quỹ đạo Tiền xử lý Khai phá dữ liệu Mẫu hình Mẫu hình di chuyển Dữ liệu Trích chọn mẫu hình Mô hình hóa mẫu hình 15 2.2.5. Khai phá luật kết hợp của mẫu hình quỹ đạo trong dự đoán vị trí của đối tượng chuyển động Trong luận án này, nghiên cứu sinh sử dụng thuật toán tựa Apriori [51] để khai phá các mẫu hình quỹ đạo. Việc khai phá này tương tự như khai phá các luật kết hợp bao gồm hai bước chính sau: (1) Xác định các vùng thường xuyên đến  Xác định mẫu hình có tính chu kỳ, phân chia toàn bộ quỹ đạo thành 𝑛 𝑇 quỹ đạo con  Nhóm tất cả các vị trí Gt có cùng khoảng dịch thời gian trong mỗi quỹ đạo con  Áp dụng thuật toán phân cụm dựa trên mật độ DBSCAN để xác định các cụm (vùng thường xuyên đến) cho mỗi khoảng dịch thời gian t (2) Suy diễn mẫu hình quỹ đạo từ các vùng thường xuyên đến  Sử dụng thuật toán tựa Apriori sinh ra tập k mục dự tuyển từ tập k-1 mục trước đó. Với các ràng buộc: o Lựa chọn các mẫu hình theo chiều hướng tăng dần. Vì các mẫu hình quỹ đạo là chuyển động theo thời gian tăng dần qua mỗi vùng. Những mẫu hình nào không đảm bảo ràng buộc này sẽ bị loại bỏ. o Lựa chọn mẫu hình ưu tiên ít mục trong hệ quả. Cách tiếp cận kiểu Apriori này có thể làm giảm đáng kể không gian tìm kiếm trong vài lần lặp lại đầu tiên, cho phép mẫu hình quỹ đạo được khai phá hiệu quả. Việc lựa chọn các mẫu hình theo chiều hướng tăng dần và loại bỏ các mẫu hình không hợp lệ được kiểm tra và thực hiện bởi toán tử kết nối có điều kiện (∞ operator). Điều kiện kết nối được thực hiện bởi hàm so sánh thứ tự kết nối, đảm bảo các vùng thường xuyên đến có thứ tự tăng dần theo thời gian. Thuật toán cho khai phá quỹ đạo được mô tả như sau: 16 Algorithm Apriori_Trajectories Input: Trajectory database D with the movement’s support = min_sup Output: Frequent Regions Procedure Apriori_Trajectories 1. R1 = find_frequent_1-itemsets(D); 2. FOR (k=2; Rk-1 ; k++) 3. Ck = apriori_gen(Rk-1, min_sup); 4. FOR EACH Tt  D // Tt is trajectory tth 5. Ct = subset(Ck,t); // use tth sub-trajectory for candidate 6. FOR EACH candidate c  Ct 7. c.count++; 8. Rk = {c  Ck | c.count  min_sup}; 9. END FOR 10. END FOR 11. RETURN (Frequent Regions = k Rk); End Procedure Procedure apriori_gen(Rk-1: frequent (k-1) itemsets; min_sup) 1. FOR EACH itemset R1  Rk-1 2. FOR EACH itemset R2  Rk-1 3. IF (R1[1]= R2[1])  (R1[2]= R2[2])...  (R1[k-2]= R2[k-2])  (R1[k-1]<R2[k-1]) THEN 4. c = R1 ∞ R2; // joint step: produce k candidate from k-1 item sets 5. IF has_infrequent_subset(c, Rk-1) THEN 6. delete c; // removal if there are multiple entries in the result 7. ELSE add c to Ck; 8. END FOR 9. END FOR 10. RETURN Ck; End Procedure Procedure has_infrequent_subset(c: candidate k-itemset; Rk-1: frequent (k-1) itemsets) 1. FOR EACH (k-1)-subset s of c 2. IF s  Rk-1 THEN RETURN TRUE 3. RETURN FARSE End Procedure Algorithm End 17 Trong thuật toán này, ở thủ tục chính Apriori_Trajectories, phần sinh tập k mục dự tuyển từ tập k-1 mục ở dòng 3, phần tính độ hỗ trợ ở dòng 4 đến 7, các mục dự tuyển có độ hỗ trợ nhỏ hơn minsup sẽ bị loại bỏ ở dòng 8. Ở thủ tục apriori_gen, bước joint step ở dòng 4 sử dụng toán tử kết nối có điều kiện để đảm bảo việc lựa chọn các mẫu hình theo chiều hướng tăng dần và loại bỏ các mẫu hình không hợp lệ. Kết quả thực nghiệm Bộ dữ liệu mẫu sử dụng tương tự của Luis O. A. và đồng nghiệp [19]. Dữ liệu này liên quan đến các hoạt động hàng ngày của đối tượng và được lấy trong khoảng thời gian 3 tháng (91 ngày). Đối tượng này có một số điểm dừng (vùng thường xuyên đến) là Home, Café, Market, Office và Laboratory. Kết quả thực nghiệm được sử dụng kết hợp với phương pháp dự đoán theo hàm chuyển động. Khi so sánh với phương pháp dự đoán chỉ theo hàm chuyển động, độ chính xác của phương pháp kết hợp đã tăng thêm đáng kể. Kết luận chương Chương 2 đã trình bày các kết quả nghiên cứu của nghiên cứu sinh bao gồm hai phương pháp đề xuất cho dự đoán vị trí của đối tượng chuyển động, nhằm góp phần giải quyết vấn đề mô hình hóa vị trí trong MODB. Phương pháp thứ nhất là dự đoán vị trí theo hàm chuyển động sử dụng mô hình W-EWMA, có ưu điểm là xử lý nhanh chóng, cho phép dự đoán được vị trí ở gần thời điểm hiện tại. Phương pháp thứ hai là dự đoán theo hành vi, tiếp cận theo hướng sử dụng khai phá luật kết hợp của các mẫu hình di chuyển của đối tượng. Phương pháp này cho phép dự đoán được vị trí ở những thời điểm xa hiện tại với độ chính xác tương đối cao. Kết hợp các phương pháp này sẽ đem lại hiệu quả tốt hơn cho cả hệ thống. Các kết quả này cũng được thể hiện trong các công bố (1)-(3). 18 Chương 3. LẬP CHỈ MỤC DỮ LIỆU KHÔNG GIAN – THỜI GIAN Trong chương này, nghiên cứu sinh sẽ trình bày kết quả nghiên cứu là một cấu trúc chỉ mục mới được đề xuất dựa trên TPR*-tree nhằm giảm bớt các vùng không gian trống mỗi khi thực hiện truy vấn liên tục bằng cách điều chỉnh MBR theo mật độ, đặt tên là DO-TPR*-tree. Kết quả này nhằm góp phần giải quyết vấn đề về lập chỉ mục dữ liệu trong cơ sở dữ liệu các đối tượng chuyển động. 3.1. R-tree R-tree là một cấu trúc cây cân bằng được xây dựng dựa trên B-tree để truy xuất nhanh các vùng không gian, bằng cách chia nhỏ không gian thành các vùng nhớ và tạo chỉ mục, sau đó áp dụng lý thuyết cây để quản lý, lưu trữ và truy xuất các vùng không gian này. R-tree có nhiều biến thể khác như R+-tree hay R*-tree cải tiến thêm về tốc độ truy vấn. R-tree cũng là cơ sở cho rất nhiều cấu trúc chỉ mục khác mà được sử dụng phổ biến như TPR-tree, TPR*-tree 3.2. TPR-tree TPR-tree (Time-Parameterized R-tree) [36] là một cây cân bằng, đa chiều dựa trên cấu trúc của R*-tree [2], phát triển từ R-tree [9]. TPR-tree cho phép dự đoán vị trí tương lai của đối tượng chuyển động bằng cách lưu trữ cả vị trí hiện tại cùng với vận tốc của từng đối tượng tại một thời điểm cụ thể. TPR-tree là cấu trúc cây rất hiệu quả cho việc lưu trữ và tìm kiếm trong cơ sở dữ liệu các đối tượng chuyển động. Nó là cơ sở cho rất nhiều cấu trúc cây khác phát triển mở rộng về sau, điển hình là TPR*-tree. 3.3. TPR*-tree Cấu trúc dữ liệu và thuật toán xử lý truy vấn của TPR*-tree [42] tương tự như của TPR-tree. Điểm khác giữa hai loại cây này nằm ở thuật toán thêm đối tượng mới vào cây nhờ đó làm tăng tốc độ xử lý truy vấn. Khi chèn đối tượng mới vào cây, TPR-tree đánh giá các thay 19 đổi tổng thể trên độ lớn diện tích của MBR, độ dài đường bao MBR và diện tích các vùng chồng chéo giữa các MBR mà sẽ bị ảnh hưởng bởi việc chèn này. TPR-tree lựa chọn nhánh cây để chèn mà những thay đổi này là nhỏ nhất. Dù cách tiếp cận này là rất hiệu quả cho việc lập chỉ mục các đối tượng tĩnh trong R*-tree, nhưng nó vẫn chưa phải là giải pháp tốt cho các đối tượng chuyển động. Bởi vì TPR-tree chỉ ước tính các thay đổi của MBR tại thời điểm chèn mà không xem xét MBR đã thay đổi theo tham số thời gian. Để giải quyết những thiếu sót này TPR*-tree sử dụng thuật toán chèn có phản hồi các biến đổi theo thời gian của MBR. Khi chèn đối tượng mới vào cây, TPR*-tree sử dụng thuật toán chèn trong đó xem xét bao nhiêu MBR sẽ quét trong không gian chỉ mục từ thời điểm chèn đến thời điểm cụ thể trong tương lai và sẽ chọn nhánh chèn sao cho vùng quét tổng thể trong nhánh này là nhỏ nhất. Cây TPR*-tree sẽ cho kết quả truy vấn tương lai nhanh hơn vì nó giúp thu gọn các MBR và hạn chế các vùng chồng lấp có thể không đem lại kết quả tìm kiếm. Ngoài ra, thuật toán xóa cũng được điều chỉnh nâng cao tương tự thuật toán chèn. Theo thử nghiệm kết quả trong [42], cây TPR*- tree mang lại hiệu suất gấp 5 lần so với cây TPR-tree. 3.4. DO-TPR*-tree Trong TPR*-tree, VBR của mỗi nút lưu trữ vận tốc lớn nhất và nhỏ nhất theo mỗi chiều của hình chữ nhật bao MBR. Và trong thực tế, các MBRs này phát triển rất nhanh theo thời gian, dẫn đến phát sinh vùng không gian trống (mà chắc chắn không chứa kết quả truy vấn) và gây ra sự chồng chéo rất lớn giữa các MBRs của các nút. Điều này sẽ làm giảm đáng kể hiệu suất xử lý truy vấn vì cần đến một số lượng ngày càng tăng của việc truy cập các nút cần thiết khi tìm kiếm do chồng chéo. Đối với vấn đề này, TPR*-tree chỉ thực hiện điều chỉnh MBR trên một nút bất cứ khi nào có thao tác cập nhật mà phản ánh sự thay 20 đổi vận tốc của đối tượng hoặc vị trí hiện tại trên nút đó. Như vậy với một nút N không được cập nhật trong một khoảng thời gian dài, kích cỡ vùng không gian trống sẽ tăng lên rất nhanh. Các truy vấn liên tục thực hiện trên cấu trúc cây TPR*-tree sẽ bị giảm hiệu suất nhanh chóng. Vấn đề này xuất phát từ tính thụ động trong việc điều chỉnh MBR trong cây TPR*-tree. Để giải quyết vấn đề này, nghiên cứu sinh đề xuất một cấu trúc chỉ mục mới dựa trên TPR*-tree, nhằm giảm bớt các vùng không gian trống mỗi khi thực hiện truy vấn liên tục bằng cách điều chỉnh MBR theo mật độ, đặt tên là DO-TPR*-tree (Density Optimal TPR*-tree). 3.4.1. Cấu trúc cây DO-TPR*-tree Cây DO-TPR*-tree kế thừa toàn bộ cấu trúc của cây TPR*-tree. Nút lá của DO-TPR*-tree là một cấu trúc bao gồm: vị trí của đối tượng chuyển động và con trỏ đến đối tượng chuyển động. Nút trung gian là một cấu trúc bao gồm: con trỏ đến cây con và hình chữ nhật bao các nhánh cây con. DO-TPR*-tree cũng sử dụng cả MBR và VBR để biểu diễn các đối tượng chuyển động. 3.4.2. Thuật toán tìm kiếm DOA_Search Kỹ thuật xử lý truy vấn Giả sử 𝑇𝑢𝑗 và 𝑇𝑢𝑗+1lần lượt là các thời điểm cập nhật liên tiếp thứ j và (j+ 1) mà sẽ có điều chỉnh MBR ở nút N. Chúng ta cùng xem xét tình huống xử lý truy vấn P tại nút N của cây TPR*-tree mà P thực hiện trong khoảng thời gian [𝑇𝑢𝑗, 𝑇𝑢𝑗+1]. Giả sử có k truy vấn liên tục sau thời điểm cập nhật thứ j ký hiệu Qj,k tại các thời điểm truy vấn 𝑇𝑞𝑗,𝑖 xẩy ra ở nút N và nằm trong khoảng thời gian giữa hai lần cập nhật liên tiếp [𝑇𝑢𝑗, 𝑇𝑢𝑗+1]. Ta có: 𝑇𝑢𝑗< 𝑇𝑞𝑗,1< 𝑇𝑞𝑗,2< < 𝑇𝑞𝑗,𝑘< 𝑇𝑢𝑗+1 Vì MBR của nút N mở rộng nhanh chóng trong khoảng thời gian [𝑇𝑢𝑗, 𝑇𝑢𝑗+1], truy vấn tại thời điểm 𝑇𝑞𝑗,𝑖 (1 ≤ i ≤ k) sẽ xem xét toàn bộ 21 MBR của N và vì vậy sẽ dẫn đến tồn tại những vùng không gian trống ngày càng lớn mà việc thực hiện truy vấn trên đó không đem lại thêm kết quả nào. Rõ ràng là nếu có thể thực hiện điều chỉnh MBR ở nút N tại thời điểm 𝑇𝑞𝑗,𝑖 khi thực hiện truy vấn Qj,i nào đó, thì tất cả các truy vấn sau đó Qj,x (i < x ≤ k) sẽ không phải xử lý trong vùng không gian trống đó nữa ở khoảng thời gian còn lại [𝑇𝑞𝑗,𝑖, 𝑇𝑢𝑗+1]. Phương pháp đề xuất của nghiên cứu sinh là bắt buộc điều chỉnh MBR dựa trên mật độ của nút N trong cây TPR*-tree. Lợi ích của phương pháp này là giảm được một số lượng lớn các truy vấn liên tục vào nút N trong khoảng thời gian [𝑇𝑞𝑗,𝑖, 𝑇𝑢𝑗+1] do MBR của nó đã được điều chỉnh nhỏ lại và giảm thiểu không gian trống. Trong phương pháp đề xuất, nghiên cứu sinh đưa ra hai định nghĩa sau mà sẽ được sử dụng trong thuật toán đề xuất. ĐỊNH NGHĨA 3.1 [Node Density – Mật độ của một nút]. Giả sử N là một nút của cây TPR*-Tree. Mật độ của nút N, ký hiệu DN, là tỉ số giữa số lượng Entry nằm trong N trên diện tích của MBR của nút đó. Mật độ của nút N tại thời điểm T, ký hiệu DN(T), là tỉ số của số lượng Entry nằm trong N trên diện tích của MBR của nút đó tại thời điểm T. DN (T) = 𝑁𝑢𝑚_𝐸𝑁(𝑇) 𝐴𝐵𝑅𝑁(𝑇) (3-1) Trong đó, - Num_EN(T) số lượng các Entry nằm trong N tại thời điểm T. Nếu N là nút lá thì Num_EN(T) là số đối tượng chuyển động trong N - ABRN(T) là diện tích của MBR của nút N tại thời điểm T ĐỊNH NGHĨA 4.2 [Node Density Optimal – Mật độ đủ tốt của một nút]. Giả sử N là một nút của cây TPR*-Tree. Mật độ của nút N tại thời điểm truy vấn Tq được gọi là đủ tốt nếu tỉ số của mật độ của nút N tại thời điểm cập nhật cuối cùng trước đó Tu với nó nhỏ hơn một số λ cho trước. 22 𝐷𝑁(𝑇𝑢) 𝐷𝑁(𝑇𝑞) < λ (3-2) Trong đó, - 𝐷𝑁(𝑇𝑞) là mật độ của nút N tại thời điểm truy vấn Tq - 𝐷𝑁(𝑇𝑢) là mật độ của nút N tại thời điểm cập nhật cuối cùng Tu - λ là một số cho trước. Nhìn chung, lựa chọn λ là tùy thuộc vào ngữ cảnh của từng ứng dụng cụ thể và tùy từng thời điểm khác nhau, do mật độ các đối tượng chuyển động thay đổi theo thời gian. Trong ứng dụng quản lý phương tiện chuyển động, λ có thể khởi tạo bằng giá trị h-1 trong đó h là chiều cao của cây. Giá trị này có thể điều chỉnh lại trong quá trình sử dụng ứng dụng. Ví dụ với mật độ giao thông cao vào thời điểm đầu giờ sáng hay giờ tan tầm thì giảm giá trị λ (nhưng vẫn lớn hơn 1), còn những thời điểm khác có thể tăng λ. Trong phương pháp đề xuất này, nghiên cứu sinh kiểm tra điều kiện mật độ đủ tốt (3-2) của nút N khi có truy vấn của người sử dụng tại thời điểm truy vấn 𝑇𝑞𝑗,𝑖. Nếu không thỏa điều kiện (3-2), việc điều chỉnh MBR sẽ được thực hiện trên nút N. Vì vậy tất cả các truy vấn sau thời điểm này Qj,x (i < x ≤ k) sẽ không phải xử lý trong vùng không gian trống của N ở khoảng thời gian còn lại [𝑇𝑞𝑗,𝑖, 𝑇𝑢𝑗+1]. Nhờ đó mà giảm được một số lượng lớn các truy vấn liên tục vào nút N trong khoảng thời gian này và nâng cao hiệu năng truy vấn của TPR*-tree. Thuật toán tìm kiếm DOA_Search Gọi việc điều