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

Đề tài: 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  2008


1

LỜI CẢM ƠN Trong thời gian thực hiện đề tài khóa luận tốt nghiệp, dưới sự hướng dẫn tận tình của giáo viên hướng dẫn và được phía nhà trường tạo điều kiện thuận lợi, tôi đã có một quá trình nghiên cứu, tìm hiểu và học tập nghiêm túc để hoàn thành đề tài. Kết quả thu được không chỉ do nỗ lực của cá nhân tôi mà còn có sự giúp đỡ của quý thầy cô, gia đình và các bạn. Tôi xin chân thành cảm ơn Bán giám hiệu nhà trường, Ban chủ nhiệm khoa Công Nghệ Thông Tin – Trường Đại học Công Nghệ đã quan tâm, tạo điều kiện giúp tôi hoàn thành hoàn thành khóa luận tốt nghiệp. Thầy Nguyễn Hải Châu: Thầy đã hướng dẫn, hỗ trợ tôi hoàn thành tốt đề tài về phương pháp, lý luận và nội dung trong suốt thời gian thực hiện khóa luận tốt nghiệp. Gia đình đã tạo điều kiện học tập tốt nhất. Các bạn đã giúp đỡ, trao đổi thông tin về đề tài trong quá trình thực hiện khóa luận. Trong quá trình thực hiện và trình bày khóa luận không thể tránh khỏi những sai sót và hạn chế, do vậy tôi rất mong nhận được sự góp ý, nhận xét phê bình của quý thầy cô và các bạn. Kính chúc quý thầy cô và các bạn sức khỏe! Người thực hiện đề tài Hoàng Thị Hồng Trang Đề tài: 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  2008


2

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  Đề tài: 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  2008


3

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  Đề tài: 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  2008


4

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  Đề tài: 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  2008


5

MỤC LỤC BẢNG BIỂU Hình 1: Trang WebGis www.bando.com.vn ........................................................15  Hình 2: (a) Một region mẫu, (b) Biểu diễn dạng mảng nhị phân của region, (c) Các khối cực đại và các khối phổ thông được chia sẻ trong region - (d) quadtree tương ứng. .............................................................................................................20  Hình 3: Ví dụ một PR quadtree.............................................................................22  Hình 4: Biểu diễn dạng đường..............................................................................24  Hình 5: Biểu diễn dạng khu vực ...........................................................................24  Hình 6: Biểu diễn tập đối tượng trong khu vực ....................................................24  Hình 7: Biểu diễn đối tượng dạng mạng lưới .......................................................25  Hình 8: Mô hình d-simplex..................................................................................26  Hình 9: Phép toán hợp trong không gian địa lý ....................................................28  Hình 10: Phép toán trừ trong không gian địa lý....................................................28  Hình 11: Phép toán giao trong không gian địa lý .................................................28  Hình 12: Phép toán bao phủ trong không gian địa lý ...........................................29  Hình 13 Các hàm toán tử trong không gian địa lý................................................30  Hình 14: Mô hình dữ liệu quan hệ xây dựng dựa trên Benchmark database........36  Hình 15: R-Tree và MBRs trong truy vấn ............................................................42  Hình 16: R-Tree và truy vấn trong hai cấu trúc MBR khác nhau.........................42  Hình 17: Ví dụ về R-Tree .....................................................................................44  Hình 18: Cây biểu diễn R-Tree.............................................................................47  Hình 19: Biểu diễn hai chiều của một R-Tree ......................................................47  Hình 20: Cấu trúc một R-Tree ..............................................................................48  Hình 21: Các quan hệ có thể có giữa các MBR (chứa trong, chồng lấn…) .........49  Đề tài: 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  2008


6

Hình 22: Trường hợp phân chia node ...................................................................53  Hình 23: Phân chia entry thành các nhóm node mới ............................................54  Hình 24: Minh họa cấu trúc sản phẩm ArcGIS của ESRI ....................................66  Hình 25: Kiến trúc CSDL trên nền tảng Microsoft...............................................68  Hình 26: Trang web bản đồ trực tuyến diadiem.com ...........................................72  Hình 27: Trang web bản đồ trực tuyến basao.com ...............................................73  Hình 28: Hình dạng Elip của trái đất ....................................................................76  Hình 29: Khoảng cách AB tính theo công thức Haversine trên bản đồ địa lý......79  Hình 30: Mô hình dữ liệu quan hệ ........................................................................80  Hình 31: Thông số các hệ tọa độ elip tròn xoay ...................................................84  Hình 32: Khoảng cách tính theo thuật toán Haversine và Vincenty.....................89  Đề tài: 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  2008


7

