Khóa luậ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

ng cách nhỏ nhấ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


40

giữa chúng là K. Truy vấn 3: Tìm năm shop gần nhất tính từ khu vực tôi đang đứng có bán giày dép đã được lưu trong mục Interest của người sử dụng. SELECT Human.id, Shop.id, Offer.id FROM Human, Shop, Offer WHERE `shoes` in Human.Interests AND Offer.Info = `shoes` AND Offer.Shop_id = Shop.id ORDER BY All_Spatial_Neighbour_Pairs (Shop.Location, curr_space (Human.route)) ASC 5; Với K = 5. Chú ý: ™ Tương tự như với câu truy vấn dạng K-NN, câu lệnh SQL: ORDER BY All_Spatial_Neighbour_Pairs(Shop.Location, curr_space (Human.route)) ASC 5; Cũng được sử dụng để biểu diễn các truy vấn dạng K-CP 1.6 Nối K vùng lân cận gần nhất Nối K vùng lân cận gần nhất - K nearest neighbour join: Bao gồm hai tập dữ liệu không gian và số yếu tố ngưỡng K. Kết quả trả về là tập các cặp đối tượng từ hai tập dữ liệu đầu vào thỏa mãn, với mỗi đối tượng của tập dữ liệu đầu tiên, một cặp được tạo thành với mỗi K vùng lân cận gần nhất của nó trong tập dữ liệu thứ hai. 1.7 Truy vấn K- nối khoảng cách Truy vấn K- nối khoảng cách - K-Multi-way distance join query: Một truy vấn theo dạng này bao gồm n tập dữ liệu không gian, một đồ thị truy vấn (là một đồ thị định hướng có trọng số định nghĩa hành trình có hướng giữa n tập dữ liệu đầu vào) và số yếu tố ngưỡng K. Kết quả trả về là một tập bao gồm K bộ dữ liệu riêng biệt, mỗi bộ có n đối tượng – n-tuples ( bộ dữ liệu chứa n đố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


41

tượng từ n tập dữ liệu thỏa mãn biểu đồ truy vấn). với K giá trị Ddistance nhỏ nhất (Hàm Ddistance là một hàm bậc nhất về khoảng cách với n đối tượng tạo nên n-bộ dữ liệu, chiếu theo các cạnh của đồ thị truy vấn ban đầu). Kết luận Các truy vấn liên quan đến khoảng cách trong CSDL không gian rất hữu ích trong nhiều ứng dụng sử dụng dữ liệu không gian cho việc lập quyết định và nhiều phép toán yêu cầu xừ lý dữ liệu khác. Ví dụ trong trường hợp sử dụng truy vấn cặp gần nhất – K-CPQ, tập dữ liệu đầu tiên có thể biểu diễn các ranh giới về văn hóa của Mỹ, trong khi tập dữ liệu thứ hai có thể bao gồm những địa danh nổi tiếng nhất tại Bắc Mỹ. Kết quả trả về cho loại truy vấn này sẽ bao gồm K cặp gần nhất các thành phố và vùng văn hóa, nó cung cấp một trình tự cho các nhà tổ chức để sắp xếp được lịch trình du lịch hợp lý trong các chuyến tham quan của du khách... Giá trị K ở đây có thể phụ thuộc vào ngân sách mà nhà tổ chức dự định chi trả cho mục đích sử dụng này. Trong giới hạn nghiên cứ của đề tài, chúng ta sẽ chú trọng tìm hiểu hai loại truy vấn là K-NNQ và K-CPQ, qua đó nắm được cách thiết kế các thuật toán xấp xỉ trong các truy vấn liên quan đến khoảng cách. Hình dưới minh họa một tập các điểm trong không gian hai chiều được tổ chức theo cấu trúc R-tree (MBR-based index – Minimum bounding Rectangle- based index -phương pháp đánh chỉ mục dựa trên khung giới hạn nhỏ nhất), mục đích là tìm ba vùng lân cận gần nhất (K = 3 Ù 3-NNQ) với điểm truy vấn q. Dễ thấy kết quả của phép truy vấn 3-NNQ là (p11, p8, p4) Đề 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


42

