Tóm tắt Luận án Phương pháp đánh chỉ số cho tài liệu xml tin sinh học dựa trên R - Tree

ối hình chữ nhật biên tối thiểu chứa dữ liệu (Minimum Bounding Rectangle – MBR). Chính các MBR được lưu trữ trên cấu trúc cây chứ không phải bản thân dữ liệu (như là metadata), khi đó việc tìm kiếm dữ liệu sẽ thực hiện trên các node. 1.4.2. Cấu trúc R-tree Một cách tổng quát, R-tree là một cấu trúc chỉ số cho các đối tượng không gian n-chiều và nó tương tự như B-tree. Các node lá trong cây chứa chỉ số vì vậy chúng có khuôn dạng: (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 hình chữ nhật n-chiều chứa các đối tượng không gian nó thể hiện. Các node không là lá có khuôn dạng: (MBR, chirld_ptr) - trong đó chirld_ptr là địa chỉ một node khác trong 6 cây và MBR bao gồm các hình chữ nhật trong các node thấp hơn. Một R-tree thỏa mãn các thuộc tính sau: - Mỗi một node chứa số lượng node con trong khoảng m và M ngoại trừ node gốc. - Đối với mỗi đầu vào dạng (MBR, object_ptr) tại node lá, MBR là một hình chữ nhật nhỏ nhất có chứa đối tượng dữ liệu n-chiều được biểu diễn bởi object_ptr. - Đối với mỗi đầu vào dạng (MBR, chirld_ptr) tại node không phải lá, MBR là một hình chữ nhật nhỏ nhất có chứa hình chữ nhật trong chirld node. - Node gốc có ít nhất là 2 node con ngoại trừ đó là node lá. - Đây là một loại cây cân bằng. 1.4.3. Một số thuật toán cơ bản trong phƣơng pháp R-tree [30] a) Tìm kiếm trong cấu trúc dữ liệu tổ chức dưới dạng R-tree b) Chèn (Insertion) c) . 1.4.4. Một số phƣơng pháp cải tiến  XR-tree [32]  AR*-tree [87] 1.5. Các vấn đề còn tồn tại Mô hình trong Hình 1.1, giúp dữ liệu XML được chuyển đổi về không gian đa chiều, từ đó áp dụng các phương pháp đánh chỉ số và truy vấn trong không gian giúp tăng tốc độ xử lý và giảm kích thước dữ liệu khi đánh chỉ số. Vì XML tin sinh học trên thực tế rất đa dạng nên R-tree sẽ phù hợp hơn và được lựa chọn làm cơ sở trong luận án này. Hình 1.1: Mô hình tổng quát Hình 1.2: Mô hình thể hiện quá trình chuyển đổi dữ liệu và đánh chỉ số trên đĩa cứng Phương pháp R-tree hiện còn một số vấn đề khi áp dụng vào xử lý dữ liệu XML tin sinh học như sau: 1) Vấn đề chồng chéo trong truy vấn. Đối với kỹ thuật chỉ số dựa trên không gian, không gian tìm kiếm càng lớn thì càng mất nhiều thời gian hơn để nhận được node được trả về. Nhưng điểm yếu của phương pháp dựa trên R-tree là các truy vấn đòi hỏi cửa sổ quét dữ liệu khá lớn, do đó ảnh hưởng đáng kể tới hiệu năng truy vấn. 2) Vấn đề mối liên kết anh em của các tag sau khi chuyển đổi sang không gian, mà được thể hiện như các điểm trong không gian như parent, preceding, sibling, descendant, child, 7 following, v.v theo các trục Xpath. Trong Hình 2.2 biểu diễn việc phân bố dữ liệu trên hệ trục tọa độ, tác giả nhận ra rằng tất cả các dữ liệu phân bố lệch như một hình thang/được chéo thẳng hàng (giống như cánh máy bay). Trong khi đó, tất cả các phương pháp trước đây không quan tâm đến điều đó, nên các truy vấn chưa có cải thiện đáng kể nào khi truy vấn ở vùng dữ liệu cánh máy bay này. 1.6. Kết luận Chương 1 trình bày một số khái niệm nền tảng về tin sinh học và dữ liệu tin sinh học. Dữ liệu tin sinh học ngày càng trở nên khổng lồ do được đóng góp và chia sẻ thường xuyên của cộng đồng nghiên cứu. Do các bài toán phân tích dữ liệu tin sinh học rất đa dạng, các tài liệu lưu trữ thông tin cần cấu trúc dễ thay đổi, linh hoạt, đa dạng và đặc biệt dễ chia sẻ/đóng góp. Hiện nay, tài liệu XML là một chuẩn quan trọng để mô tả và lưu trữ dữ liệu sinh tin học khổng lồ. Tuy nhiên, tài liệu XML có dữ liệu dạng text và bán cấu trúc nên việc khai thác không giống như dữ liệu thông thường. Chương 1 cũng trình bày các nghiên cứu liên quan của bài toán khai thác dữ liệu XML, các phương pháp đánh chỉ số, các thuật toán được đề xuất trong các nghiên cứu trước đây đã được nêu ra, trong đó R-tree đang là thuật toán tỏ ra hiệu quả với các tài liệu XML và truy vấn Xpath. Trên cơ sở đó, chương 1 phân tích và đưa ra các vấn đề nghiên cứu của luận án. Chƣơng 2. PHƢƠNG PHÁP ĐÁNH CHỈ SỐ BIOX-TREE 2.1. Mở đầu Các phương pháp đưa ra ở trên trong việc đánh chỉ số trong không gian dựa trên R-tree đang gặp các vấn đề: Thứ nhất, đó là vấn đề chồng chéo. Đối với kỹ thuật chỉ số dựa trên không gian, không gian tìm kiếm càng lớn thì càng mất nhiều thời gian hơn để nhận được node được trả về. Nhưng điểm yếu của phương pháp dựa trên R-tree là chúng tạo ra một cửa sổ truy vấn chưa tối ưu. Hình 2.1 minh họa một thể hiện của tài liệu XML với một số điểm nhỏ biểu thị dữ liệu XML theo mặt phẳng. Giả sử rằng, từ node bối cảnh E, chúng ta muốn lấy tất cả các node con cháu của nó bằng cách sử dụng cửa sổ truy vấn {pre(E), ; 0, post(E)} [36]. Cửa sổ thực sự cần thiết để tìm kiếm là màu trắng được xác định bởi giá trị duyệt cây theo giá trị trước của node con cháu bên trái và giá trị duyệt cây theo giá trị sau của node con cháu bên phải của node E. Kết quả là, phạm vi thừa được đánh dấu màu xám trong cửa sổ truy vấn tương ứng với trục con cháu sẽ gây ra ảnh hưởng đáng kể đến hiệu suất thực hiện các truy vấn, mà phạm vi này lại có thể rất lớn trong nhiều trường hợp. Hình 2.1: Phạm vi quét thứ tự duyệt cây theo giá trị trước và sau ban đầu (vùng xám) và thu nhỏ (vùng trắng) cho truy vấn con cháu được thực hiện theo truy vấn mẫu 8 Thứ hai, đó là vấn đề mối liên kết anh em của các tag sau khi chuyển đổi sang không gian, mà được thể hiện như các điểm trong không gian như parent, preceding, sibling, descendant, child, following, v.v theo các trục Xpath. Trong Hình 2.2 biểu diễn việc phân bố dữ liệu trên hệ trục tọa độ, với dữ liệu DNA gạo kiểm thử trên 1000 node (Hình 2.2a), với dữ liệu Swissprot kiểm thử trên khoảng 20.000 node (Hình 2.2b), tác giả nhận ra rằng tất cả các dữ liệu dữ liệu phân bố lệch như một hình thang/được chéo thẳng hàng (giống như cánh máy bay). Tác giả đã thử nghiệm trên nhiều tài liệu XML khác nhau với từ vài trăm node đến vài trăm nghìn node cũng ra kết quả tương tự. (a) (b) Hình 2.2: Ví dụ về phân phối các điểm quy đổi cho một tài liệu XML Trong khi đó, tất cả các phương pháp trước đây không quan tâm đến điều đó, chúng chỉ tập trung vào xử lý mối quan hệ giữa cha mẹ/con cái hoặc tổ tiên/con cháu và bỏ qua các trục khác mà chúng cũng là phần quan trọng trong xử lý truy vấn, đặc biệt là xử lý luồng truy vấn XPath với các vị từ. Các truy vấn chưa có cải thiện đáng kể nào khi truy vấn ở vùng dữ liệu cánh máy bay này. Từ đó, tác giả đi sâu nghiên cứu phương pháp đánh chỉ số mới, được cải tiến từ R-tree giúp các truy vấn Xpath chạy hiệu quả hơn trong một số trục. Dựa theo mô hình đã lựa chọn trong chương 1, tác giả sẽ có những đề xuất cải tiến trong các thành phần: chuyển đổi, đánh chỉ số, module xử lý truy vấn. Hình 2.3: Các thành phần được đề xuất cải tiến trong phương pháp BioX-tree Các kết quả trong chương này được công bố trong các công trình 1, 2, 3, 4 phần “Danh mục các công trình của tác giả”. 9 2.2. Phƣơng pháp đánh chỉ số cải tiến BioX-tree 2.2.1. Chuyển đổi tài liệu XML Vẫn tuân thủ theo nguyên tắc chung đó trong phân tích và chuyển đổi tài liệu XML, tác giả đã xây dựng một chương trình riêng để thực hiện để đảm bảo độ chính xác khi so sánh với phương pháp dựa trên R-tree của các nghiên cứu trước. Trong tài liệu [20], trình chuyển đổi được triển khai bằng hai thủ tục startEuity (t, a, att) và endEuity (t). Ở đây, tác giả đã thêm một tham số mới theo cách riêng của tác giả để tăng hiệu quả tìm kiếm lên, bên cạnh việc vẫn sử dụng tham số duyệt cây theo giá trị trước và duyệt cây theo giá trị sau. Đó là tham số được sử dụng để chỉ cấp độ l (level) của từng node. Hai thủ tục trên được sửa đổi với tên mới startElement và endElement, trình bày trong Thuật toán 2.1. Thuật toán ConvertXMLDocument(XMLdoc) Đầu vào: tài liệu XML cần chuyển đổi. Đầu ra: file txt chứa các giá trị trên không gian của một node(E) = {pre (E), post (E), par (E), att (E), tag (E)}. Begin l = -1; startElement(t, a, atts) l ← l +1; v ← (pre = gpre, post = _, par = (S.top()).pre, level= l, att = a, tag = t) S.push(v); Gpre ← gpre + 1; for v’ IN atts do startElement(v’, true, nil ); endElement(v’); endElement(t) v ← S.pop(); v.post ← gpost; gpost ← gpost +1; chèn v vào bảng kết quả; l ← l-1; End Thuật toán 2.1: Hai thuật toán sửa đổi trong chuyển đổi tài liệu XML 2.2.2. Cấu trúc chỉ số trên cây BioX-tree BioX-tree áp dụng chiến lược chèn/tách khác nhau để đạt được các mối quan hệ anh em của dữ liệu XML một cách dễ dàng hơn, trong khi không gây ảnh hưởng đến khả năng phân biệt không gian của chỉ số quá nhiều. Tương tự phương pháp Xpath và R-tree nêu trong chương 1, mỗi tag name trong tài liệu XML sau khi chuyển đổi được biểu diễn dưới dạng một entry[30] gồm 5 thuộc tính node(E) = {pre (E), post (E), par (E), att (E), tag (E)}. Một node sẽ có kích thước tương ứng với 1 block trong ổ đĩa cứng. Các node không là lá (non-leaf node) có dạng (pointer, MBR) trong đó con trỏ pointer trỏ đến node con và MBR là một hình chữ nhật nhỏ nhất bao quanh tất cả entry trực thuộc nó. 10 Chúng ta hiểu đơn giản rằng các node không là lá sẽ chứa các thông tin metadata của các node lá, cần biết thông tin về các node lá có thể tìm ở đây. Các node lá (leaf node), đây là nơi chứa các phần tử sau chuyển đổi, chúng có trách nhiệm duy trì các quỹ đạo liên kết của dữ liệu XML thực tế. Để làm điều đó, tác giả áp dụng các phương pháp liên kết đôi để giữ các kết nối với anh em XML ở trước và anh em XML theo sau. Tác giả cũng sử dụng con trỏ để giữ kết nối với cha mẹ của các con XML. Tóm lại, tác giả sử dụng 3 con trỏ trong một node lá để kết nối với anh em ở trước, anh em theo sau và cha mẹ của chúng, nên mỗi node dạng này sẽ có tập các con trỏ có dạng tuple (previouspointer, nextpointer, parpointer). Mục đích là tác giả cố gắng duy trì mối quan hệ phản ánh phân bố dữ liệu hình cánh máy bay trên không gian để làm cho các cửa sổ truy vấn sau này sẽ được thu nhỏ hơn và bắt buộc 1 node trên cây sẽ chỉ chứa các anh chị em của nó giúp chúng ta có thể nhanh chóng tìm ra các mối quan hệ anh em trong BioX-tree. Hình 2.4: Hệ thống cây phân cấp theo các tag trong tài liệu XML DNA gạo Ví dụ, Hình 2.2 mô tả cấu trúc cây của một tài liệu liên quan đến DNA gạo mà tác giả sẽ thử nghiệm trong các phần sau, đây một bộ dữ liệu XML được công bố trên ngân hàng Gene NCBI. Chúng được đánh số duyệt cây theo giá trị trước và duyệt cây theo giá trị sau trên đầu dựa theo cách đánh và thuật toán tác giả đã trình bày ở trên. Sau khi chuyển đổi dữ liệu (để đơn giản hóa chúng ta chỉ sử dụng giá trị duyệt cây theo giá trị trước để mô tả), các node sẽ được biểu diễn trong cấu trúc cây BioX-tree như trong Hình 2.3, các node dữ liệu có cùng cha mẹ sẽ được lưu trữ trong cùng một node lá. Trong trường hợp node lá quá nhiều entry và bị tràn khỏi mảng, nó sẽ được tách ra và có các con trỏ kết nối với nhau để đảm bảo vẫn kết nối với các anh em. Các mũi tên thẳng thể hiện các con trỏ từ một node lá đến node anh em trước và tiếp theo của chúng, mũi tên cong biểu diễn kết nối với cha mẹ của chúng. 11 Hình 2.5: Các node lá thể hiện sự liên kết trên cây cấu trúc BioX-tree Ở ví dụ này, các entry có giá trị duyệt cây theo giá trị trước là 21, 22, 23 là các node anh em trong tài liệu XML sẽ được chèn vào cùng một node lá và một con trỏ sẽ được sử dụng để kết nối đến node cha mẹ của chúng, là node chứa entry 24. Có nghĩa là, 21, 22, 23 và 24 là anh em và có cùng một cha mẹ. 2.2.3. Các thuật toán Vì khi thay đổi cấu trúc cây sẽ ảnh hưởng đến việc chèn, xóa và truy vấn các node, nên tác giả sẽ thiết kế lại một số thuật toán cho phù hợp hơn. Mục này sẽ trình bày các thuật toán được sửa đổi, các thuật toán không được trình bày nghĩa là tác giả sẽ sử dụng lại như trong phương pháp gốc. 2.2.3.1. Thuật toán chèn Với mục tiêu là giữ mối quan hệ anh em của dữ liệu XML, thuật toán chèn sẽ khá phức tạp. Mã giả cơ bản giải thích quá trình chèn cũng như chiến lược phân tách trong trường hợp node lá có đầy đủ trong Thuật toán 2.2. Thuật toán Insert(N,E) Đầu vào: node bối cảnh N và entry E sẽ được chèn thêm. Begin 1. Gọi FindSiblingNode(N,E) để tìm node lá N’ chứa anh em của entry E mới cần chèn. 2. if node N’ được tìm thấy 3. if (N’ còn không gian để thêm) then 4. chèn entry E vào N’ 5. else 6. Gọi CreateNewLeafNode(E) để tạo một node lá mới trên cây entry E sẽ được chèn vào đây 7. endif 8. else 9. Gọi CreateNewLeafNode(E) để tạo một node lá mới trên cây, entry E sẽ được chèn vào đây 10. endif End. Thuật toán 2.2: Thuật toán chèn Thuật toán FindsiblingNode(N, E) Đầu vào: node bối cảnh N, entry E cần tìm anh em. 12 Đầu ra: node N chứa các anh em của entry E. Begin 1. if N là không phải là node lá 2. Duyệt tìm các entry E’ trong N có MBR giao với MBR của entry E 3. Gọi FindSiblingNode(N’, E) trong đó N’ là node con của N được chỉ ra bởi E’ 4. else 5. if N chứa một entry là anh em của E 6. trả về N 7. endif End. Thuật toán 2.3: Thuật toán FindSiblingNode Thuật toán CreateNewLeafNode(E) Đầu vào: entry E được chèn thêm. Begin 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 12. 13. Tìm node anh em của entry E, N’ được tìm thấy if (N’ còn chỗ trống để thêm entry e) then Thêm entry E vào N’ else Tìm ngược từ dưới lên trên đến khi thấy node cha Q. Đi qua đường dẫn bên phải gần nhất từ node cha Q để đến node P có level 1 if node không là lá P không đầy entry E sẽ được thêm vào node lá trong P else Tạo node không là lá R mới ở level 1, tạo một node lá mới và chèn entry E vào. endif endif End. Thuật toán 2.4: Thuật toán CreateNewLeafNode Thuật toán 2.3: FindSiblingNode và Thuật toán 2.4: CreateNewLeafNode mô tả các thuật toán phụ 2.2.3.2. Thuật toán truy vấn BioX-tree khác với phương pháp áp dụng R-tree ở chỗ BioX-tree có thể trả lời trực tiếp hầu hết các truy vấn trên các trục mà không cần bước tinh chỉnh trong khi phương pháp dựa trên R-tree thực tế chỉ có khả năng trả lời trực tiếp 4 truy vấn trục chính (ancestor, preceding, following, descendant) như đã trình bày ở phần mở đầu. Trước khi đi vào chi tiết của từng thuật toán, Thuật toán 2.5 và Thuật toán 2.6 thể hiện các thuật toán dùng cho truy vấn điểm và truy vấn phạm vi. Đây là các truy vấn trên không gian cơ bản và được coi là các thuật toán phụ có sẵn trong phương pháp R-tree, tác giả không cải tiến gì thêm ở đây. Với sự hỗ trợ của các truy vấn này, chúng ta có thể nhận được kết quả trả về là tập hợp node hoặc chính xác một node tùy theo mong muốn. Thuật toán FindNode(N,E) // point query 13 Đầu vào: node bối cảnh N và entry E cần tìm kiếm Đầu ra: node N chứa entry E Begin 1. if (N là node lá) 2. Duyệt tìm các entry E’ trong N có MBR giao với MBR của entry E 3. Gọi FindNode(N’, E) trong đó N’ là node con của N được chỉ ra bởi E’ 4. else 5. if N chứa entry E 6. return N 7. endif End. Thuật toán 2.5: Thuật toán truy vấn điểm Thuật toán RangeQuery(N, Q, RESULT) //window query Đầu vào: node bối cảnh N (khi bắt đầu, node bối cảnh sẽ là node gốc) và cửa sổ truy vấn Q Output: danh sách RESULT chứa tất cả các entry có MBR giao với Q Begin 1. if N không là node lá 2. Duyệt tìm các entry E’ trong N có MBR giao với MBR của Q 3. Gọi RangeQuery(N’, Q, RESULT) trong đó N’ là node con của N được chỉ ra bởi E’ 4. else 5. Duyệt tìm các entry E’’ trong N có MBR giao với MBR của Q 6. Thêm E’’ to RESULT 7. endif End. Thuật toán 2.6: Thuật toán truy vấn phạm vi Để tránh dài dòng trong việc liệt kê các loại truy vấn khác nhau nhưng có sự tương đồng với nhau, tác giả chia các thuật toán xử lý truy vấn trên BioX-tree thành 2 loại: một loại bao gồm các thuật toán cho các truy vấn anh em và một loại cho các truy vấn khác. 2.2.4. Xử lý truy vấn 2.2.4.1 Thuật toán cho các truy vấn anh em Thuật toán SiblingQuery(N, E, RESULT) Đầu vào: node bối cảnh N (khi bắt đầu, node bối cảnh sẽ là node gốc) và entry E cần tìm anh em Đầu ra: Danh sách RESULT chứa tất cả các entry là anh em của entry E Begin 1. Gọi FindNode(N, E) để tìm node N’ chứa entry E 2. if (N’ được tìm thấy) 3. Duyệt các entry E’ trong N’ 4. Thêm E’ to RESULT 5. if (anh em sau theo pointer F không null) 6. Gọi FollowingSiblingQuery(NF, RESULT) trong đó NF là node trỏ đến bởi F 7. if (anh em trước theo pointer P không null) 8. Gọi PrecedingSiblingQuery(NP, RESULT) trong đó NP là node trỏ đến bởi P 9. Else 10. Không tìm thấy node anh em 14 11. Endif End. Thuật toán 2.7: Thuật toán truy vấn anh em Thuật toán FollowingSiblingQuery(NF, RESULT) Đầu vào: node bối cảnh NF Đầu ra: Danh sách RESULT chứa các entry anh em sau của NF Begin 1. Duyệt các entry E’ trong NF 2. Thêm E’ vào RESULT 3. if (anh em sau theo pointer F không null) 4. Gọi FollowingSiblingQuery(NF’, RESULT) trong đó NF’ là node trỏ đến bởi F 5. endif 6. endfor End. Thuật toán 2.8: Thuật toán truy vấn anh em sau Thuật toán PrecedingSiblingQuery(NP, RESULT) Đầu vào: node bối cảnh NP Đầu ra: Danh sách RESULT chứa các entry anh em trước của NP Begin 1. Duyệt các entry E’ trong NP 2. Thêm E’ vào RESULT 3. if (anh em trước theo pointer P không null) 4. Gọi PrecedingSiblingQuery(NP’, RESULT) trong đó NP’ là node trỏ tới bởi P 5. endif 6. endfor End. Thuật toán 2.9: Thuật toán truy vấn Anh em trước 2.2.4.2 Thuật toán cho các truy vấn khác Thuật toán ChildrenQuery(N, Q, RESULT) Đầu vào: node bối cảnh N và cửa sổ truy vấn Q Đầu ra: Danh sách RESULT chứa tất cả các con của entry E Begin 1. if (N là node không là lá) 2. Duyệt các entry E’ trong N có MBR giao với MBR của Q 3. Gọi ChildrenQuery(N’, Q, RESULT) trong đó N’ là node con của N được trỏ tới bởi E’ 4. else 5. Duyệt các entry E’’ trong E có MBR giao với MBR của Q 6. Gọi SiblingQuery(N, E’’, RESULT) 7. endif End. Thuật toán 2.10: Thuật toán truy vấn con 15 Thuật toán AncestorQuery(N, E, RESULT) Đầu vào: node bối cảnh N và entry E cần tìm các tổ tiên Đầu ra: Danh sách RESULT chứa tất cả các tổ tiên của E Begin 1. Gọi FindNode(N, E) để tìm node N chứa entry E 2. if (N không null) 3. if (con trỏ parent pointer F không null) 4. Duyệt các entry E’ trong NP, NP là node được trỏ tới bởi P 5. if E’ tổ tiên của E, thêm E’ vào RESULT 6. Nhảy tới bước 3, sao cho NP thay cho N 7. else 8. Node đầu vào là gốc 9. else 10. Node cần tìm không tồn tại 11. endif End. Thuật toán 2.11: Thuật toán truy vấn tổ tiên Khác với các thuật toán trên, trong truy vấn con cháu (Descendant query), tác giả chỉ hướng đến thu nhỏ kích thước cửa sổ của truy vấn và sau đó nhúng cửa sổ này vào một truy vấn phạm vi bình thường. Như trong phần chuyển đổi tác giả đã thêm tham số level l vào các node, bằng cách sử dụng tham số này chúng ta có thể cắt giảm kích thước cửa sổ của không gian tìm kiếm. Kết quả thực nghiệm thuật toán 2.2.5. Đánh giá độ phức tạp của các thuật toán Truy vấn anh em của phương pháp đề xuất có độ phức tạp: - Trường hợp tốt nhất là O(k + logm N), trong đó n là số node có trong cây, m là số entry trong 1 node. Trong đó k là số anh em tìm được của truy vấn. - Trường hợp xấu nhất là O(k + N) - Trung bình là O( k + m logmN) 2.3. Kết quả thực nghiệm phƣơng pháp BioX-tree 2.3.1. Mô hình và môi trƣờng thử nghiệm  Mô hình thử nghiệm Hình 2.6: Mô hình thử nghiệm phương pháp BioX-tree và R-tree  Dữ liệu thử nghiệm 16 Tác giả sử dụng 4 tài liệu tin sinh học khác nhau từ các nguồn dữ liệu uy tín. Chúng mô tả đa dạng sinh học khác nhau, về DNA, Protein, và mô tả về cây phân loài: DNACorn, DNARice, Swissprot, Allhomologies  Kịch bản Trong các truy vấn Xpath thì các truy vấn trên trục anh em, con cái là quan trọng và hay được sử dụng nhất bởi vì chúng trả về những tập kết quả nhỏ, đích danh và có giá trị sử dụng trong tính toán. Ví dụ như người sử dụng cần tìm trên dữ liệu XML: con cháu của node hiện tại, hoặc anh em của node hiện tại. Những truy vấn trục phụ khác như tổ tiên, hậu duệ, phía trước, theo sau thường là một tập chứa rất nhiều kết quả và ít được sử dụng trong thực tế. Kịch bản thực nghiệm 2 loại truy vấn Xpath trên trục anh em và trục con cái là dạng truy vấn là truy vấn điểm (point query). Các trục còn lại của Xpath sử dụng truy vấn phạm vi (range query). Mỗi tài liệu XML nêu trên được coi như một CSDL khác nhau và thực hiện riêng. Trên một tài liệu XML, tác giả chọn ngẫu nhiên 200 tag name, sau đó thực hiện truy vấn tìm các tập tag name có mối quan hệ liên quan theo các trục Xpath. Các truy vấn được thực hiện trên tài liệu XML có kích thước tăng dần, được thể hiện bằng độ phức tạp của cây XML với số tag name/node lần lượt là 20.000 – 40.000 – 60.000 – 80.000. Với mỗi loại truy vấn, kết quả trung bình số lần truy cập ổ cứng của 200 lựa chọn trên sẽ được lấy ra để đánh giá hiệu năng của các phương pháp. Số lần truy cập đĩa cứng càng ít có nghĩa là hiệu năng của truy vấn càng cao.  Công cụ và môi trường thử nghiệm Công cụ thực hiện lập trình các thuật toán là ngôn ngữ lập trình C++ trên Visual Studio 2008. Môi trường chạy thực nghiệm trên máy tính có cấu hình CPU: Intel Xeon E5520 - 2.7 GHz, RAM: 20 GB, OS: Windows Server 2008 R2 Enterprise. 2.3.2. Xây dựng chƣơng trình  Thiết kế file chỉ số  Thiết kế chương trình.  Biểu đồ lớp 17 Hình 2.7: Biểu đồ lớp của chương trình BioX-tree 2.3.3. Đánh giá hiệu quả giảm kích thƣớc dữ liệu Để đánh giá được hiệu quả thực tế của phương pháp nén dữ liệu từ tài liệu XML về tài liệu chuyển đổi về không gian số, tác giả đã làm thực nghiệm trên các tài liệu thực tế như Hình 2.8. Qua đó cho thấy tỷ lệ nén khá tốt, đặc biệt với các tài liệu mô tả DNA. Tuy nhiên, với tài liệu Allhomologies mô tả thông tin phân loài thì khá bất ngờ vì có tỷ lệ nén thấp. Để hiểu lý do tỷ lệ nén khác nhau giữa các tài liệu, tác giả đã phân tích các file XML và nhận ra một vấn đề. Tài liệu Allhomologies mô tả thông tin phân loài nên đa phần có tag dạng Attribute, đây là tag mô tả nhiều thuộc tính trên một chuỗi ký tự. Thuật toán chuyển đổi khi gặp các tag dạng này sẽ phải bóc tách từng Attribute trong một chuỗi thành các tag riêng rẽ vì vậy đã làm tăng kích thước tài liệu chuyển đổi. Như vậy, có thể thấy rằng, trên thực tế phương pháp chuyển đổi này không phải lúc nào cũng có tỷ lệ nén tốt vì còn tùy thuộc vào cấu trúc của tài liệu XML. Hình 2.8: So sánh kích thước tài liệu XML và tài liệu chuyển dổi về không gian số 2.3.4. So sánh kết quả của phƣơng pháp BioX-tree và R-tree Trong các phương pháp đánh chỉ số trên không gian, đơn vị để đo hiệu năng sẽ là số node truy cập trung bình, vì thực chất thời gian xử lý nhanh hay chậm phụ thuộc vào việc một truy vấn cần phải truy cập (I/O) nhiều hay ít vào ổ cứng để đọc các block. Nghĩa là truy xuất đọc các node (block) càng ít thì tương ứng với việc thời gian xử lý sẽ càng tối ưu hơn. a. Truy vấn node Hình 2.9, 2.10 cho thấy hiệu suất của BioX-tree tốt hơn nhiều so với R-tree. Lý do là để đạt được kết quả, R-tree phải sử dụng truy vấn phạm vi để quét tất cả các node anh em hoặc con cháu, sau đó lọc ra các node dự kiến. Nhưng BioX-tree xử lý các truy vấn này bằng cách trước tiên chỉ tiếp cận một node lá có chứa đối tượng và sau đó tìm kiếm tất cả các anh em, các node con thông qua các con trỏ. Điều này giúp tránh vấn đề chồng chéo của R-tree. Kích thước dữ liệu XML càng lớn, R-tree càng chồng chéo nhiều hơn. Đó là lý do tại sao hiệu suất của R- tree giảm nhanh chóng khi kích cỡ dữ liệu tăng. Hình 2.9: Truy vấn anh em Hình 2.10: Truy vấn con cái b. Truy vấn phạm vi 18 Hình 2.11 cho thấy hiệu suất của BioX-tree kém hơn một chút so với R-tree ngoại trừ dữ liệu kích thước lớn. Lý do là tác giả đã ép buộc các node anh em của một đối tượng dữ liệu XML vào một số node lá của R-tree. Chắc chắn, điều đó làm cho cấu trúc lập chỉ số kém tối ưu hơn, dẫn đến vấn đề chồng chéo. Mặc dù vậy, nhờ có con trỏ (đến cha mẹ) của BioX-tree, hiệu suất của BioX-tree không tệ hơn nhiều so với R-tree. Hình 2.12 cho thấy hiệu suất của BioX- tree tốt hơn một chút so với R-tree. Thay vì quét toàn bộ một trong bốn vùng rời rạc trên mặt phẳng, BioX-tree chỉ tìm con của một node con cháu và sau đó sử dụng các con trỏ (đến node anh em) để đạt được phần còn lại. Tương tự như Hình 2.12, Hình 2.13, 2.14 cho thấy hiệu suất của BioX-tree kém hơn một chút so với R-tree. Lý do là truy vấn phạm vi buộc phải quét một trong bốn vùng rời rạc dẫn đến vấn đề chồng chéo nghiêm trọng Hình 2.11: Truy vấn tổ tiên Hình 2.12: Truy vấn con cháu Hình 2.13: Truy vấn các node theo sau Hình 2.14: Truy vấn các node phía trước Tóm lại, các phương pháp lập chỉ số được đề xuất của tác