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

nghiên cứu này trong thực tiễn. Thành tựu của nó mang lại những kết quả to lớn không chỉ về mặt lý luận đơn thuần trong cuộc cách mạng hóa về bản đồ và bài toán tìm kiếm thông tin địa lý kỹ thuật số. Trong dòng chảy của công nghệ, các nhà khoa học, kỹ sư đang không ngừng cải tiến các kỹ thuật, các thuật toán cũng như tìm kiếm giảp pháp tích hợp tốt nhất cho các ứng dụng GIS, tất cả đều có chung một mục tiêu đó là hướng đến một giải pháp hoàn thiện nhất, có thể tối thiểu hóa thấp nhất thời gian đáp ứng của hệ thống đối với một yêu cầu xử lý truy vấn cũng như giới hạn tối đa số lượng các phép tính phức tạp cần phải thực hiện, trong khi vẫn đảm bảo đưa ra cho khách hàng những kết quả truy xuất tốt nhất, chính xác nhất. Dưới đây là khái quát một số trong rất nhiều các nghiên cứu và ứng dụng có liên quan trong lĩnh vực này 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. Trong những năm gần đây, bắt đầu từ 2003 trong Papadias(2003) một kiến trúc hứa hẹn nhiều tiềm năng đã và đang được nghiên cứu và không ngừng được ứng dụng trong các sản phẩm liên quan đến hệ thống thông tin địa lý - GIS cũng như hệ quản trị cơ sở dữ liệu không gian. Đây là cấu trúc được xây dựng dựa trên ý tưởng tích hợp mạng không gian với không gian khoảng cách trong đại số Euclidean, sao chép lại các ràng buộc thực thể trong thực tế Giải pháp được đề xuất này đặt ra yêu cầu cấp thiết phải xây dựng và phát triển một hệ thống framework chuyên biệt để xử lý tất cả các truy vấn cơ bản nhất trong CSDL không gian. Và những kỹ thuật xấp xỉ khoảng cách đã được trình bày trên đây hoàn toàn có thể được áp dụng trong kiến trúc framework này với mục đích hỗ trợ chương trình xử lý đưa ra các truy xuất CSDL nhanh chóng và hiệu quả so với các phương pháp tìm kiếm và truy vấn thông thường. Đề 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


65

Có thể kể đến một số nhà cung cấp các hệ thống framework và các phần mềm tích hợp như một giải pháp toàn diện cho việc xây dựng, ứng dụng và quản lý hệ thông tin địa lý như ESRI (Viện nghiên cứu các hệ thống môi trường) thành lập vào năm 1969, ESRI có trụ sở tại Redlands, California. Website: www.esri.com ESRI công bố sản phẩm phần mềm ArcGIS 9 vào tháng 5 năm 2004, những phiên bản tiếp theo liên quan đến phần mềm tích hợp này được thiết kế nhằm đưa ra bộ sản phẩm phần mềm GIS hoàn thiện. Hai sản phẩm đã được công bố chính là ArcGIS Engine, bộ công cụ phần mềm có thể được dùng để nhúng các hàm GIS vào các ứng dụng có sẵn, và ArcGIS Server, ứng dụng kỹ thuật về không gian địa lý trong hệ thống thông tin quy mô lớn thông qua việc quản lý và ứng dụng dữ liệu tập trung kết hợp với các chuẩn công nghệ thông tin Ngày nay, các sản phẩm GIS của ESRI đang trên đà phát triển, việc đổi mới trong công nghệ cho phép các hoạt động GIS tinh vi hơn thông qua hỗ trợ số hóa cá nhân (PDA) trên desktop cho các doanh nghiệp. Tính năng mới của phần mềm giúp doanh nghiệp xử lý mạng, xuất dữ liệu điện tử, công cụ dễ sử dụng và đáp ứng được ưu điểm của công nghệ GIS. Trong đó ArcGIS framework được đánh giá là giải pháp toàn diện cho thông tin địa lý bao gồm một tập hợp các sản phẩm phần mềm GIS cung cấp cho người dùng hệ thống các sản phẩm cho phép xây dựng các ứng dụng tùy biến, destop, server, ứng dụng web…: DestopGIS, ServerGIS, DeveloperGIS, MobileGIS, Dịch vụ GIS Web. Đề 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


66

Hình 24: Minh họa cấu trúc sản phẩm ArcGIS của ESRI Phiên bản ArcGIS mới nhất là ArcGIS 9.3 Chi tiết tại website chính thức: www.esri.com/software/arcgis/index.html Ngày 28 tháng 4 năm 2008 tại trụ sở ở Redlands, California — ESRI tuyên bố khai trương ESRI Vietnam song hành với ESRI Thái Lan trong khu vực. Việc mở ESRI Vietnam cho phép ESRI phục vụ tốt hơn người dùng trong khu vực và cũng thừa nhận sự pháp triển và trưởng thành trong thị trường GIS. Phần mềm ESRI đã được bán trong khu vực nhiều năm qua, và việc thêm văn phòng ESRI Vietnam sẽ cung cấp một sự hỗ trợ tốt hơn cho cả những ngừơi dùng và hy vọng mở rộng thị trường giáo dục trong quốc gia để gia tăng đào tạo về GIS thông qua việc liên doanh với các trường và đại học nội địa. Sự xuất hiện của ESRI VietNam nhằm hỗ trợ tốt hơn khách hàng khu vực, đặc biệt, tại Việt Nam, các dòng sản phẩm quen thuộc của ESRI được sử dụng chính thức nhiều hơn một thập kỷ trước. Theo www.mathgis.com 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) Ứng dụng rộng rãi và thành công nhất trong ngành khoa học công nghệ nghiên cứu và kiến thiết các hệ quản trị cơ sở dữ liệu không gian, các giải Đề 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


67

pháp quản lý, mô hình hóa, xử lý truy vấn và hiển thị dữ liệu địa lý chính là GIS – Hệ thống thông tin địa lý. Thực tế không thể phủ nhận rằng ngày nay các ứng dụng liên quan đến GIS cũng như CSDL không gian đang dần trở nên phổ biến và đi vào mọi mặt của cuộc sống công nghệ hiện đại. Không chỉ dừng ở khái niệm xây dựng các bản đồ địa lý, GIS còn là công cụ đắc lực cho nhà quản lý hoạch định được chiến lược phát triển cơ sở hạ tầng cho một xã, một huyện, một thành phố hay một quốc gia. Đi cùng với sự phát triển nhanh chóng đó là yêu cầu lưu trữ, xử lý một khối lượng dữ liệu ngày càng lớn và phức tạp. Để xử lý một khối lượng dữ liệu khổng lồ trong khoảng thời gian cho phép của hệ thống không phải là điều đơn giản, do vậy trong ngành kinh doanh công nghệ hiện đại, hệ thống có tốc độ xử lý càng nhanh, hiệu năng càng cao thì càng đắt giá. Trong cuộc cạnh tranh khốc liệt giữa các hãng cung cấp giải pháp trong ứng dụng GIS và hệ quản trị CSDL, việc tìm kiếm các thuật toán tối ưu luôn là ưu tiên được đặt lên hàng đầu. Với GIS - chức năng quan trọng nhất tạo nên sức mạnh thực sự của GIS so với các phương pháp khác chính là khả năng phân tích và tìm kiếm dữ liệu không gian, trong đó số lượng truy vấn tìm kiếm liên quan đến khoảng cách lại chiếm đa số. Do vậy rõ ràng các thuật toán xấp xỉ khoảng cách đóng vai trò quan trọng trong thiết kế giải pháp xử lý các truy vấn và cải thiện đáng kể tốc độ xử lý, phân tích của hệ thống. Với thời gian truy xuất nhanh chóng và kết quả truy xuất đáng tin cậy các hệ thống sử dụng thuật toán và các kỹ thuật xấp xỉ khoảng cách đang thể hiện ưu thế rõ rệt trên thị trường công nghệ. Sản phẩm mới nhất về CSDL hiện nay phải kể đến SQL Server 2008 với những ưu điểm vượt trội do Microsoft tung ra thị trường gần đây. ™ Lưu trữ được nhiều loại dữ liệu hơn bao giờ hết Cùng với sự bùng nổ các loại ứng dụng mới đặc biệt là các loại ứng dụng viễn thông trên nền tảng IP như OCS 2007 hay Exchange 2007 UM thì hàng loạt các định dạng dữ liệu mới cũng ra đời và người ta cũng muốn lưu trữ , tìm kiếm, truy vấn, chia sẻ, đồng bộ chúng. Vì vậy việc lưu trữ những dự liệu như vậy trên hệ CSDL đã được SQL Server 2008 giải quyết khá triệt để và rốt ráo với khả năng lưu trữ hầu hết các loại dữ liệu từ dự liệu dạng Spatial cho Đề 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