Hình 15: R-Tree và MBRs trong truy vấn Với ví dụ minh họa dưới đây, ta xét với hai tập điểm 2 chiều khác nhau (tổ chức theo cấu trúc R-Tree, một tập dữ liệu được thể hiện với MBR không tô màu, tập còn lại được thể hiện theo cấu trúc MBR chia sẻ). Nếu ta muốn bao gồm 3 cặp điểm gần nhất (3-CPs) từ hai tập dữ liệu trên thì thu được kết quả là ((p8, q8), (p11, q10), (p4, q6)) Hình 16: R-Tree và truy vấn trong hai cấu trúc MBR khác nhau 2 R – Tree Kỹ thuật Phân nhánh-và-giới hạn (branch-and-bound) đang là một kỹ thuật thành công nhất sử dụng trong việc thiết kế các thuật toán giải quyết các câu hỏi của ngôn ngữ truy vấn trên cấu trúc dạng cây. Hàm chức năng 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


43

hạn thấp hơn và giới hạn cao hơn là nền tảng cơ bản của hiệu năng tính toán trong thuật toán phân nhánh-và-giới hạn. Kỹ thuật giả định cơ bản sử dụng trong các thuật toán truy vấn khoảng cách là các tập dữ liệu không gian được đánh chỉ mục bởi cấu trúc của họ R-Tree. R-Tree và các biến thể của nó được đánh giá là sự lựa chọn hoàn hảo trong việc đánh chỉ mục cho rất nhiều loại dữ liệu không gian (điểm, đoạn thẳng, hình chữ nhật, đa giác…) và vẫn đang được tiếp tục phát triển trong các hệ thống thương mại như Informix và Oracle. 2.1 Khái niệm R-Tree là các cấu trúc cây dữ liệu sử dụng cho dữ liệu không gian đa chiều, có tính chất cân bằng độ cao và có thứ tự, được thiết kế cho thiết bị lưu trữ thứ cấp, và là sự tổng quát hóa của B-tree[3] cho các không gian dữ liệu đa chiều. Chúng được sử dụng để tổ chức động các đối tượng trong không gian d chiều được biểu diễn bởi Đường biên d-chiều tối thiểu (Minimum Bounding d-dimentional hyper-Rectangle – MBR – hoặc khung giới hạn d-chiều nhỏ nhất). Một MBR được xác định bởi hai điểm trong không gian d chiều thuộc bề mặt của nó, một điểm là tọa độ d nhỏ nhất và một điểm là tọa độ d lớn nhất (chúng là các điểm kết thúc của các đường chéo thuộc MBR). Một nút trong cây R-Tree tương ứng với MBR bao gồm cả các nút con của nó. Các lá của cây bao gồm nhiều con trỏ trỏ đến các đối tượng của CSDL thay vì các con trỏ trỏ đến các nút con. Các nút được xử lý giống như các trang nhớ trên đĩ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


44

Hình 17: Ví dụ về R-Tree Hình trên mô tả một số hình chữ nhật ở bên trái và cây R-Tree tương ứng ở phía bên phải. Các đường ba chấm biểu thị khung giới hạn của cây con đã được phát sinh từ nút bên trong. Với các kiểu cấu trúc cây khác như cấu trúc chỉ mục, một chỉ mục của cây R-Tree phân chia không gian đa chiều bằng cách nhóm các đối tượng trong từng loại thứ tự. Một không gian con chứa bởi một nút thuộc cây R-Tree luôn phải nằm trong không gian con của nút cha của nó, đó là đặc tính bao đóng MBR. Theo đặc tính này, một MBR của một nút R-tree (ở bất cứ tầng nào ngoại trừ phía bên trái cây) luôn bao trọn MBR của nút R-tree con cháu của nó. Đặc điểm này của kỹ thuật giới hạn không gian giữa các MBR của các nút trong cây R-tree thường được sử dụng trong thuật toán nối không gian và thuật toán truy vấn liên quan đến khoảng cách. Chú ý rằng MBR – Đường biên tối thiểu - và thuộc tính đi kèm MBR chính là các kỹ thuật xấp xỉ cơ bản. Ở tầng bên trái, một khu vực xấp xỉ MBR được bao phủ bởi các đối tượng nó đi kèm, trong khi tại các tầng bên trong một khu vực xấp xỉ MBR lại được bao phủ bởi các cây con của các nút tương ứng. Một thuộc tính quan trọng khác của R-tree là MBR face property (tạm dịch: thuộc tính bề mặt MBR) – mỗi bề mặt của bất kỳ MBR của mỗi nút R-tree (tại bất kỳ tầng nào) liền kề ít nhất một điểm của một số đối tượng không gian trong CSDL không gian. Đặc điểm này được sử dụng trong các thuật toán truy vấn liên quan đến khoảng cách. Một trong những phiên bản phổ biến và có hiệu năng cao nhất là R* -tree (Beckmann et al.,1990). R* đã bổ sung hai cải tiến lớn vào cấu trúc R-Tree ban đầu trong trường hợp xảy ra việc quá tải các nút trong cây. Đầu tiên, hơn cả việc chỉ tính toán đến các khu vực , thuật toán phân tách nút trong R*-tree còn tối thiểu hóa chu vi và các phần mở rộng nằm gối lên nhau của MBRs. Thứ hai, việc tràn nút không được phân tách ngay lập tức, nhưng các phần chia các mục trong nút được chèn lại từ đầu của cây R*- tree (việc chèn bắt buộc) Corall et al (2000) đã đưa ra một sự tổng quát hóa của các chức năng dùng trong việc tính toán khoảng cách tối thiểu giữa điểm và MBRs (MINMINDIST). Đề 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


