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

Luận án trình bày các kỹ thuật dự báo vị trí và truy vấn đối tượng chuyển động trong cơ sở dữ liệu không gian thời gian, nâng cao hiệu quả xử lý dữ liệu.

• Tác giả: Nguyễn Tiến Phương
• Người hướng dẫn: PGS. Đặng Văn Đức
• Trường học: Học viện Khoa học và Công nghệ Việt Nam
• Chuyên ngành: Cơ sở toán học cho tin học
• Đề tài: Kỹ Thuật Dự Báo Vị Trí Đối Tượng Chuyển Động Trong Cơ Sở Dữ Liệu Không Gian Thời Gian
• Loại tài liệu: luận án tiến sĩ
• Năm xuất bản: 2015
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CAM ĐOAN
• 1. CHƯƠNG 1: CƠ SỞ DỮ LIỆU CÁC ĐỐI TƯỢNG CHUYỂN ĐỘNG
• 1.1. Một số khái niệm cơ bản
• 1.2. Cơ sở dữ liệu không gian-thời gian
• 1.3. Cơ sở dữ liệu các đối tượng chuyển động
• 1.4. Dữ liệu trong cơ sở dữ liệu các đối tượng chuyển động
• 1.5. Truy vấn trong cơ sở dữ liệu các đối tượng chuyển động
• 1.6. Các vấn đề cần giải quyết
• 1.6.1. Vấn đề về mô hình hóa vị trí
• 1.6.2. Vấn đề về ngôn ngữ truy vấn
• 1.6.3. Vấn đề về lập chỉ mục
• 1.6.4. Vấn đề về tính không chắc chắn/không chính xác
• 2. CHƯƠNG 2: DỰ ĐOÁN VỊ TRÍ CỦA ĐỐI TƯỢNG CHUYỂN ĐỘNG
• 2.1. Dự đoán vị trí của đối tượng dựa theo hàm chuyển động
• 2.2. Dự đoán dựa theo hàm tuyến tính
• 2.3. Dự đoán dựa theo hàm phi tuyến
• 2.4. Dự đoán dựa trên hành vi của đối tượng
• 2.5. Luật kết hợp
• 2.6. Thuật toán phân cụm dựa trên mật độ DBSCAN
• 2.7. Mẫu hình di chuyển
• 2.8. Khai phá mẫu hình di chuyển
• 2.9. Khai phá luật kết hợp của mẫu hình quỹ đạo để dự đoán vị trí của đối tượng chuyển động
• 3. CHƯƠNG 3: LẬP CHỈ MỤC DỮ LIỆU KHÔNG GIAN-THỜI GIAN
• 3.1. Cấu trúc cây R-tree
• 3.2. Cấu trúc cây TPR-tree
• 3.3. Cấu trúc cây DO-TPR*-tree
• 3.4. Thuật toán tìm kiếm DOA_Search
• 3.5. Kết quả thực nghiệm
• DANH MỤC CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng Quan Về Kỹ Thuật Dự Báo Vị Trí Đối Tượng Chuyển Động

Kỹ thuật dự báo vị trí đối tượng chuyển động trong cơ sở dữ liệu không gian-thời gian đang trở thành một lĩnh vực nghiên cứu quan trọng. Sự phát triển của công nghệ định vị và cơ sở dữ liệu đã tạo ra nhiều cơ hội mới cho việc quản lý thông tin vị trí. Các ứng dụng của kỹ thuật này không chỉ giúp nâng cao hiệu quả trong quản lý giao thông mà còn hỗ trợ trong nhiều lĩnh vực khác như cứu hộ, cứu nạn và theo dõi tài sản.

1.1. Khái Niệm Cơ Bản Về Dự Báo Vị Trí

Dự báo vị trí là quá trình ước lượng vị trí tương lai của một đối tượng dựa trên dữ liệu lịch sử và các mô hình toán học. Các phương pháp dự báo thường sử dụng hàm chuyển động để xác định quỹ đạo di chuyển của đối tượng.

1.2. Tầm Quan Trọng Của Cơ Sở Dữ Liệu Không Gian

Cơ sở dữ liệu không gian cung cấp nền tảng cho việc lưu trữ và truy vấn thông tin vị trí. Việc tổ chức dữ liệu một cách hiệu quả giúp tăng tốc độ truy vấn và giảm thiểu chi phí cập nhật thông tin.

II. Thách Thức Trong Dự Báo Vị Trí Đối Tượng Chuyển Động

Mặc dù có nhiều tiến bộ trong kỹ thuật dự báo vị trí, nhưng vẫn tồn tại nhiều thách thức cần giải quyết. Các vấn đề như tính không chắc chắn trong dữ liệu, độ chính xác của mô hình dự báo và khả năng xử lý dữ liệu lớn là những yếu tố quan trọng cần được xem xét.

2.1. Tính Không Chắc Chắn Trong Dữ Liệu

Dữ liệu vị trí thường xuyên thay đổi và có thể bị ảnh hưởng bởi nhiều yếu tố bên ngoài. Việc xử lý tính không chắc chắn này là một thách thức lớn trong việc dự đoán chính xác vị trí của đối tượng.

2.2. Độ Chính Xác Của Mô Hình Dự Báo

Độ chính xác của các mô hình dự báo phụ thuộc vào chất lượng dữ liệu đầu vào và phương pháp dự báo được sử dụng. Cần có các phương pháp cải tiến để nâng cao độ chính xác trong dự đoán vị trí.

III. Phương Pháp Dự Báo Vị Trí Đối Tượng Chuyển Động Hiện Nay

Có nhiều phương pháp khác nhau được áp dụng để dự đoán vị trí của đối tượng chuyển động. Các phương pháp này bao gồm dự đoán theo hàm chuyển động, mô hình hóa hành vi và khai thác mẫu hình di chuyển.

3.1. Dự Đoán Theo Hàm Chuyển Động

Phương pháp này sử dụng các hàm toán học để mô hình hóa chuyển động của đối tượng. Các hàm này có thể là tuyến tính hoặc phi tuyến, tùy thuộc vào đặc điểm di chuyển của đối tượng.

