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

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

TÓM TẮT LUẬN ÁN TIẾN SĨ TOÁN HỌC

HÀ NỘI - 2015

Công trình được hoàn thành tại:

Học viện Khoa học và Công nghệ, Viện Hàn lâm KH và CN Việt Nam

2

Người hướng dẫn khoa học: PGS. TS. Đặng Văn Đức

Phản biện 1: PGS. TS. Huỳnh Quyết Thắng

Phản biện 2: PGS. TS. Bùi Thu Lâm

Phản biện 3: PGS. TS. Lê Trọng Vĩnh

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:

Viện Hàn lâm Khoa học và Công nghệ Việt Nam Vào hồi giờ ngày tháng năm

Có thể tìm hiểu luận án tại thư viện:

1. Thư viện Quốc gia Việt Nam

2. Thư viện Học viện Khoa học và Công nghệ

3

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. Nhiều mô hình cơ sở dữ

liệu các đối tượng chuyển động đã 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 bài

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

đối tượng chuyển động 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. 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. Có một số hướng

để giải quyết vấn đề này, trong đó cơ sở dữ liệu các đối tượng chuyển

động (MODB) là dễ tiếp cận và đang được nghiên cứu, phát triển

mạnh mẽ. Chính vì vậy, luận án đặt mục tiêu chính là nghiên cứu về

các vấn đề liên quan đến MODB bao gồm: tổ chức, lưu trữ, truy vấn

vị trí của đối tượng trong tương lai và đề xuất một số kỹ thuật để nâng

cao tốc độ, tính chính xác trong truy vấn. Lớp bài toán mà luận án

hướng tới là quản lý thông tin đối tượng chuyển động hay quản lý và

điều hành giao thông. Trong lớp bài toán này, độ chính xác dự đoán

vị trí không cần quá cao (sai số một vài mét có thể chấp nhận được)

và nghiêng về tăng tốc độ tính toán để phản hồi cho người sử dụng

hay ra quyết định nhanh chóng.

4

Trong luận án này, nghiên cứu sinh đã thực hiện và giải quyết

những vấn đề sau:

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

b) Nghiên cứu, đề xuất một số phương pháp, kỹ thuật nâng

cao tốc độ và độ chính xác của các truy vấn vị trí của đối

tượng chuyển độ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. Trong luận án, nghiên cứu sinh đã đề xuất cấu

trúc chỉ mục mới là DO-TPR*-tree, dựa trên TPR*-tree, có hiệu năng

truy vấn cao hơn. Cấu trúc này thể hiện được hiệu quả cao 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.

Các kết quả chính của luận án được công bố trong các công trình

khoa học (1)-(4). Các kết quả này cũng đã được báo cáo và thảo luận

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

HL KH và CN Việt Nam và 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”.

5

Chương 1. CƠ SỞ DỮ LIỆU CÁC ĐỐI TƯỢNG CHUYỂN ĐỘNG

Trong chương này, nghiên cứu sinh sẽ trình bày kết quả nghiên cứu

và tổng hợp các vấn đề liên quan đến cơ sở dữ liệu các đối tượng

chuyển động bao gồm một số khái niệm cơ bản về MODB và các vấn

đề còn cần giải quyết là (1) mô hình hóa vị trí, (2) ngôn ngữ truy vấn,

