Tóm tắt Luận án Tiến sĩ Toán học: 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

BỘ GIÁO DỤC VÀ ĐÀO TẠO<br /> <br /> VIỆN HÀN LÂM<br /> KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM<br /> <br /> HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ<br /> <br /> NGUYỄN TIẾN PHƯƠNG<br /> <br /> MỘT SỐ KỸ THUẬT DỰ BÁO VỊ TRÍ VÀ TRUY VẤN<br /> CÁC ĐỐI TƯỢNG CHUYỂN ĐỘNG TRONG CƠ SỞ DỮ LIỆU<br /> KHÔNG GIAN-THỜI GIAN<br /> Chuyên ngành: Cơ sở toán học cho tin học<br /> Mã số: 62 46 01 10<br /> <br /> TÓM TẮT LUẬN ÁN TIẾN SĨ TOÁN HỌC<br /> <br /> HÀ NỘI - 2015<br /> <br /> 2<br /> <br /> Công trình được hoàn thành tại:<br /> Học viện Khoa học và Công nghệ, Viện Hàn lâm KH và CN Việt Nam<br /> <br /> Người hướng dẫn khoa học: PGS. TS. Đặng Văn Đức<br /> <br /> Phản biện 1: PGS. TS. Huỳnh Quyết Thắng<br /> Phản biện 2: PGS. TS. Bùi Thu Lâm<br /> Phản biện 3: PGS. TS. Lê Trọng Vĩnh<br /> <br /> Luận án sẽ được bảo vệ trước Hội đồng chấm luận án cấp Học viện họp tại:<br /> Viện Hàn lâm Khoa học và Công nghệ Việt Nam<br /> Vào hồi<br /> giờ ngày<br /> tháng<br /> năm<br /> <br /> Có thể tìm hiểu luận án tại thư viện:<br /> 1. Thư viện Quốc gia Việt Nam<br /> 2. Thư viện Học viện Khoa học và Công nghệ<br /> <br /> 3<br /> MỞ ĐẦU<br /> Sự kết hợp các chức năng của công nghệ định vị cá nhân, công<br /> nghệ định vị vệ tinh, công nghệ truyền thông không dây và công nghệ<br /> GIS đã tạo ra một môi trường mới trong đó tất cả các đối tượng chuyển<br /> động có thể xác định vị trí của chúng. Các công nghệ này là cơ sở cho<br /> 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ụ<br /> dựa trên vị trí. Dịch vụ dựa trên vị trí là dịch vụ được đặc chế dựa<br /> trên những thông tin về vị trí của đối tượng. Nhiều mô hình cơ sở dữ<br /> liệu các đối tượng chuyển động đã và đang được nghiên cứu, thử<br /> nghiệm. Trong các mô hình này, dữ liệu của các đối tượng chuyển<br /> động, bao gồm cả thông tin về vị trí trong quá khứ, hiện tại và tương<br /> lai được lưu trữ và cập nhật thường xuyên. Khó khăn lớn khi giải bài<br /> toán này là làm thế nào để khai thác một cách có hiệu quả khi số lượng<br /> đối tượng chuyển động là rất lớn và thường xuyên thay đổi vị trí. Việc<br /> truy vấn vị trí của đối tượng trong tương lai cùng với tính không chắc<br /> 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<br /> xá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<br /> quản lý các dữ liệu thay đổi liên tục theo thời gian. Có một số hướng<br /> để giải quyết vấn đề này, trong đó cơ sở dữ liệu các đối tượng chuyển<br /> động (MODB) là dễ tiếp cận và đang được nghiên cứu, phát triển<br /> mạnh mẽ. Chính vì vậy, luận án đặt mục tiêu chính là nghiên cứu về<br /> các vấn đề liên quan đến MODB bao gồm: tổ chức, lưu trữ, truy vấn<br /> vị trí của đối tượng trong tương lai và đề xuất một số kỹ thuật để nâng<br /> cao tốc độ, tính chính xác trong truy vấn. Lớp bài toán mà luận án<br /> hướng tới là quản lý thông tin đối tượng chuyển động hay quản lý và<br /> điều hành giao thông. Trong lớp bài toán này, độ chính xác dự đoán<br /> vị trí không cần quá cao (sai số một vài mét có thể chấp nhận được)<br /> và nghiêng về tăng tốc độ tính toán để phản hồi cho người sử dụng<br /> hay ra quyết định nhanh chóng.<br /> <br /> 4<br /> Trong luận án này, nghiên cứu sinh đã thực hiện và giải quyết<br /> những vấn đề sau:<br /> a) Nghiên cứu về cơ sở dữ liệu các đối tượng chuyển động<br /> b) Nghiên cứu, đề xuất một số phương pháp, kỹ thuật nâng<br /> cao tốc độ và độ chính xác của các truy vấn vị trí của đối<br /> tượng chuyển động.<br /> Các kết quả chính bao gồm:<br /> (1) Giải quyết vấn đề về mô hình hóa vị trí của đối tượng chuyển<br /> động dưới dạng thuộc tính động. Thuộc tính động ít cần phải cập nhật<br /> 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ở<br /> dữ liệu (mà thường là rất lớn trong các ứng dụng MODB). Thuộc tính<br /> động có thể được xác định nhờ vào hai phương pháp dự đoán vị trí đã<br /> đề xuất trong luận án:<br /> - Dự đoán vị trí của đối tượng dựa theo hàm chuyển động sử dụng<br /> mô hình W-EWMA<br /> - Dự đoán dựa trên hành vi của đối tượng sử dụng khai phá luật kết<br /> hợp của các mẫu hình di chuyển.<br /> (2) Giải quyết vấn đề về lập chỉ mục không gian cho biểu diễn hình<br /> 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<br /> không gian-thời gian. Trong luận án, nghiên cứu sinh đã đề xuất cấu<br /> trúc chỉ mục mới là DO-TPR*-tree, dựa trên TPR*-tree, có hiệu năng<br /> truy vấn cao hơn. Cấu trúc này thể hiện được hiệu quả cao khi xây<br /> dựng ứng dụng MODB với hạ tầng viễn thông đang phát triển, đôi lúc<br /> còn xảy ra tình trạng mất kết nối như ở Việt Nam.<br /> Các kết quả chính của luận án được công bố trong các công trình<br /> khoa học (1)-(4). Các kết quả này cũng đã được báo cáo và thảo luận<br /> tại các hội nghị, hội thảo khoa học tại Viện Công nghệ thông tin, Viện<br /> HL KH và CN Việt Nam và hội thảo Quốc gia “Một số vấn đề chọn<br /> lọc của Công nghệ thông tin và truyền thông”.<br /> <br /> 5<br /> Chương 1. CƠ SỞ DỮ LIỆU CÁC ĐỐI TƯỢNG CHUYỂN ĐỘNG<br /> <br /> Trong chương này, nghiên cứu sinh sẽ trình bày kết quả nghiên cứu<br /> và tổng hợp các vấn đề liên quan đến cơ sở dữ liệu các đối tượng<br /> chuyển động bao gồm một số khái niệm cơ bản về MODB và các vấn<br /> đề còn cần giải quyết là (1) mô hình hóa vị trí, (2) ngôn ngữ truy vấn,<br /> (3) lập chỉ mục dữ liệu và (4) tính không chắc chắn/không chính xác<br /> trong dữ liệu vị trí của các đối tượng chuyển động.<br /> 1.1.<br /> <br /> Một số khái niệm cơ bản<br /> <br /> 1.1.1. Cơ sở dữ liệu không gian-thời gian<br /> Cơ sở dữ liệu không gian-thời gian được xây dựng nhằm giải quyết<br /> các bài toán không gian thay đổi theo thời gian. Chúng ta có thể hiểu<br /> điểm chuyển động và vùng chuyển động được thể hiện trong miền<br /> không gian ba chiều (không gian 2D + thời gian). Các kiểu dữ liệu này<br /> có thể được tích hợp như kiểu dữ liệu cơ sở (thuộc tính) trong mô hình<br /> quan hệ, hướng đối tượng hoặc các mô hình dữ liệu DBMS khác.<br /> <br /> Hình 1.1. Cơ sở dữ liệu không gian-thời gian và MODB<br /> 1.1.2. Cơ sở dữ liệu các đối tượng chuyển động<br /> CSDL các đối tượng chuyển động là dạng thu gọn của CSDL<br /> không gian-thời gian, trong đó chỉ quan tâm đến điểm chuyển động<br /> mà không xét đến các đối tượng khác (đường hay vùng chuyển động).<br /> 1.1.3. Dữ liệu trong cơ sở dữ liệu các đối tượng chuyển động<br /> Kiểu dữ liệu cơ bản trong cơ sở dữ liệu các đối tượng chuyển động<br /> là điểm chuyển động (moving point – mpoint).<br /> <br />