Tiến Sĩ 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 -

3
MỤC LỤC
LỜI CAM ĐOAN . 1
LỜI CẢM ƠN . 2
MỤC LỤC 3
DANH MỤC CÁC TỪ VIẾT TẮT VÀ KÝ HIỆU 5
DANH SÁCH HÌNH VẼ 7
DANH SÁCH BẢNG . 9
MỞ ĐẦU . 10
Các ứng dụng của dịch vụ dựa trên vị trí . 10
Tình hình nghiên cứu trên thế giới và trong nước . 12
a. Mô hình hóa dữ liệu vị trí 13
b. Các cách tiếp cận xử lý truy vấn phụ thuộc vị trí 15
c. Tính riêng tư 18
Chương 1 CƠ SỞ DỮ LIỆU CÁC ĐỐI TƯỢNG CHUYỂN ĐỘNG 22
1.1. Một số khái niệm cơ bản . 22
1.1.1. Cơ sở dữ liệu không gian-thời gian . 22
1.1.2. Cơ sở dữ liệu các đối tượng chuyển động . 24
1.1.3. Dữ liệu trong cơ sở dữ liệu các đối tượng chuyển động . 26
1.1.4. Truy vấn trong cơ sở dữ liệu các đối tượng chuyển động 27
1.2. Các vấn đề cần giải quyết 29
1.2.1. Vấn đề về mô hình hóa vị trí . 29
1.2.2. Vấn đề về ngôn ngữ truy vấn 30
1.2.3. Vấn đề về lập chỉ mục . 30
1.2.4. Vấn đề về tính không chắc chắn/không chính xác 31
Chương 2 DỰ ĐOÁN VỊ TRÍ CỦA ĐỐI TƯỢNG CHUYỂN ĐỘNG 33
2.1. Dự đoán vị trí của đối tượng dựa theo hàm chuyển động 35
2.1.1. Dự đoán dựa theo hàm tuyến tính 36
2.1.2. Dự đoán dựa theo hàm phi tuyến . 36
2.2. Dự đoán dựa trên hành vi của đối tượng 504
2.2.1. Luật kết hợp 52
2.2.2. Thuật toán phân cụm dựa trên mật độ DBSCAN . 53
2.2.3. Mẫu hình di chuyển 54
2.2.4. Khai phá mẫu hình di chuyển . 57
2.2.5. 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 . 61
Chương 3 LẬP CHỈ MỤC DỮ LIỆU KHÔNG GIAN-THỜI GIAN 71
3.1. R-tree 73
Cấu trúc cây R-tree . 73
3.2. TPR-tree 76
Cấu trúc cây TPR-tree 76
3.3. TPR*-tree 80
3.4. DO-TPR*-tree . 81
3.4.1. Cấu trúc cây DO-TPR*-tree . 83
3.4.2. Thuật toán tìm kiếm DOA_Search . 84
3.4.3. Kết quả thực nghiệm 89
KẾT LUẬN . 95
DANH MỤC CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ . 97
TÀI LIỆU THAM KHẢO . 985
DANH MỤC CÁC TỪ VIẾT TẮT VÀ KÝ HIỆU
2D/3D 2/3 Dimensional – 2/3 chiều
CAMEL
Continuous Active Monitor Engine - Cơ chế giám sát tích cực liên
tục
DBMS Database Management System – Hệ quản trị cơ sở dữ liệu
DOA_Search
Thuật toán tìm kiếm điều chỉnh theo mật độ của nút trên cây DO-
TPR*-tree
DO-TPR*-tree Cấu trúc cây điều chỉnh theo mật độ dựa trên TPR*-tree
EWMA
Exponentially Weighted Moving Average – Trung bình động trọng
số mũ
GIS Geographical Information System – Hệ thống thông tin địa lý
GPRS General Packet Radio Service - Dịch vụ vô tuyến gói tổng hợp
GPS Global Positioning System – Hệ thống định vị toàn cầu
GSM
Global System for Mobile Communications - Hệ thống thông tin di
động toàn cầu
LBS Location Based Service – Dịch vụ dựa trên vị trí
MAI Motion Adaptive Indexing - Chỉ mục thích ứng chuyển động
MBR Minimum Bounding Rectangle – Hình chữ nhật bao nhỏ nhất
MODB
Moving Objects Database – Cơ sở dữ liệu các đối tượng chuyển
động
MODM
Moving Objects Database Model – Mô hình cơ sở dữ liệu các đối
tượng chuyển động
MQM Monitoring Query Management - Quản lý giám sát truy vấn
MSB
Motion-Sensitive bounding Boxes - Hộp ranh giới nhạy chuyển
động
PLACE
Pervasive Location-Aware Computing Environments - Môi trường
tính toán khắp nơi nhận biết vị trí
RMF Recursive Motion Function – Hàm chuyển động đệ quy 6
SINA
Scalable INcremental hash-based Algorithm – Thuật toán đánh giá
các truy vấn phụ thuộc vị trí đồng thời
SMA Simple Moving Average – Trung bình động đơn giản
SMS Short Message Services – Dịch vụ tin nhắn ngắn
TM Transition Matrix – Ma trận chuyển đổi
VBR Velocity Bounding Rectangle – Hình chữ nhật bao vận tốc
VCI Velocity-Constraint Indexing – Chỉ mục ràng buộc vận tốc
W-EWMA
Window Exponentially Weighted Moving Average – Trung bình
động trọng số mũ sử dụng cửa sổ giới hạn 7
DANH SÁCH HÌNH VẼ
Hình 0.1. Môi trường nhận biết vị trí 10
Hình 0.2. Các thiết bị định vị vị trí . 11
Hình 0.3. Ứng dụng của hệ thống quản lý và điều hành giao thông đô thị 11
Hình 1.1. Cơ sở dữ liệu không gian-thời gian và MODB . 23
Hình 1.2. Mô hình hệ thống ứng dụng MODB . 25
Hình 1.3. Điểm chuyển động rời rạc và liên tục . 27
Hình 1.4. Các kiểu truy vấn phổ biến trong MODB . 28
Hình 1.5. Ngữ nghĩa của CÓ THỂ và CHẮC CHẮN trong MODB 31
Hình 2.1. Dự đoán sai của mô hình tuyến tính . 37
Hình 2.2. So sánh thời gian tính toán của các kỹ thuật dự đoán . 46
Hình 2.3. So sánh kết quả dự đoán của của W-EWMA và EWMA . 47
Hình 2.4. Ảnh hưởng của w với kết quả dự đoán . 48
Hình 2.5. Ảnh hưởng của giá trị α với kết quả dự đoán . 49
Hình 2.6. Quỹ đạo chuyển động của đối tượng và các thông tin địa lý 55
Hình 2.7. Phân tách quỹ đạo của đối tượng 58
Hình 2.8. Quỹ đạo con 59
Hình 2.9. Quy trình khai phá mẫu hình di chuyển 60
Hình 2.10. Sai lệch khi dự đoán di chuyển của đối tượng trong thực tế . 62
Hình 2.11. So sánh độ chính xác của hai phương pháp dự đoán 69
Hình 3.1. Các cấu trúc cây phát triển từ TPR-tree (2005-2012) . 72
Hình 3.2. Biểu diễn hai chiều của R-tree 75
Hình 3.3. Biểu diễn cấu trúc cây R-tree 758
Hình 3.4. Các điểm chuyển động ở các nút lá của TPR-tree 76
Hình 3.5. Các điểm chuyển động trong các nút trung gian của TPR-tree 77
Hình 3.6. Cập nhật khoảng giới hạn theo tham số thời gian . 78
Hình 3.7. Biểu diễn nút trung gian trong cây TPR-tree 79
Hình 3.8. Vùng quét từ thời điểm 0 đến thời điểm 1 81
Hình 3.9. MBR của R tại thời điểm khởi tạo 0 và mở rộng R 1 tại thời điểm 1 . 82
Hình 3.10. Ảnh hưởng của độ lớn phạm vi truy vấn 92
Hình 3.11. So sánh hiệu năng của DO-TPR*-tree với TPR*-tree 93DANH SÁCH BẢNG
Bảng 2.1. Tọa độ các điểm trên quỹ đạo mẫu . 67
Bảng 2.2. Dữ liệu mẫu về di chuyển hàng ngày của đối tượng 67
Bảng 2.3. Quỹ đạo của đối tượng 68
Bảng 2.4. Di chuyển thường xuyên và độ hỗ trợ 68
Bảng 2.5. Mẫu hình di chuyển với độ hỗ trợ nhỏ nhất là 0.5 . 69
Bảng 3.1. Dữ liệu thực nghiệm các đối tượng chuyển động . 90