68

đến dạng File Streams. ™ Khả năng thao tác song hành trên các bảng dữ liệu phân vùng SQL Server 2005 hỗ trợ việc lưu trữ và thao tác song hành liên bảng ghi CSDL. SQL Server 2008 tiếp tục nâng cao khả năng thao tác song hành với các bảng dữ liệu phân vùng liên hệ thống. Điều này có nghĩa là khi người dùng có thể thực hiện một truy vấn mà liên quan đến dữ liệu trên hai phân vùng CSDL thì SQL Server 2008 sẽ xử lý truy vấn này song hành cùng lúc trên mỗi phân vùng. ™ Tăng tốc khả năng truy vấn dữ liệu Cùng với khả năng nén CSDL lên đến trên 50% thì hiệu xuất truy vấn dữ liệu cũng được cải thiện đáng kể với Support Star Schema và Star Query Optimizations trên SQL Server 2008. Hình 25: Kiến trúc CSDL trên nền tảng Microsoft 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 Khó khăn đối với kích thước địa lý thực của đối tượng ở đây là sự chênh Đề 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


69

lệch về khoảng cách giữa các điểm càng nhỏ khi kích thước tăng. Ý tưởng sử dụng kỹ thuật tính toán gần đúng như một công cụ hạn chế những khó khăn phát sinh do sự khác biệt giữa đối tượng địa lý trong không gian thực và biểu diễn hình học của đối tượng đó trong CSDL không gian, đang được áp dụng cho việc xây dựng các cấu trúc đánh chỉ mục cũng như trong quá trình tính toán các kết quả chính xác. Có rất nhiều tiêu chuẩn tương tự trong các CSDL đa phương tiện và các hệ thống trợ giúp việc lập quyết định đang được định nghĩa dựa trên cơ sở là các không gian vecto trong không gian thứ nguyên bậc cao. Các phương pháp chỉ mục phân chia dữ liệu sử dụng trong các không gian thông thường (như grid file, R-tree và các biến thể của chúng) thường hoạt động tốt với các không gian thứ nguyên bậc thấp, nhưng lại thể hiện nghèo nàn khi bậc thứ nguyên tăng lên. Vấn đề nảy sinh này thường được gọi theo thuật ngữ là “dimensional curse[1]” – tạm dịch là “trở ngại về bậc thứ nguyên”. Giải pháp đưa ra là Vector-approximation file (VA-file[2]) (Weber, Schek, & Blott, 1998) ứng dụng trong tìm kiếm tương đương trên các không gian vector thứ nguyên bậc cao. VA-file – The vector approximate file: Cấu trúc tổ chức dữ liệu duới dạng chia không gian dữ liệu thành 2b ô chữ nhật – rectangle cells, mỗi ô được định nghĩa một số bít xác định là b (như một số lượng bit trên mỗi chiều). Thay vì tổ chức dưới dạng phân cấp như cấu trúc grid file hoặc R-tree, VA-file cấp phát cho mỗi ô một chuỗi bít riêng có độ dài b và qui định xấp xỉ vị trí của các điểm dữ liệu vào trong mỗi ô bằng các chuỗi bít này. VA-file bản thân nó đơn giản chỉ như một mảng của các phân phối gọi là xấp xỉ hình học. Trong bài toán tìm kiếm k lân cận gần nhất, toàn bộ các file xấp xỉ sẽ được duyệt qua và các đường biên cận trên và cận dưới giới hạn khoảng cách trong truy vấn có thể được xác định dễ dàng dựa vào các ô dạng chữ nhật được biểu diễn một cách gần đúng. Qua đó, một số lượng lớn các vectơ nằm trong chuỗi tìm kiếm này sẽ được lược bỏ dựa trên khung giới hạn gần đúng trên – bước lược bỏ nhằm giới hạn không gian tìm kiếm này còn được gọi là filtering step – Bước lọc. Sau bước này việc tìm kiếm sẽ được thu nhỏ trong giới hạn một tập cá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


70

trường hợp khả thi còn lại. Các trường hợp này sau đó sẽ được xem xét theo thứ tự tăng dần của đường biên khoảng cách thấp hơn đối với điểm truy vấn q, khoảng cách chính xác đến q sẽ được tính toán. Tuy nhiên, không cần thiết phải xét hết tất cả các trường hợp trên, nếu đường biên cận dưới tiến vượt quá k-th khoảng cách gần nhất, quá trình tìm kiếm K-NNQs (K Nearest Neighbour queries) dừng. VA-file khắc phục được các khó khăn gây ra bởi “dimentional curse” bằng cách thay vì chú trọng quản lý cách thức phân chia dữ liệu thuộc các phương pháp chỉ mục thông thường, VA-file theo dõi cách thức lọc dữ liệu của file đã đánh dấu. Như vậy chính dữ liệu (không phải là không gian) sẽ được phân chia thành các ô, và các vector sẽ được gán tương đương theo giá trị gần đúng dựa vào các ô chứa chúng. VA-file bao gồm các giá trị xấp xỉ đã được chia nhỏ dưới dạng bít mã hóa này. Cùng với VA-file là VA+-file là hai cấu trúc lưu trữ các điểm tính toán gần đúng trong quá trình xử lý trên không gian thứ nguyên bậc cao. Ngoài ra, A-tree[3] (Sakurai, Yoshikawa, Uemura, & Kojima 2000) là một cấu trúc khác nơi các biểu diễn của MBR và các đối tượng dữ liệu được xây dựng dựa trên các phép tính gần đúng liên quan từ các MBR ở cấp “cha” của chúng. Những cấu trúc này đang được sử dụng trong việc tính toán chính xác các truy vấn tìm kiếm lân cận gần nhất trong không gian thứ nguyên bậc cao và biểu diễn, thực thi tốt hơn so với các kỹ thuật khác dựa trên R-tree. 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 Thực tế, từ khi hệ thống định vị vệ tinh GPS được đưa vào sử dụng cho mục đích dân sự, nó đã ở ra một cuộc cách mạng công nghệ mới trong lĩnh vực trắc địa - bản đồ theo hướng không ngừng nâng cao hiệu quả của công tác đo đạc ngoại nghiệp cho đến việc đáp ứng mọi yêu cầu về độ chính xác (độ chính xác đo đạc GPS ngày nay có thể đạt ở mức mm với khoảng cách vài ngàn km). Tuy nhiên công nghệ này chỉ được ứng dụng nhiều trong kỹ 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


