Thư viện tri thức trực tuyến
Kho tài liệu với 50,000+ tài liệu học thuật
© 2023 Siêu thị PDF - Kho tài liệu học thuật hàng đầu Việt Nam
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
Nội dung xem thử
Mô tả chi tiết
BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM
KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM
HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ
NGUYỄN TIẾN PHƯƠNG
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
Chuyên ngành: Cơ sở toán học cho tin học
Mã số: 62 46 01 10
LUẬN ÁN TIẾN SĨ TOÁN HỌC
HÀ NỘI - 2015
BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM
KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM
HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ
NGUYỄN TIẾN PHƯƠNG
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
Chuyên ngành: Cơ sở toán học cho tin học
Mã số: 62 46 01 10
LUẬN ÁN TIẾN SĨ TOÁN HỌC
NGƯỜI HƯỚNG DẪN KHOA HỌC:
1. PGS. TS. Đặng Văn Đức
HÀ NỘI -2015
1
LỜI CAM ĐOAN
Tôi xin cam đoan những kết quả trình bày trong luận án là mới, trung thực và chưa
từng được công bố trong bất kỳ công trình của ai khác. Những kết quả viết chung với
cán bộ hướng dẫn đã được sự đồng ý khi đưa vào luận án.
Nghiên cứu sinh
Nguyễn Tiến Phương
2
LỜI CẢM ƠN
Lời đầu tiên, tôi xin gửi lời cảm ơn sâu sắc tới PGS. TS. Đặng Văn Đức đã tận
tình hướng dẫn, giúp đỡ tôi trong quá trình nghiên cứu và hoàn thành luận án này.
Tôi cũng xin chân thành cảm ơn Lãnh đạo Viện Công nghệ thông tin, Viện Hàn
lâm Khoa học và Công nghệ Việt Nam đã tạo điều kiện thuận lợi cho quá trình nghiên
cứu của mình, cảm ơn các các bộ của phòng Hệ thông tin Địa lý đã nhiệt tình trong
công tác, giúp tôi dành thời gian hoàn thành luận án.
Cuối cùng, tôi xin cảm ơn gia đình, bạn bè, đồng nghiệp đã luôn là nguồn động
viên, ủng hộ, giúp tôi thêm động lực để hoàn thành tốt luận án này.
NCS. Nguyễn Tiến Phương
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 ........................................................ 50
4
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 ......................................................................................... 98
5
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 DOTPR*-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 .................................................................... 75
8
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 R1 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 ............................ 93