45

Giả sử có (A, B) biểu diễn một MBR trong không gian d-chiều, với A = (a1, a2, …, ad) và B = (b1, b2, …, bd) sao cho ai ≤ bi, với 1 ≤ i ≤ d là các điểm kết thúc của một trong những đường chéo chính của nó. Ta có hai MBRs là M1 (A, B) và M2 (C, D), MINMINDIST (M1, M2) được định nghĩa như sau: Chúng ta có thể áp dụng chức năng về khoảng cách này cho một cặp các loại phần tử bất kỳ (MBRs hoặc điểm) lưu trữ trong cấu trúc R-tree trong quá trình tính toán của thuật toán rẽ nhánh và cận nhằm thu nhỏ không gian tìm kiếm. Những đặc tính quan trọng nhất của MINMINDIST: ™ Nếu bất kỳ một hoặc một cặp MBR (dạng chữ nhật) nào suy biến thành một hoặc một cặp điểm, ta phải thu được khoảng cách nhỏ nhất giữa điểm đó và MBR hoặc giữa hai điểm này. ™ Đặc điểm của đường biên cấp thấp hơn: Với mỗi cặp điểm trong không gian đa chiều (p ; q) đi cùng với một cặp MBR tương ứng (Mp; Mq), chứng minh được rằng MINMINDIST (Mp; Mq) ≤ MINMINDIST(p, q). ™ MINMINDIST là một dãy đơn điệu không giảm với các bậc của R-Tree. 2.2 Cấu trúc của một R-tree Một cách tổng quát, R-tree là một cấu trúc chỉ mục cho các đối tượng không gian n-chiều và nó tương tự như B-tree. Cấu trúc chỉ mục này là thực sự linh động, thao tác chèn và xóa có thể kết hợp với phép tìm kiếm và phải tái tổ chức theo chu kỳ. Các nút lá trong cây chứa chỉ mục dẫn đến chúng theo khuôn 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


46

(MBR, object_ptr) - Trong đó object_ptr tham chiếu đến một bộ dữ liệu trong cơ sở dữ liệu và MBR là một rectangle n-chiều chứa các đối tượng không gian nó biểu diễn. Các nút không phải lá có khuôn dạng sau: (MBR, chirld_ptr) - Với chirld_ptr là địa chỉ một nút khác trong cây và MBR bao gồm các rectangle trong các nút thấp hơn. Nói cách khác, không gian MBR chứa mọi đối tượng được đánh chỉ mục trong các cây con có gốc là đầu vào của MBR. Cho M là số lượng tối đa đầu vào có thể vừa đủ với một nút và cho tham số m xác định số lượng tối thiểu đầu vào tại một nút. Một R-tree thỏa mãn các thuộc tính sau: ™ Mỗi một nút chứa số lượng nút con trong khoảng m và M ngoại trừ nút gốc. ™ Đối với mỗi đầu vào dạng (MBR, object_ptr) tại nút lá, MBR là một rectangle nhỏ nhất có chứa đối tượng dữ liệu n-chiều được biểu diễn bởi object_ptr. ™ Mỗi nút không phải nút lá có số lượng nút con trong khoảng m và M ngoại trừ nút gốc. ™ Đối với mỗi đầu vào dạng (MBR, chirld_ptr) tại nút không phải nút lá, MBR là một rectangle nhỏ nhất có chứa rectangle trong chirld node. ™ Nút gốc có ít nhất là 2 nút con ngoại trừ đó là nút lá. ™ Đây là một loại cây cân bằ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