71

đo tĩnh chính xác và chủ yếu là về phương diện mặt bằng còn về thành phần độ cao ít được quan tâm hơn, đặc biệt trong kỹ thuật đo động thì thành phần độ cao hầu như bị bỏ qua trong các ứng dụng độ chính xác cao. Ngày nay với sự gia tăng về số lượng vệ tinh, cấu hình vệ tinh ngày càng tốt, công nghệ chế tạo máy thu ngày càng cao và các phần mềm xử lý ngày càng tinh vi thì chắc chắn rằng độ chính xác đo tĩnh và đo động cả về phương diện mặt bằng lẫn độ cao sẽ không ngừng được cải thiện. Với các thuật toán tính khoảng cách dựa trên địa hình trái đất với hệ tọa riêng cho từng khu vực như với thuật toán Vincenty sẽ trình bày trong chương dưới đây, sai số so với khoảng cách thực tế là rất nhỏ. Do đó tỉ lệ khoảng cách giữa các đối tượng trên bản đồ so với thực tế cũng đạt đến độ chính xác cao với sai số ở mức chấp nhận được. Trong các bản đồ số dạng 2D – hình học phẳng, thuật toán xấp xỉ khoảng cách trở nên đặc biệt hữu dụng trong việc tìm đường đi ngắn nhất từ vị trí định vị đến đối tượng tìm thấy thỏa mãn trong truy vấn, hoặc tính khoảng cách gần đúng đến vị trí đã định giữa các khu vực thông qua các tuyến giao thông: Đường phố, đường xe cơ giới, đường xe buýt hoặc đường thủy… Hiện nay tại Việt Nam đã có rất nhiều trang web bản đồ trực tuyến sử dụng công nghệ WebGIS trợ giúp cộng đồng mạng trong việc tìm đường đi, tìm địa điểm, khu vực… phục vụ trong tra cứu, du lịch hoặc quản lý tài nguyên, quản lý đô thi, đất đai, hệ thống thủy lợi… Ví dụ một số trang web bản đồ trực tuyến đang hoạt động hiệu quả hiện nay như: www.diadiem.com Trang web tìm đường tại hầu hết các tỉnh thành trong cả nước, hỗ trợ hiển thị bản đồ địa lý dưới dạng hình vẽ 2D và hình ảnh 3D từ vệ tinh. Cho phép người dùng tìm đường đi ngắn nhất giữa hai vị trí trong thành phố Đề 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


72

Hình 26: Trang web bản đồ trực tuyến diadiem.com Trang web www.basao.com.vn , cũng là một trang web bản đồ trực tuyến, hỗ trợ tìm đường trên bản đồ 2D nhưng có ưu thế hơn do cho phép tìm kiếm đường đi dựa trên phương tiện giao thông sử dụng: Ôto, xe buýt, xe máy, đường thủy, đường hàng không… Đề 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


73

Hình 27: Trang web bản đồ trực tuyến basao.com Chú thích [1] Dimensional curse: Một số lượng lớn các cấu trúc chỉ mục thứ nguyên bậc cao tập trung chiếm nhiều tài nguyên của bộ nhớ và ảnh hưởng đến hiệu xuất của các thao tác xử lý – hiện tượng này được gọi là “dimensional curse” [2] VA-file – The vector approximate file: Cấu trúc tổ chức dữ liệu duới dạng chia không gian dữ liệu thành các ô chữ nhật – rectangle cells, mỗi ô được định nghĩa một số bít nhất định như một số lượng bit trên mỗi chiều. VA-file đơn giản như một mảng của các phân phối gọi là xấp xỉ hình học. [3] A-tree: Một cấu trúc đánh chỉ mục mới sử dụng trong việc tìm kiếm tương tự cá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


74

dữ liệu trong không gian thứ nguyên bậc cao. Ý tưởng cơ bản của A-Tree là sử dụng Virtual Bounding Rectangles – VBRs (Khung giới hạn ảo), là kiểu khung bao gồm và xấp xỉ các MBR và các đối tượng dữ liệu. VBRs có ưu thế biểu diễn được các đối tượng khá chặt chẽ. 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 1. Tính toán khoảng cách giữa các đối tượng địa lý theo công thức Haversine 1.1 Công thức Haversine 1.1.1 Khái niệm Công thức Haversine là một đẳng thức quan trọng được sử dụng trong quá trình điều hướng[1], đưa ra các great-circle distance[2] (tạm dịch: khoảng cách vòng cung lý tưởng) giữa hai điểm trên bề mặt khối cầu từ giá trị tọa độ (kinh độ, vĩ độ) cho trước của chúng. Công thức Haversine là trường hợp đặc biệt của các thuật toán phổ biến trong lượng giác cầu (spherical strigonometry[3]) Great-circle distance: Là khoảng cách ngắn nhất giữa hai điểm bất kì trên bề mặt khối cầu tính dọc theo một hướng đi trên bề mặt khối cầu (nghĩa là đo đường đi vòng cung trên bề mặt, hoàn toàn khác với khoảng cách tính theo đường thẳng nối hai điểm đó qua bên trong khối cầu). Khoảng cách này thể hiện sự khác biệt trong khái niệm khoảng cách giữa hai điểm trong hình học Euclidean và hình học không gian. Cụ thể: Khoảng cách giữa hai điểm trong không gian Euclidean là độ dài đoạn thẳng nối hai điểm đó. Trong hình học cầu, đoạn thẳng được thay thế bằng đường cong. Với hai điểm không đối xứng trực tiếp với nhau qua tâm của hình cầu (hoặc elip tròn xoay) thì chỉ tồn tại duy nhất một great–circle (đường cong lý tưởng), hai điểm này phân ly great-circle thành hai cung, độ dài của cung ngắn hơn chính là great-circle distance (khoảng cách vòng cung lý tưởng). Chú ý rằng hai đường great-circle tương ứng này phải cùng nằm trên một mặt phẳng cắ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


75

hình cầu qua tâm của nó. Với hai điểm đối xứng với nhau qua tâm hình cầu sẽ có vô số các great- circle thỏa mãn giữa chúng và độ dài của các vòng cung này đều bằng nhau và bằng một nửa chu vi của hình cầu đó (bằng πR – R là bán kính hình cầu). Do trái đất cũng có hình dạng gần như một khối cầu, các phương trình cho great-circle distance đóng vai trò rất quan trọng trong bài toán tìm khoảng cách ngắn nhất giữa các điểm trên bề mặt trái đất cũng như trong quá trình điều hướng (định hướng đường đi ngắn nhất cho các phương tiện hàng không và hàng hải). 1.1.2 Công thức Haversine Với hai điểm A và B thuộc mặt cầu (có bán kính R) với tọa độ địa lý (kinh độ, vĩ độ) tương ứng: A (φ1, λ 1) B (φ 2, λ 2) Δ φ = φ1 – φ2 Δλ = λ1 – λ2 Với góc được tính theo đơn vị radian, ta có khoảng cách d giữa hai điểm A và B (tính toán dựa trên great-circle – đường tròn lý tưởng [4] đường tròn trên bề mặt của hình cầu có chu vi bằng chu vi của hình cầu đó và chia nó ra làm hai bán cầu bằng nhau) trong phương trình liên hệ sau: Đặt h = haversin(d/R) với 0 ≤ h ≤ 1 Ö h = (sin(Δ φ/2))2 + cos(φ1) * cos(φ2) * (sin(Δλ/2)2 ) Từ phương trình trên, ta tính được khoảng cách d một cách đơn giản nếu sử dụng hàm nghịch đảo của hàm haversin hoặc sử dụng hàm arcsin (hàm sin nghịch đảo) Đề 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