A. PHẦN MỞ ĐẦU 1. Giới thiệu Trong vài năm trở lại đây, cùng với sự phát triển không ngừng của các kỹ thuật công nghệ hiện đại, “kỷ nguyên số” đã được bắt đầu và ứng dụng trong mọi lĩnh vực khoa học cũng như phục vụ nhu cầu sử dụng của con người. Nếu như cách đây vài thập kỷ, câu chuyện con người có thể quan sát toàn cảnh trái đất từ trên cao xuống thông qua các thiết bị kỹ thuật như máy tính, tivi… tại bất kỳ đâu và bất kỳ lúc nào vẫn là một viễn cảnh xa vời thì ngày nay điều này đã trở nên quá đơn giản. Để có thể quan sát Trái đất từ mọi góc độ, một cá nhân chỉ cần trang bị cho mình một máy tính nối mạng, và một phần mềm hiển thị hình ảnh 3D như Google Earth hay truy cập vào các trang web bản đồ trực tuyến sẵn có trên mạng Internet… Như vậy, trong bối cảnh hiện tại, sự hiện thực hóa bản đồ số và đưa các kỹ thuật lập bản đồ cũng như phân tích địa lý vào sử dụng rộng rãi với mục đích dân sự cho tất cả các tổ chức, cá nhân có nhu cầu đang trở thành một ngành kinh doanh nhiều lợi nhuận. Trong đó phải kể đến GIS – Hệ thống thông tin địa lý – với rất nhiều công cụ ứng dụng trợ giúp đắc lực cho quá trình xây dựng hệ thống hạ tầng cơ sở dữ liệu không gian và quản lý dữ liệu địa lý. Cùng với đó là hàng loạt các sản phẩm toàn diện và chuyên biệt sử dụng trong ngành khoa học bản đồ và xử lý dữ liệu không gian địa lý được các hãng sản xuất tung ra. Công nghệ GIS cùng với các sản phẩm phần mềm hỗ trợ có rất nhiều ứng dụng trong khoa học nghiên cứu, phục vụ trong đời sống, dịch vụ công ích, quản lý tài nguyên…. và nhiều lĩnh vực khác. Trong cuộc cạnh tranh ngôi vị nhà cung cấp hàng đầu các sản phẩm ứng dụng GIS và xử lý dữ liệu địa lý thì yếu tố giá thành cũng như hiệu năng của chương trình là quan trọng nhất. Trong cuộc cạnh tranh về công nghệ này, nhiều nghiên cứu đã được đưa ra như: Tối ưu hóa khả năng quản lý dữ liệu địa lý bằng phương pháp đánh chỉ Đề tài: 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  2008


8

mục động với cấu trúc dạng cây (tree-like structure) phục vụ tăng tốc quá trình tìm kiếm dữ liệu – đây là vấn đề đặc biệt quan trọng với một khối lượng dữ liệu khổng lồ và phức tạp như thông tin địa lý. Tăng tốc quá trình thực thi với các truy vấn đến Cơ sở dữ liệu không gian, tối thiểu hóa thời gian thực thi của hệ thống, đơn giản hóa độ phức tạp tính toán trong giải thuật nhằm tiết kiềm thời gian thực hiện và tăng hiệu năng tính toán. Trong vấn đề về giải thuật, phương pháp ưu việt chính là tìm ra và áp dụng các thuật toán tính toán khoảng cách tốt nhất, đảm bảo yêu cầu dung hòa giữa độ phức tạp tính toán, tốc độ thực thi và độ chính xác càng cao càng tốt. Nhận thấy sự cần thiết trong ngành khoa học nghiên cứu lý thuyết về các thuật toán tính toán khoảng cách giữa các đối tượng địa lý trong thực tế và vai trò to lớn của các bài toán tính toán gần đúng này, đề tài khóa luận tốt nghiệp “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” đã được xây dựng dựa trên quá trình nghiên cứu các thành tựu khoa học trong lĩnh vực này và hệ thống lại một cách bài bản và chi tiết. Bố cục khóa luận Khóa luận tốt nghiệp được trình bày với phần nội dung gồm 04 chương: Chương 1: Tổng quan về cơ sở dữ liệu không gian. 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. 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ế. Chương 4: Một số thuật toán tính toán khoảng cách trong không gian địa lý và đánh giá hiệu năng. 2. Ý nghĩa khoa học và thực tiễn Về khía cạnh nghiên cứu khoa học, các tập đoàn công nghệ trong lĩnh vực GIS vẫn không ngừng nghiên cứu các phương pháp tối ưu hóa các sản phẩm sử dụng thông tin địa lý trong các thiết bị hỗ trợ bản đồ, tìm đường và xác Đề tài: 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  2008


9

