Luận Vă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

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 93