76

Suy ra: Dựa vào công thức trên, ta có công thức tính khoảng cách đường tròn lý tưởng – Great Circle Distance – C như sau: C = 2 arcsin (sqrt(h)) Ö C = 2 arcsin (sqrt ( (sin(Δ φ/2))2 + cos(φ1) * cos(φ2) * (sin(Δλ/2)2 ) ) Ứng dụng công thức Haversine vào việc tính toán khoảng cách trên bề mặt trái đất: Khi sử dụng Haversin trên bề mặt cầu trái đất, công thức chỉ có tính chất tính toán gần đúng do đặc điểm đặc biệt của bề mặt trái đất là hình dạng không phải là một hình cầu hoàn hảo mà có dạng như hình elip bị dẹt ở hai cực Bắc và Nam với bán kính R xấp xỉ từ 6356.78 km ở cực đến 6378.14 km tại xích đạo. Do đó ở đây có một sự điều chỉnh nhỏ nằm trong khoảng sai số 1% với quy ước coi như trái đất là khối cầu hoàn hảo với bán kính quy định như một đại lượng hình học không đổi R = 6367.45 km. Như vậy, bỏ qua trính chất elip không đáng kể của bề mặt trái đất, ta có thể áp dụng công thức Haversine trong các hàm tính toán về khoảng cách trong thông tin địa lý với dữ liệu địa lý thông thường. Hình 28: Hình dạng Elip của trái đất North Pole RR Equatorial plane Ellipsoid Đề 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


77

1.2 Công thức Haversine trong truy vấn tìm khoảng cách ngắn nhất Công thức Haversin ứng dụng trong thuật toán tính toán khoảng cách giữa hai điểm trong không gian tọa độ địa lý Có hai điểm A và B với tọa độ địa lý (kinh độ, vĩ độ) tương ứng (lat1, long1) và (lat2, long2) Ö Công thức Haversine sử dụng trong tính toán khoảng cách d = AB theo bề mặt cầu của trái đất được tính toán như sau: R = Bán kính trái đất (Quy ước = 6,371km) Δlat = lat2− lat1 Δlong = long2− long1 h = sin²(Δlat/2) + cos(lat1) * cos(lat2) * sin²(Δlong/2) c = 2 * atan2(sqrt(h), sqrt(1−h)) d = R * c Chú ý: Các góc cần phải đổi đơn vị từ độ (trong kinh độ, vĩ độ) sang đơn vị Radian trước khi tính toán các hàm lượng giác và khoảng cách. Hàm atan2(x, y) trả về giá trị arctg (x/y) theo đơn vị radian. VD1: Hai điểm A & B với kinh độ, vĩ độ tương ứng, tọa độ có dạng độ/phút/giây và hậu tố chỉ một trong bốn hướng địa lý: N-Bắc/S-Nam/E- Đông/W-Tây. A (530 09’ 02’’N; 0010 50’ 40”W) Ù A(53,1560; - 1,84440 ) B (520 12’ 17”N; 0000 08’ 26” E) Ù B (52,20470; 0,14060) Với hệ quy đổi: 10 = 60’; 1’ = 60” Ta có đoạn mã Javascript sau để thực hiện thuật toán tính toán khoảng cách giữa hai điểm: var R = 6371; // km var dLat = (lat2-lat1).toRad(); var dLon = (lon2-lon1).toRad(); Đề 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


78

var h = Math.sin(dLat/2) * Math.sin(dLat/2) + Math.cos(lat1.toRad()) * Math.cos(lat2.toRad()) * Math.sin(dLon/2) * Math.sin(dLon/2); var c = 2 * Math.atan2(Math.sqrt(h), Math.sqrt(1-h)); var d = R * c; Với: Hàm toRad() – Hàm chuyển giá trị tọa độ từ dạng kinh độ, vĩ độ sang đơn vị Radian Ö Kết quả thu được: dHaversine = AB = 170,2 km & Khoảng cách vòng cung lý tưởng là C = 105,8 km (Đây là đại lượng sử dụng đánh giá độ chính xác tính toán của các thuật toán tính khoảng cách trên bề mặt cầu). Tương ứng với vị trí trên bản đồ tìm được như sau: Đề 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


79

Hình 29: Khoảng cách AB tính theo công thức Haversine trên bản đồ địa lý VD2: Trở lại với mô hình cơ sở dữ liệu Benchmark đã đề cập trong Chương 2 - Mục 1: Các truy vấn liên quan đến khoảng cách. Ta có truy vấn tìm khoảng cách vị trí đối tượng gần nhất tính từ vị trí hiện tại của người dùng Đề 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


80

Hình 30: Mô hình dữ liệu quan hệ Truy vấn: Tìm nhà hàng gần nhất (giả thiết với Other.type = 1) tính từ khu vực hiện tại tôi đang đứng ( với giá trị Human.Id = 20) SELECT Other.id FROM Human, Other WHERE Other.type = 1 AND Human.Id = 20 ORDER BY Spatial_Neighbour (Other.Location, curr_space (Human.Route)) ASC = 1; Chú ý: ™ Trong trường hợp này K = 1. ™ Với câu lệnh SQL: ORDER BY Spatial_Neighbour (Other.Location, curr_space (Human.Route) ) ASC = 1; ™ Hàm curr_space(): Hàm trả về các thông tin cập nhật tọa độ hiện thời của thiết bị (tọa độ hiện tại của người sử dụng thiết bị) ™ Hàm Spatial_Neighbour (attribute, reference) được sử dụng để biểu diễn truy vấn dạng K-NN giữa các thuộc tính. Kết quả trả về được sắp xếp theo quy tắc tăng dần về khoảng cách (ở đây là khoảng cách gần nhất giữa người sử dụng đến nhà hàng). Với giá trị ASC = 1 ta thu được kết quả trả lời truy vấn là vị trí nhà hàng gần nhất tính từ vị trí hiện tại. Thuật toán xác định đối tượng trong khu vực thỏa mãn và tính toán khoảng Đề 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


81

cách từ vị trí xác định đến đối tượng sẽ được cài đặt trong hàm Spatial_Neighbour (attribute, reference). Giá trị trả về của hàm là tất cả các vùng lân cận gần nhất (ở đây là nhà hàng) thể hiện trong tham số reference (Other.Location) và thỏa mãn đến dữ liệu nhập vào từ tham số attribute. Sử dụng hàm tính toán Haversine cài đặt như trên, ta có thể tính được khoảng cách trên bề mặt trái đất từ tọa độ xác định đến tọa độ vị trí tìm thấy trong truy vấn: Giả sử vị trí hiện tại: Giá trị trả về của hàm Curr_Space (Human.Route) là vị trí có tọa độ C (200 50’ 30”S; 0030 09’ 21”W) Một số nhà hàng tìm thấy trên bản đồ có vị trí lần lượt là: ™ R1 (200 55’ 00”S; 0030 01’ 30”W) Ö Dhaversine CR1 = 15,95 km ™ R2 (210 00’ 00”S; 0020 59’ 10”W) Ö Dhaversine CR2 = 24,91 km ™ R3 (200 55’ 00”S; 0020 59’ 20”W) Ö Dhaversine CR1 = 19,25 km Kết quả tính toán được trả về và sắp xếp theo thứ tự tăng dần, với K = 1 Ö Ta thu được vị trí điểm gần nhất thỏa mãn truy vấn là R1. 1.3 Đánh giá thuật toán Haversine Công thức Haversine thực thi đặc biệt thành công với các tính toán số học kể cả với các khoảng cách nhỏ (khác với các cách tính toán dựa trên các luật thuộc bề mặt cầu của hàm cosin[] – Một tập các quy tắc tính toán đối với hàm cosin trên bề mặt hình cầu được đưa ra bởi R.W Sinnot trong “Sky and Telescope” xuất bản năm 1984; công thức tính bình phương hàm sin của góc θ/2 có thể được tính xấp xỉ bằng: (1-cosθ)/2 = sin²(θ/2)). Độ chính xác tính toán trong thuật toán Haversine: 0.3% (Sai số tính được so với khoảng cách trong thực tế) Trong thực tế, khi Sinnott phát minh ra công thức Haversine, khả năng tính toán số lớn của máy tính còn rất hạn chế. Ngày nay, công cụ Javascript và các máy tính hiện đại nhất sử dụng số dấu phẩy động 64-bit theo chuẩn IEEE 754, đã cung cấp tới 15 số chính xác sau dấu phẩy. Với độ chính xác cao như vậy, Đề 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


82

công thức tính theo đại lượng hàm cosin trên bề mặt cầu đưa ra kết quả khá tin cậy với khoảng cách nhỏ trong khoảng 1m. Tính khoảng cách d theo công thức cosin d=cos(sin(lat1).sin(lat2)+cos(lat1).cos(lat2).cos(long2−long1)).R Đoạn mã Javascript: var R = 6371; // km var d = Math.acos(Math.sin(lat1)*Math.sin(lat2) + Math.cos(lat1)*Math.cos(lat2) * Math.cos(lon2-lon1)) * R; Tuy nhiên, do độ chính xác của hàm tính toán này chỉ đáng tin cậy với khoảng cách nhỏ nên không thể sử dụng trong tính toán các khoảng cách lớn, đặc biệt là khoảng cách địa lý trên bề mặt trái đất. Thêm vào đó, tính chất Ellip của trái đất cũng là lí do hạn chế gần như tuyệt đối việc sử dụng công thức cosin trên trong tính khoảng cách. Trong một số trường hợp, công thức Haversine đã đơn giản hóa việc tính toán khoảng cách trên bề mặt cầu do việc xấp xỉ bán kính trái đất dưới dạng bán kính của một hình cầu lý tưởng (có bán kính qua bằng nhau tại mọi điểm trên bề mặt cầu), tuy nhiên việc đơn giản hóa này cũng mang lại sai số lớn khi tính toán các đối tượng cách xa nhau theo kinh độ cũng như vĩ độ địa lý. Khắc phục được hạn chế này là công thức Vincenty được Thaddeus Vincenty (‘TV’) phát minh, sử dụng trong tính toán khoảng cách địa lý với một cặp thông tin vị trí kinh độ và vĩ độ trên bề mặt trái đất, sử dụng mô hình ellip tròn xoay chính xác của trái đất. 2. Tính toán khoảng cách trong hệ tọa độ địa lý theo khoảng cách Vincenty 2.1 Khái niệm Thuật toán Vencenty (1975) được đặt theo tên của người phát minh là Thaddeus Vincenty – nhà đo đạc bản đồ người Ba Lan. Vencenty là một kỹ Đề 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


83

thuật tính toán đo đạc khoảng cách trong không gian địa lý với độ chính xác đáng kinh ngạc là 0,5mm hoặc 0.000015”. Hiện nay thuật toán Vicenty là tối ưu nhất để tính khoảng cách 2 điểm trên mặt ellipsoid với sai số vài cm trên đường đáy dài vài chục ngàn km. Các dạng Elip tròn xoay sử dụng trong tính toán khoảng cách địa lý Ellipsoid (elilp tròn xoay) có phương trình toán học nên xác định được tọa độ các điểm trên bề mặt của nó. Từ quá khứ, lịch sử nghiên cứu ngành khoa học trắc địa và thông tin địa lý đã ghi nhận nhiều nhà khoa học đã tìm cách tính kích thước của ellipsoid sao cho gần giống với trái đất thực nhất và cho các kết quả không giống nhau. Nguyên nhân là do trình độ khoa học công nghệ, công nghệ tính toán (trước đây do chưa có máy vi tính nên chủ yếu tính toán bằng tay). Geoid - Là mặt nước biển trung bình yên tĩnh xuyên qua các lục địa và hải đảo. Ta tưởng tượng trái đất có nước chiếm >70% diện tích, nếu cho toàn bộ trái đất bị nước bao phủ thì mặt nước biển trung bình đó chính là Geoid. Geoid dùng để xác định độ cao các điểm trên bề mặt trái đất. Độ cao của 1 điểm là khoảng cách theo phương dây dọi từ điểm đó đến mặt geoid. WGS 84 – Là hệ thống tọa độ do Bộ Quốc Phòng Mỹ tìm ra năm 1984. Đây là kiểu mô hình ứng dụng toàn cầu dạng elip tròn xoay được sử dụng đo tọa độ trên bề mặt trái đất, nó mô hình gần như chính xác hình dạng trái đất theo dạng Geoid (bề mặt trái đất xấp xỉ theo mực nước biển trung bình). Ngoài ra còn một số mô hình dạng elip tròn xoay khác cũng được sử dụng rộng rãi, đặc biệt là trong tính toán, đo đạc vị trí địa lý trong Geoid khu vực như: Airy (1830) sử dụng ở Anh, International 1924 sử dụng tại Châu Âu, Clarke (1880) ở Ấn Độ, and GRS-67 ở Nam Mỹ, tại Mỹ (NAD83) và Úc sử dụng GRS-80. Mỗi loại elip tròn xoay được thiết kế và xây dựng cho các loại dữ liệu đặc trưng cho từng khu vực và lãnh thổ địa lý trên trái đất. Các thông số của elip tròn xoay bao gồm ™ Kích thước bán trục dài – a Đề 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


84

™ Kích thước bán trục ngắn – b ™ Độ dẹt – f Bảng thông số các elip tròn xoay: Ellipsoid Bán trục dài–a (m) Bán trục ngắn – b(m) Độ dẹt - f WGS-84 a=6 378 137 (±2 ) b=6 356 752.3142 f = 1 / 298.257223563 GRS-80 a =6 378 137 b=6 356 752.3141 f = 1 / 298.257222101 Airy (1830) a=6 377 563.396 b = 6 356 256.909 f = 1 / 299.3249646 Int’l 1924 a =6 378 388 b = 6 356 911.946 f = 1 / 297 Clarke  (1880)  a=6 378 249.145 b = 6 356 514.86955 f = 1 / 293.465 GRS‐67  a = 6 378 160 b = 6 356 774.719 f = 1 / 298.25 Hình 31: Thông số các hệ tọa độ elip tròn xoay Có thể coi các Elip tròn xoay này như các hệ tọa độ tương ứng với từng vùng lãnh thổ trên bề mặt trái đất sử dụng trong công việc đo đạc, tính toán tọa độ cũng như ghi nhận vị trí địa lý của các đối tượng thực trên bề mặt trái đất và mô phỏng nó trên bản đồ. Hiện nay, Việt Nam đang sử dụng hệ tọa độ riêng trên lãnh thổ Việt Nam – Hệ tọa độ quốc gia VN 2000 – Hệ được xây dựng dựa trên nền tảng ellipsoid WGS84 nhưng được định vị lại cho phù hợp lãnh thổ Việt Nam (vẫn là ellipsoid WGS84 nhưng được di dời và xoay 1 khoảng rất nhỏ). Tuy nhiên điều này đang gây ra những trở ngại trong việc tích hợp các bản đồ Việt Nam với hệ thống bản đồ chung của thế giới và quá trình sử dụng các thiết bị đo Đề 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


85

đạc hiện đại nhập ngoại trợ giúp quá trình khảo sát địa lý trên lãnh thổ Việt Nam cũng gặp nhiều khó khăn. Với sự phát triển của các công cụ bản đồ vệ tinh rất phổ biến hiện nay như Google Earth, việc xác định vị trí địa lý tại mọi vị trí trên trái đất với bất kỳ công dân nào trở nên dễ dàng hơn bao giờ hết, do đó yếu tố bảo mật tọa độ trong lãnh thổ quốc gia đã trở nên không cần thiết. Năm 2002, Bộ Tài nguyên và môi trường đã có quyết định về hệ thống tham số tính chuyển giữa Hệ tọa độ quốc tế WGS-84 và Hệ tọa độ quốc gia VN-2000. Trong đó đã quy định hệ thống tham số chuyển hệ tọa độ như sau: ™ Tham số dịch chuyển gốc tọa độ: -191,90441429 m; -39,30318279 m; - 111,45032835m. ™ Góc xoay trục tọa độ: -0,00928836”; 0,01975479”; -0,00427372”. ™ Hệ số tỷ lệ chiều dài: k = 1,0000002529062 78. 2.2 Thuật toán Vincenty Thuật toán Vincenty thể hiện nhiều ưu điểm trong việc tính toán khoảng cách địa lý do ưu thế về độ chính xác khá cao. Tuy nhiên, việc triển khai thuật toán này là khác phức tạp, bao gồm nhiều phép toán trung gian và các vòng lặp lồng nhau, do đó đề tài không đi sâu vào nghiên cứu và phân tích chi tiết thuật toán Vincenty. Trong giới hạn nghiên cứu của luận văn, tác giả chỉ dừng ở mức tham khảo giả mã của thuật toán với tính chất tra cứu khi cần sử dụng. 2.2.1 Cài đặt thuật toán Vincenty sử dụng hệ tọa độ ellipsoid WGS - 84 Dưới đây là đoạn mã JavaScript thực hiện thuật toán Vincenty sử dụng các thông số tính toán của hệ tọa độ WGS-84 /* Tính toán khoảng cách địa lý giữa hai điểm có tọa độ (kinh độ, vĩ độ) cho trước (ở dạng độ thập phân) sử dụng công thức Vincenty cho trái đất dạng elip tròn xoay*/ function distVincenty(lat1, lon1, lat2, lon2) { var a = 6378137, b = 6356752.3142, f = 1/298.257223563; /* WGS-84 ellipsiod */ Đề 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


86

var L = (lon2-lon1).toRad(); var U1 = Math.atan((1-f) * Math.tan(lat1.toRad())); var U2 = Math.atan((1-f) * Math.tan(lat2.toRad())); var sinU1 = Math.sin(U1), cosU1 = Math.cos(U1); var sinU2 = Math.sin(U2), cosU2 = Math.cos(U2); var lambda = L, lambdaP = 2 * Math.PI; var iterLimit = 20; while (Math.abs(lambda-lambdaP) > 1e-12 && --iterLimit>0) { var sinLambda = Math.sin(lambda), cosLambda = Math.cos(lambda); var sinSigma = Math.sqrt (( cosU2 * sinLambda) * (cosU2 * sinLambda) + (cosU1 * sinU2 - sinU1 * cosU2 * cosLambda) * (cosU1 * sinU2 - sinU1 * cosU2 * cosLambda ) ); if (sinSigma==0) return 0; // co-incident points var cosSigma = sinU1 * sinU2 + cosU1 * cosU2 * cosLambda; var sigma = Math.atan2(sinSigma, cosSigma); var sinAlpha = cosU1 * cosU2 * sinLambda / sinSigma; var cosSqAlpha = 1 – sinAlpha * sinAlpha; var cos2SigmaM = cosSigma – 2 * sinU1 * sinU2/cosSqAlpha; if (isNaN(cos2SigmaM)) cos2SigmaM = 0; /* equatorial line: cosSqAlpha = 0 */ var C = f/16 * cosSqAlpha * (4 + f * (4 – 3 * cosSqAlpha)); lambdaP = lambda; lambda = L + (1 - C) * f * sinAlpha * (sigma + C * sinSigma * ( cos2SigmaM + C * cosSigma * ( 1 + 2 * cos2SigmaM * cos2SigmaM ) ) ); Đề 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


87

} if (iterLimit==0) return NaN // formula failed to converge var uSq = cosSqAlpha * (a*a - b*b) / (b*b); var A = 1 + uSq/16384 * (4096 + uSq * (-768 + uSq * (320 - 175 * uSq))); var B = uSq/1024 * (256 + uSq * (-128 + uSq * (74 – 47 * uSq))); var deltaSigma = B * sinSigma* (cos2SigmaM + B/4 * (cosSigma * (- 1 + 2 * cos2SigmaM * cos2SigmaM ) - B/6 * cos2SigmaM * ( 3 + 4 * sinSigma * sinSigma ) * ( -3 + 4 * cos2SigmaM * cos2SigmaM) ) ); var s = b * A * (sigma - deltaSigma); s = s.toFixed(3); // round to 1mm precision return s; } Như vậy, với hệ thống tham số chuyển tọa độ đã quy định ở trên, ta hoàn toàn có thể ứng dụng thuật toán Vincenty vào bài toán tính khoảng cách địa lý trên lãnh thổ Việt Nam trong hệ tọa độ VN-2000 tương ứng mà không ảnh hưởng đến độ chính xác của thuật toán cũng như cơ sở hạ tầng bản đồ địa lý đã xây dựng dựa trên VN-2000 của nước ta. 2.2.2 Sử dụng hàm tính toán Vincenty trong truy vấn tìm khoảng cách địa lý Trở lại với ví dụ trong phần 1.2 – Chương 4 về khoảng cách Haversine, ta tính toán khoảng cách giữa hai điểm này theo thuật toán Vincenty và so sánh độ chính xác tính toán của hai phương pháp trên dựa vào đại lượng great- circle distance (khoảng cách vòng cung lý tưởng) - C đã có ở trên. VD1: Hai điểm A & B với kinh độ, vĩ độ tương ứng, tọa độ có dạng độ/phút/giây và hậu tố chỉ một trong bốn hướng địa lý: N-Bắc/S-Nam/E- Đông/W-Tây. A (530 09’ 02’’N; 0010 50’ 40”W) Ù A(53,1560; - 1,84440 ) Đề 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


88

B (520 12’ 17”N; 0000 08’ 26” E) Ù B (52,20470; 0,14060) Với hệ quy đổi: 10 = 60’; 1’ = 60” Ö Ta có dVincenty = AB = 156,067 km Theo trên ta có : dHaversine = AB = 170,2 km & Khoảng cách mặt cầu lý tưởng là C = 105,8 km Dễ dàng nhận thấy với cùng tọa độ điểm, thuật toán Vincenty cho khoảng cách chính xác hơn tuy mất nhiều thời gian tính toán hơn. VD2: Sử dụng thuật toán Vincenty tính toán khoảng cách giữa hai khu vực tại Australia theo hệ tọa độ WGS-84: Khoảng cách giữa trung tâm hai thành phố Flinder Peak và Buninyong, với tọa độ tương ứng là: Flinder Peak (370 57’ 03”S; 1440 25’ 29” E) Buninyong (370 39’ 10” S; 1430 55’ 35” E) ÖdVincenty = 54,959 km Chú ý: Độ chính xác của thuật toán Vincenty còn phụ thuộc rất nhiều vào hệ tọa độ elip tròn xoay mà nó được sử dụng cũng như vị trí địa lý khu vực áp dụng thuật toán, độ chính xác nằm trong khoảng 0.5mm (tương đương sai số tọa độ là 0,00015”) chỉ đúng trên lý thuyết elip, đại lượng sai số này sẽ thay đổi khi áp dụng vào các Geiod (bề mặt cầu xây dựng dựa trên mực nước biển trung bình) trên bề mặt trái đất trong thực tế. Với các vùng lãnh thổ địa lý khác nhau việc sử dụng các hệ tọa độ phù hợp là rất quan trọng, nó quyết định độ chính xác tính toán về khoảng cách của thuật toán Vincenty. Tỉ lệ sai số khác nhau trong từng trường hợp là do sử dụng các geoid khác nhau ( như WGS-84, GRS-80, Airy…. ). Bằng thực nghiệm đã cho thấy, sử dụng thuật toán Vincenty tính khoảng cách tại vị trí địa lý có độ cao so với mặt nước biển trung bình là 2km, sai số tính được khoảng 0,03% (lớn hơn so với khoảng cách thực tế). Giả sử thực hiện đo đạc tại nước Anh sử dụng hệ tọa độ WGS-84, thu được kết quả tính toán của thuật toán Vincenty với sai số là 28m (tương đương 0.003%) – lớn Đề 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


89

hơn khi sử dụng hệ tọa độ elip tròn xoay Airy, là hệ tọa độ được xây dựng phù hợp dựa trên đặc thù địa lý và lãnh thổ nước Anh. 3. Đánh giá thuật toán Haversine và Vincenty Với mục đích so sánh độ chính xác và đánh giá hiệu năng của hai thuật toán Haversine và Vincenty, ta sử dụng lại tọa độ các điểm trong truy vấn tại mục 1.2 Chương 4 – (đã dùng để tính toán khoảng cách trong công thức Haversine) để ứng dụng tính với công thức Vincenty. Ta có bảng thống kê kết quả của phép tính khoảng cách theo tọa độ địa lý theo công thức Haversine và Vincenty như dưới đây: Với tọa độ vị trí hiện tại ghi nhận là - C (200 50’ 30”S; 0030 09’ 21”W) Một số nhà hàng tìm thấy trên bản đồ có vị trí lần lượt là: ™ R1 (200 55’ 00”S; 0030 01’ 30”W) ™ R2 (210 00’ 00”S; 0020 59’ 10”W) ™ R3 (200 55’ 00”S; 0020 59’ 20”W) Khoảng cách d = CRi tương ứng với từng thuật toán như sau: R1 R2 R3 Kinh độ 200 55’ 00”S 210 00’ 00”S 200 55’ 00”S Vĩ độ 0030 01’ 30”W 0020 59’ 10”W 0020 59’ 20”W Dhaversine 15,95 km 24,91 km 19,25 km DVincenty 15,946 km 24,879 km 19,253km Hình 32: Khoảng cách tính theo thuật toán Haversine và Vincenty Nhận xét: ™ Xét về độ chính xác kết quả: Sai số về kết quả tính toán khoảng cách giữa hai thuật toán là 0,35%, tức là chênh lệch vị trí khi dùng hai phương Đề 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


90

pháp này có thể lên đến 3,5km nếu khoảng cách tính toán là trên 950km. Với khoảng cách nhỏ, hai thuật toán thể hiện sai số không chênh lệch nhiều so với thực tế), tuy nhiên thuật toán Vincenty cho kết quả với độ chính xác cao hơn, điều này sẽ là lợi thế khá rõ rệt với kết quả là những khoảng cách lớn (hàng nghìn hoặc hàng vạn km). Trong trường hợp với phương tiện đường bộ như ôto hoặc xe máy, việc tìm kiếm vị trí cần xác định trong khoảng bán kính sai số vài km với thuật toán Haversine thực sự là vấn đề lớn. ™ Xét theo độ phức tạp tính toán: Rõ ràng, để có kết quả tính toán chính xác đến từng mm, thuật toán Vincenty phải triển khai khá phức tạp, qua nhiều phép toán trung gian và các vòng lặp. Do đó, nếu so sánh theo tính đơn giản khi cài đặt, tốc độ truy xuất dữ liệu và thời gian trả lời truy vấn thì thuật toán Haversine lại là lựa chọn tốt hơn. Thuật toán Haversine sử dụng ít phép tính cũng như các toán tử vào ra hơn thuật toán Vincenty rất nhiều. Ö Như vậy, hai thuật toán đề cập trên đây đều có những ưu điểm và nhược điểm nhất định, tùy vào mục đích sử dụng và yêu cầu đối vớp phép toán mà có thể áp dụng loại thuật toán phù hợp. Chú thích [1] Quá trình điều hướng: Là tập hợp các học thuyết trên lý luận cũng như các ứng dụng thực tiễn sử dụng trong tiến trình lập kế hoạch, theo dõi và điều khiển các phương tiện lớn trong ngành hàng hải, hàng không di chuyển trên bề mặt trái đất. [2] Great-circle distance: (Theo wikipedia) Là khoảng cách ngắn nhất giữa hai điểm bất kì trên bề mặt khối cầu tính dọc theo một hướng đi trên bề mặt khối cầu (nghĩa là đo đường đi vòng cung trên bề mặt trái ngược với khoảng cách tính theo đường thẳng nối hai điểm đó qua bên trong khối cầu). Tham khảo thêm tại: [3] Spherical strigonometry - lượng giác cầu: Là một thành phần trong nghành hình học khối cầu ứng dụng trong việc xử lý các đa giác – đặc biệt với tam giác - trên bề mặt cầu và giải thích mối liên quan giữa các góc tương ứng. Đây là một công 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


91

quan trọng dùng tính toán trong ngành thiên văn học, bề mặt trái đất, điều hướng quỹ đạo và không gian) C. KẾT LUẬN 1. Những kết quả đạt được Luận văn trên đây đã trình bày tổng quan các khái niệm từ cơ bản về CSDL không gian, các toán tử, đến các kỹ thuật quan trọng và phức tạp trả lời cho bài toán tính toán gần đúng đối với các truy vấn liên quan đến khoảng cách. Đề tài đã nghiên cứu và trình bày một cách khoa học các kiểu truy vấn tiêu biểu về khoảng cách trong không gian địa lý, thuật toán R-tree dưới dạng một cấu trúc đánh chỉ mục động trong tìm kiếm không gian và các ứng dụng nổi bật liên quan. Ngoài ra, đề tài đã thực hiện nghiên cứu các thuật toán tính toán khoảng Đề 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


