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

Home 17:06 18:12 9 1 Home Café 07:55 08:33 9 2 Café Laboratory 08:40 09:35 9 3 Laboratory Home 18:25 19:38 10 1 Home Laboratory 08:32 09:02 10 2 Laboratory Office 11:03 16:27 10 3 Office Home 17:28 18:15 Tiến hành thực nghiệm trên máy tính PC (cấu hình: CPU 2GHz, 1GB RAM) chạy hệ điều hành Windows 7 cài đặt MONET-DB, sử dụng MonetDB/SQL và MonetDB/GIS. Quỹ đạo của đối tượng với chu kỳ được xác định là “một ngày” biểu diễn trên bảng sau: Bảng 2.3. Quỹ đạo của đối tượng TjID Trajectory T1 Home, Office T2 Home, Café, Laboratory, Office T3 Home, Laboratory, Café, Office T6 Home, Café, Market Các di chuyển thường xuyên giữa hai điểm dừng được biểu diễn trên bảng 2.4 dưới đây cùng với độ hỗ trợ tương ứng. Bảng 2.4. Di chuyển thường xuyên và độ hỗ trợ Move Sup Home
Office 0.5 Home
Café 0.3 Café
Laboratory 0.4 Laboratory
Office 0.5 69 Sử dụng dữ liệu như mô tả trong bảng 2.4 và lựa chọn minsup = 0.5, thu được mẫu hình di chuyển trong bảng 2.5 dưới đây. Bảng 2.5. Mẫu hình di chuyển với độ hỗ trợ nhỏ nhất là 0.5 Move Sup Home
Office 0.5 Office
Home 0.6 Laboratory
Office 0.5 Truy vấn đối tượng X tại một thời điểm cho trước với minsup = 0.5? Ví dụ: bây giờ đang là 8h và đối tượng X đang ở điểm dừng Home. Đối tượng X sẽ ở đâu vào lúc 14h15 ngày hôm nay? Kết quả là đang ở Office. LET given_time= time(14,15) // at 14h15 SELECT o.obj_loc FROM tblMovingObjects WHERE o.id=’X’ AND time(o) = given_time o.obj_loc = “Office”; 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 đã được cải thiện như biểu diễn trên biểu đồ hình 2.11 dưới đây. Hình 2.11. So sánh độ chính xác của hai phương pháp dự đoán 70 Biểu đồ này biểu diễn độ chính xác xấp xỉ tương ứng với lượng dữ liệu sử dụng cho khai phá tăng dần theo số ngày. Độ chính xác trung bình của phương pháp dự đoán theo hàm chuyển động (ở đây nghiên cứu sinh sử dụng W-EWMA) là khoảng 82% với tập dữ liệu đã mô tả ở trên. Độ chính xác này được biểu diễn bởi đường đánh dấu hình thoi . Nhìn vào biểu đồ hình 2.11 ở trên có thể thấy khi kết hợp với phương pháp dự đoán theo mẫu hình di chuyển, độ chính xác tăng lên đáng kể (xấp xỉ 88%), được biểu diễn bởi đường đánh dấu hình vuông . 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 cơ sở dữ liệu các đối tượng chuyển động. 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 khắc phục được nhược điểm của phương pháp thứ nhất là 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). 71 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 là DO-TPR*-tree, 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. Như đã đề cập ở chương 2, dữ liệu vị trí của đối tượng chuyển động được mô hình hóa dưới dạng các thuộc tính động. Lập chỉ mục dữ liệu trong cơ sở dữ liệu các đối tượng chuyển động chính là lập chỉ mục các thuộc tính động. Việc lập chỉ mục thuộc tính động này có thể giải quyết bằng cách tách thành hai vấn đề con. Đầu tiên là biểu diễn hình học của giá trị thuộc tính động (tốc độ di chuyển, vị trí ban đầu, thời điểm bắt đầu) trong không gian-thời gian. Thứ hai là lập chỉ mục không gian của biểu diễn hình học nói trên. Vấn đề biểu diễn hình học liên quan đến các câu hỏi: Làm thế nào để ánh xạ một đối tượng (chính xác hơn là giá trị thuộc tính động) vào một vùng (hoặc một đường/điểm) trong không gian? Làm thế nào để ánh xạ một truy vấn vào các khu vực khác trong không gian cốt để mà kết quả truy vấn là các đối tượng có vùng giao với vùng truy vấn? Vùng đối tượng được cập nhật khi và chỉ khi các thuộc tính động được cập nhật một cách rõ ràng chứ không phải là liên tục (ví dụ như khi tốc độ của đối tượng thay đổi). Việc lập chỉ mục không gian liên quan đến câu hỏi là làm thế nào để có thể tìm thấy những vùng giao nhau nêu trên một cách nhanh chóng và hiệu quả. Một số nghiên cứu về cấu trúc cây nhằm giảm chi phí cập nhật đối tượng đã được đề xuất, chẳng hạn như RUM-tree hay FD-tree. RUM-tree [37] xử lý việc cập nhật theo kiểu dựa trên bản ghi nhớ (memo-based) nhằm hạn chế việc truy cập đĩa cứng thường xuyên khi thanh lọc các mục cũ trong quá trình cập nhật. Nhờ đó, chi phí cho thao tác cập nhật trong RUM-tree giảm bằng chi phí của một thao tác thêm mới. Trong khi đó FD-tree [18] là cấu trúc cây chỉ mục sử dụng đặc trưng phần cứng như ổ đĩa flash hay SSD có tốc độ cao hơn nhằm tối ưu hiệu năng cập nhật bằng cách hạn chế các thao tác ghi ngẫu nhiên trong khi vẫn giữ được hiệu quả khi tìm kiếm. 72 Hầu hết các phương pháp lập chỉ mục trong cơ sở dữ liệu các đối tượng chuyển động hiện có đều dựa trên phương pháp lập chỉ mục không gian truyền thống là R- tree và các mở rộng của nó, mà điển hình là TPR-tree. Hình 3.1. Các cấu trúc cây phát triển từ TPR-tree (2005-2012) TPR-tree [36] 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ác cấu trúc cây khác 73 phát triển mở rộng về sau như TPR*-tree, LGU TPR-tree [59], VTPR-tree [60], TPRA-tree [61] (hình 3.1). Nhiều nỗ lực trong việc cải tiến cấu trúc chỉ mục TPR- tree để hiệu quả hơn cho truy vấn tương lai như Bdual-tree. Cấu trúc Bdual-tree [48] được giới thiệu nhằm nâng cao hiệu năng cập nhật so với các phương pháp trước. Bdual-tree đem lại hiệu năng tổng thể khá tốt, tuy nhiên khi so sánh với TPR*-tree thì TPR*-tree vẫn đem lại hiệu năng tốt nhất về thời gian xử lý truy vấn [42]. Nhìn hình 3.1 trên cũng có thể thấy TPR*-tree vẫn tiếp tục được cải tiến thêm khá nhiều trong những năm gần đây theo nhiều hướng khác nhau phù hợp với từng hoàn cảnh và ứng dụng cụ thể trong thực tế như Efficient TPR*-tree [57] năm 2011 hay HTPR*-tree [58] năm 2012. Cả Efficient TPR*-tree và HTPR*-tree đều là cấu trúc cây được cải tiến từ TPR*-tree nhằm làm tăng hiệu năng cập nhật các đối tượng chuyển động. Efficient TPR*-tree sử dụng vùng đệm (buffering) để tăng tốc độ cập nhật. Còn HTPR*-tree thì thêm thời gian tạo lập hay cập nhật của các đối tượng vào các nút lá và sử dụng chiến lược cập nhật từ dưới lên với các cấu trúc hỗ trợ là chỉ mục băm, véc tơ nhị phân và bảng truy cập trực tiếp. Phần đầu chương này, nghiên cứu sinh sẽ giới thiệu sơ lược về các cấu trúc cây có liên quan khi xây dựng cây đề xuất bao gồm R-tree, TPR-tree và TPR*-tree. Tiếp theo sẽ giới thiệu kỹ thuật xử lý, thuật toán tìm kiếm của cấu trúc cây đề xuất DO- TPR*-tree dựa trên TPR*-tree nhằm làm tăng hiệu năng truy vấn. Các thực nghiệm được thực hiện ở phần cuối chương này đã chứng tỏ cấu trúc cây DO-TPR*-tree đem lại hiệu năng tốt hơn trong nhiều trường hợp so với cấu trúc cây ban đầu. 3.1. R-tree Cấu trúc cây R-tree R-tree [9] 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. R-tree chia nhỏ không gian ban đầu thành các khối có thể lồng nhau hoặc chồng chéo lên nhau 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. Hình khối thường được sử dụng là hình chữ nhật bao nhỏ nhất chứa dữ liệu (Minimum Bounding Rectangle 74 - MBR). Chính các MBR được lưu trữ trên cấu trúc cây dưới dạng các nút chứ không phải bản thân dữ liệu, khi đó việc tìm kiếm dữ liệu sẽ được thực hiện trên các nút. Các nút lá trong cây chứa chỉ mục vì vậy chúng có khuôn dạng: (MBR, object_ptr), trong đó object_ptr tham chiếu đến một bộ dữ liệu trong cơ sở dữ liệu và MBR là một hình chữ nhật n-chiều chứa các đối tượng không gian nó thể hiện. Các nút không phải lá gọi là nút trung gian, có khuôn dạng: (MBR, chirld_ptr), trong đó chirld_ptr là địa chỉ nút con của nó trong cây và MBR là hình chữ nhật nhỏ nhất bao tất cả các MBR trong các nút ở mức thấp hơn. Nói cách khác, không gian MBR chứa mọi đối tượng được lập chỉ mục trong các cây con có gốc là đầu vào của MBR. Cho m và M tương ứng là số lượng tối thiểu và tối đa đầu vào có thể vừa đủ với một nút, trong đó m∈ [0, M/2]. R-tree thỏa mãn các thuộc tính sau: - R-tree là cây cân bằng - Nút gốc có ít nhất 2 nút con (ngoại trừ cây chỉ có một nút) - Mỗi một nút chứa số lượng nút con trong khoảng m và M ngoại trừ nút gốc - Nút lá là cấu trúc có dạng (MBR, object_ptr), trong đó MBR là hình chữ nhật nhỏ nhất có chứa dữ liệu của đối tượng được biểu diễn bởi object_ptr - Nút trung gian là cấu trúc có dạng (MBR, chirld_ptr), trong đó MBR là hình chữ nhật nhỏ nhất bao tất cả các hình chữ nhật trong nút con của nó trỏ bởi chirld_ptr - Tất cả các nút lá ở cùng một mức. 75 Hình 3.2. Biểu diễn hai chiều của R-tree Hình 3.3. Biểu diễn cấu trúc cây R-tree Hình 3.2 biểu diễn một ví dụ của R-tree với m=2 và M=4. Các nút trung gian là a, b, c và d, được biểu diễn dưới dạng hai chiều là các hình chữ nhật bao nhỏ nhất bao trọn các nút lá tương ứng là [1,2,5,6], [3,4,7,10], [8,9,14] và [11,12,13] thể hiện như trên hình 3.3 Cấu trúc chỉ mục trong R-tree thực sự linh động, thao tác chèn, xóa, cập nhật có thể kết hợp với phép tìm kiếm và có thể thực hiện đệ quy. 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 76 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í 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ể. Cấu trúc cây TPR-tree Nút lá của 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 (subtree) và hình chữ nhật bao tất cả các vị trí của đối tượng chuyển động (hình chữ nhật bao các nhánh cây con). Trong TPR-tree, các hình chữ nhật bao trong không gian n-chiều sử dụng các tham số của thời gian, tọa độ của chúng là hàm thời gian. Một hình chữ nhật bao theo tham số thời gian sẽ bao bọc tất cả điểm kèm theo hay các hình chữ nhật tại tất cả thời gian tương lai gần nhất. Vì vậy nó có khả năng bao bọc các điểm chuyển động liên tục. Hình 3.4. Các điểm chuyển động ở các nút lá của TPR-tree 77 Hình 3.5. Các điểm chuyển động trong các nút trung gian của TPR-tree Đối với mỗi chiều n, khoảng bao được xác định bởi hai hàm tuyến tính theo thời gian: [xn├ (tref) + vn├ (t – tref), xn ┤ (tref) + vn ┤ (t – tref)], trong đó: - xn├ = xn├ (tref) = mini{oi.xn├ (tref)} - xn ┤= xn ┤(tref ) = maxi{oi.xn ┤(tref)} - vn├ = mini{oi.vn├} - vn ┤= maxi{oi.vn┤} - tref là thời gian mà hình chữ nhật bao được tạo ra. Các hình chữ nhật bao không bao giờ thu nhỏ lại và trên thực tế nó có thể phát triển rất nhanh theo thời gian. Điều đó làm hiệu suất truy vấn giảm dần theo thời gian vì vậy các hình chữ nhật bao phải được điều chỉnh và cập nhật lại. Đối với mỗi chiều n, điểm cuối của khoảng bao sẽ được cập nhật như sau: xn├ = mini{oi.xn├ (tupd)} – vn├ (tupd – tref) xn┤= maxi{oi.xn ┤ (tupd)} – vn ┤(tupd – tref) tref là thời gian hình chữ nhật bao được tạo ra. tupd là thời gian khi thực hiện cập nhật. 78 Hình 3.6. Cập nhật khoảng giới hạn theo tham số thời gian Trong ví dụ tại hình 3.6, các nét đậm phía trên và phía dưới thể hiện thời điểm được tạo ra và nét đứt là thời gian cập nhật, 4 đường thể hiện đường đi của 4 đối tượng chuyển động o1, o2, o3, o4. Với không gian hai chiều, một đối tượng chuyển động O có thể được biểu diễn bởi hình chữ nhật bao nhỏ nhất (MBR) OR và hình chữ nhật bao vận tốc (VBR) OV={OV1-,OV1+,OV2-,OV2+} trong đó OVi- biểu diễn vận tốc chuyển động của đường bao dưới còn OVi+ biểu diễn vận tốc chuyển động của đường bao trên của OR theo mỗi chiều thứ i tương ứng (1 ≤ i ≤ 2). 79 (a) MBRs & VBRs tại thời điểm 0 (b) MBRs tại thời điểm 1 Hình 3.7. Biểu diễn nút trung gian trong cây TPR-tree Hình 3.7a biểu diễn MBR và VBR của 4 đối tượng chuyển động a, b, c, d. Các mũi tên đen gắn trên mỗi MBR của đối tượng biểu thị hướng chuyển động với vận tốc là số đính kèm của MBR đó, trong đó số âm nghĩa là hướng chuyển động ngược với chiều của trục số. VBR của đối tượng a là aV={1,1,1,1} (hai số đầu cho trục x, hai số sau cho trục y). Tương tự VBR của b, c, d lần lượt là bV={-2,-2,-2,-2}, cV={- 2,0,0,2} và dV={-1,-1,1,1}. Các nút trung gian cũng được biểu diễn bởi MBR và VBR, như trong ví dụ hình 3.7a, các nút trung gian N1 (chứa đối tượng a và b) và N2 (chứa đối tượng c và d) có các VBR lần lượt là N1V={-2,1,-2,1} và N2V={-2,0,-1,2} và hướng được biểu diễn bởi các mũi tên trắng gắn trên mỗi MBR. Để xử lý truy vấn qR tại thời điểm tương lai của người sử dụng, TPR-tree tính toán mở rộng các MBRs và VBRs tại thời điểm truy vấn theo vận tốc tương ứng của mỗi chiều rồi tìm kiếm đệ quy trong các cây con của MBR nào mà chồng lên miền truy vấn qR như ví dụ trên hình 3.7b. Có thể nói 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ác cấu trúc cây khác phát triển mở rộng về sau, điển hình là TPR*-tree. 80 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 đổ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í dụ, cho hai điểm thời gian khác nhau t1 và t2 (t1 < t2). Vùng quét của MBR từ t1 đến t2 được định nghĩa là vùng không gian chỉ mục mà quét bởi MBR mở rộng trong khoảng thời gian (t2 – t1). Hình 3.8 dưới đây minh họa vùng quét trong TPR*-tree. Ở thời điểm khởi tạo ban đầu 0, chúng ta có MBR N ở hình 3.8a, đến thời điểm 1, MBR quét trong không gian chỉ mục như hình 3.8b, trong đó vùng quét được đánh dấu bởi hình đa giác tô màu xám. Trong ví dụ này, vùng quét có kích thước là 23 (đơn vị diện tích). 81 (a) Thời điểm 0 (b) Thời điểm 1 Hình 3.8. Vùng quét từ thời điểm 0 đến thời điểm 1 Thuật toán chèn tìm nút lá trong cây TPR*-tree bằng cách chọn đệ quy từ trên xuống cây con sẽ chứa nút chèn vào. Trong quá trình tìm kiếm, thuật toán 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. Vì vậy, thuật toán cần tính thêm diện tích các vùng quét mỗi khi chèn đối tượng. Tiến trình này đòi hỏi tốn thêm thời gian tính toán so với cây TPR-tree. Tuy nhiên cây TPR*-tree sẽ cho kết quả truy vấn 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 Dù đạt được những kết quả đáng kể và được sử dụng trong rất nhiều hệ thống lập chỉ mục dữ liệu không gian-thời gian, cấu trúc cây TPR*-tree vẫn còn tồn tại vài vấn đề cần giải quyết. Một trong số đó là tính thụ động trong việc điều chỉnh MBR trong cây 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 82 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 đổi vận tốc của đối tượng hoặc vị trí hiện tại trên nút đó. Hình 3.9 dưới đây minh họa lợi ích của việc điều chỉnh các MBRs này. Trong hình 3.9a, tại thời điểm khởi tạo 0, một MBR bao các đối tượng O1 và O2 được tạo ra và biểu diễn bởi hình chữ nhật R. Hình 3.9b minh họa vị trí của các đối tượng tại thời điểm 1. Các đối tượng O1 và O2 đã di chuyển lại gần nhau hơn trong khi MBR của chúng lại mở rộng ra xa hơn (hình chữ nhật R1). Nếu điều chỉnh MBR xảy ra ở thời điểm 1 (có thao tác cập nhật hay thêm nút), chúng ta sẽ có MBR nhỏ hơn nhiều như R’ trong hình 3.9b. Với việc thu gọn MBR tại thời điểm 1, chúng ta có thể loại bỏ không gian trống R1 – R’, dẫn đến sẽ loại bỏ được những truy cập nút không cần thiết (vì chắc chắn không có kết quả) khi vùng truy vấn có giao hoặc nằm trong vùng không gian trống R1 – R’ này. (a) Thời điểm 0 (b) Thời điểm 1 Hình 3.9. MBR của R tại thời điểm khởi tạo 0 và mở rộng R1 tại thời điểm 1 Rõ ràng việc điều chỉnh MBR là giải pháp cho hiệu năng tốt hơn khi truy vấn. Tuy nhiên, với TPR*-tree, điều chỉnh các MBRs chỉ xảy ra khi có xuất hiện thao tác 83 cập nhật hay thêm mới đối tượng. 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. Điều này phát sinh 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). Cấu trúc cây, các định nghĩa, kỹ thuật xử lý và thuật toán tìm kiếm DOA_Search sẽ được trình bày cụ thể trong phần tiếp theo. 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. Các thuật toán thêm mới hay xóa đối tượng của cây DO-TPR*-tree là tương tự cây TPR*-tree như mô tả dưới đây. 84 3.4.2. Thuật toán tìm kiếm DOA_Search Kỹ thuật xử lý truy vấn Như mô tả ở phần trên, cây TPR*-tree mang tính thụ động trong việc điều chỉnh MBR. Nghĩa là việc điều chỉnh MBR ở một nút N trong cây chỉ xảy ra khi có thao tác cập nhật hay thêm mới đối tượng chuyển động trong MBR của nút đó. Giả sử DEF Algorithm Insert (e) Input: e is the entry to be inserted Output: Inserted e into Node N 1. re-insertedi= false for all levels 1≤ i ≤ h−1 (h is the tree height) 2. Initialize an empty re-insertion list Lreinsert 3. Invoke Choose Path to find the leaf node N to insert e 4. Invoke Node Insert (N, e) 5. For each entry e' in the Lreinsert 6. Invoke Choose Path to find the leaf node N to insert e' 7. Invoke Node Insert (N, e) 8. End for Algorithm End Algorithm Node Insert (N, e) /* Input: N is the node where entry e is inserted */ 1. if N is a leaf node 2. enter the information of e 3. if N overflows 4. if re-inserted0 = false //no re-insertion at leaf level yet 5. invoke Pick Worst to select a set Sworst of entries 6. remove entries in Sworst from N; add them to Lreinsert 7. re-inserted0 = true 8. else 9. invoke Node Split to split N into itself and N' 10. let P be the parent of N 11. Node Insert(P,∅) or Node Insert(P,N') if N has been split 12. else //N is a non-leaf node 13. similar to lines 2-9 except that (i) the MBR/VBR of the affected child node is adjusted, and (ii) in lines 4, 7 replace re-inserted0 with re-insertedi where i is the level of N End Node Insert 85 và DEFHIlầ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 [DEF, DEFHI]. 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 DJF,K 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 [DEF , DEFHI]. Ta có: DEF< DJF,I< DJF,L< < DJF,M< DEFHI Vì MBR của nút N mở rộng nhanh chóng trong khoảng thời gian [DEF, DEFHI], truy vấn của người sử dụng tại thời điểm DJF,K (1 ≤ i ≤ k) sẽ xem xét toàn bộ 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 DJF,K 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 [DJF,K, DEFHI]. 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 [DJF,K, DEFHI] 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. 86 DN (T) = NE6_PQ(9) RSTQ(9) (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 nằm 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 3.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. UQ(9V) UQ(9W) < λ (3-2) Trong đó, − XN(DJ) là mật độ của nút N tại thời điểm truy vấn Tq − XN(DE) 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 λ. Điều kiện mật độ đủ tốt (3-2) nhằm đảm bảo vùng không gian trống trong MBR của nút N tại thời điểm truy vấn chưa quá lớn đến mức ảnh hưởng đến các truy vấn tiếp sau thời điểm này. 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 DJF,K. Nếu 87 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 [DJF,K, DEFHI]. 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 cây TPR*-Tree. Thuật toán tìm kiếm DOA_Search Gọi việc điều chỉnh MBR khi kiểm tra điều kiện (3-2) là điều chỉnh mật độ đủ tốt - Density Optimal Adjustment (DOA). Truy vấn tương lai của người sử dụng được biểu diễn dưới dạng (QBR, QT). Trong đó, QBR là ký hiệu phạm vi truy vấn (bao gồm MBR và VBR) trong không gian truy vấn hai chiều và QT là ký hiệu khoảng thời gian truy vấn (bao gồm thời gian bắt đầu và thời gian kết thúc). Truy vấn tương lai dự đoán các đối tượng chuyển động mà sẽ đi vào vùng QBR trong khoảng thời gian QT. Thuật toán tìm kiếm đề xuất DOA_Search được mô tả dưới đây, trong đó trả về tập các định danh của những đối tượng thỏa mãn truy vấn tương lai (QBR, QT). 88 Thuật toán tìm kiếm từ trên xuống các nút lá từ nút gốc. Trong quá trình tìm kiếm, tiến trình tìm kiếm sẽ xác định đường tìm kiếm bằng cách tính toán các hình chữ nhật bao từ mỗi mục e ở các nút trung gian. Tiến trình sẽ lưu nội dung mỗi mục e đã gặp vào vùng nhớ cache tại dòng 11. Việc tính toán mật độ của nút được thực hiện ở dòng Algorithm DOA_Search(QBR, QT, rootNode) Input: (QBR, QT) = future-time query answered. rootNode= address to the root of a sub-tree being searched. Output: SBR= objects’ ids satisfying (QBR, QT). 1. IF rootNode is a leaf node THEN 2. SBR ← ∅; // initialization 3. FOR EACH moving object O IN rootNode 4. IF O IN (QBR, QT) THEN //O is expected computed to be positioned d in QBR within interval QT 5. SBR= SBR ∪ O.id; 6. END IF 7. END FOR 8. ELSE // rootNode is a non-leaf node 9. FOR EACH index entry e IN rootNode 10. IF OVERLAP(e.MBR, QBR, QT) THEN // if there is an overlap between the MBR of e and QBR within QT 11. Cache(e); // cache the content of e into the memory buffer 12. nodeDensity = Cal_NodeDensity(e.childNode); // calculate the Node Density Optimal of the child node pointed to by e 13. λ = h-1; // h is the tree height 14. IF (nodeDensity >= λ) THEN // a DOA execution is needed on childNode 15. Adjust (e.MBR, e.VBR); // adjust the MBR and VBR data of e 16. END IF 17. childSBR ← DOA_Search(QBR, QT, childNode); 18. SBR ← SBR ∪ childSBR; 19. END IF 20. END FOR 21. RETURN SBR 22. END IF Algorithm End 89 12. Điều kiện mật độ đủ tốt của nút được kiểm tra ở dòng 14, nếu điều kiện này không đạt, việc điều chỉnh MBR của nút đó sẽ được thực hiện ở dòng 15. Khi đến nút lá ở dòng 5, thuật toán sẽ đưa ra nhóm các định danh của các đối tượng chuyển động thỏa mãn điều kiện truy vấn và trả về ở dòng 21. Định lý 4.1 (Thuật toán DOA_Search là đúng). Thuật toán DOA_Search trả về đúng và đầy đủ các kết quả truy vấn phạm vi trong tương lai. Chứng minh. Ta thấy, mọi nút trong cây đều được duyệt. Điều này có thể thấy ở dòng 3, mọi nút lá và dòng 9, mọi nút trung gian trong cây (a). Tất cả các nút lá có vị trí nằm trong phạm vi hình chữ nhật truy vấn QBR trong khoảng thời gian truy vấn tương lai QT đều được đưa vào danh sách kết quả truy vấn (dòng 4 và 5) (b). Tất cả các mục entry của nút trung gian mà có hình chữ nhật bao giao với hình chữ nhật truy vấn QBR trong khoảng thời gian truy vấn tương lai QT (dòng 9, 10) đều được duyệt và tìm kiếm đệ quy để tìm ra nút lá bên trong thỏa mãn kết quả truy vấn (dòng 17, 18) (c). Thuật toán dừng khi duyệt hết tất cả các nút trong cây (d). Từ (a) (b) (c) và (d) ta có điều phải chứng minh. 3.4.3. Kết quả thực nghiệm Trong phần này, nghiên cứu sinh trình bày một số kết quả thực nghiệm so sánh phương pháp đề xuất với phương pháp sử dụng cây TPR*-tree. Có thể thấy được phương pháp đề xuất của nghiên cứu sinh đem đến hiệu năng truy vấn tốt hơn trong trường hợp truy vấn tương lai liên tục, mà rất hay được sử dụng trong các hệ thống quản lý phương tiện chuyển động. 90 Dữ liệu thực nghiệm Dữ liệu thực nghiệm được sinh ngẫu nhiên bằng thuật toán kiểu GSTD [43], một thuật toán nổi tiếng được sử dụng ở rất nhiều nghiên cứu trước trong việc đánh giá hiệu năng của các cấu trúc chỉ mục cho đối tượng chuyển động. Với thuật toán này, nghiên cứu sinh tạo ra bốn tập dữ liệu bao gồm [1.000, 10.000, 50.000, 100.000] đối tượng chuyển động có vận tốc chuyển động ngẫu nhiên trong khoảng từ [-50, 50] và vận tốc thay đổi tối đa cho mỗi lần cập nhật là 5. Những đối tượng này giả lập sẽ di chuyển trong không gian truy vấn hai chiều có kích thước từ 0 đến 10,000. Trong không gian truy vấn này, mỗi đối tượng được biểu diễn như là một điểm có vị trí ban đầu và phân bố đều trong không gian. Cấu trúc bản ghi mô tả chi tiết bao gồm định danh, MBR, VBR và thời điểm tham chiếu như sau: struct MovingObject { int oid; // unique identification of object float mbr[4]; // MRB of object float vbr[4]; // VRB of object float ref; // reference time at which the object is inserted or updated } Dữ liệu mẫu thể hiện trong bảng 3.1 dưới đây: Bảng 3.1. Dữ liệu thực nghiệm các đối tượng chuyển động oid X1 X2 Y1 Y2 Vx1 Vx2 Vy1 Vy2 ref time 0 3383.691 3383.713 6253.745 6253.767 -13.148 -13.148 -46.418 -46.418 0 1 1463.102 1463.125 1174.597 1174.619 29.806 29.806 18.544 18.544 0 2 699.142 699.164 1529.711 1529.734 -24.100 -24.100 4.767 4.767 0 3 8125.313 8125.335 747.351 747.373 -24.063 -24.063 38.967 38.967 0 4 1899.701 1899.724 7856.583 7856.605 11.642 11.642 5.390 5.390 0 520 1721.404 1721.427 7964.688 7964.710 9.970 9.970 -5.254 -5.254 1 521 9796.890 9796.912 1979.648 1979.671 27.163 27.163 -26.776 -26.776 1 522 6352.922 6352.944 9722.270 9722.292 49.548 49.548 -25.330 -25.330 1 850 1960.613 1960.635 4836.069 4836.092 -22.374 -22.374 -36.063 -36.063 3 851 6955.288 6955.311 4882.243 4882.265 -1.135 -1.135 -10.259 -10.259 3 91 Thực nghiệm được thực hiện trên máy tính cài hệ điều hành Windows 8 với bộ xử lý Intel Core i3, 1.80GHz, 4GB RAM bộ nhớ trong. Kết quả thực nghiệm Thực nghiệm 3-1. Đánh giá hiệu năng theo độ lớn phạm vi truy vấn Trước tiên nghiên cứu sinh đánh giá hiệu năng của DO-TPR*-tree theo độ lớn phạm vi truy vấn. Trong thực nghiệm này, kích thước vùng truy vấn QBR theo mỗi chiều là [100, 100]. Thời điểm cập nhật cuối cùng trong cây DO-TPR*-tree là 10. Phạm vi truy vấn thay đổi từ thời điểm 10 đến 50 với các giá trị lần lượt là [10-20], [10-30], [10-40] và [10-50]. Các kết quả thực nghiệm được biểu diễn trong hình 3.10 dưới đây, trong đó đồ thị hiển thị trung bình các kết quả tìm được ở hình 3.10a, trung bình số nút phải xử lý ở hình 3.10b, thời gian thực hiện truy vấn ở hình 3.10c. Ở cả 3 đồ thị, phạm vi truy vấn biểu diễn trên trục x. (a) Trung bình kết quả tìm được 0,00 100,00 200,00 300,00 400,00 500,00 600,00 1 0 - 2 0 1 0 - 3 0 1 0 - 4 0 1 0 - 5 0 A V G . D A T A R E T R IE V E S ( N U M ) FUTURE QUERY TIME INTERVAL 1K 10K 50K 100K 92 (b) Trung bình số nút phải xử lý (c) Thời gian thực hiện truy vấn Hình 3.10. Ảnh hưởng của độ lớn phạm vi truy vấn Những kết quả thực nghiệm này cho thấy trung bình số nút phải xử lý và thời gian thực hiện truy vấn ngày càng tăng khi phạm vi truy vấn tương lai ngày càng xa. Thực nghiệm 3-2. So sánh hiệu năng của DO-TPR*-tree với TPR*-tree Trong thực nghiệm này, nghiên cứu sinh so sánh, đánh giá hiệu năng của phương pháp đề xuất, DO-TPR*-tree, với phương pháp gốc là TPR*-tree. Các kết quả thực nghiệm của cả hai phương pháp này được biểu diễn trong hình 3.11, trong đó đồ thị hiển thị trung bình các kết quả tìm được ở hình 3.11a, trung bình số nút phải xử lý ở hình 3.11b, thời gian thực hiện truy vấn ở hình 3.11c. 0,00 50,00 100,00 150,00 200,00 250,00 1 0 - 2 0 1 0 - 3 0 1 0 - 4 0 1 0 - 5 0 A V G . N O D E A C C E S S ( N U M ) FUTURE QUERY TIME INTERVAL 1K 10K 50K 100K 0,00 5,00 10,00 15,00 20,00 25,00 30,00 1 0 - 2 0 1 0 - 3 0 1 0 - 4 0 1 0 - 5 0 Q U E R Y E X E C U T IO N T IM E ( S ) FUTURE QUERY TIME INTERVAL 1K 10K 50K 100K 93 (a) Trung bình kết quả tìm được (b) Trung bình số nút phải xử lý (c) Thời gian thực hiện truy vấn Hình 3.11. So sánh hiệu năng của DO-TPR*-tree với TPR*-tree 0 50 100 150 200 250 300 1 0 - 2 0 1 0 - 3 0 1 0 - 4 0 1 0 - 5 0 A V G . D A T A R E T R IE V E S ( N U M ) FUTURE QUERY TIME INTERVAL TPR*-TRee DO-TPR*-Tree 0 20 40 60 80 100 120 140 1 0 - 2 0 1 0 - 3 0 1 0 - 4 0 1 0 - 5 0 A V G . N O D E A C C E S S ( N U M ) FUTURE QUERY TIME INTERVAL TPR*-TRee DO-TPR*-Tree 0 5 10 15 20 1 0 - 2 0 1 0 - 3 0 1 0 - 4 0 1 0 - 5 0 Q U E R Y E X E C U T IO N T IM E ( S ) FUTURE QUERY TIME INTERVAL TPR*-TRee DO-TPR*-Tree 94 Những kết quả thực nghiệm trên chỉ ra rằng số lượng trung bình kết quả tìm được là tương đương nhưng trung bình số nút phải xử lý ít đi và thời gian thực hiện truy vấn giảm xuống khoảng 30%. Phương pháp mà nghiên cứu sinh đề xuất cho kết quả truy vấn nhanh hơn phương pháp gốc. Ở Việt Nam, với hạ tầng viễn thông đang phát triển, mạng truyền thông 3G thường bị lỗi hay chập chờn ở nhiều điểm ngay cả khi đang ở trong thành phố, tần suất cập nhật vị trí các điểm chuyển động sẽ bị hạn chế. Do đó khi truy vấn, hệ thống đòi hỏi cần nhiều lần điều chỉnh mật độ đủ tốt. Phương pháp của nghiên cứu sinh tỏ ra rất hiệu quả trong điều kiện này. Trong những trường hợp không cần điều chỉnh mật độ đủ tốt, phương pháp của nghiên cứu sinh hoạt động tương tự phương pháp gốc của TPR*-tree. Kết luận chương Chương 3 đã trình bày một số cấu trúc cây cơ bản việc trong lập chỉ mục dữ liệu không gian-thời gian. Trong chương này, nghiên cứu sinh cũng đã trình bày kết quả nghiên cứu là một cấu trúc cây mới được đề xuất dựa trên cây 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. Thuật toán xử lý truy vấn DOA_Search trong cấu trúc cây này đã được đưa ra và chứng minh tính đúng đắn. Các thực nghiệm cũng chứng tỏ cấu trúc cây DO-TPR*-tree đem lại hiệu năng truy vấn tốt hơn trong nhiều trường hợp so với cấu trúc cây ban đầu là TPR*-tree. Kết quả nghiên cứu này được thể hiện trong công bố (4) của nghiên cứu sinh. 95 KẾT LUẬN Luận án đã đề xuất các phương pháp giải quyết một số vấn đề còn tồn tại trong việc xây dựng cơ sở dữ liệu các đối tượng chuyển động để giải quyết các bài toán trong ứng dụng MODB đang phát triển rất mạnh mẽ hiện nay, đặc biệt là ứng dụng quản lý thông tin đối tượng chuyển động hay quản lý và điều hành giao thông. Các kết quả chính bao gồm: (1) Giải quyết vấn đề về mô hình hóa vị trí của đối tượng chuyển động dưới dạng thuộc tính động. Thuộc tính động ít cần phải cập nhật hơn thông tin vị trí do đó sẽ hạn chế được tần suất cập nhật vào cơ sở dữ liệu (mà thường là rất lớn trong các ứng dụng MODB). Thuộc tính động có thể được xác định nhờ vào hai phương pháp dự đoán vị trí đã đề xuất trong luận án: - Dự đoán vị trí của đối tượng dựa theo hàm chuyển động sử dụng mô hình W- EWMA - Dự đoán dựa trên hành vi của đối tượng sử dụng khai phá luật kết hợp của các mẫu hình di chuyển (2) Giải quyết vấn đề về lập chỉ mục không gian cho biểu diễn hình học của các thuộc tính động nhằm tăng hiệu năng truy vấn trên dữ liệu không gian-thời gian. Luận án đã đề xuất cấu trúc chỉ mục mới là DO-TPR*-tree, dựa trên cấu trúc cây TPR*- tree. Cấu trúc này sử dụng điều chỉnh mật độ đủ tốt và tỏ ra rất hiệu quả khi xây dựng ứng dụng MODB với hạ tầng viễn thông đang phát triển, đôi lúc còn xảy ra tình trạng mất kết nối như ở Việt Nam. Luận án hướng tới một số vấn đề có thể tiếp tục nghiên cứu: - Phát triển phương pháp dự đoán theo hành vi của đối tượng theo các mô hình thống kê, suy luận khác nhằm nâng cao khả năng dự đoán vị trí của đối tượng ở tương lai xa. - Phát triển cấu trúc chỉ mục DO-TPR*-tree trên mạng giao thông đô thị (Fixed Network) nhằm tiếp tục tối ưu truy vấn liên tục vị trí đối tượng chuyển động trong 96 các ứng dụng MODB cho đô thị (quản lý phương tiện/người chuyển động trong thành phố với số lượng rất lớn, tần suất cập nhật và truy vấn liên tục rất cao). 97 DANH MỤC CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ 1. Nguyễn Tiến Phương, Đặng Văn Đức và đồng nghiệp, “Một mô hình dịch vụ trên cơ sở vị trí địa lý để theo dõi, giám sát đối tượng chuyển động”, Kỷ yếu hội thảo “Một số vấn đề chọn lọc của Công nghệ thông tin và truyền thông”, Biên Hòa, 2009, trang 512-523. 2. Nguyễn Tiến Phương, Đặng Văn Đức, “Dự đoán vị trí của đối tượng chuyển động theo mô hình W-EWMA”, Kỷ yếu hội thảo “Một số vấn đề chọn lọc của Công nghệ thông tin và truyền thông”, Cần Thơ, 2011, trang 109-116. 3. Nguyen Tien Phuong, Dang Van Duc, “Predict the location of moving objects using mining Association rules of movement patterns”, Journal of Computer Science and Cybernetics, T.29, S.3 (2013), p252-264. 4. Nguyen Tien Phuong, Dang Van Duc, “DO-TPR*-tree: A density optimal method for TPR*-tree”, Journal of Computer Science and Cybernetics, T31, S1 (2015), p43-54. 98 TÀI LIỆU THAM KHẢO 1. Agrawal R., Imielinski T., Swami A. (2003), “Mining association rules between sets of items in large databases”, ACM Sigmod Int. Conf. on Management of Data, pp. 207-216. 2. Beckmann N., Kriegel H., Schneider R., and Seeger B. (1990), “The R*-tree: An efficient and robust access method for points and rectangles”, Proc. of ACM SIGMOD Record, New York, NY, USA, 19, pp. 322-331. 3. Cai Y. (2004), “Processing range-monitoring queries on heterogeneous mobile objects”, Proc. IEEE Inter. Conf. on Mobile Data Management, pp. 27-38. 4. Cai Y., and Ying Cai (2006), “Real-time processing of range-monitoring queries in heterogeneous mobile databases”, IEEE Transactions on Mobile Computing, 5(7), pp. 931-942. 5. Craig S., Raj M., Stephen B. (2003), “An Approach to Predicting the Location of Moving Objects During On-Road Navigation”, 18th Int. Joint Conf. on Artificial Intelligence. 6. Gedik B. (2006), “MobiEyes: A distributed location monitoring service using moving location queries”, IEEE Transactions on Mobile Computing, 5(10), pp. 1384-1402. 7. Gedik B. (2006), “Processing moving queries over moving objects using motion-adaptive indexes”, IEEE Transactions on Knowledge and Data Engineering, 18(5), pp. 651-668. 8. Güting R. H. (2000), “A Foundation for Representing and Querying Moving Objects”, ACM transactions on database systems, 25(1), pp. 1-42. 9. Guttman A. (1984), “R-trees: a dynamic index structure for spatial searching”, Proc. of ACM SIGMOD ’84, Boston, Massachusetts, USA, ACM, New York, NY, USA, pp. 47–57. 10. Guttman, Antonin (1984), “R-trees: a dynamic index structure for spatial searching”, SIGMOD Record (ACM Special Interest Group on Management of Data), pp. 47-57. 99 11. Hoyoung J. et al. (2008), “A Hybrid Prediction Model for Moving Objects”, Data Engineering, IEEE 24th Int. Conf.. 12. Huang X., and Jensen C. S. (2004), “Towards a streams-based framework for defining location-based queries”, Proc. of the 2nd Workshop on SpatioTemporal Database Management (STDBM), pp. 73–80. 13. Ilarri S. (2006), “Location-dependent queries in mobile contexts: Distributed processing using mobile agents”, IEEE Transactions on Mobile Computing, 5(8), pp. 1029-1043. 14. Kalnis P., Mamoulis N., Bakiras S. (2005), “On discovering moving clusters in spatio-temporal data”, Proc. of the Intl. Symposium on Spatial and Temporal Databases, pp. 364–381. 15. Kim Dong-Oh, Lee Kang-Jun (2007), “An Efficient Indexing Technique for Location Prediction of Moving Objects”, Proc. of the 11th Int. Conf., KES 2007 and XVII Italian Workshop on Neural Networks Conf. on Knowledge- Based Intelligent Information and Engineering Systems. 16. Lazaridis I., Porkaew K., and Mehrotra S. (2002), “Dynamic queries over mobile objects”, Proc. of the 8th Int. Conf. on Extending Database Technology (EDBT), Springer, Berlin/Heidelberg, Germany, pp. 269-286. 17. Lee D. L., Xu J., Zheng B., and Lee W. C. (2002), “Data management in location-dependent information services”, IEEE Pervasive Computing, Vol. 1, pp. 65-72. 18. Li Y., He B., Luo Q., and Yi K. (2009), “Tree indexing on flash disks”, Proc. of ICDE ’09, Shanghai, China, IEEE Computer Society, Washington DC, USA, pp. 1303-1306. 19. Luis O. A., Vania B. et al. (2007), “A Model for Enriching Trajectories with Semantic Geographical Information”, Proc. of the 15th annual ACM Int. Sym. on Advances in geographic information systems, New York, NY, USA. 100 20. Madhavan R., and Schlenoff C. (2003), “Moving Object Prediction and Tracking for Off-road Autonomous Navigation”, Proc. of the SPIE Aerosense 2003 Conf., Orlando, FL. 21. Marcin G., Pawel J. 2009, “Using Apriori-like Algorithms for Spatio- Temporal Pattern Queries”, Proc. of the Int. MultiConf. on Computer Science and Information Technology, pp. 43-48. 22. Martin E., Hans-Peter K., Jörg S., Xiaowei X. (1996), “A density-based algorithm for discovering clusters in large spatial databases with noise”, Proc. of the 2nd Int. Conf. on Knowledge Discovery and Data Mining (KDD-96), AAAI Press. pp. 226–231. 23. Mikołaj M. (2007), “Mining Frequent Trajectories of Moving Objects for Location Prediction”, Proc. of the 5th Int. Conf. on Machine Learning and Data Mining in Pattern Recognition. 24. Mokbel M. F. (2004), “SINA: Scalable incremental processing of continuous queries in spatiotemporal databases”, Proc. ACMSIGMOD Inter. Conf. on Management of Data, pp. 623-634. 25. Mokbel M. F., and Aref W. G. (2008), “SOLE: Scalable on-line execution of continuous queries on spatiotemporal data streams”, VLDB J., 17(5), pp. 971– 995. 26. Mokbel M. F., Xiong X., Hammad M. A., and Aref W. G. (2005), “Continuous query processing of spatiotemporal data streams in PLACE”, GeoInformatica, 9(4), pp. 343-365. 27. MonetDB (2008), “MonetDB Introduction”, www.monetdb.org/documentation/ UserGuide. 28. Nascimento M. A., Silva J. R. O., and Theodoridis, Y. (1999), “Evaluation of access structures for discretely moving points”, Proc. of the 1st Int. Workshop on Spatio-Temporal Database Management (STDBM), Springer, Berlin/Heidelberg, Germany, pp. 171–188. 101 29. Nehme R. V., et al. (2006), “SCUBA: Scalable Cluster-Based Algorithm for evaluating continuous spatio-temporal queries on moving objects”, Advances in Database Technology – EDBT, Springer Berlin/Heidelberg, pp. 1001-1019. 30. Nehme R. V., et al. (2007), “ClusterSheddy: Load shedding using moving clusters over spatiotemporal data streams”, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp. 637-651. 31. Nishimura S. (2011), “MD-HBase: A scalable multidimensional data infrastructure for location aware services”, IEEE 12th Int. Conf. on Mobile Data Management, pp. 7-16. 32. Ouri W., Prasad S., Bo X., Jutai Z., and Sam C. (1999), “DOMINO: databases fOr MovINg Objects tracking”, SIGMOD Rec, 28(2), pp. 547-549 33. Patel J. M., Chen Y., and Chakka V. P. (2004), “Stripes: an efficient index for predicted trajectories”, SIGMOD, pp. 635-646. 34. Patroumpas K. and Sellis T. K. (2004), “Managing trajectories of moving objects as data streams”, Proc. of the 2nd Workshop on Spatio-Temporal Database Management (STDBM), pp. 41-48. 35. Prabhakar S. (2002), “Query indexing and velocity constrained indexing: Scalable techniques for continuous queries on moving objects”, IEEE Transactions on Computers, 51(10), pp. 1124-1140. 36. Saltenis S., Jensen C. S., Leutenegger S. T., and Lopez M. A. (2000), “Indexing the positions of continuously moving objects”, Proc. of ACM SIGMOD Record, New York, NY, USA, 29, pp. 331-342. 37. Silva Y. N., Xiong X., and Aref W. G. (2009), “The RUM-tree: Supporting frequent updates in R-trees using memos”, VLDB Journal, 18, pp. 719-738. 38. Sistla A. P. (1997), “Modeling and querying moving objects”, Proc. Int. Conf. on Data Engineering, pp. 422-432. 39. Spaccapietra, et al. (2007), A conceptual view on trajectories, Technical report, Ecole Polytechnique Federal de Lau-sanne. 102 40. Su J., Xu H., and Ibarra O. H. (2001), “Moving objects: Logical relationships and queries”, Proc. of the 7th Int. Symposium on Advances in Spatial and Temporal Databases (SSTD), Springer, Berlin/Heidelberg, Germany, pp. 3- 19. 41. Tao Y., Faloutsos C., Papadias D., and Liu B. (2004), “Prediction and indexing of moving objects with unknown motion patterns”, SIGMOD, pp. 611-622. 42. Tao Y., Papadias D., and Sun J. (2003), “The TPR*-tree: An optimized spatio- temporal access method for predictive queries”, Proc. of the 29th Int. Conf. on Very Large Data Bases, USA, pp. 790-801. 43. Theodoridis Y., Silva R., and Nascimento M. (1999), “On the generation of spatiotemporal datasets,” Advances in Spatial Databases, pp. 147-164. 44. Trajcevski G. (2004), “CAT: Correct answers of continuous queries using triggers”, Lecture Notes in Computer Science 2992, pp. 837-840. 45. Wang Y., Lim E.P., Hwang S.Y. (2006), “Efficient mining of group patterns from user movement data”, DKE57, pp. 240-282. 46. Wolfson O., Xu B., Chamberlain S., and Jiang L. (1998), “Moving objects databases: issues and solutions”, Scientific and Statistical Database Management, pp. 111-122. 47. Xiaoguang H., Yan Y., et al. (2007), “Prediction of Moving Objects' K- Nearest Neighbor Based on Fuzzy-Rough Sets Theory”, Fuzzy Systems and Knowledge Discovery. 48. Yiu M., Tao Y., and Mamoulis N. (2008), “The Bdual-tree: Indexing moving objects by space filling curves in the dual space”, The Int. Journal on Very Large Data Bases, 17, pp. 379-400. 49. Zheng B. (2010), “DISQO: A DIStributed Framework for Spatial Queries over Moving Objects”, 39th Int. Conf. on Parallel Processing, pp. 414-423. 50. Chen, Y. (2003), “CAMEL: A moving object database approach for intelligent location aware services”, Lecture Notes in Computer Science 2574, pp. 331- 334. 103 51. Arthur A.S., Gopalan N.P. (2011), “Frequent Pattern Mining of Trajectory Coordinates using Apriori Algorithm”, International Journal of Computer Applications (0975 – 8887), vol. 22, no. 9. 52. Heena R., Shuchita U., Vinod K. (2014), “Frequent Pattern Analysis of Moving Objects Using Apriori Algorithm”, International Journal of Emerging Research in Management &Technology, vol. 3, issue 4. 53. Gokhan Y., Dimitrios K., et al. (2005), “A data mining approach for location prediction in mobile environments” Data & Knowledge Engineering, vol. 54, no. 2, pp. 121-146. 54. S. Rajagopal, R.B. Srinivasan, R.B. Narayan, X.B.C. Petit (2002), “GPS-based predictive resource allocation in cellural networks”, Proceedings of the IEEE International Conference on Networks (IEEE ICON’02), pp. 229-234. 55. A. Bhattacharya, S.K. Das (2002), “LeZi-Update: An information-theoretic approach to track mobile users in PCS networks”, ACM Wireless Networks, vol. 8, issue (2–3), pp. 121-135. 56. Patrick P. C., Martial H. (2006), “Learning and Predicting Moving Object Trajectory: A Piecewise Trajectory Segment Approach”, tech. report CMU- RI-TR-06-42, Robotics Institute, Carnegie Mellon University. 57. Lim S.C. (2011), “A More Efficient TPR*-Tree with Cooling-down Nodes”, Proceedings of the Korea Information Science Society, Vol. 1 No. 1B. 58. Fang Y., Cao J., Wang J., et al. (2012), “HTPR*-Tree: An Efficient Index for Moving Objects to Support Predictive Query and Partial History Query”, LNCS 7142. 59. Lin B., Su J. (2005), “Handling Frequent Updates of Moving Objects”, ACM 14th Conference on Information and Knowledge Management. 60. Liao W., Tang G., Jing N., Zhong Z. (2006), “VTPR-Tree: An Efficient Indexing Method for Moving Objects with Frequent Updates”, LNCS 4231. 104 61. He M.-S., Dong Y.-H., Fu S.-C. (2011), “TPRA-tree: An Improved Spatial- temporal Index for Predictive Queries”, Journal of Ningbo University Natural Science and Engineering Edition, Vol. 24 No. 1. 62. Jamal R. (2013), “Detection of Objects in Motion - A Survey of Video Surveillance”, Journal of Scientific Research - Advances in Internet of Things, Vol.3 No.4. 63. Caifeng L., Ling W., Jidong C., et al. (2007), “Effective Density Queries for Moving Objects in Road Networks”, Proc. of the joint 9th Asia-Pacific web and 8th Int. Conf. on web-age Info. Mgt. Conf. on Adv. in data and web Mgt., Berlin, pp. 200-211