3.2. Khai Thác Mẫu Hình Di Chuyển

Khai thác mẫu hình di chuyển giúp nhận diện các quỹ đạo di chuyển phổ biến của đối tượng. Điều này có thể cải thiện độ chính xác của dự đoán vị trí trong tương lai.

IV. Ứng Dụng Thực Tiễn Của Kỹ Thuật Dự Báo Vị Trí

Kỹ thuật dự báo vị trí có nhiều ứng dụng thực tiễn trong đời sống. Từ quản lý giao thông đến theo dõi tài sản, các ứng dụng này giúp nâng cao hiệu quả và giảm thiểu rủi ro trong nhiều lĩnh vực.

4.1. Quản Lý Giao Thông Thông Minh

Các hệ thống quản lý giao thông thông minh sử dụng kỹ thuật dự báo vị trí để tối ưu hóa luồng giao thông, giảm thiểu ùn tắc và nâng cao an toàn giao thông.

4.2. Theo Dõi Tài Sản

Kỹ thuật này cũng được áp dụng trong việc theo dõi tài sản như xe cộ, thiết bị và hàng hóa. Việc dự đoán vị trí giúp người dùng có thể quản lý tài sản một cách hiệu quả hơn.

V. Kết Luận Về Kỹ Thuật Dự Báo Vị Trí Đối Tượng Chuyển Động

Kỹ thuật dự báo vị trí đối tượng chuyển động trong cơ sở dữ liệu không gian-thời gian đang phát triển mạnh mẽ. Mặc dù còn nhiều thách thức, nhưng tiềm năng ứng dụng của nó là rất lớn. Nghiên cứu và cải tiến các phương pháp dự báo sẽ giúp nâng cao hiệu quả và độ chính xác trong quản lý thông tin vị trí.

5.1. Tương Lai Của Kỹ Thuật Dự Báo

Với sự phát triển của công nghệ, kỹ thuật dự báo vị trí sẽ ngày càng trở nên chính xác và hiệu quả hơn. Các nghiên cứu mới sẽ tiếp tục mở ra nhiều cơ hội ứng dụng trong thực tiễn.

5.2. Đề Xuất Nghiên Cứu Thêm

Cần có thêm nhiều nghiên cứu để giải quyết các vấn đề còn tồn tại trong dự báo vị trí. Việc phát triển các mô hình mới và cải tiến các phương pháp hiện tại sẽ là hướng đi quan trọng trong tương lai.

Nội dung chính

Tổng quan luận án

Luận án tiến sĩ của Nguyễn Tiến Phương, bảo vệ tại Học viện Khoa học và Công nghệ, Viện Hàn lâm Khoa học và Công nghệ Việt Nam, năm 2015, thuộc chuyên ngành Cơ sở toán học cho tin học (mã số 62 46 01 10), dưới sự hướng dẫn của PGS. Đặng Văn Đức. Luận án tiếp cận theo hướng định lượng – kỹ thuật, kết hợp xây dựng mô hình lý thuyết với thực nghiệm trên dữ liệu mô phỏng.

Tính cấp thiết và khoảng trống nghiên cứu

Sự hội tụ của công nghệ định vị vệ tinh (GPS), truyền thông không dây (GPRS/3G), thiết bị di động thông minh và hệ thống thông tin địa lý (GIS) đã tạo ra môi trường nhận biết vị trí, trong đó lượng dữ liệu vị trí các đối tượng chuyển động cập nhật liên tục và có quy mô rất lớn. Các hệ quản trị cơ sở dữ liệu (DBMS) quan hệ truyền thống không được thiết kế để xử lý dữ liệu thay đổi liên tục theo thời gian như vị trí đối tượng chuyển động, dẫn đến ba vấn đề cốt lõi: (i) chi phí cập nhật quá cao khi số lượng đối tượng lớn, (ii) hiệu năng truy vấn thấp do thiếu cấu trúc chỉ mục phù hợp, (iii) độ không chắc chắn trong dữ liệu vị trí chưa được xử lý thỏa đáng. Tại Việt Nam, thời điểm nghiên cứu chưa có công trình cụ thể nào về hệ cơ sở dữ liệu nhận biết vị trí hay mô hình cơ sở dữ liệu các đối tượng chuyển động (MODM).

Mục tiêu và các kết quả chính

Luận án đặt mục tiêu nghiên cứu các vấn đề liên quan đến cơ sở dữ liệu các đối tượng chuyển động (MODB), bao gồm tổ chức, lưu trữ và truy vấn vị trí trong tương lai, đồng thời đề xuất kỹ thuật nâng cao tốc độ và độ chính xác truy vấn. Cụ thể, luận án giải quyết hai vấn đề:

(a) Nghiên cứu cơ sở dữ liệu các đối tượng chuyển động.

(b) Đề xuất phương pháp, kỹ thuật nâng cao tốc độ và độ chính xác truy vấn vị trí.

Hai kết quả chính được công bố:

(1) Giải quyết vấn đề mô hình hóa vị trí thông qua hai phương pháp dự đoán: dự đoán theo hàm chuyển động sử dụng mô hình W-EWMA và dự đoán theo hành vi sử dụng khai phá luật kết hợp mẫu hình di chuyển.

(2) Đề xuất cấu trúc chỉ mục DO-TPR*-tree nhằm giảm vùng không gian trống và nâng cao hiệu năng truy vấn dữ liệu không gian-thời gian.

Đối tượng và phạm vi nghiên cứu

Đối tượng nghiên cứu là các kỹ thuật dự đoán vị trí và truy vấn trong cơ sở dữ liệu không gian-thời gian cho đối tượng chuyển động (điểm chuyển động – moving point). Lớp bài toán hướng tới là quản lý thông tin đối tượng chuyển động và quản lý, điều hành giao thông, trong đó sai số vị trí vài mét được chấp nhận và ưu tiên tốc độ phản hồi. Phạm vi không gian: không gian hai chiều (2D); phạm vi thời gian thực nghiệm giới hạn trong bộ dữ liệu mô phỏng được mô tả trong chương 3.