92

cách Haversine & Vincenty và ứng dụng thử nghiệm trong một số truy vấn trên không gian địa lý, đánh giá kết quả, độ chính xác sai số trong từng thuật toán và rút ra kết luận về hiệu năng thực thi đối với hệ thống xử lý truy vấn. Dựa vào các đánh giá này đề tài hệ thống lại các vấn đề về tính toán xấp xỉ khoảng cách trong truy vấn trên CSDL không gian, các ứng dụng mới nhất trong thực tế, các sản phẩm công nghệ GIS đang được sử dụng rộng rãi trên thị trường. 2. Đánh giá Các thuật toán tính toán khoảng cách trên CSDL không gian với các đối tượng địa lý dựa trên bề mặt trái đất được đánh giá hiệu năng dựa trên độ chính xác tính toán của thuật toán so với khoảng cách chính xác đo đạc được bên ngoài. Do đó phải tính đến tính chất hình dạng elip dẹt của Trái đất và sự lồi lõm, khúc khuỷa trên bề mặt địa cầu. Như vậy để xây dựng được hàm tính toán với độ chính xác càng cao so với thực tế đòi hỏi độ phức tạp tính toán cũng như số lượng toán tử càng lớn, kéo theo đó là thời gian xử lý đòi hỏi cho hệ thống thực thi thuật toán càng dài. Như vậy, việc cân bằng giữa hai yếu tố là hiệu năng và thời gian đáp ứng của hệ thống là rất quan trọng, nó quyết định đến giá thành sản phẩm, mức độ hoàn thiện và giá trị sử dụng cũng như đáp ứng yêu cầu của người sử dụng. Hiện nay, với sự mở rộng của các ứng dụng GIS trong rất nhiều lĩnh vực bao gồm cả các chương trình quy hoạch tài nguyên, quản lý quy hoạch đô thị, hạ tầng cơ sở quốc gia và khu vực…, việc lựa chọn các phương tiện trợ giúp việc lập quyết định cũng như làm nền tảng xây dựng các mô hình ứng dụng đa phương tiện liên quan đến dò tìm vị trí địa lý, tính toán khoảng cách nằm trong mối quan hệ giữa các đối tượng không gian, luôn là yếu tố quyết định. Chúng ta có thể tìm thấy rất nhiều ứng dụng được xây dựng và cung cấp phục vụ trong quá trình triển khai từ cơ sở dữ liệu không gian đến việc xây dựng các bản đồ kỹ thuật số và tích hợp các phương tiện định vị với các phần mềm quản lý, xử lý dữ liệu không gian. 3. Hướng phát triển Đề 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