47

Hình 18: Cây biểu diễn R-Tree Hình 19: Biểu diễn hai chiều của một R-Tree 2.3 Thuật toán R-Tree R-tree là một cây cân bằng tương tự như B-tree. Ý tưởng như sau: Các index sẽ nằm tại các nút lá chứa các điểm dữ liệu, khi đó việc tìm kiếm không gian sẽ thực hiện trên một số lượng nhỏ các nút. Một cơ sở dữ liệu không gian bao gồm tập hợp của các bộ đại diện cho các đối tượng trong không gian, mỗi bộ có một nhận biết duy nhất ,ta cóthể dùng nhận biết này để truy xuất nó. Các node lá trong R-Tree chứa các đầu vào mẫu tin chỉ mục (index record entries) (I, tuple-identifier [4]) với tuple- identifier (nhận dạng bộ dữ liệu) tham khảo đến một bộ trong cơ sở dữ liệu và I là hình chữ nhật n chiều, hình này là khung giới hạn nhỏ nhất - MBR của các index đối tượng 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


48

I = (I0, I1,… In). n - số chiều không gian Ii - một khoảng biên khép kín [a,b], mô tả phạm vi của đối tượng cùng với chiều i. Một node không phải là node lá chứa các entry như sau (I, child-pointer), child-point là địa chỉ của node thấp hơn trong R-Tree và I bao phủ tất cả các hình chữ nhật trong các entry của các node thấp hơn. Hình 20: Cấu trúc một R-Tree Đề 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


49

Hình 21: Các quan hệ có thể có giữa các MBR (chứa trong, chồng lấn…) 2.3.1 Tìm kiếm trong cấu trúc dữ liệu tổ chức dưới dạng R-Tree Tìm kiếm Thuật toán tìm kiếm duyệt cây từ gốc (root) đi xuống theo cách tương tự như B-tree. Tuy nhiên khi thăm một node sẽ có nhiều hơn một cây con dưới node đó cần được tìm kiếm, vì lý do đó thuật toán không thể bảo đảm thực hiện tốt trong các trường hợp xấu nhất. Tuy nhiên với nhiều kiểu của dữ liệu thuật toán cập nhật sẽ duy trì hình dạng của cây cho phép thuật toán tìm kiếm loại đi các vùng không liên quan của không gian được đánh chỉ mục, và kiểm tra duy nhất dữ liệu gần vùng tìm kiếm. Chúng ta sẽ biểu diễn phần hình chữ nhật của một chỉ mục E là EI, và phần nhận dạng dữ liệu hay child-pointer là Ep. Thuật toán tìm kiếm: Cho R-tree có root là T, tìm tất cả các mẫu tin chỉ mục mà có các hình chữ nhật chồng lên một hình chữ nhật cần tìm S. ™ S1 [Tìm kiếm trên cây con] Nếu T là một node lá, kiểm tra mỗi mục E để xác định xem Ei có trùng lên S hay không. Với tất cả các mục trùng nhau, thực hiện tìm kiếm trên cây mà node root của nó được chỉ bởi Ep. ™ S2 [Tìm kiếm trên node lá] NếuT là một lá, kiểm tra tất cả các mục E để xác định EI có trùng lên S hay không. Nếu trùng E là một record đủ tiêu chuấn. 2.3.1.1 Chèn (Insertion) Việc thêm các index cho các bộ dữ liệu mới giống như thêm trong B-tree là các index mới được thêm vào cho các lá, các node chứa quá số lượng sẽ bị Đề 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


50