---

Tổng quan tài liệu và vị trí của luận án

Các hướng nghiên cứu trước

Luận án điểm lại các công trình theo ba hướng chính:

Hướng mô hình hóa dữ liệu vị trí:

• Sistla cùng đồng nghiệp thiết kế mô hình dữ liệu MOST [38], duy trì véc tơ vị trí cập nhật theo hàm tuyến tính hoặc phi tuyến dạng chuyển động đệ quy (Recursive Motion Function – RMF).
• Guting và đồng nghiệp [8] thiết kế hệ thống biểu diễn đối tượng chuyển động bằng kiểu dữ liệu trừu tượng "điểm chuyển động" và "vùng chuyển động".
• Su và Ibarra [40] đề xuất cơ sở dữ liệu ràng buộc thông tin vị trí bằng công thức toán học.
• MD-HBase [31] tạo hệ quản trị dữ liệu cho dịch vụ dựa trên vị trí, tận dụng cấu trúc chỉ mục đa chiều trên bộ lưu trữ khóa-giá trị.
• Huang và Jensen [12] sử dụng dòng dữ liệu (data streams) để mô hình hóa dữ liệu vị trí; Patroumpas và Sellis [34] mô hình hóa đối tượng chuyển động như dòng quỹ đạo.
• PLACE [26] mở rộng hệ thống quản lý dòng dữ liệu với khả năng nhận biết vị trí, sử dụng ước lượng gia tăng.
• Chen đề xuất CAMEL [50], cơ chế giám sát tích cực liên tục dựa trên dòng dữ liệu và chỉ số lưới.

Hướng xử lý truy vấn phụ thuộc vị trí:

• Cai và đồng nghiệp [3][4] phát triển MQM (Monitoring Query Management), trong đó đối tượng chuyển động tự giám sát truy vấn và báo cáo khi vị trí ảnh hưởng đến kết quả.
• MobiEyes [6] định nghĩa khu vực giám sát cho mỗi truy vấn, đối tượng thông báo khi vượt ranh giới.
• Gedik [7] đề xuất MAI (Motion Adaptive Indexing), lập chỉ mục các hộp ranh giới nhạy chuyển động (MSB) thay vì lập chỉ mục vị trí trực tiếp.
• Prabhakar và đồng nghiệp [35] đề xuất lập chỉ mục truy vấn kết hợp VCI (Velocity-Constraint Indexing).
• Zheng và đồng nghiệp đề xuất DISQO [49] xử lý cả truy vấn chụp lại và truy vấn không gian liên tục.
• Hệ thống DOMINO [32] sử dụng mô hình MOST kết hợp dự đoán vị trí tương lai.
• CAT [44] lưu quỹ đạo đối tượng và dùng trigger để cập nhật truy vấn liên tục.
• SINA [24] đánh giá truy vấn vị trí đồng thời; SOLE [25] (Mokbel và Aref) xử lý dòng dữ liệu vị trí với phát tán tải (load shedding); SCUBA [29] phân cụm đối tượng và truy vấn; LOQOMOTION [13] dùng tác nhân di động cho truy vấn người dùng lẫn đối tượng chuyển động; Lazaridis và đồng nghiệp [16] xử lý truy vấn động qua chỉ mục hình bao chuyển động.

Hướng lập chỉ mục dữ liệu không gian-thời gian:

• Cấu trúc R-tree [10] lập chỉ mục không gian tĩnh, không phù hợp trực tiếp với dữ liệu vị trí thay đổi liên tục.
• TPR-tree [36] lưu vị trí hiện tại và vận tốc tại các thời điểm cụ thể, cho phép dự đoán vị trí tương lai.
• TPR*-tree [42] cải tiến từ TPR-tree, đạt hiệu suất cao hơn khoảng 5 lần so với TPR-tree; là nền tảng để tiếp tục cải tiến theo nhiều hướng khác nhau trong giai đoạn 2005–2012.

Khoảng trống luận án giải quyết

Các nghiên cứu trên chưa giải quyết thỏa đáng hai vấn đề kết hợp: (i) dự đoán vị trí hiệu quả trong cả ngắn hạn lẫn dài hạn để giảm tần suất cập nhật vào MODB, và (ii) cấu trúc chỉ mục xử lý tình trạng mất kết nối định kỳ khiến MBR (Minimum Bounding Rectangle) của nút cây phình to với vùng không gian trống lớn. Đặc biệt, chưa có nghiên cứu nào trong nước về lĩnh vực này.

---

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết và khái niệm

Luận án xây dựng trên các khái niệm và lý thuyết sau:

• Cơ sở dữ liệu không gian-thời gian (Spatio-temporal database): kết hợp cơ sở dữ liệu không gian (hỗ trợ hình học, chỉ mục đa chiều) và cơ sở dữ liệu thời gian (thời gian hiệu lực – valid time, thời gian giao dịch – transaction time).
• MODB (Moving Objects Database): dạng thu gọn của cơ sở dữ liệu không gian-thời gian, chỉ quan tâm đến điểm chuyển động (moving point – mpoint).
• Thuộc tính động (dynamic attribute): thuộc tính có giá trị thay đổi liên tục theo hàm phụ thuộc thời gian, gồm các thuộc tính phụ updatevalue, updatetime và function; khái niệm này là nền tảng cho việc giảm tần suất cập nhật.
• Mẫu hình di chuyển (movement pattern): chuỗi vùng địa lý mà đối tượng di chuyển qua với độ hỗ trợ (support) đủ lớn, được khai phá từ quỹ đạo lịch sử.
• Luật kết hợp (association rules): áp dụng trên mẫu hình quỹ đạo để suy diễn vị trí tương lai.
• MBR (Minimum Bounding Rectangle) và VBR (Velocity Bounding Rectangle): các khái niệm hình học bao quanh tập đối tượng trong cấu trúc chỉ mục cây.

Phương pháp nghiên cứu (định lượng – kỹ thuật)