93

Ý tưởng khai thác thông tin về tìm đường đi, địa điểm và tính toán khoảng cách ngắn nhất thỏa mãn yêu cầu truy vấn trên nền tảng bản đồ số không phải là mới, hiện nay trên thế giới đã có nhiều tập đoàn lớn khai thác lĩnh vực này như Yahoo, Google, MapQuest… Ở Việt Nam cũng đã có một số công ty đầu tư phát triển sản phẩm trong lĩnh vực này như Dolsoft và các trang web sử dụng bản đồ trực tuyến trong dò tìm địa điểm, quảng cáo, quản lý tài nguyên như của Bộ tài nguyên và môi trường, Công ty bất động sản Basao,… Dữ liệu thông tin địa lý rất phong phú và ngày càng đa dạng cộng với yêu cầu sử dụng thông tin thật nhanh chóng và chính xác từ thị trường dẫn đến việc quản lý, truy xuất khối dữ liệu khổng lồ này luôn là vấn đề tiêu tốn nhiều thời gian và công sức nhằm tối ưu hóa quá trình xử lý của các nhà khoa học công nghệ. Một sản phẩm tốt và toàn diện là sản phẩm vừa xử lý được thông tin một cách khoa học, vừa có khả năng thực hiện các truy vấn nhanh chóng và chính xác. TÀI LIỆU THAM KHẢO Tài liệu tiếng Anh [1] [Beckmann et al. 1990] Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger - “The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles”. SIGMOD Conference 1990: pp 322-331. [2] Calculate distance, bearing and more between two Latitude/Longitude Đề 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