(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

trong dữ liệu vị trí của các đối tượng chuyển động.

1.1. Một số khái niệm cơ bản

1.1.1. Cơ sở dữ liệu không gian-thời gian

Cơ sở dữ liệu không gian-thời gian được xây dựng nhằm giải quyết

các bài toán không gian thay đổi theo thời gian. Chúng ta có thể hiểu

điểm chuyển động và vùng chuyển động được thể hiện trong miền

không gian ba chiều (không gian 2D + thời gian). Các kiểu dữ liệu này

có thể được tích hợp như kiểu dữ liệu cơ sở (thuộc tính) trong mô hình

quan hệ, hướng đối tượng hoặc các mô hình dữ liệu DBMS khác.

Hình 1.1. Cơ sở dữ liệu không gian-thời gian và MODB

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

CSDL các đối tượng chuyển động là dạng thu gọn của CSDL

không gian-thời gian, trong đó chỉ quan tâm đến điểm chuyển động

mà không xét đến các đối tượng khác (đường hay vùng chuyển động).

1.1.3. Dữ liệu trong cơ sở dữ liệu các đối tượng chuyển động

Kiểu dữ liệu cơ bản trong cơ sở dữ liệu các đối tượng chuyển động

là điểm chuyển động (moving point – mpoint).

6

a. Rời rạc b. Liên tục

Hình 1.2. Điểm chuyển động rời rạc và liên tục

Điểm chuyển động mpoint được định nghĩa khác như là một hàm

liên tục từ thời gian vào không gian hai chiều (2D), hoặc như một

đường gấp khúc (polyline) trong không gian ba chiều (2D + thời gian).

1.1.4. Truy vấn trong 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 cần đáp ứng được việc

cập nhật thường xuyên, đồng thời lại phải đảm bảo truy vấn hiệu quả.

Các kiểu truy vấn phổ biến trong MODB là truy vấn điểm, truy vấn

phạm vi và truy vấn k láng giềng gần nhất. Ngoài ra còn vài kiểu truy

vấn phức tạp hơn như truy vấn phạm vi liên tục hay truy vấn mật độ…

1.2. Các vấn đề cần giải quyết

Các vấn đề này bao gồm (1) Mô hình hóa vị trí; (2) Ngôn ngữ truy

vấn; (3) Lập chỉ mục và (4) Tính không chắc chắn/không chính xác.

1.2.1. Vấn đề về mô hình hóa vị trí

Để mô tả được các đối tượng chuyển động trong cơ sở dữ liệu và

trả lời được các truy vấn về vị trí, vị trí của các đối tượng chuyển động

sẽ phải được cập nhật một cách liên tục. Việc cập nhận liên tục này sẽ

dẫn đến vấn đề là làm giảm mạnh hiệu năng của hệ thống. Nếu không

thì lại dẫn đến vấn đề là kết quả truy vấn vị trí bị sai lệch. Hơn nữa

việc cập nhật liên tục qua mạng không dây cũng sẽ dẫn đến vấn đề

quá tải băng thông khi số lượng đối tượng cùng cập nhật là rất lớn.

1.2.2. Vấn đề về ngôn ngữ truy vấn

7

Ngôn ngữ truy vấn truyền thống như SQL là không đủ để diễn tả

các truy vấn trong MODB. Cho dù đã có những nghiên cứu về ngôn

ngữ truy vấn không gian và thời gian, nhưng những nghiên cứu này

vẫn là rời rạc và với các ứng dụng MODB, chúng cần được tích hợp

lại để trả lời truy vấn một cách chính xác.

1.2.3. Vấn đề về lập chỉ mục

Số lượng các đối tượng chuyển động trong CSDL có thể rất lớn.

Do vậy chúng ta cần phải lập chỉ mục cho thuộc tính vị trí. Việc sử

dụng cách lập chỉ mục trực tiếp cho thuộc tính không gian như thông

thường là không thể được do việc thay đổi liên tục giá trị của thuộc

tính này sẽ dẫn đến cũng phải lập lại chỉ mục cho nó một cách liên tục.

1.2.4. Vấn đề về tính không chắc chắn/không chính xác

Vị trí của đối tượng chuyển động trong CSDL về cơ bản là không

chính xác với vị trí thực tế của nó bất kể chính sách cập nhật vị trí của

đối tượng vào CSDL. Tính không chắc chắn vốn có này có ý nghĩa

khác nhau cho mô hình cơ sở dữ liệu, truy vấn và lập chỉ mục. Vì sự

không chắc chắn trong cơ sở dữ liệu vị trí, sẽ có thêm hai kiểu ngữ

nghĩa trong truy vấn là “CÓ THỂ” và “CHẮC CHẮN”.

Dù tính không chắc chắn đã được nghiên cứu rộng rãi, việc xây

dựng mô hình mới và khả năng không gian-thời gian cho các đối tượng

chuyển động vẫn cần phải xem xét lại các giải pháp hiện có.

Kết luận chương

Chương 1 đã giới thiệu các vấn đề cơ bản về CSDL các đối tượng

chuyển động. MODB là dạng thu gọn của CSDL không gian-thời gian,

trong đó chỉ quan tâm đến các điểm chuyển động mà không xét đến

các đối tượng khác. Các vấn đề còn tồn tại cần giải quyết trong CSDL

các đối tượng chuyển động cũng được tổng hợp lại. Các chương tiếp

theo nghiên cứu sinh sẽ trình bày các nghiên cứu của mình, góp phần

giải quyết một số vấn đề này.

8

Chương 2. DỰ ĐOÁN VỊ TRÍ CỦA ĐỐI TƯỢNG CHUYỂN ĐỘNG

Trong chương này, nghiên cứu sinh sẽ trình bày hai phương pháp

dự đoán vị trí của đối tượng chuyển động, được đề xuất nhằm góp

phần giải quyết vấn đề mô hình hóa vị trí trong MODB. Phương pháp

thứ nhất là dự đoán vị trí theo hàm chuyển động chỉ hiệu quả với dự

đoán ở tương lai gần. Phương pháp thứ hai là dự đoán theo hành vi

của đối tượng 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, 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 hai

phương pháp này sẽ đem lại hiệu quả tốt hơn cho truy vấn trong toàn

hệ thống.

2.1. Dự đoán vị trí của đối tượng dựa theo hàm chuyển động

Các hàm chuyển động có thể chia thành hai dạng sau:

- Hàm tuyến tính: mô tả chuyển động theo đường thẳng - Hàm phi tuyến: mô tả chuyển động theo đường cong bất kỳ 2.1.1. Dự đoán dựa theo hàm tuyến tính

Cho một đối tượng có vị trí l0 tại thời điểm t0 có vận tốc v0. Mô

hình chuyển động tuyến tính sẽ dự đoán vị trí của đối tượng tại thời

điểm tq bởi biểu thức:

l(tq)=l0 + v0 * (tq-t0) trong đó l và v là các véc-tơ n chiều

Với mô hình tuyến tính, việc tính toán vị trí của đối tượng chuyển

động ở thời điểm tiếp theo rất nhanh chóng. Tuy nhiên, với nhiều bài

toán thực tế, độ chính xác này thường không cao do đối tượng có thể

di chuyển trong mạng lưới giao thông đô thị phức tạp và có rất nhiều

yếu tố ảnh hưởng đến véc tơ vận tốc (độ lớn và hướng) của đối tượng.

2.1.2. Dự đoán dựa theo hàm phi tuyến

Trong thực tế, chuyển động của các đối tượng thường là phi tuyến.

Với mô hình này, chuyển động của đối tượng được biểu diễn bởi các

9

hàm toán học phức tạp hơn vì vậy độ chính xác dự đoán sẽ cao hơn

mô hình tuyến tính.

Hàm chuyển động đệ quy và ma trận chuyển động

Sử dụng hàm chuyển động đệ quy là phương pháp dự đoán vị trí

từ những vị trí trước đó trong quá khứ. Phương pháp này biểu diễn vị

𝑓

trí l của đối tượng tại thời điểm t (ký hiệu lt) dưới dạng biểu thức sau:

𝑖=1

𝑙𝑡 = ∑ 𝑐𝑖 ∗ 𝑙𝑡−𝑖

trong đó ci là ma trận hệ số và f là số tối thiểu các vị trí gần nhất

để tính được các phần tử của tất cả ci.

Xét đối tượng O trong không gian n chiều. Tại thời điểm ti và ti+1

(0 < i < q), q là thời điểm truy vấn, vị trí của O được biểu diễn lần lượt

bởi các véc tơ Pi và Pi+1 như sau:

và 𝑃𝑖+1

𝑃𝑖⃗⃗ = (𝑝𝑖,1, 𝑝𝑖,2, … , 𝑝𝑖,𝑛) ⃗⃗⃗⃗⃗⃗⃗⃗ = (𝑝𝑖+1,1, 𝑝𝑖+1,2, … , 𝑝𝑖+1,𝑛) Véc tơ dịch chuyển của O từ thời điểm ti đến ti+1, ký hiệu 𝑖⃗⃗⃗ , được

mô tả như sau:

𝑖⃗⃗⃗ = (𝑖,1, 𝑖,2, … , 𝑖,𝑛) = 𝑃𝑖+1 ⃗⃗⃗⃗⃗⃗⃗⃗ − 𝑃𝑖⃗⃗

Do đó muốn tính 𝑃𝑖+1

⃗⃗⃗⃗⃗⃗⃗⃗ ta cần xác định véc tơ dịch chuyển 𝑖⃗⃗⃗ . Có một số kỹ thuật dự đoán theo hàm chuyển động đệ quy hay được sử

dụng như SMA và EWMA. Chúng sử dụng các vị trí trong quá khứ

của đối tượng để xác định véc tơ dịch chuyển, từ đó dự đoán vị trí của

đối tượng ở các thời điểm tiếp theo.

Kỹ thuật dự đoán theo trung bình động đơn giản - SMA

Biểu thức tính i,k theo SMA (Simple Moving Average) như sau:

Kỹ thuật dự đoán theo trung bình động trọng số mũ - EWMA

10

Biểu thức tính EWMA như sau:

Kỹ thuật dự đoán vị trí đối tượng theo mô hình W-EWMA

Nhằm làm giảm khối lượng tính toán không cần thiết, nghiên cứu

sinh đề xuất kỹ thuật dự đoán đặt tên là W-EWMA (Window

Exponentially Weighted Moving Average). Theo kỹ thuật này thay vì

tính tất cả các j,k, chỉ tính w bước gần nhất trước đó. Biểu thức (2-10) tính W-EWMA như sau:

Giải thuật tính toán theo kỹ thuật W-EWMA như dưới đây:

Algorithm Cal_W-EWMA

Input: 𝑃𝑖 = {𝑝𝑖,1, 𝑝𝑖,2, … , 𝑝𝑖,𝑛} Output: 𝑃𝑖+1 = {𝑝𝑖+1,1, 𝑝𝑖+1,2, … , 𝑝𝑖+1,𝑛} 1. w ← a; ← b // initialization w 2. Sd = 0; Sa = 0 // initialization Sd, Sa 3. FOR EACH pi,k IN Pi 4.

FOR j = i-w to i-1 // windowed

5.

j,k = pj,k – pj-1,k calculate 

6.

Sd ← Sd + i-1-j * j,k Sa ← Sa + i-1-j END FOR pi+1,k = pi,k + Sd/Sa

7. 8. 9. 10. END FOR

11. 𝑃𝑖+1 ← {𝑝𝑖+1,1, 𝑝𝑖+1,2, … , 𝑝𝑖+1,𝑛} 12. RETURN Pi+1

Algorithm End.

11

Trong kỹ thuật này, độ phức tạp thuật toán là O(n*w), với

n là số chiều của không gian dữ liệu, w là hằng số xác định

trước bằng công thức (2-10a) w = S/(v*f), Trong đó S là độ dài

trung bình của các tuyến đường trên bản đồ (m), v là vận tốc

di chuyển trung bình (m/s), f là tần suất cập nhật dữ liệu (s).

Các kết quả thực nghiệm trên cho thấy, kỹ thuật dự đoán vị

trí của đối tượng theo mô hình W-EWMA cho kết quả khá

chính xác với thời gian tính toán nhanh hơn theo mô hình

EWMA hay SMA. Giá trị w có thể lựa chọn khởi tạo giá trị

ban đầu theo công thức (2-10a) và điều chỉnh lại cho hợp lý

trong quá trình sử dụng hệ thống. Giá trị nên lựa chọn theo

từng loại ngữ cảnh hay ứng dụng cụ thể: nhỏ phù hợp hơn

với những ứng dụng mà đối tượng di chuyển với hướng và vận

tốc ít biến đổi (phương tiện hàng hải, hàng không) còn lớn

lại dễ thích nghi với những ứng dụng mà đối tượng di chuyển

với hướng và vận tốc hay thay đổi (phương tiện đường bộ).

2.2. Dự đoán dựa trên hành vi của đối tượng

2.2.1. Luật kết hợp

Luật kết hợp là một biểu thức có dạng: XY, trong đó X và

Y là tập các mục cùng xuất hiện trong một bộ cho trước [1]...

2.2.2. Thuật toán phân cụm dựa trên mật độ DBSCAN

Thuật toán phân cụm dựa trên mật độ thông dụng nhất là thuật toán

DBSCAN, cho phép tìm các đối tượng mà có số đối tượng láng giềng

lớn hơn một ngưỡng tối thiểu. Một cụm được xác định bằng tập tất cả

các đối tượng liên thông mật độ với các láng giềng của nó [22]...

2.2.3. Mẫu hình di chuyển

Trong thực tế chuyển động của đối tượng thường có tính chu kỳ

theo một mẫu hình (pattern) nào đó. Ví dụ như con người đi làm hàng

12

ngày theo một tuyến đường định trước. Phương tiện giao thông công

cộng có lịch trình, tuyến đường và điểm đỗ cố định…

Định nghĩa 3.1 [Điểm dừng]

Điểm dừng là một phần quan trọng trong quỹ đạo mà đối tượng

không có dịch chuyển rõ ràng trong một khoảng thời gian nhất định.

Điểm dừng được mô tả bởi một kiểu đặc trưng không gian với khoảng

thời gian xác định (không rỗng).

Định nghĩa 3.2 [Di chuyển]

Di chuyển từ điểm dừng l1 đến l2 được ký hiệu l1  l2 là một phần

của quỹ đạo trong khoảng thời gian xác định được giới hạn bởi hai

điểm dừng liên tiếp l1 và l2 trong đó các điểm dừng này không bị trùng

về mặt thời gian.

Định nghĩa 3.3 [Quỹ đạo]

Quỹ đạo P là một danh sách sắp thứ tự của các điểm dừng và các

di chuyển. P thường được biểu diễn như sau:

P = {(l0, l1, …, ln-1)}

trong đó li (0 ≤ i < n) biểu diễn đối tượng tại vị trí li ở thời điểm i.

Định nghĩa 3.4 [Độ hỗ trợ của di chuyển]

Cho X={P1, P2,…, Pn} là tập các quỹ đạo; Trong đó mỗi quỹ đạo

Pi (0 < i  n) được định nghĩa như định nghĩa 3.3 ở trên.

Độ hỗ trợ của di chuyển AB, ký hiệu là sup(AB), là tỉ số của

các quỹ đạo Pi trong X mà có chứa di chuyển AB trên tổng số quỹ

đạo có trong X.

|{P ∈ X |AB ∈ P| |X|

sup(AB) =

Trong đó ký hiệu |Z| biểu diễn số phần tử có trong tập Z.

Định nghĩa 3.5 [Mẫu hình di chuyển]

Một di chuyển được gọi là mẫu hình di chuyển nếu độ hỗ trợ s của

nó lớn hơn hoặc bằng một ngưỡng cho trước gọi là minsup.

Định nghĩa 3.6 [Mẫu hình quỹ đạo]

13

Quỹ đạo P được gọi là mẫu hình quỹ đạo nếu nó được biểu diễn

𝑗𝑚 𝑗2 …  𝑅𝑡𝑚

𝑐 𝑗𝑛 → 𝑅𝑡𝑛

dưới dạng của một luật kết hợp đặc biệt:

𝑗1 𝑅𝑡2

P: 𝑅𝑡1 với ràng buộc về thời gian:

t1 < t2 < … < tm < tn

Tham số c là độ chắc chắn hay xác xuất biểu thị khả năng xảy ra.

Định nghĩa 3.7 [Truy vấn tương lai]

Truy vấn tương lai là truy vấn dự đoán không gian-thời gian thỏa

mãn điều kiện sau: tq  tc + d

Trong đó tq là ký hiệu thời gian tại thời điểm truy vấn, tc là ký hiệu

thời gian hiện thời và d là thời gian ở tương lai thỏa mãn:

tq < T, 0 < d < T (T là ngưỡng thời gian truy vấn)

2.2.4. Khai phá mẫu hình di chuyển

Khai phá mẫu hình di chuyển đã được nghiên cứu và có một số kết

quả nhất định. Các nghiên cứu này bao gồm các nhóm sau:

(1) Biến đổi dữ liệu thô: Dữ liệu thô được xấp xỉ và chuyển đổi

thành một định dạng phân tích.

(2) Chỉ mục: Kalniset và đồng nghiệp sử dụng một chỉ số lưới Gt

tại mỗi thời điểm t để lưu trữ dữ liệu tại thời điểm đó. Sau đó

áp dụng thuật toán phân cụm dựa trên mật độ DBSCAN trên

các chỉ số lưới Gt để xác định các cụm tại thời điểm t.

(3) Tiếp cận kiểu Apriori: Cách tiếp cận kiểu Apriori có thể được

áp dụng để khai phá các mẫu hình quỹ đạo một cách hiệu quả.

Một vấn đề trong việc dự đoán vị trí đối tượng dựa theo mẫu

hình là làm thế nào để xác định được mẫu hình dựa trên thông tin

về vị trí của nó trong quá khứ. Một số nghiên cứu cho rằng có thể

làm được bằng cách khai phá mẫu hình. Tuy nhiên để thu được

mẫu hình cần một lượng rất lớn dữ liệu lịch sử của đối tượng để

14

tiến hành khai phá. Điều này cũng có nghĩa là số lượng mẫu hình

phát hiện được cũng sẽ rất lớn. Vì vậy cần có phương pháp để tổ

chức các mẫu hình này để trả lời các truy vấn dự đoán vị trí một

các hiệu quả. Nhằm góp phần giải quyết vấn đề này, nghiên cứu

sinh đề xuất sử dụng khung quy trình khai phá mẫu hình di chuyển

và lưu trữ trong CSDL không gian như hình dưới đây.

Hình 2.9. Quy trình khai phá mẫu hình di chuyển

Quy trình này được phân thành 3 mức: dữ liệu, trích chọn mẫu hình

và mô hình hóa mẫu hình. (1) Ở mức dữ liệu, trong CSDL lưu trữ cả

dữ liệu địa lý và dữ liệu quỹ đạo chuyển động của đối tượng. (2) Ở

mức trích chọn mẫu hình, dữ liệu được làm sạch và chuyển đổi thành

định dạng chuẩn (tiền xử lý) để chuẩn bị cho bước khai phá dữ liệu. Ở

mức này, dữ liệu cũng được chuyển đổi thành định dạng đầu vào theo

yêu cầu của các thuật toán khai phá. (3) Ở bước khai phá dữ liệu, người

sử dụng có thể xác định các tham số khai phá như độ hỗ trợ tối thiểu…

để có thể trích chọn chỉ các đặc trưng thỏa mãn ràng buộc. Sau khai

phá chúng ta có các mẫu hình di chuyển và sẽ được mô hình hóa cho

bước dự đoán vị trí về sau.

15

2.2.5. Khai phá luật kết hợp của mẫu hình quỹ đạo trong dự

đoán vị trí của đối tượng chuyển động

Trong luận án này, nghiên cứu sinh sử dụng thuật toán tựa Apriori

[51] để khai phá các mẫu hình quỹ đạo. Việc khai phá này tương tự

như khai phá các luật kết hợp bao gồm hai bước chính sau:

𝑛

(1) Xác định các vùng thường xuyên đến  Xác định mẫu hình có tính chu kỳ, phân chia toàn bộ quỹ

đạo thành

quỹ đạo con

𝑇

 Nhóm tất cả các vị trí Gt có cùng khoảng dịch thời gian

trong mỗi quỹ đạo con

 Áp dụng thuật toán phân cụm dựa trên mật độ DBSCAN

để xác định các cụm (vùng thường xuyên đến) cho mỗi

khoảng dịch thời gian t

(2) Suy diễn mẫu hình quỹ đạo từ các vùng thường xuyên đến

 Sử dụng thuật toán tựa Apriori sinh ra tập k mục dự tuyển

từ tập k-1 mục trước đó. Với các ràng buộc:

o Lựa chọn các mẫu hình theo chiều hướng tăng

dần. Vì các mẫu hình quỹ đạo là chuyển động theo

thời gian tăng dần qua mỗi vùng. Những mẫu hình

nào không đảm bảo ràng buộc này sẽ bị loại bỏ. o Lựa chọn mẫu hình ưu tiên ít mục trong hệ quả.

Cách tiếp cận kiểu Apriori này có thể làm giảm đáng kể không gian

tìm kiếm trong vài lần lặp lại đầu tiên, cho phép mẫu hình quỹ đạo

được khai phá hiệu quả. Việc lựa chọn các mẫu hình theo chiều hướng

tăng dần và loại bỏ các mẫu hình không hợp lệ được kiểm tra và thực

hiện bởi toán tử kết nối có điều kiện (∞ operator). Điều kiện kết nối

được thực hiện bởi hàm so sánh thứ tự kết nối, đảm bảo các vùng

thường xuyên đến có thứ tự tăng dần theo thời gian. Thuật toán cho

khai phá quỹ đạo được mô tả như sau:

16

Algorithm Apriori_Trajectories

Input: Trajectory database D with the movement’s support = min_sup Output: Frequent Regions Procedure Apriori_Trajectories

1. R1 = find_frequent_1-itemsets(D);

2. FOR (k=2; Rk-1 ; k++) 3.

Ck = apriori_gen(Rk-1, min_sup);

FOR EACH Tt  D

4. 5.

Ct = subset(Ck,t);

// Tt is trajectory tth // use tth sub-trajectory for candidate

FOR EACH candidate c  Ct

6. 7.

c.count++;

Rk = {c  Ck | c.count  min_sup};

END FOR

8. 9. 10. END FOR 11. RETURN (Frequent Regions = k Rk);

End Procedure Procedure apriori_gen(Rk-1: frequent (k-1) itemsets; min_sup)

1. FOR EACH itemset R1  Rk-1

2.

FOR EACH itemset R2  Rk-1

3.

IF (R1[1]= R2[1])  (R1[2]= R2[2])...  (R1[k-2]= R2[k-2])

 (R1[k-1]

4.

c = R1 ∞ R2; // joint step: produce k candidate from k-1 item sets

IF has_infrequent_subset(c, Rk-1) THEN

delete c; // removal if there are multiple entries in the result

ELSE add c to Ck;

END FOR

5. 6. 7. 8. 9. END FOR 10. RETURN Ck;

End Procedure Procedure has_infrequent_subset(c: candidate k-itemset; Rk-1: frequent (k-1) itemsets)

1. FOR EACH (k-1)-subset s of c

IF s  Rk-1 THEN RETURN TRUE

2. 3. RETURN FARSE

End Procedure

Algorithm End

17

Trong thuật toán này, ở thủ tục chính Apriori_Trajectories, phần sinh

tập k mục dự tuyển từ tập k-1 mục ở dòng 3, phần tính độ hỗ trợ ở

dòng 4 đến 7, các mục dự tuyển có độ hỗ trợ nhỏ hơn minsup sẽ bị

loại bỏ ở dòng 8. Ở thủ tục apriori_gen, bước joint step ở dòng 4 sử

dụng toán tử kết nối có điều kiện để đảm bảo việc lựa chọn các mẫu

hình theo chiều hướng tăng dần và loại bỏ các mẫu hình không hợp lệ.

Kết quả thực nghiệm

Bộ dữ liệu mẫu sử dụng tương tự của Luis O. A. và đồng nghiệp

[19]. Dữ liệu này liên quan đến các hoạt động hàng ngày của đối tượng

và được lấy trong khoảng thời gian 3 tháng (91 ngày). Đối tượng này

có một số điểm dừng (vùng thường xuyên đến) là Home, Café,

Market, Office và Laboratory.

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 đã

tăng thêm đáng kể.

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 MODB. 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 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).

18

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 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.

Kết quả này 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.

3.1. R-tree

R-tree 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, bằng cách chia nhỏ không

gian thành các vùng nhớ 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. 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…

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í tương lai 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ể. 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ấu trúc cây khác phát triển mở rộng về sau,

điển hình là TPR*-tree.

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

19

đổ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à 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. Cây TPR*-tree

sẽ cho kết quả truy vấn tương lai 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

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 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

20

đổi vận tốc của đối tượng hoặc vị trí hiện tại trên nút đó. 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. Vấn đề này xuất phát 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).

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.

3.4.2. Thuật toán tìm kiếm DOA_Search

Kỹ thuật xử lý truy vấn Giả sử 𝑇𝑢𝑗 và 𝑇𝑢𝑗+1lầ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 [𝑇𝑢𝑗, 𝑇𝑢𝑗+1]. 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 𝑇𝑞𝑗,𝑖 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 [𝑇𝑢𝑗, 𝑇𝑢𝑗+1]. Ta có:

𝑇𝑢𝑗< 𝑇𝑞𝑗,1< 𝑇𝑞𝑗,2< … < 𝑇𝑞𝑗,𝑘< 𝑇𝑢𝑗+1 Vì MBR của nút N mở rộng nhanh chóng trong khoảng thời gian [𝑇𝑢𝑗, 𝑇𝑢𝑗+1], truy vấn tại thời điểm 𝑇𝑞𝑗,𝑖 (1 ≤ i ≤ k) sẽ xem xét toàn bộ

21

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 𝑇𝑞𝑗,𝑖 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 [𝑇𝑞𝑗,𝑖, 𝑇𝑢𝑗+1].

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 [𝑇𝑞𝑗,𝑖, 𝑇𝑢𝑗+1] 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.

𝑁𝑢𝑚_𝐸𝑁(𝑇) 𝐴𝐵𝑅𝑁(𝑇)

(3-1) DN (T) =

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 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 4.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.

22

𝐷𝑁(𝑇𝑢) 𝐷𝑁(𝑇𝑞)

< λ (3-2)

Trong đó, - 𝐷𝑁(𝑇𝑞) là mật độ của nút N tại thời điểm truy vấn Tq - 𝐷𝑁(𝑇𝑢) 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 λ.

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 𝑇𝑞𝑗,𝑖. Nếu 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 [𝑇𝑞𝑗,𝑖, 𝑇𝑢𝑗+1]. 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 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

23

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).

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