Dự đoán theo hàm chuyển động:

• Mô hình tuyến tính: tính vị trí $l(t_q) = l_0 + v_0 \times (t_q - t_0)$ (công thức 2-1).
• Mô hình phi tuyến và phân đoạn tuyến tính thông minh (piece-wise line segments).
• Mô hình W-EWMA (Window Exponentially Weighted Moving Average): cửa sổ giới hạn trên chuỗi vận tốc, khắc phục nhược điểm của EWMA (Exponentially Weighted Moving Average) và SMA (Simple Moving Average) khi dự đoán vị trí gần thời điểm hiện tại.

Dự đoán theo hành vi đối tượng:

• Thuật toán phân cụm DBSCAN (Density-Based Spatial Clustering of Applications with Noise) để phân tách quỹ đạo thành quỹ đạo con và xác định các điểm dừng.
• Khai phá mẫu hình di chuyển từ quỹ đạo con.
• Khai phá luật kết hợp trên mẫu hình quỹ đạo để dự đoán vị trí ở các thời điểm xa hiện tại.

Lập chỉ mục:

• Phân tích lý thuyết và cài đặt cấu trúc cây R-tree, TPR-tree, TPR*-tree.
• Đề xuất cấu trúc DO-TPR*-tree với điều kiện mật độ đủ tốt (density-ordered) tại thời điểm truy vấn.
• Xây dựng và chứng minh tính đúng đắn của thuật toán tìm kiếm DOA_Search.

Nguồn dữ liệu

Thực nghiệm sử dụng bộ dữ liệu mô phỏng các đối tượng chuyển động được mô tả trong Bảng 3 (chương 3), bao gồm tọa độ quỹ đạo mẫu (Bảng 2.1), dữ liệu di chuyển hàng ngày (Bảng 2.2) và dữ liệu thực nghiệm cho cấu trúc chỉ mục (Bảng 3.1). Không có dữ liệu thực tế thu thập từ hệ thống định vị ngoài thực địa được sử dụng trong luận án.

---

Nội dung chính theo từng chương

Chương 1: Cơ sở dữ liệu các đối tượng chuyển động

Chương 1 tổng hợp nền tảng lý luận về MODB. Luận điểm trung tâm là các hệ quản trị CSDL quan hệ hiện có không đủ khả năng xử lý dữ liệu vị trí thay đổi liên tục, đòi hỏi phải xây dựng mô hình riêng. Chương xác định bốn vấn đề cần giải quyết trong MODB:

(1) Mô hình hóa vị trí: Cập nhật vị trí liên tục gây giảm mạnh hiệu năng hệ thống; không cập nhật thì kết quả truy vấn sai lệch; cập nhật qua mạng không dây GPRS/3G/Wifi/Wimax/LTE đồng thời số lượng lớn gây quá tải băng thông.

(2) Ngôn ngữ truy vấn: SQL truyền thống không đủ diễn đạt truy vấn kết hợp phạm vi không gian và thời gian cho đối tượng chuyển động. Các nghiên cứu về ngôn ngữ truy vấn không gian và thời gian còn rời rạc, chưa tích hợp.

(3) Lập chỉ mục: Số lượng đối tượng rất lớn (ví dụ hàng triệu cư dân); lập chỉ mục trực tiếp thuộc tính vị trí buộc phải cập nhật chỉ mục liên tục, không chấp nhận được trong thực tế.

(4) Tính không chắc chắn/không chính xác: Vị trí lưu trong CSDL không luôn trùng vị trí thực tế. Với truy vấn phạm vi, tồn tại hai ngữ nghĩa: "CÓ THỂ" (MAY – khoảng không chắc chắn có giao với vùng truy vấn) và "CHẮC CHẮN" (MUST – khoảng không chắc chắn nằm hoàn toàn trong vùng truy vấn). Câu trả lời xác suất cũng được đề cập (ví dụ: đối tượng object 1 nằm trong P với xác suất 0.x).

Chương mô tả ba kiểu truy vấn phổ biến trong MODB: truy vấn điểm, truy vấn phạm vi và truy vấn k láng giềng gần nhất.

Chương 2: Dự đoán vị trí của đối tượng chuyển động

Chương 2 trình bày hai phương pháp dự đoán vị trí. Luận điểm xuất phát là thuộc tính động (dynamic attribute) – biểu diễn chuyển động của đối tượng thay vì chỉ lưu vị trí tức thời – là chìa khóa giảm tần suất cập nhật CSDL.

Phương pháp 1: Dự đoán theo hàm chuyển động sử dụng W-EWMA

Mô hình tuyến tính (công thức 2-1) tính toán nhanh nhưng độ chính xác thấp trong mạng lưới giao thông phức tạp. Thực nghiệm so sánh thời gian tính toán của các kỹ thuật dự đoán (Hình 2.x – So sánh thời gian tính toán) và so sánh kết quả dự đoán giữa W-EWMA và EWMA (Hình 2.x). Luận án phân tích ảnh hưởng của tham số cửa sổ $w$ và tham số $\alpha$ lên kết quả dự đoán. W-EWMA phù hợp dự đoán vị trí gần thời điểm hiện tại; mô hình tuyến tính đơn thuần dẫn đến dự đoán sai trong nhiều trường hợp thực tế.

Phương pháp 2: Dự đoán theo hành vi – khai phá luật kết hợp mẫu hình di chuyển

Quy trình gồm: (i) phân tách quỹ đạo bằng DBSCAN thành quỹ đạo con; (ii) khai phá mẫu hình di chuyển với ngưỡng độ hỗ trợ nhỏ nhất; (iii) khai phá luật kết hợp từ mẫu hình quỹ đạo để dự đoán vị trí.

