MỤ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 9