tách ra và quá trình tách này sẽ lan truyền lên phía trên cây. Thuật toán Chèn (Insert): Thêm một mục nhập chỉmục mới E vào trong R-tree ™ I1: [Tìm vị trí cho dữ liệu mới] dùng thuật toán chọn lá (ChooseLeaf) để chọn một node lá L để thêm E. ™ I2: [Thêm dữ liệu cho node lá] nếu L có chỗ cho một entry khác, thêm E nếu không thì dùng thuật toán chia node (SplitNode) đểcó được L và LL chứa E và tất cả các mục nhập của L. ™ I3: [Lan truyền các thay đổi lên phía trên] Dùng thuật toán điều chỉnh cây (AdjustTree) trên L, đồng thời bỏ qua LL nếu việc phân chia đã được thực hiện. ™ I4: [Tăng trưởng cây] Nếu việc phân chia node lan truyền làm cho root phân chia, tạo ra một root mới, mà con của root mới này là 2 node kết quả. 2.3.1.2 Thuật toán Chọn lá (ChooseLeaf): Chọn một node lá mà node lá này đặt một chỉ mục mới E. ™ CL1: [Khởi tạo] cho tập N là node root. ™ CL2: [Kiểm tra lá] Nếu N là một lá, trả về N. ™ CL3: [Chọn cây con] Nếu N không phải là một lá, cho F là entry trong N mà các hình chữ nhật của nó FI cần mở rộng lá để tính EI. Giải quyết các hạn chế bằng cách chọn entry với hình chữ nhật có diện tích nhỏ nhất. ™ CL4: [Đi xuống cho đến khi một node lá được tìm thấy] tập N là node con được chỉ đến bởi Fp và lặp lại từ CL2. 2.3.1.3 Thuật toán điều chỉnh cây (AdjustTree): Đi lên từ một node lá L đến root, điều chỉnh hình chữ nhật bao phủ và lan truyền phân chia các node chia khi cần thiế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


51

™ AT1: [Khởi tạo] cho tập N=L, nếu L đã được phân chia trước đó, tập NN là kết quả của node thứ hai . ™ AT2: [Kiểm tra nếu thực hiện] Nếu N là root, ngưng. ™ AT3: [Điều chỉnh vùng phủ hình chữ nhật trong mục nhập cha] Cho P là node cha của N và cho EN là các entry của N trong P. Điều chỉnh EN I để cho nó bao sát xung quanh tất cả các hình chữ nhật entry trong N. ™ AT4: [Lan truyền node bị tách lên phía trên] Nếu N có NN (partner) kết quả từ một phân chia mới nhất, tạo một entry mới ENN P trỏ đến NN và ENN I bao quanh tất cả các hình chữ nhật trong NN, thêm ENN vào P nếu có chỗ. Nếu không dùng SplitNode đểtạo ra P và PP chứa ENN và tất cả các entry của P. ™ AT5: [Di chuyển đến mức kết tiếp]. Cho tập N=P và tập NN=PP nếu có sự phân chia xảy ra. Lặp lại bước AT2. 2.3.2 Xóa (Deletion) Thuật toán xóa Thay đổi vị trí index của record E từ R-tree ™ D1: [Tìm node chứa record] thực hiện thuật toán FindLeaf để xác định vị trí node lá L chứa E. Ngưng nếu record được tìm thấy. ™ D2: [Xóa record] Xóa E từ L. ™ D3: [Lan truyền thay đổi] dùng thuật toán CondenseTree bỏ qua L. ™ D4: [Rút ngắn cây] Nếu root có duy nhất một con sau khi cây đã được điều chỉnh, tạo con cho root mới. 2.3.2.1 Thuật toán tìm lá (FindLeaf): Cho R-tree có root là T, tìm node lá chứa đầu vài chỉ mục E. ™ FL1: [Tìm cây con] nếu T không phải là node lá, kiểm tra mỗi entry F trong T để xác định, nếu FI chồng lấp với EI. Với mỗi entry thực hiện thuật toán FindLeaf trên cây mà root của nó được trỏ đến bởi Fp cho đế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


52