94

points, [3] E.Miglierina, E. Molho, F. Patrone, S.H. Tijs – “An axiomatic approach to approximate olutions in vector optimization” - 2005/10, tr. 3-27 [4] Gutman A (1984) – “R-Trees: A Dynamic Index Structure For Spatial Searching” - Proceedings of the ACM SIGMOD Conference, pp 44-57 [5] [6] Kamel I, Faloutsos C (1994) Hilbert - “R-tree: An Improved R-Tree Using Fractals” - Proceedings of the VLDB Conference, pp 144-155 [7] Oliver Günther, Hans-Jörg Schek – “Advances in Spatial Databases, Second International Symposium” - SSD'91, Zürich, Switzerland, August 28-30, 1991, Proceedings Springer 1991, pp 144-160 [8] Qingxiu Shi and Bradford G.Nickerson www.cs.unb.ca/html/documents/TR06-179.pdf - “Decreasing Radius K-Nearest Neighbor Search using Mapping-based Indexing Schemes” - May 17 , 2006 [9] Ralf Hartmut Güting Fernuniversität Hagen Praktische – “Spatial Database Systems- Tutorial Notes” - Informatik IV D-58084 Hagen-Germany, pp 2-41 [10] Roger Weber, Hans-Jörg Schek, Stephen Blott – “A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces” - VLDB 1998: pp 194-205. [11] Rutovitz, D., 1968. Data structures for operations on digital images. In: Cheng, G.C., Pollock, D.K., Rosenfeld, A. (Eds.), Pictorial Pattern Recognition. Thompson, Washington, pp. 105-133. [12] Samet H (1990) The Design and Analysis of Spatial Data Structures. Addison-Wesley Publishing Company Inc. [13] Vincenty formula for distance between two Latitude/Longitude Đề 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