định vị trí địa lý của đối tượng. Trong đó, giải pháp đặt ra không chỉ dừng ở việc xây dựng một hệ quản trị cơ sở dữ liệu chuyên biệt quản lý dữ liệu không gian và các thuộc tính đặc biệt của nó với dung lượng khổng lồ và phức tạp, quan trọng hơn là giải pháp nào để tối ưu hóa hiệu năng truy xuất dữ liệu, các giải thuật đề xuất giúp hệ thống thực thi các phép toán (đặc biệt là các phép tính khoảng cách quy mô hàng chục ngàn km) phải thật nhanh chóng nhưng vẫn đảm bảo độ chính xác cần thiết. Trong không gian địa lý với đặc thù bề mặt Trái đất không ổn định, việc dùng các phương pháp tính toán gần đúng là không thể tránh khỏi, tuy nhiên sai số đặt ra cần nằm trong khoảng chấp nhận được, sự cân bằng giữa độ chính xác và thời gian xử lý, trả lời truy vấn và giá thành chính là chìa khóa thành công cho bất kỳ sản phẩm có sử dụng thuật toán dò đường và tính khoảng cách nào. Khóa luận trình bày cụ thể về các giải pháp sử dụng trong bài toán tính toán xấp xỉ khoảng cách, hệ thống một cách khoa học các kỹ thuật sử dụng trong tìm kiếm đối tượng cũng như tính khoảng cách giữa các đối tượng trong truy vấn. Đây hầu hết là những kỹ thuật quan trọng và hiệu quả đang được sử dụng rộng rãi trong các ứng dụng khai thác thông tin về đường đi, địa điểm và quảng cáo trên nền tảng bản đồ số. Do đó các vấn đề về lý thuyết trong lĩnh vực này luôn là đề tài khoa học có tính chất thời sự trên các diễn đàn công nghệ GIS cũng như trong đội ngũ các nhà phân tích, thiết kế sản phẩm. Từ các thuật toán có sẵn, nhà sản xuất hoàn toàn có thể cài đặt và “nhúng” vào trong nhiều ứng dụng như: Bản đồ kỹ thuật số, phần mềm định vị và chỉ đường trên các thiết bị cầm tay, các thiết bị di động đi kèm các phương tiện giao thông, thiết bị tìm vết và đường đi ngắn nhất tích hợp GPS (Hệ thống định vị toàn cầu), …. 3. Mục đích nghiên cứu Đề tài được thực hiện với mục đích Tìm hiểu khái niệm Cơ sở dữ liệu không gian, các công nghệ GIS đương đại. Nghiên cứu các kỹ thuật tính toán gần đúng về khoảng cách và các thuật Đề tài: 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  2008


10

toán liên quan sử dụng trong các truy vấn trên CSDL không gian. Các ứng dụng thiết thực của bài toán tính toán xấp xỉ trong công nghệ thông tin địa lý. Thử nghiệm một số truy vấn sử dụng kỹ thuật tính toán xấp xỉ trong một số truy vấn tiêu biểu. 4. Đối tượng nghiên cứu Mô hình, cấu trúc dữ liệu và cách xây dựng dữ liệu không gian và hệ quản trị CSDL không gian, các phép toán thực thi. Các kỹ thuật tính toán xấp xỉ khoảng cách trong không gian tìm kiếm và các thuật toán. Sản phẩm ứng dụng các kỹ thuật tính toán xấp xỉ đang được sử dụng trong thực tế. Thuật toán tính toán khoảng cách trên bề mặt cầu ứng dụng trong truy vấn về khoảng cách trong không gian địa lý: Haversine, Vincenty. 5. Phạm vi nghiên cứu Do hạn chế về thời gian và giới hạn trong khuôn khổ một đề tài khóa luận tốt nghiệp, đề tài tập trung trình bày các thuật toán và giải pháp sử dụng trong các truy vấn liên quan đến khoảng cách trong CSDL không gian, phục vụ trong quá trình xử lý, phân tích và hiển thị dữ liệu địa lý của một ứng dụng GIS bất kỳ trong thực tế. Qua đó đưa ra đánh giá hiệu năng của từng giải pháp và đề xuất các hướng phát triển cho thuật tính toán gần đúng trong tương lai. Qua đó, độc giả có được cái nhìn tổng quan về các kỹ thuật cũng như thuật toán tính toán gần đúng đang được sử dụng trong các ứng dụng xây dựng, quản lý và thiết kế dữ liệu thông tin địa lý, cơ sở dữ liệu không gian và hướng phát triển của chúng trong công cuộc nghiên cứu nhằm hoàn thiện tốc độ xử lý, tính toán, truy xuất dữ liệu của hệ thống với sự trợ giúp của các thuật toán tích hợp hiệu quả và chính xác. Đề tài: Tính toán xấp xỉ với các truy vấn liên