khi E được tìm thấy hay tất cả các entry đã được kiểm tra. ™ FL2: [Tìm node lá cho mục cho record] Nếu T là lá, kiểm tra mỗi entry để xem nếu nó phù hợp với E, nếu E được tìm thấy trả về T. 2.3.2.2 Thuật toán Gom cây (CondenseTree): Cho một node lá L, mộtentry được xóa từ node lá này, loại ra node này nếu nó có quá ít các chỉ mục và xây dựng lại các entry của nó. Lan truyền việc loại node này lên trên khi cần thiết. Điều chỉnh các hình chữ nhậtbao phủ trên đường dẫn đến root, làm cho các hình chữ nhật này nhỏ hơn nếu có thể. ™ CT1: [khởi tạo] cho tập N=L, tập Q là tập của các node bịloạibỏ, Q là tập rổng. ™ CT2: [Tìm entry cha] nếu N và root, nhảy tới bước CT6. Nếu không thì cho P là cha của N, và cho EN là các entry của N trong P. ™ CT3: [Loạinode không đủ(Eliminate under-full node)] Nếu N có ít hơn m entry, xóa EN khỏi P và thêm N vào tập Q. ™ CT4: [Điều chỉnh hình chữ nhật bao phủ] Nếu N không bị loại bỏ, điều chỉnh EN I để chứa sát lại các entry trong N. ™ CT5: [Di chuyển lên trên mộtmức trong cây] Cho tập N=P và lặp lại từ CT2. ™ CT6: [Chèn lại các entry bị mồi côi (Re-insert orphaned entries)] Chèn lại vào tất cà các entry của các node trong tập Q. Các entry từ các node lá bị loại bỏ được chèn lại vào trong các lá của cây như đã được mô tả trong thuật toán Insert, nhưng các entry từ các node có mức cao hơn phải được đặt cao hơn trong cây, vì vậy các lá của các cây con phụ thuộc vào chúng sẽ nằm trên cùng mức như các lá của cây mẹ. 2.3.3 Cập nhật Nếu một bộ dữ liệu được cập nhật để cho hình chữ nhật bao phủ nó bị thay đổi, bản ghi chỉ mục của nó phải bị xóa, cập nhật và chèn lại, vì vậy nó sẽ phả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


53

tìm cách để đặt đúng vị trí trong cây. Một cách tìm kiếm khác so với cách được mô tả ở trên có thể hữu ích hơn, ví dụ để tìm tất cả các đối tượng dữ liệu được chứa hoàn toàn trong một vùng tìm kiếm, hoặc tất cả các đối tượng chứa vùng tìm kiếm. Các bước thực hiện có thể được thực hiện bằng các biến đổi dễ hiểu trên thuật toán đã cho. Tìm một entry cụ thể mà nhận dạng của nó đã được biết trước cần đến thuật toán xóa và được thực hiện bằng thuật toán FindLeaf. Các biến đổi của phạm vi xóa, trong phạm vi này, tất cả các đối tượng dữliệu trên diện tích liên quan được xóa đi, cũng được R-tree cung cấp khá tốt. 2.3.3.1 Thuật toán tách node (Node Splitting) Để thêm một một entry mới để một node đầy chứa M các chỉ mục, cần phải phân chia tập hợp của M+1 các entry thành hai node. Sự phân chia nên được thực hiện theo cách làm cho nó không chắc có thể thực hiện được việc phân chia cả hai node mới sẽ cần được kiểm tra trên việc tìm kiếm thứ tự. Khi đó sự quyết định thăm một node phụ thuộc vào hình chữ nhật bao phủ nó có chồng lên diện tích tìm kiếm. Tổng số diện tích của hai hình chữ nhật bao phủ sau khi tách có thể được giảm đến mức tối thiểu. Hình dưới đây minh họa điều này. Diện tích của các hình chữ nhật trong trường hợp “bad split”lớn hơn nhiều so với trường hợp “good split”. Hình 22: Trường hợp phân chia node Cùng tiêu chuẩn đã được dùng trong thủ tục ChooseLeaf để quyết định xem nơi nào có thể chèn một chỉ mục mới vào tại mỗi mức trong cây, cây con được chọn là một cây mà hình chữ nhật bao phủ của nó phải được mở rộng ít Good Bad split Đề 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


54

nhất khi chèn chỉ mục mới vào. Chúng ta quay lại thuật toán phân chia tập M+1 entry thành hai nhóm cho mỗi node mới. Hình 23: Phân chia entry thành các nhóm node mới Thuật toán A Quadractic-Cost Thuật toán này cố gắng tìm một vùng được tách ra có diện tích nhỏ, nhưng không bảo đảm là có thể tìm được một vùng có thể có diện tích nhỏ nhất. Chi phí là bậc hai theo M và tuyến tính theo số lượng của các chiều. Thuật toán chọn hai trong M+1 entry làm phần tử đầu tiên của hai nhóm mới bằng cách chọn hai entry này, hai entry này có thể làm lãng phí diện tích lớn nhất nếu cả hai được đặt trong cùng một nhóm. Như vậy diện tích hình chữ nhật bao phủ cả hai entry, trừ đi diện tích của chính các entry, sẽ là lớn nhất. Các entry còn lại được gán vào các nhóm cùng lúc. Tại mỗi bước, việc mở rộng diện tích đòi hỏi phải thêm mỗi entry còn lạicho mỗi nhóm được tính toán, và entry được gán thì sẽ xuất hiện một sự khác biệt lớn nhất giữa hai nhóm. Thuật toán Quadratic Split Phân chia một tập M+1 các chỉ mục thành hai nhóm. ™ QS1: [chọn entry đầu tiên cho mỗi nhóm] Áp dụng thuật toán PickSeeds để chọn hai entry làm các phần tử đầu tiên của các nhóm. Gán mỗi entry cho một nhóm. ™ QS2: [Kiểm tra nếu đã thực hiện] Nếu tất cả các entry đã được gán, ngưng. Nếu một nhóm có một vài entry mà tất cả những entry còn lạ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