Dữ liệu thực nghiệm bao gồm: tọa độ điểm trên quỹ đạo mẫu (Bảng 2.1), dữ liệu di chuyển hàng ngày của đối tượng (Bảng 2.2), quỹ đạo phân tách (Bảng 2.3), di chuyển thường xuyên và độ hỗ trợ (Bảng 2.4), mẫu hình di chuyển với độ hỗ trợ nhỏ nhất là 0 (Bảng 2.5). Phương pháp này cho phép dự đoán ở thời điểm xa hiện tại với độ chính xác tương đối cao, bù đắp cho nhược điểm của phương pháp thứ nhất. Hình so sánh độ chính xác giữa hai phương pháp (Hình 2.x – So sánh độ chính xác hai phương pháp) minh họa ưu thế của phương pháp hành vi ở dự đoán dài hạn.

Chương 3: Lập chỉ mục dữ liệu không gian-thời gian

Chương 3 trình bày nền tảng về các cấu trúc cây chỉ mục và đề xuất cấu trúc mới.

Nền tảng: R-tree [10] biểu diễn hai chiều và cây R-tree đa tầng (Hình 3.x); TPR-tree lưu điểm chuyển động tại nút lá (Hình 3.x) và nút trung gian (Hình 3.x), cập nhật khoảng giới hạn theo tham số thời gian. Hình 3.x thể hiện vùng quét từ thời điểm 0 đến thời điểm 1; Hình 3.x minh họa MBR của R tại thời điểm khởi tạo và mở rộng tại thời điểm 1. Các cấu trúc cây phát triển từ TPR-tree trong giai đoạn 2005–2012 được tóm tắt tại Hình 3.x.

Cấu trúc đề xuất: DO-TPR*-tree

Luận điểm: TPR*-tree gặp vấn đề khi đối tượng chuyển động mất kết nối (không gửi cập nhật vị trí), khiến MBR của nút phình ra vùng không gian trống rất lớn, làm truy vấn lạc vào các nút không có đối tượng thực sự, giảm hiệu năng.

DO-TPR*-tree điều chỉnh MBR của một nút nếu điều kiện mật độ đủ tốt không thỏa mãn tại thời điểm truy vấn. Thuật toán DOA_Search thực hiện tìm kiếm trong cây DO-TPR*-tree và đã được chứng minh tính đúng đắn trong luận án.

Dữ liệu thực nghiệm: Bảng 3.1 (dữ liệu thực nghiệm các đối tượng chuyển động). Kết quả: ảnh hưởng của độ lớn phạm vi truy vấn lên hiệu năng (Hình 3.x); so sánh hiệu năng DO-TPR*-tree với TPR*-tree (Hình 3.x – trang 93) cho thấy DO-TPR*-tree đạt hiệu năng tốt hơn trong nhiều trường hợp. Cấu trúc này phù hợp với hạ tầng viễn thông có thể bị gián đoạn kết nối như tại Việt Nam.

---

Kết quả và những đóng góp mới

Luận án tự nêu hai nhóm đóng góp chính:

Đóng góp về lý luận và kỹ thuật:

Kết quả	Nội dung
(1) Phương pháp dự đoán 1	Dự đoán vị trí theo hàm chuyển động dùng mô hình W-EWMA; xử lý nhanh, phù hợp dự đoán ngắn hạn; giảm tần suất cập nhật thuộc tính động vào MODB
(2) Phương pháp dự đoán 2	Dự đoán theo hành vi qua khai phá luật kết hợp của mẫu hình di chuyển; cho phép dự đoán dài hạn với độ chính xác tương đối cao
(3) Cấu trúc chỉ mục DO-TPR*-tree	Điều chỉnh MBR của nút khi điều kiện mật độ không thỏa mãn tại thời điểm truy vấn; mọi truy vấn sau đó không bị lạc vào vùng không gian trống của nút
(4) Thuật toán DOA_Search	Thuật toán tìm kiếm trong DO-TPR*-tree; đã được chứng minh tính đúng đắn

Đóng góp thực tiễn:

Cấu trúc DO-TPR*-tree thể hiện hiệu quả cao khi xây dựng ứng dụng MODB trong điều kiện hạ tầng viễn thông phát triển chưa đồng đều, có tình trạng mất kết nối như ở Việt Nam. Kết hợp hai phương pháp dự đoán vị trí cho phép hệ thống phản hồi nhanh hơn và giảm tải cập nhật, phù hợp với lớp bài toán quản lý và điều hành giao thông đô thị. Các kết quả được công bố trong bốn công trình khoa học (1)–(4) và báo cáo tại hội thảo Quốc gia "Một số vấn đề chọn lọc của Công nghệ thông tin và truyền thông".

Luận án không nêu kiến nghị chính sách hay giải pháp hành chính cụ thể ngoài phạm vi kỹ thuật.

---

Hạn chế và hướng nghiên cứu tiếp

Luận án không trình bày một mục riêng về hạn chế. Tuy nhiên, từ phạm vi nghiên cứu có thể ghi nhận:

• Phương pháp dự đoán theo hàm chuyển động tuyến tính thừa nhận độ chính xác thấp trong mạng lưới giao thông phức tạp do nhiều yếu tố ảnh hưởng đến véc tơ vận tốc.
• Luận án xác định trong lớp bài toán hướng tới, sai số vị trí vài mét được chấp nhận; các bài toán đòi hỏi độ chính xác định vị cao hơn nằm ngoài phạm vi.
• Thực nghiệm sử dụng dữ liệu mô phỏng; chưa có thực nghiệm trên dữ liệu thực thu thập từ hệ thống định vị ngoài thực địa quy mô lớn.
• Vấn đề ngôn ngữ truy vấn (vấn đề số 2) và bảo vệ tính riêng tư (vấn đề số 3, đề cập trong phần tổng quan) không được luận án giải quyết, được đặt lại cho các nghiên cứu tiếp theo.
• Tính không chắc chắn/không chính xác (vấn đề số 4) được nhận diện nhưng chưa có giải pháp toàn diện trong luận án.

---

Giá trị tham khảo

Luận án có giá trị tham khảo chủ yếu cho các nhóm đối tượng sau trong lĩnh vực tin học, khoa học máy tính và kỹ thuật phần mềm:

• Nghiên cứu sinh và nhà nghiên cứu nghiên cứu về cơ sở dữ liệu không gian-thời gian, cơ sở dữ liệu các đối tượng chuyển động, lập chỉ mục đa chiều và khai phá dữ liệu quỹ đạo. Chương 1 cung cấp tổng quan hệ thống về MODB và bốn vấn đề mở. Chương 3 trình bày chi tiết nền tảng R-tree, TPR-tree, TPR*-tree trước khi đề xuất DO-TPR*-tree.
• Giảng viên và sinh viên đại học, cao học trong các học phần cơ sở dữ liệu nâng cao, GIS và dịch vụ dựa trên vị trí: phần mở đầu và chương 1 có thể dùng làm tài liệu đọc thêm về ứng dụng LBS, MODB và các kiểu truy vấn phổ biến.
• Kỹ sư phần mềm và nhà phát triển hệ thống xây dựng ứng dụng quản lý phương tiện, giám sát giao thông, dịch vụ taxi công nghệ hoặc các hệ thống theo dõi tài sản di động: chương 2 và chương 3 cung cấp thuật toán cụ thể có thể tích hợp vào hệ thống.
• Người làm chính sách và quản lý trong lĩnh vực giao thông đô thị tại Việt Nam: phần mở đầu mô tả bối cảnh ứng dụng, ví dụ hệ thống giám sát giao thông Hà Nội từ tháng 3/2015 và đề án giao thông thông minh, có thể tham khảo khi đặt bài toán kỹ thuật.

---

Câu hỏi thường gặp

1. Sự khác biệt giữa W-EWMA và EWMA trong dự đoán vị trí là gì?

Cả hai đều là các mô hình trung bình động trọng số mũ. W-EWMA (Window Exponentially Weighted Moving Average) sử dụng cửa sổ giới hạn (window) trên chuỗi dữ liệu đầu vào, trong khi EWMA (Exponentially Weighted Moving Average) không giới hạn cửa sổ. Luận án trình bày kết quả so sánh dự đoán giữa W-EWMA và EWMA (Hình trong chương 2) và phân tích ảnh hưởng của tham số $w$ (kích thước cửa sổ) và tham số $\alpha$ lên kết quả dự đoán. W-EWMA được đề xuất thay thế SMA và EWMA trong ngữ cảnh dự đoán vị trí ngắn hạn của đối tượng chuyển động.

2. DO-TPR*-tree giải quyết vấn đề mất kết nối của đối tượng chuyển động như thế nào?

Khi một đối tượng chuyển động mất kết nối và không gửi cập nhật vị trí, MBR của nút chứa nó trong cây TPR*-tree phình ra một vùng không gian trống rất lớn theo thời gian. DO-TPR*-tree kiểm tra điều kiện mật độ đủ tốt của nút tại thời điểm truy vấn; nếu điều kiện không thỏa mãn, cấu trúc điều chỉnh MBR của nút đó. Nhờ vậy, các truy vấn thực hiện sau thời điểm điều chỉnh không bị lạc vào vùng không gian trống, nâng cao hiệu năng. Kết quả thực nghiệm so sánh hiệu năng được trình bày tại trang 93 (Hình so sánh DO-TPR*-tree với TPR*-tree).

3. Hai phương pháp dự đoán vị trí trong luận án bổ sung cho nhau như thế nào?

Phương pháp 1 (dự đoán theo hàm chuyển động dùng W-EWMA) xử lý nhanh và phù hợp dự đoán vị trí gần thời điểm hiện tại, nhưng kém chính xác ở thời điểm xa. Phương pháp 2 (dự đoán theo hành vi, khai phá luật kết hợp mẫu hình di chuyển qua DBSCAN) cho phép dự đoán ở thời điểm xa hiện tại với độ chính xác tương đối cao, nhưng phụ thuộc vào dữ liệu quỹ đạo lịch sử. Luận án nêu rõ kết hợp hai phương pháp này mang lại hiệu quả tốt hơn cho toàn hệ thống truy vấn MODB.

4. Luận án xác định ngưỡng chấp nhận sai số như thế nào trong lớp bài toán hướng tới?

Luận án xác định lớp bài toán quản lý thông tin đối tượng chuyển động và quản lý, điều hành giao thông là lớp bài toán ưu tiên tốc độ phản hồi hơn độ chính xác tuyệt đối. Cụ thể, sai số vị trí vài mét được xác định là có thể chấp nhận trong lớp bài toán này. Tiêu chí này định hướng lựa chọn cả hai phương pháp dự đoán và thiết kế cấu trúc chỉ mục DO-TPR*-tree.

5. Thuật toán DBSCAN được sử dụng trong luận án với mục đích cụ thể nào?

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) được sử dụng trong phương pháp dự đoán theo hành vi (chương 2) để phân tách quỹ đạo di chuyển của đối tượng thành các quỹ đạo con. Từ các quỹ đạo con này, luận án khai phá mẫu hình di chuyển và sau đó khai phá luật kết hợp của mẫu hình quỹ đạo để dự đoán vị trí. Kết quả phân tách được minh họa qua Bảng 2.3 (quỹ đạo của đối tượng) và Bảng 2.4 (di chuyển thường xuyên và độ hỗ trợ).

---

Kết luận

Luận án của Nguyễn Tiến Phương (2015) nghiên cứu hai bài toán kỹ thuật cốt lõi trong cơ sở dữ liệu các đối tượng chuyển động: dự đoán vị trí và lập chỉ mục dữ liệu không gian-thời gian. Về dự đoán vị trí, luận án đề xuất mô hình W-EWMA cho dự đoán ngắn hạn và phương pháp khai phá luật kết hợp mẫu hình di chuyển cho dự đoán dài hạn, hai phương pháp bổ sung cho nhau trong khuôn khổ thuộc tính động. Về lập chỉ mục, luận án đề xuất cấu trúc DO-TPR*-tree dựa trên TPR*-tree với cơ chế điều chỉnh MBR theo điều kiện mật độ, kèm thuật toán DOA_Search đã được chứng minh, cho hiệu năng tốt hơn TPR*-tree trong nhiều trường hợp thực nghiệm. Hai đóng góp này hướng đến ứng dụng thực tiễn trong quản lý và điều hành giao thông đô thị, đặc biệt phù hợp với điều kiện hạ tầng viễn thông đang phát triển của Việt Nam.

