[FONT=Times New Roman]ỤC LỤC

MỤC LỤC............................................. .................................................. ......................... 2

MỤC LỤC BẢNG BIỂU .................................................. .............................................. 5

A. PHẦN MỞ ĐẦU............................................ .................................................. ........ 7

1. Giới thiệu .................................................. .................................................. .......... 7

2. Ý nghĩa khoa học và thực tiễn .................................................. ............................ 8

3. Mục đích nghiên cứu .................................................. .......................................... 9

4. Đối tượng nghiên cứu .................................................. ....................................... 10

5. Phạm vi nghiên cứu .................................................. .......................................... 10

B. NỘI DUNG .................................................. .................................................. ........ 11

CHƯƠNG 1: TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU KHÔNG GIAN....................... 11

1. Khái niệm............................................ .................................................. ............. 11

1.1 Hệ thống cơ sở dữ liệu không gian.............................................. ................. 11

1.2. Cơ sở dữ liệu không gian (Spatial Database) .............................................. 12

2. Mô hình cơ sở dữ liệu không gian .................................................. ................. 16

2.1 xây dựng mô hình CSDL không gian .................................................. .......... 17

2.2 Cơ sở hình học trong tổ chức các đối tượng không gian cơ bản.................. 25

3. Truy vấn thực hiện trong CSDL không gian.............................................. .... 30

CHƯƠNG 2: BÀI TOÁN TÍNH TOÁN XẤP XỈ VỚI CÁC TRUY VẤN LIÊN

QUAN ĐẾN KHOẢNG CÁCH TRONG CƠ SỞ DỮ LIỆU KHÔNG GIAN........ 34

1. Các truy vấn liên quan đến khoảng cách............................................. ........... 34

1.1 Truy vấn khu vực theo khoảng cách δ .................................................. ......... 37

1.2 Truy vấn K vùng lân cận gần nhất............................................ ..................... 38

1.3 Truy vấn nối các khu vực theo khoảng cách δ (truy vấn đệm).................... 39

1.4 Phép nối khoảng cách Iceberg........................................... ........................... 39

1.5 Truy vấn K cặp đối tượng gần nhất .................................................. ............ 39

1.6 Nối K vùng lân cận gần nhất .................................................. ...................... 40

1.7 Truy vấn K- nối khoảng cách .................................................. ....................... 40

2 R – Tree.............................................. .................................................. .............. 42

2.1 Khái niệm............................................ .................................................. ............ 43

2.2 Cấu trúc của một R-tree.............................................. .................................... 45

2.3 Thuật toán R-Tree .................................................. ......................................... 47

3 Các kỹ thuật tính toán xấp xỉ khoảng cách .................................................. .. 56

3.1 Thu nhỏ không gian tìm kiếm .................................................. .................... 56

3.2 Kỹ thuật tìm kiếm theo kinh nghiệm.......................................... ................. 59

3.2.1 Tìm kiếm khu vực............................................. ............................................. 59

3.2.2 Simulated Annealing .................................................. ................................... 60

3.2.3 Thuật toán phát sinh .................................................. ................................... 61

CHƯƠNG 3 MỘT SỐ ỨNG DỤNG CỦA BÀI TOÁN TÍNH TOÁN XẤP XỈ

KHOẢNG CÁCH TRONG THỰC TẾ.............................................. ......................... 63

1. Ứng dụng trong việc xây dựng một hệ thống khung (framework) xử lý hiệu

quả các truy vấn không gian cơ bản. .................................................. .................... 64

2. Tăng tốc quá trình phân tích, thực thi và hiển thị dữ liệu địa lý trong các

truy vấn liên quan đến khoảng cách (DBQs) .................................................. ....... 66

3. xây dựng thuật toán xấp xỉ như một công cụ hạn chế những khó khăn phát

sinh đối với kích thước địa lý của đối tượng .................................................. ........ 68

4. Tính toán độ chính xác về vị trí trên bản đồ và chênh lệch về khoảng cách

giữa các đối tượng trong truy vấn .................................................. ......................... 70

CHƯƠNG 4 MỘT SỐ THUẬT TOÁN TÍNH KHOẢNG CÁCH TRONG KHÔNG

GIAN địa lý & ĐÁNH GIÁ HIỆU NĂNG............................................. ................. 74

1. Tính toán khoảng cách giữa các đối tượng địa lý theo công thức Haversine

74

1.1 Công thức Haversine......................................... ............................................ 74Đ

1.2 Công thức Haversine trong truy vấn tìm khoảng cách ngắn nhất............ 77

1.3 Đánh giá thuật toán Haversine .................................................. ..................... 81

2. Tính toán khoảng cách trong hệ tọa độ địa lý theo khoảng cách Vincenty. 82

2.1 Khái niệm............................................ .................................................. ............ 82

2.2 Thuật toán Vincenty .................................................. ...................................... 85

3. Đánh giá thuật toán Haversine và Vincenty.......................................... ............. 89

C. KẾT LUẬN............................................ .................................................. .............. 91

1. Những kết quả đạt được.......................................... ............................................ 91

2. Đánh giá.............................................. .................................................. .............. 92

3. Hướng phát triển .................................................. ............................................... 92

TÀI LIỆU THAM KHẢO............................................ ................................................ 93