55

phải được gán vào nó theo thứ tự để cho nhóm này có m nhỏ nhất, gán các entry và ngưng. ™ QS3: [Chọn entry để gán] Thực hiện thuật toán PickNext để chọn entry kế tiếp để gán. Thêm entry này vào nhóm mà hình chử nhật bao phủcủa nó sẽ phải mở rộng ít nhất để chứa entry này. Giải quyết các hạn chế bằng cách thêm entry vào nhóm có diện tích nhỏ nhất, khi đó nhóm này có các entry ít hơn nhóm khác. Lặp lại QS2. Thuật toán PickSeeds Chọn hai entry làm phần tử đầu tiên của các nhóm. ™ PS1: [Tính toán sự thiếu hiệu quảcủa việc nhóm các entry với nhau] Cho mỗi cặp các entry E1 và E2 , tạo một hình chữ nhật J bao gồm E1I và E2I Tính d = area(J) – area (E1I) - area(E2I). ™ PS2: [Chọn cặp gây lãng phí nhất] Chọn cặp có d lớn nhất. Thuật toán PickNext Chọn một mục còn lại để phân loại vào một nhóm. ™ PN1: [Xác định giá trị của việc đặt mỗi entry trong mỗi nhóm] Cho mỗi entry E chưa được phân nhóm, tính d1 = diện tích được yêu cầu tăng trong hình chữ nhật bao phủ của nhóm 1 để bao gồm EI, tính toán d2 tương tự như trên cho nhóm 2. ™ PN2: [Tìm entry thích hợp nhất cho một nhóm] Chọn bất kỳ entry nào có sự khác biệt lớn nhất giữa d1 và d2. Thuật toán LinearPickSeeds Chọn hai entry làm các phần tử đầu tiên của các nhóm. ™ LPS1: [Tìm các hình chữ nhật xa nhất theo tất cả các chiều] Theo mỗi chiều, tìm các entry mà hình chữ nhật của nó có cạnh dưới cao nhất và có cạnh trên thấp nhất. Ghi lại việc phân chia. ™ LPS2: [Điều chỉnh hình dạng của cụm hình chữ nhật] Chuẩn hóa việc phân chia bằng cách chia chiều rộng của toàn bộ các tập theo chiều Đề 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


56

tương ứng. ™ LPS3: [Chọn cặp cách xa nhất] Chọn cặp có sự phân chia được chuẩn hóa lớn nhất theo bất kỳ chiều nào. Trên đây đề tài đã trình bày thuật toán R-tree, chúng ta có thể áp dụng phương pháp này để tạo index cho cụm. Ta xem các cụm như là các không gian mà chúng ta cần truy xuất, các vùng dữ liệu của cụm sẽ được phân chia để nằm trong các hình chữ nhật nhỏ (không gian 2 chiều), ta sẽ có các hình chữ nhật lớn hơn bao ngoài các hình chữ nhật nhỏ chứa dữ liệu này áp dụng R-tree để tạo cây, khi đó nếu cần truy xuất một vùng dữ liệu nào đó trong cụm ta sẽ dùng thuật toán tìm để xác định địa chỉ vùng dữ liệu này đang nằm ở lá nào trong cây hay nói cách khác là lá nào đang chứa thông tin về vị trí của vùng dữ liệu mà ta đang cần, khi biết các thông tin vềvịtrí trong không gian của vùng dữ liệu đang tìm ta sẽ truy xuất đến rất nhanh cụm dữ liệu này. Như vậy từ nếu tạo được index cho cụm thì việc tìm kiếm tương tự sẽ đư