Trích đoạn nội dung tài liệu

MỞ ĐẦU Sự kết hợp các chức năng của công nghệ định vị cá nhân, công nghệ định vị vệ tinh, công nghệ truyền thông không dây và công nghệ GIS đã tạo ra một môi trường mới trong đó tất cả các đối tượng chuyển động có thể xác định vị trí của chúng. Các công nghệ này là cơ sở cho việc phát triển mạnh mẽ môi trường nhận biết vị trí và các dịch vụ dựa trên vị trí. Dịch vụ dựa trên vị trí là dịch vụ được đặc chế dựa trên những thông tin về vị trí của đối tượng. Những dịch vụ này là tiềm năng để nâng cao chất lượng cuộc sống nhờ việc thêm các thông tin vị trí vào hầu hết các thiết bị, đối tượng chuyển động như ô tô, máy bay, tàu thủy, máy tính xách tay, điện thoại di động, vật nuôi và cả con người… Hình dưới đây thể hiện một môi trường nhận biết vị trí đơn giản mà trong đó các đối tượng chuyển động sử dụng các thiết bị định vị vị trí như GPS hay điện thoại thông minh.

Các đối tượng này có thể gửi thông tin về vị trí và vận tốc của mình lên máy chủ cơ sở dữ liệu và lấy thông tin cũng như thực hiện các truy vấn từ đó. Môi trường nhận biết vị trí Các ứng dụng của dịch vụ dựa trên vị trí Các thiết bị có hỗ trợ định vị vị trí như GPS, RFID, các thiết bị cầm tay, điện thoại di động… ngày càng được sử dụng rộng rãi (hình 0. Điều này là tiền đề cho việc 10 phát triển các ứng dụng dựa trên vị trí mà trong đó các đối tượng chuyển động cùng với các thiết bị này thay đổi vị trí liên tục trong không gian, theo thời gian. Các thiết bị định vị vị trí Các ứng dụng có thể thấy rõ nhất là quản lý và điều hành giao thông đô thị (hình 0.3); theo dõi, dự báo thời tiết; cảnh báo sóng thần, động đất; theo dõi và xử lý cứu hộ, cứu nạn… Trong các ứng dụng này, người sử dụng có thể thực hiện các truy vấn kiểu như: “Tìm tất cả các xe taxi chưa có khách cách sân bay 1km trong vòng 15 phút nữa?”, “Ước tính lưu lượng xe cộ tại ngã tư A lúc 11h trưa nay”, “Cơn bão B đang hình thành có ảnh hưởng đến vùng V hay không, nếu có thì bao giờ và phạm vi, mức độ phá hủy như thế nào?”… Hình 0.

Ứng dụng của hệ thống quản lý và điều hành giao thông đô thị 11 Với tốc độ đô thị hóa ngày càng nhanh, các thành phố lớn trên chục triệu dân ngày càng nhiều, vấn đề quản lý và điều hành giao thông đô thị càng trở nên bức thiết. Hơn nữa với mức sống ngày càng cao, nhu cầu quản lý tài sản cá nhân như xe cộ, vật nuôi trong nhà hay thậm chí là cả giám sát chăm sóc trẻ em, người cao tuổi ngày càng lớn. Để đáp ứng được các nhu cầu đó, bài toán quản lý thông tin các đối tượng chuyển động dựa trên nền tảng của môi trường và ứng dụng định vị vị trí càng cần có lời giải chính xác, tối ưu. Nhiều mô hình cơ sở dữ liệu các đối tượng chuyển động (MODM - Moving Objects Database Model) đã và đang được nghiên cứu, thử nghiệm.

Trong các mô hình này, dữ liệu của các đối tượng chuyển động, bao gồm cả thông tin về vị trí trong quá khứ, hiện tại và tương lai được lưu trữ và cập nhật thường xuyên. Khó khăn lớn khi giải quyết bài toán này là làm thế nào để khai thác hệ thống một cách hiệu quả khi số lượng đối tượng chuyển động trong không gian-thời gian (spatio- temporal) là rất lớn và thường xuyên thay đổi vị trí. Việc truy vấn vị trí của đối tượng trong tương lai cùng với tính không chắc chắn của nó cũng là một vấn đề cần giải quyết và nâng cao tính chính xác. Một số phương pháp đã được đề xuất nhằm nâng cao khả năng dự đoán vị trí cũng như tăng tốc độ truy vấn của các đối tượng chuyển động.

Tuy nhiên các nghiên cứu này mới đạt được những kết quả nhất định và còn một số khó khăn, hạn chế cần cải tiến, khắc phục. Luận án này tập trung chính vào việc góp phần giải quyết lớp bài toán quản lý thông tin đối tượng chuyển động hay quản lý và điều hành giao thông một cách nhanh chóng, hiệu quả hơn. Tình hình nghiên cứu trên thế giới và trong nước Vấn đề quản lý thông tin đối tượng chuyển động trong môi trường và ứng dụng dựa trên vị trí đã được đặt ra và tìm cách giải quyết từ những năm 90 của thế kỷ trước. Nó đã đạt được những kết quả nhất định và đang được ứng dụng trong thực tế ở nhiều nước phát triển trên thế giới như Mỹ, Nhật Bản, Hàn Quốc… Ở Việt Nam, TP.

Hà Nội đang áp dụng hệ thống giám sát giao thông qua bản đồ số và camera từ tháng 3/2015 (hình 0. Đồng thời, Hà Nội cũng là địa phương đầu tiên thực hiện thí điểm đề án giao thông thông minh dự kiến trong tháng 7/2015 và sẽ triển khai 12 diện rộng 13 trên toàn quốc trong những năm tới. Với đề án này, thông qua phần mềm cài đặt trên điện thoại của người tham gia giao thông, các nhà mạng thu thập thông tin về tốc độ, hướng di chuyển, mật độ xe trên đường. Dữ liệu này sau đó được gửi về trung tâm giám sát để điều chỉnh tức thời hoặc đưa ra các nghiên cứu, quy hoạch giao thông đô thị.

Cũng thông qua đó, người tham gia giao thông có thể xác định đường đi tối ưu, tránh các điểm ùn tắc… Như vậy, cùng với sự phát triển mạnh mẽ của các ứng dụng dựa trên vị trí, khái niệm về hệ cơ sở dữ liệu nhận biết vị trí (Location-aware database systems) ngày càng trở nên quan trọng và đặt ra những thách thức lớn cho sự phát triển của các hệ quản trị cơ sở dữ liệu hiện có. Các hệ quản trị cơ sở dữ liệu hiện tại không phù hợp với việc quản lý các dữ liệu thay đổi liên tục theo thời gian như vị trí của các đối tượng chuyển động. Hệ cơ sở dữ liệu nhận biết vị trí phải có các khả năng sau: a) Mô hình hóa một lượng lớn dữ liệu vị trí theo cách thức nào đó để có thể cập nhật vào và lấy ra một cách hiệu quả b) Xử lý hiệu quả các truy vấn dữ liệu phụ thuộc vị trí c) Đảm bảo sự riêng tư về thông tin vị trí của người dùng. Mô hình hóa dữ liệu vị trí Ứng dụng cung cấp dịch vụ dựa trên vị trí yêu cầu phải truy cập vào một lượng lớn dữ liệu vị trí lại liên tục thay đổi.