SBR ← ; // initialization

IF O IN (QBR, QT) THEN //O is expected computed to be positioned

2. 3. 4.

FOR EACH moving object O IN rootNode d in QBR within interval QT

SBR= SBR  O.id;

END IF END FOR

5. 6. 7. 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

Cache(e); // cache the content of e into the memory buffer

11. 12.

13. 14.

nodeDensity = Cal_NodeDensity(e.childNode); // calculate the Node Density Optimal of the child node pointed to by e λ = h-1; // h is the tree height IF (nodeDensity >= λ) THEN // an DOA execution is needed on childNode Adjust (e.MBR, e.VBR); //adjust the MBR and VBR data of e END IF childSBR ← DOA_Search(QBR, QT, childNode);

15. 16. 17.

SBR ← SBR  childSBR;

END IF

18. 19. 20. END FOR 21. RETURN SBR 22. END IF

Algorithm End.

24

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 trong.

Tiến trình sẽ lưu nội dung mỗi mục e gặp phải 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 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ý 3.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

Những kết quả thực nghiệm 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

25

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 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ác công bố (4) của nghiên cứu sinh.

26

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 MODB để 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. 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. Luận án

đã đề xuất cấu trúc chỉ mục mới là DO-TPR*-tree, dựa trên 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.

- 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 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).

27

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.