95

points, Movable-type.co.uk, retrieved 29 Dec 2006. [14] Yannis Manolopoulos, Apostolos N. Papadopoulos and Michael Gr. Vassilakopoulos, Editors - “Spatial databases : technologies, techniques and trends” - Idea Group Publishing (an imprint of Idea Group Inc.) 2004, pp.147 – 168. [15] Yannis Theodoridis - Department of Informatics, University of Piraeus, GR-18534 Piraeus - “Ten Benchmark Database Queries for Location-based Services” - The Computer Journal, British Computer Society 2003, pp.713 -723. [16] Yasushi Sakurai, Masatoshi Yoshikawa, Shunsuke Uemura, and Haruhiko Kojima - "The A-tree: An Index Structure for High- Dimensional Spaces Using Relative Approximation" - in Proc. of the 26th International Conference on Very Large Data Bases (VLDB), pp. 516-526. Tài liệu tiếng Việt [17] ệ_thống_thông_tin_địa_lý [18] 3568 – “Cấu trúc Index động cho tìm kiếm không gian” – Trường ĐH Công nghệ thông tin thành phố Hồ Chí Minh. [19] Lê Văn Trung, Lâm Đạo Nguyên 9f8.dir/doc.pdf - “Giải pháp cập nhật dữ liệu không gian sử dụng công nghệ tích hợp viễn thám và GIS” - Bộ môn Địa Tin Học, Trường Đại học Bách khoa, Tp. Hồ Chí Minh. [20] Ts Đặng Văn Đức – “Hệ thống thông tin địa lý” – Nhà XB Khoa học và kỹ thuật – Hà Nội, 2001. Tr.11-202.