Vì có quá nhiều dữ liệu, việc tổ chức chúng theo cách mà những thông tin liên quan có thể được lấy ra một cách hiệu quả là rất quan trọng. Hơn thế, do dữ liệu thay đổi thường xuyên, việc giảm chi phí cập nhật cũng rất cần thiết. Hai kỹ thuật chính để biểu diễn dữ liệu vị trí thường được sử dụng là: cơ sở dữ liệu các đối tượng chuyển động (MODB) và dòng dữ liệu liên tục (data streams). Cơ sở dữ liệu các đối tượng chuyển động Cơ sở dữ liệu các đối tượng chuyển động là phần mở rộng của một hệ thống quản lý cơ sở dữ liệu truyền thống, hỗ trợ lưu trữ dữ liệu vị trí cho đối tượng chuyển 14 động liên tục.

Những nỗ lực đầu tiên trong việc mô hình hóa đối tượng chuyển động là biểu 15 diễn các chuyển động của chúng như là mẫu của các dữ liệu vị trí có sẵn [28]. Nhược điểm của kỹ thuật này là đòi hỏi chi phí cập nhật cao. Sistla cùng đồng nghiệp đã thiết kế mô hình dữ liệu MOST [38] mà trong đó duy trì một véc tơ vị trí cho mỗi đối tượng chuyển động. Véc tơ vị trí sẽ thay đổi theo thời gian bởi một hàm cập nhật, ngay cả nếu không xảy ra một sự cập nhật rõ ràng.

Hàm cập nhật có thể là tuyến tính hoặc phi tuyến dưới dạng chuyển động đệ quy. Guting và đồng nghiệp [8] thiết kế một hệ thống sử dụng các kiểu dữ liệu trừu tượng để biểu diễn các đối tượng chuyển động bằng các khái niệm như: “điểm chuyển động” và “vùng chuyển động”. Su và Ibarra [40] đề xuất một cơ sở dữ liệu ràng buộc thông tin vị trí bằng cách sử dụng công thức toán học để biểu diễn dữ liệu. MD-HBase [31] đã tạo ra hệ quản trị dữ liệu cho dịch vụ dựa trên vị trí mà tận dụng cấu trúc chỉ mục đa chiều nằm trên bộ lưu trữ theo cặp khóa-giá trị.

Bộ lưu trữ cặp khóa-giá trị này cho phép DBMS để xử lý việc chèn một lượng lớn dữ liệu với tốc độ cao trong khi vẫn duy trì khả năng chịu lỗi. Cấu trúc chỉ mục này làm cho việc truy vấn dữ liệu hiệu quả hơn. Trong CSDL các đối tượng chuyển động, việc dự đoán vị trí đóng vai trò quan trọng trong mô hình hóa vị trí nhằm giảm tần suất cập nhật thông tin này. Có một số phương pháp như dự đoán theo hàm chuyển động [33], [34], lô-gíc mờ [47], xác xuất thống kê [5], [19] hay kết hợp nhiều phương pháp khác nhau [15], [23].

Lập chỉ mục là đặc biệt quan trọng trong cơ sở dữ liệu các đối tượng chuyển động vì có một lượng rất lớn dữ liệu và chẳng hệ thống nào muốn tìm kiếm bằng cách kiểm tra tất cả các dữ liệu có trong đó. Cấu trúc cây R-tree [10] có thể được sử dụng để lập chỉ mục dữ liệu không gian, tuy nhiên vì dữ liệu vị trí thường xuyên thay đổi, các chỉ mục này sẽ cần phải được cập nhật thường xuyên. Việc mở rộng cấu trúc cây R-tree cũng như các chiến lược lập chỉ mục khác đã được nghiên cứu để giảm bớt gánh nặng cập nhật, điển hình là TPR-tree, TPR*-tree. TPR-tree [36] 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 những thời điểm cụ thể và do đó rất hiệu quả cho việc tìm kiếm, đồng thời cho phép dự đoán vị trí của đối tượng chuyển động.

Cây TPR*-tree [42] được cải tiến từ TPR-tree và mang lại hiệu suất cao hơn, gấp 5 lần so với cây TPR-tree. Đây là cấu trúc chỉ mục được 16 đánh giá rất cao và tiếp tục được cải 17 tiến 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ế. Dòng dữ liệu liên tục cho thông tin vị trí (data streams) Một dòng dữ liệu liên tục là một cấu trúc được sử dụng cho thông tin đầu vào, trong đó lượng dữ liệu là rất lớn (giả định là vô hạn) và thay đổi liên tục.