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

hình dưới. DNACorn: Hình 2.16: File dữ liệu DNACorn sau chuyển đổi 80 DNARice: Hình 2.17: File dữ liệu DNARice sau chuyển đổi Swissprot: Hình 2.18: File dữ liệu Swissprot sau chuyển đổi Allhomologies Hình 2.19: File dữ liệu Allhomologies sau chuyển đổi 81 Tỷ lệ nén của các tài liệu được thể hiện trong hình 2.20. 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.20: 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ố Tóm lại, các phương pháp lập chỉ số được đề xuất của tác giả có hiệu suất tốt hơn nhiều với các truy vấn node nhưng hiệu suất gần như tương tự với các truy vấn phạm vi. Trong thực tiễn, các truy vấn node được sử dụng nhiều hơn các truy vấn 82 phạm vi bởi vì người dùng hiếm khi cần tất cả dữ liệu tổ tiên hoặc dữ liệu con cháu của một đối tượng. Thực tế, truy vấn anh em trước, anh em sau, con cái mang lại nhiều lợi ích cho cơ sở dữ liệu DNA trong việc tìm kiếm. 2.3.4. So sánh kết quả của phƣơng pháp BioX-tree và R-tree Các phương pháp đánh chỉ số trên đĩa cứng đều đánh giá hiệu quả thực nghiệm thuật toán dựa trên số lần truy xuất đĩa cứng, với lý do các truy xuất đĩa cứng là tuần tự không phải ngẫu nhiên, tốc độ truy xuất đĩa cứng chậm hơn rất nhiều so với bộ nhớ chính. Nên chi phí thời gian của các phương pháp đánh chỉ số này chủ yếu đo số lần truy xuất đĩa cứng này. Chi phí thời gian sẽ được tính đến khi phương pháp sử dụng nhiều bộ nhớ để tính toán hoặc giải quyết các bài toán phân cụm (clustering). Tuy nhiên, phương pháp đề xuất chưa tận dụng bộ nhớ chính để tăng thời gian tính toán, cũng như tối ưu bằng phương pháp phân cụm. Do vậy, các thực nghiệm chỉ đánh giá dựa trên số lần truy xuất đĩa cứng, mỗi lần truy xuất là lấy 1 block tương đương với 1 node trên cây đánh chỉ số. a. Truy vấn điểm Hình 2.21, 2.22 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. 83 Bảng 2.6: Kết quả truy vấn anh em BioX-tree Kích thước dữ liệu tính theo số tag Số truy vấn thử nghiệm Số block truy cập trung bình R-tree BioX-tree R-tree BioX-tree 20000 tag 200 200 416.74 7.08 40000 tag 200 200 845.78 9.82 60000 tag 200 200 1248.26 8.2 80000 tag 200 200 1681.74 8.3 Hình 2.21: Biểu đồ so sánh truy vấn anh em giữa BioX-tree và R-tree Bảng 2.7: Kết quả truy vấn con cái BioX-tree Kích thước dữ liệu tính theo số tag Số truy vấn thử nghiệm Số block truy cập trung bình R-tree BioX-tree R-tree BioX-tree 20000 tag 200 200 416.74 4.46 40000 tag 200 200 845.78 4.56 60000 tag 200 200 1248.26 2.24 80000 tag 200 200 1681.74 2.46 84 Hình 2.22: Biểu đồ so sánh truy vấn con cái giữa BioX-tree và R-tree b. Truy vấn phạm vi Các truy vấn phạm vi buộc cả R-tree và BioX-tree phải tìm kiếm rất nhiều đối tượng liên quan đến đối tượng, tất cả tổ tiên hoặc con cháu. Thông thường, chúng phải sử dụng các hình chữ nhật có một phần tư mặt phẳng để tìm kiếm các node của một trục nhất định. Điều này tạo ra nhiều bước dư thừa do vấn đề chồng chéo và dẫn đến tốn nhiều thời gian hơn trong việc tìm kiếm và xử lý dữ liệu. Hình 2.23 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 thậm chí còn tốt hơn khi số lượng chồng chéo hoặc kích thước dữ liệu đủ lớn. Hình 2.24 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. 85 Tương tự như Hình 2.23, Hình 2.25, 2.26 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 Bảng 2.8: Kết quả truy vấn tổ tiên BioX-tree Kích thước dữ liệu tính theo số tag Số truy vấn thử nghiệm Số block truy cập trung bình R-tree BioX-tree R-tree BioX-tree 20000 tag 200 200 4.04 4.16 40000 tag 200 200 5.62 6.04 60000 tag 200 200 5.56 5.52 80000 tag 200 200 11.73 8.06 Hình 2.23: Biểu đồ so sánh truy vấn tổ tiên giữa BioX-tree và R-tree Bảng 2.9: Kết quả truy vấn hậu duệ BioX-tree Kích thước dữ liệu tính theo số tag Số truy vấn thử nghiệm Số block truy cập trung bình R-tree BioX-tree R-tree BioX-tree 20000 tag 200 200 5 3.1 40000 tag 200 200 6.9 4.9 60000 tag 200 200 14.1 12.2 80000 tag 200 200 25.6 23.9 86 Hình 2.24: Biểu đồ so sánh truy vấn hậu duệ giữa BioX-tree và R-tree Bảng 2.10: Kết quả truy vấn các node theo sau BioX-tree Kích thước dữ liệu tính theo số tag Số truy vấn thử nghiệm Số block truy cập trung bình R-tree BioX-tree R-tree BioX-tree 20000 tag 200 200 165.75 165.55 40000 tag 200 200 314.48 189.1 60000 tag 200 200 272.22 920.1 80000 tag 200 200 236.19 1800.65 Hình 2.25: Biểu đồ so sánh truy vấn các node theo sau giữa BioX-tree và R-tree 87 Bảng 2.11: Kết quả truy vấn các node phía trƣớc BioX-tree Kích thước dữ liệu tính theo số tag Số truy vấn thử nghiệm Số block truy cập trung bình R-tree BioX-tree R-tree BioX-tree 20000 tag 200 200 102.4 74.6 40000 tag 200 200 173.41 140.5 60000 tag 200 200 322.55 195.55 80000 tag 200 200 520.52 350.46 Hình 2.26: Biểu đồ so sánh truy vấn các node phía trƣớc giữa BioX-tree và R- tree 2.4. Kết luận chƣơng 2 Trong chương này, tác giả đã nghiên cứu và trình bày đề xuất một phương pháp cải tiến xử lý hiệu quả các trục XPath, được coi là nền tảng cho xây dựng các truy vấn phức tạp. Để xử lý hiệu quả các truy vấn như vậy, tác giả đề xuất phương pháp BioX-tree với một số cải tiến quan trọng như thêm con trỏ để chỉ ra mối quan hệ: cha mẹ - con cái, anh em, bước chuyển đổi từ tài liệu XML lên không gian được bổ sung một số tham số, thiết kế lại các thuật toán truy vấn trên các trục chính của Xpath để tăng tốc độ khi thực hiện. 88 Phần thực nghiệm được thực hiện trên những loại dữ liệu tin sinh học XML từ các nguồn uy tín và phổ biến trong cộng đồng sinh học. Trong cấu trúc mới này, kết quả thực nghiệm cho thấy hiệu quả vượt trội hơn phương pháp lập chỉ số dựa trên R-tree trên truy vấn điểm, là thuật toán hay được sử dụng nhất trong thực tế, vì các thuật toán mới dựa trên theo dõi quỹ đạo liên kết bằng cách sử dụng các con trỏ được tối ưu hóa cao cho đọc ghi I/O đĩa cứng. Nhưng bên cạnh đó vẫn còn một số nhược điểm mà tác giả tiếp tục nghiên cứu và trình bày cách giải quyết trong chương 3. Các kết quả nghiên cứu ở Chương 2 được công bố trong công trình 2, 3, 4 phần “Danh mục công trình của tác giả”. 89 Chƣơng 3. PHƢƠNG PHÁP ĐÁNH CHỈ SỐ MỞ RỘNG BIOX+-TREE 3.1. Mở đầu Nén dữ liệu dữ liệu tin sinh học đã được nghiên cứu trong nhiều năm gần đây. Trong dữ liệu XML tin sinh thông thường gồm có dữ liệu mô tả và dữ liệu sinh học AND/Protein. Vì vậy, có hai hướng nghiên cứu chính: (1) nén dữ liệu XML nói chung và (2) nén dữ liệu sinh học. Tác giả tập trung vào nén dữ liệu XML. Mặc dù, không có phương pháp nén đặc thù cho dữ liệu tin sinh học cho tệp XML, các nghiên cứu gần đây về nén dữ liệu XML tin sinh chia ra làm hai hướng: (1) nén truy vấn là phương pháp cho phép truy vấn dữ liệu trên chính dữ liệu nén mà không cần giải nén trước, (2) nén dữ liệu không truy vấn là phương pháp tập trung vào tối ưu tỉ lệ nén và chỉ cho phép truy vấn file dữ liệu XML sau khi được giải nén. Vì kích thước tệp dữ liệu tin sinh rất lớn, nên tác giả cho rằng việc tối ưu về kích thước cho truy vấn quan trọng hơn, vì vậy nghiên cứu này tập trung vào hướng đầu tiên. Do đặc điểm của cấu trúc dữ liệu sau khi đánh chỉ số được tối ưu để tăng hiệu quả truy vấn thường có kích thước nhỏ hơn nên có thể coi đây là một phương pháp nén và đồng thời cho phép truy vấn trực tiếp thay vì phải giải nén. Sau đây là một số phương pháp đã thực hiện. Phương pháp đầu tiên là XGrind [82] công bố bởi Tolani và Haritsa. Phương pháp này nén dữ liệu bằng cách thay thế các tên thuộc tính và phần tử thành các ký tự duy nhất. Phương pháp cho phép truy vấn trực tiếp trên tài liệu nén tuy nhiên chỉ hỗ trợ các truy vấn đường dẫn giản đơn, không có khả năng hỗ trợ các truy vấn Xpath. Tương tự, Xpress [52] công bố bởi Min et al. sử dụng phương pháp toán học nghịch đảo để mã hóa các đường dẫn nhãn của tài liệu XML thành các đoạn riêng biệt. Các truy vấn dựa vào mỗi quan hệ giữa các đoạn đó để tăng hiệu quả trên tài liệu XML nén. Nhược điểm của Xpress và XGrind là tỷ lệ kích thước giữa dữ liệu nén và gốc là tuyến tính, không hỗ trợ nhiều truy vấn. Do đó, Cheng and NG đã đề 90 xuất kỹ thuật XQzip [15]. XQzip sử dụng cây chỉ số có cấu trúc (Structure Index Tree (SIT)) cho tài liệu XML gốc. Và XQueC [7] Arion et al. sử dụng cây tóm tắt có cấu trúc (structure summary tree) để lưu trữ tài liệu XML. Các phương pháp này cho tỷ lệ nén cao hơn và truy vấn nhanh hơn. Để tăng hiệu quả các truy vấn Xpath, Arroyuelo et al. [8] đưa ra kỹ thuật tạo ra cây đánh nhãn từ cấu trúc cây XML, sau đó sử dụng phương pháp đánh chỉ số mảng bit (bit array) để nén tài liệu XML. Phần dữ liệu được nén bằng phương pháp thông thường bất kỳ. Để giảm độ trễ và tối ưu băng thông truyền dữ liệu, Qian et al. [62] đưa ra phương pháp tách phần cấu trúc tài liệu XML ra khỏi phần nội dung và nén riêng biệt, đã cho hiệu quả tốt hơn các phương pháp trước. Các phương pháp nén có xu hướng tách và nén riêng phần cấu trúc tài liệu XML và dữ liệu trong tài liệu XML. Với phần cấu trúc, có các phương pháp nổi bật đã áp dụng mã hoá cấu trúc theo thứ tự duyệt cây. Dietz [21] là phương pháp đầu tiên sử dụng kỹ thuật mã hóa cấu trúc bằng phương pháp duyệt thứ tự cây theo duyệt cây theo thứ tự trước (post-order) và duyệt cây theo thứ tự sau (pre-order). Yếu điểm của phương pháp này là sẽ phải tính lại thứ tự duyệt cây theo thứ tự trước và sau mỗi khi có dữ liệu mới. Để khắc phục vấn đề này, Li and Moon in XISS [61] đã sử dụng phương pháp B+tree để đánh chỉ số phần tử và thuộc tính. Tuy nhiên, truy vấn có hiệu năng không tốt vì rất nhiều kết quả trung gian và mỗi khi tạo node mới, sẽ phải sắp xếp toàn cục lại lần nữa. Tiếp đó, R-tree được xây dựng để cải tiến hơn nữa việc xử lý. Trong chương 2, tác giả đã đưa ra ý tưởng tăng hiệu quả truy vấn trục XPath cho các anh em trước, sau và tổ tiên bằng cách thêm các con trỏ, các biến tham số cho các node lá của cây R-tree. Nhờ các con trỏ này các truy vấn trục Xpath khác (descendant) và kể cả các trục con cũng được hưởng lợi để có hiệu quả tốt hơn. Tuy nhiên, nhược điểm của phương pháp là có thể tạo ra cây chỉ số R-tree không tối ưu. Vì vậy, nội dung tiếp theo, tác giả phân tích không gian dữ liệu 91 chuyển đổi của tài liệu XML và đề xuất các thuật toán mà có thể khắc phục phần nào khuyết điểm trên. Trong chương này, luận án trình bày đề xuất chuyển đổi số các tag name về tọa độ không gian dạng số để giảm kích thước tài liệu và đề xuất phương pháp đánh chỉ số mới để tăng hiệu quả truy vấn tài liệu XML, kết quả cũng chỉ ra được một số vấn đề thực tế do sự đa dạng tài liệu XML tin sinh học. Các thành phần được đề xuất cải tiến là: module đánh chỉ số, module xử lý truy vấn. Hình 3.1: Các thành phần đƣợc cải tiến trong phƣơng pháp mở rộng BioX+-tree Kết quả nghiên cứu ở chương này được công bố ở công trình số 5, phần “Danh mục các công trình của tác giả”. 3.2. Phƣơng pháp BioX+-tree 3.2.1. Phân tích không gian dữ liệu chuyển đổi của tài liệu XML Ở nghiên cứu trong chương 2, tác giả đã nhận thấy rằng phân bố dữ liệu XML trên không gian có xu hướng tập trung vào 2 trục Xpath anh em trước và sau, do vậy đã đề xuất sử dụng thêm con trỏ để tăng hiệu quả truy vấn. Trong phần này, tác giả sẽ phân tích không gian dữ liệu chuyển đổi của tài liệu XML và cách tổ chức các dữ liệu đó trên cây chỉ số R-tree. Để dễ hình dung và không cần tìm lại các kiến thức ở phần trên, tác giả sẽ tổng hợp lại nhanh phương pháp chuyển đổi dữ liệu XML. Giả sử, chúng ta có một tài liệu XML tên X, để chuyển đổi sang không gian số, chúng ta cần duyệt cây theo thứ tự trước và đánh số thứ tự cho từng tag name của 92 tài liệu X. Như Hình 3.2 (các biểu tượng chấm tròn tương đương với 1 tag name trong X, cây phân cấp có cấu trúc giống hệt cấu trúc cây XML của X), chúng ta thấy rằng, với thuật toán duyệt cây theo thứ tự trước, tag gốc XML sẽ có thứ tự là 1, và các tag con có thứ tự tiếp theo từ bên trái sang phải. Tương tự vậy, với thuật toán duyệt cây theo thứ tự sau, tag gốc sẽ có số thứ tự cuối cùng, và các tag con/cháu tận cùng bên trái sẽ bắt đầu từ 1. Và với 2 thuật toán duyệt cây XML của X, Hình 3.2 sẽ ghi chú 2 thứ tự này trên từng chấm tròn (tag name) như pre-post, vd tag gốc sẽ được ghi chú là 1-31, trong đó 31 chính là tổng số tag name của X. Hình 3.2: Cây tài liệu XML đƣợc đánh số thứ tự Như vậy, mỗi một tag name trong X đã có một toạ độ Đề Các trong không gian 2 chiều. Bắt đầu từ bây giờ, chúng ta có thể sử dụng các phương pháp đánh chỉ số không gian cho dữ liệu của X. Trong luận án này, tác giả sử dụng phương pháp đánh chỉ số R-tree cho không gian 2 chiều. Phương pháp R-tree truyền thống sẽ nhóm các phần tử trên toạ độ không gian vào từng node trên cây R-tree và thể hiện các nhóm này trong các MBR - hình chữ nhật nhỏ nhất mà bao/chứa tất cả các phần tử của từng nhóm. Tuy nhiên, ở nghiên cứu trước, để giữ mối quan hệ giữa các anh em của X, tác giả đã nhóm các tag anh em vào các node lá của R-tree, và sử dụng các con trỏ để kết nối các node lá R-tree cùng mang anh em của một cha, phương pháp này là BioX-tree. Hình 3.3 mô tả các node lá của BioX-tree trong không gian 2 chiều qua các hình chữ nhật MBR. Trong đó, R là MBR của các tag con của tag gốc (1-31) của Hình 1, tương tự vậy R1, 2, 3 trong Hình 3.3 là các MBR của các tag con của các tag 2-10, 12-10, 22-30 trong Hình 3.2, và tương tự cho các MBR nhỏ hơn. Từ mô tả trực quan trên không gian của Hình 3.3, tác giả đưa ra các định lý về các MBR các cây con của các tag của X khi thể hiện trong không gian cây BioX-tree. 93 Hình 3.3: Các MBR của node lá trong cây BioX-tree Định lý 1: Giả sử trong 1 tài liệu XML, tag T là cha của các tag t1,t2,.., tn (sibling). Các MBR mà bao các tag con (cây con) của t1, t2,, tn trên không gian của BioX-tree luôn tách rời (không giao nhau). VD: R1, R2, R3 là các hình chữ nhật bao các cây con luôn tách rời và trải từ trái qua phải trên không gian của Hình 3.3. Để chứng minh cho định lý này, chúng ta dễ dàng nhận ra rằng, các phần tử con trong các MBR bao cây con các anh em trái cùng cha luôn có giá trị nhỏ hơn các phần tử con trong MBR bao cây con phải với giá trị duyệt cây theo thứ tự trước. Ngược lại, luôn lớn hơn với giá trị duyệt cây theo thứ tự sau. Do vậy, các MBR cho cây con của các node con cùng cha trong tài liệu X trên không gian của BioX-tree luôn tách rời. Như vậy, Định lý 1 cho chúng ta thấy rằng, việc gượng ép các tag XML anh em cùng cha vào trong cùng node lá BioX-tree có thể không ảnh hưởng nhiều đến tối ưu cấu trúc cây BioX-tree cho các truy vấn. Kết quả thực nghiệm trong chương 2 về BioX-tree vì thế thể hiện được điều này. 94 Định lý 2: Giả sử trong 1 tài liệu XML, tag T là cha của các tag t1, t2,.., tn (sibling). Ngoại trừ các MBR bao cây con của t1 và tn (anh em đầu tiên và sau cùng), MBR mà bao t1, t2,..., tn sẽ bao tất cả MBR của các cây con của t2,.., tn-1. VD: R sẽ bao toàn bộ R2 và R21, R22, R23. Để chứng minh cho định lý này, chúng ta dễ dàng nhận ra rằng các giá trị duyệt cây theo thứ tự trước-duyệt cây theo thứ tự sau của t1 và tn là liền trước và sau giá trị duyệt cây theo thứ tự trước-duyệt cây theo thứ tự sau của T. Do vậy, các giá trị duyệt cây theo thứ tự trước-duyệt cây theo thứ tự sau của các t2,..., tn hiển nhiên là phải trong phạm vi MBR bao t1 và tn. Từ định lý 2, tác giả rút ra hệ quả 2.1 cho truy vấn tìm kiếm 1 tag XML trong cây BioX-tree như sau Hệ quả 2.1: Giả sử khi tìm 1 tag t của tài liệu XML trong cây tìm kiếm BioX- tree, và phát hiện giá trị duyệt cây theo thứ tự trước-duyệt cây theo thứ tự sau của t nằm trong hình chữ nhật R1 và R2. Nếu R1 nằm trong R2, thì thuật toán tìm kiếm sẽ không cần tiếp tục duyệt các cây con khác của R2 để tìm t vì chắc chắn t thuộc các cây con của R1. Từ các định lý và hệ quả có được, tác giả thiết kế lại các thuật toán BioX-tree để tối ưu lại truy vấn, khắc phục nhược điểm về cấu trúc. 3.2.2. Các thuật toán đề xuất Từ các kết luận thu được ở mục 3.1, tác giả đề xuất các thuật toán Chèn và Truy vấn mới và tác giả gọi phương pháp mới mở rộng của cây BioX-tree là BioX+- tree. Mục tiêu của thuật toán là giảm bớt các bước duyệt cây dư thừa để tối ưu tốc độ truy vấn, đồng thời giảm bớt nhược điểm về cầu trúc của cây BioX-tree. BioX + -tree sẽ bỏ con trỏ Par (trỏ tới parent node) vì chưa thực sự mang lại hiệu quả mong đợi và làm tốn khá nhiều bộ nhớ lưu trữ. Thuật toán Insert(N,E) Đầu vào: node N chứa entry E 95 Đầu ra: entry E được chèn vào cây Begin Gọi FindNode(N,E) để tìm node lá N’ chứa anh em của entry E cần chèn if (N’ không null), if (N’ là node đầu tiên hoặc node cuối cùng) fullnode = m //m là số lượng entry nhỏ nhất trong 1 node else fullnode = M //M là số lượng entry lớn nhất trong 1 node if |N’| <fullnode //vẫn còn khoảng trống và chưa đầy Chèn entry E vào node N’. else CreateNewLeafNode(E) //tạo một node lá mới chứa E, sau đó chèn node này vào cây else CreateNewLeafNode(E) //tạo một node lá mới chứa E, sau đó chèn node này vào cây Creatpointers (pre, post, N’) End Thuật toán 3.1: Thuật toán Insertion Sự khác biệt ở thuật toán này là sẽ cân nhắc các tag đầu và cuối của node lá trong BioX + -tree, các node chứa các tag đầu và cuối sẽ chỉ chứa tối đa m tag thay vì M. Như vậy, sẽ làm giảm bớt kích thước của MBR bao node lá, và có thể giảm vấn đề giao cắt giữa các MBR của BioX+-tree. Các truy vấn sẽ hưởng lợi từ cấu trúc này. Thuật toán FindNode(N, E) Đầu vào: node N chứa entry E Đầu ra: node bối cảnh N và entry E cần tìm kiếm Begin minN = N 96 if (N không là lá), Duyệt các entry E’ trong N với MBR (N’) giao với MBR của E if (N’ giao hoặc bên trong minN) invoke FindNode(N’,E), với N’ là các node con của N trỏ tới bởi E’. if N’ bên trong N minN=N’ else if N chứa entry E, Return N. End Thuật toán 3.2: Thuật toán truy vấn Thuật toán này áp dụng Định lý 2 và Hệ quả 2.1, nghĩa là khi tìm kiếm E, nếu R1 nằm trong R2, thì bỏ qua bước duyệt cây con của R2 và lưu lại giá trị R1. - Tại bất kỳ node trung gian nào, - Nếu có R chứa R1 thì sẽ bỏ qua duyệt cây con - Nếu có R nằm trong R1, thì lưu lại R để so sánh bước tiếp theo, tiếp tục duyệt R - Nếu R không nằm tron 2 trường hợp trên, tiếp tục duyệt R 3.3. Kết quả thực nghiệm phƣơng pháp BioX+-tree 3.3.1. Mô hình và môi trƣờng thử nghiệm  Mô hình thử nghiệm Mô hình thử nghiệm của tác giả cũng sẽ tương tự như đã thực hiện trên BioX- tree, chỉ khác là phương pháp BioX-tree và BioX+-tree sẽ được thử nghiệm và ghi nhận lại kết quả. 97 Hình 3.4: Mô hình thử nghiệm thuật toán BioX+-tree và BioX-tree Để đánh giá hiệu quả thực tế của phương pháp, tác giả thử nghiệm trên các tài liệu XML tin sinh học có nguồn gốc phổ biến và đa dạng.  Dữ liệu thử nghiệm Như thử nghiệm trong chương 2, tác giả vẫn sẽ 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 khác nhau: - DNACorn: Chứa thông tin mô tả DNA Ngô như các tác giả, năm công bố, gene,... nguồn gốc từ NCBI (https://www.ncbi.nlm.nih.gov). - DNARice: Chứa thông tin mô tả DNA Gạo như các tác giả, năm công bố, gene,... nguồn gốc từ NCBI (https://www.ncbi.nlm.nih.gov). - Swissprot: Tập các thông tin về chức năng của protein với chú thích chính xác, nhất quán và phòng phú, nguồn từ: https://www.uniprot.org. - Allhomologies: chứa thông tin cây phân loài của họ nhà chuột, nguồn từ ftp://ftp.ensembl.org/  Kịch bản Gần giống như các bước trong chương 2, kịch bản thực nghiệm trên 2 loại truy vấn Xpath trục anh em và trục con cái với dạng câu truy vấn là truy vấn điểm (point query). Những trục còn lại của Xpath sử dụng truy vấn phạm vi (range query). 98 Trong phần này sẽ đi sâu hơn nữa vào các truy vấn anh em, có sự phân biệt anh em trước và anh em sau. Mỗi tài liệu XML đượ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. Tuy nhiên, phần này không đi so sánh theo kích thước (số tag name/node) tăng dần như chương 2, mà tác giả sẽ chạy thuật toán trên cùng 80.000 tag đầu vào của 4 loại file dữ liệu tin sinh với những đặc tính dữ liệu khác nhau. 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 Tương tự như thử nghiệm trong chương 2, tác giả vẫn sử dụng các môi trường và thiết bị đó để thực 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. 3.3.2. So sánh kết quả của phƣơng pháp BioX+-tree và BioX-tree a. Truy vấn anh em (Sibling queries) Truy vấn phải tìm toàn bộ các anh em của một tag bất kỳ trong tài liệu XML. Hình 3.5 cho thấy kết quả trung bình BioX+-tree luôn tốt hơn BioX-tree cho tất cả các tài liệu XML. Với tài liệu Allhomologies, thực nghiệm cho kết quả tốt nhất. 99 Bảng 3.1: Kết quả truy vấn anh em BioX+-tree File đầu vào Số truy vấn thử nghiệm Số block truy cập trung bình BioX + -tree BioX-tree BioX + -tree BioX-tree DNACorn 200 200 7,915 10,45 DNARice 200 200 7,85 9,8 Swissprot 200 200 5,69 8,565 Allhomologies 200 200 4,405 8,895 Hình 3.5: Biểu đồ so sánh truy vấn anh em BioX+-tree và BioX-tree b. Truy vấn anh em trƣớc (Sibling proceding queries) Truy vấn chỉ tìm các anh em trước của một tag bất kỳ trong tài liệu XML. Hình 3.6 cũng cho thấy kết quả trung bình BioX+-tree luôn tốt hơn BioX-tree cho tất cả các tài liệu XML. Và có vẻ với tài liệu Allhomologies, thực nghiệm vẫn cho kết quả tốt nhất. 100 Bảng 3.2: Kết quả truy vấn anh em trƣớc BioX+-tree File đầu vào Số truy vấn thử nghiệm Số block truy cập trung bình BioX + -tree BioX-tree BioX + -tree BioX-tree DNACorn 200 200 7,915 10,45 DNARice 200 200 7,85 9,8 Swissprot 200 200 5,69 8,565 Allhomologies 200 200 5,405 8,895 Hình 3.6: Biểu đồ so sánh truy vấn anh em trƣớc BioX+-tree và BioX-tree c. Truy vấn anh em sau (Sibling following queries) Truy vấn chỉ tìm các anh em sau của một tag bất kỳ trong tài liệu XML. Hình 3.7 cũng cho thấy kết quả trung bình BioX+-tree luôn tốt hơn BioX-tree cho tất cả các tài liệu XML . Tuy nhiên, kết quả cho tài liệu DNARice có vẻ khác biệt nhiều. Điều này chứng tỏ rằng, có những tình huống BioX+-tree sẽ cho kết quả rất tốt khi truy vấn loại bỏ được nhiều truy xuất dư thừa theo Định lý 2 và Hệ quả 2.1. 101 Bảng 3.3: Kết quả truy vấn anh em sau BioX+-tree File đầu vào Số truy vấn thử nghiệm Số block truy cập trung bình BioX + -tree BioX-tree BioX + -tree BioX-tree DNACorn 200 200 7,915 10,45 DNARice 200 200 1,095 9,8 Swissprot 200 200 5,69 8,565 Allhomologies 200 200 5,33 8,82 Hình 3.7: Biểu đồ so sánh truy vấn anh em sau BioX+-tree và BioX-tree d. Truy vấn con cái (Children queries) Các truy vấn này cần tìm các tag con của một tag bất kỳ trong tài liệu XML. Để làm điều này, cách tốt nhất là tính toán ra được 1 tag con (first hoặc last), sau đó sử dụng truy vấn sibling của tag con đó. Như thế, truy vấn này sẽ trở thành sibling query như trên. Tuy nhiên, trong nghiên cứu này, tác giả tạo ra một range query với cửa sổ tìm kiếm giới hạn để có thể tìm thấy các tag con của một tag bất kỳ. Hình 3.8 cũng cho thấy kết quả trung bình BioX+-tree và BioX-tree cơ bản là giống nhau cho tất cả các tài liệu XML. Có vẻ như cửa sổ tìm kiếm được giới hạn đủ tốt để không thấy sự khác biệt giữa 2 cấu trúc cây này. 102 Bảng 3.4: Kết quả truy vấn con cái BioX+-tree File đầu vào Số truy vấn thử nghiệm Số block truy cập trung bình BioX + -tree BioX-tree BioX + -tree BioX-tree DNACorn 200 200 2,505 2,505 DNARice 200 200 2,405 2,405 Swissprot 200 200 2,005 2,005 Allhomologies 200 200 0,27 0,22 Hình 3.8: Biểu đồ so sánh truy vấn con cái BioX+-tree và BioX-tree e. Truy vấn phạm vi (Range query) Ngoài các truy vấn theo các trục Xpath như trên, các truy vấn còn lại sử dụng các cửa sổ vùng mà có giới hạn phạm vi không gian, tác giả thực nghiệm chung các truy vấn vùng này. Thực nghiệm trên các truy vấn này sẽ không tận dụng các con trỏ mà kết nối node lá của BioX-tree và BioX+-tree. Như vậy, kết quả được đánh giá hoàn toàn dựa vào sự tối ưu của cầu trúc cây. Để khách quan khi so sánh hiệu năng truy vấn giữa 2 cầu trúc BioX-tree và BioX+-tree, tác giả dùng 50 truy vấn cố định (không ngẫu nhiên) để thực nghiệm. 103 Kết quả ở Hình 3.9 đã cho thấy không phải tài liệu nào cũng cho kết quả truy vấn khác nhau, tuy nhiên vẫn có các tài liệu XML mà cấu trúc BioX+-tree cho kết quả hiệu năng tốt hơn cấu trúc BioX-tree. Bảng 3.5: Kết quả truy vấn phạm vi BioX+-tree Index file Số truy vấn thử nghiệm Số block truy cập trung bình BioX + -tree BioX-tree BioX + -tree BioX-tree DNACorn 200 200 15,9 15,9 DNARice 200 200 18,32 18,32 Swissprot 200 200 2,66 8,58 Allhomologies 200 200 10,52 15,1 Hình 3.9: Biểu đồ so sánh truy vấn phạm vi BioX+-tree và BioX-tree Từ các thực nghiệm trên, đã chứng tỏ rằng việc xây dựng các thuật toán theo các Định lý và Hệ quả đề ra đang mang lại hiệu quả, không chỉ các truy vấn liên quan đến các tag anh em mà còn và cho các truy vấn thông thường nhờ vào cấu trúc cây tối ưu hơn. 104 3.4. Kết luận chƣơng 3 Với mục tiêu tìm ra phương pháp đánh chỉ số mới để có thể truy hồi thông tin các tài liệu XML tin sinh học có kích thước lớn và đồng thời có thể giảm bớt kích thước lưu trữ. Trong chương 3, luận án đã phân tích mối tương quan giữa cấu trúc cây XML sau khi chuyển đổi về dữ liệu không gian số Đề các và cấu trúc cây BioX-tree. Từ đó, đưa ra các định lý và hệ quả để áp dụng xây dựng các thuật toán mới, phương pháp mới là BioX+-tree. Các kết quả thực nghiệm đã chỉ ra rằng phương pháp đánh chỉ số mới BioX+- tree tỏ ra ưu việt hơn BioX-tree trong hầu hết các loại truy vấn theo các trục Xpath và các truy vấn thông thường. Các thực nghiệm đã sử dụng các bộ dữ liệu tin sinh học từ các nguồn có uy tín và mô tả đa dạng sinh học khác nhau, mục đích để khẳng định tính khách quan và thực tế của phương pháp. Các kết quả nghiên cứu ở chương 3 được công bố trong công trình 5, phần “Danh mục công trình của tác giả”. 105 KẾT LUẬN 1) Những kết quả chính của luận án: Luận án nghiên cứu hướng tiếp cận đánh chỉ số cho dữ liệu tin sinh học kích thước lớn trên định dạng tài liệu XML với mục đích tăng tốc độ thực hiện các truy vấn và xử lý tốt các truy vấn vị từ phức tạp. Kết quả của luận án bao gồm: 1) Đề xuất phương pháp BioX-tree với cấu trúc cải tiến, thêm vào các con trỏ biểu thị mối quan hệ: cha mẹ - con cái, anh em, bổ sung các tham số trong bước chuyển đổi tài liệu XML lên không gian, thiết kế lại các thuật toán chèn, truy vấn mới giúp tăng tốc độ khi thực hiện các truy vấn, xử lý hiệu quả hơn các truy vấn phức tạp. Qua thực nghiệm cho thấy hiệu suất của BioX-tree tốt hơn nhiều so với R- tree trong truy vấn điểm. 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àm giảm nhanh chóng hiệu suất. 2) Đề xuất phương pháp BioX+-tree với những cải tiến thuật toán chèn và truy vấn giúp giảm hơn nữa các bước duyệt cây dư thừa để tối ưu tốc độ thực thi, đồng thời giảm bớt nhược điểm về cầu trúc của cây BioX-tree được đề xuất trong chương 2. Từ các thực nghiệm đã chứng minh việc xây dựng các thuật toán theo các Định lý và Hệ quả đề ra đang mang lại hiệu quả, không chỉ các truy vấn liên quan đến các anh em mà còn và cho các truy vấn thông thường nhờ vào cấu trúc cây tối ưu hơn. 2) Hƣớng phát triển của luận án: (1). Tiếp tục nghiên cứu, đề xuất các phương pháp đánh chỉ số cho dữ liệu tin sinh học với mục tiêu cải thiện hơn nữa hiệu suất truy vấn. 106 (2). Mở rộng nghiên cứu áp dụng vào các hệ thống CSDL có hỗ trợ R-tree như SQL server, Big data để có thể thử nghiệm trên các CSDL tin sinh học kích thước rất lớn. 107 Danh mục các công trình của tác giả 1 Dinh Duc Luong, Hoang Do Thanh Tung, “A Survey on Indexing for Gene Database”, International Clustering Workshop: Teaching, Research, Business, December 27-29, 2014, pp. 50-54. 2 Hoang Do Thanh Tung, Dinh Duc Luong, “A proposed Indexing Method for Treefarm database”, International Conference on Information and Convergence Technology for Smart Society, Vol.2 No.1, Jan, 19-21,2016 in Ho Chi Minh, Vietnam, pp. 79-81. 3 Vương Quang Phương, Lê Thị Thùy Giang, Đinh Đức Lương, Ngô Văn Bình, Hoàng Đỗ Thanh Tùng, “Giải pháp công nghệ quản lý nguồn gốc giống heo”, Kỷ yếu Hội thảo Quốc gia lần thứ XXI:Một số vấn đề chọn lọc của CNTT và TT, Thanh Hóa, 27-28/7/2018, Tr. 110-116. 4 Hoang Do Thanh Tung, Dinh Duc Luong, “An Improved Indexing Method for Xpath Queries”, Indian Journal of Science and Technology, Vol 9(31), DOI:10.17485/ijst/2016/v9i31/92731, August 2016, pp. 1-7. 5 Dinh Duc Luong, Vuong Quang Phuong, Hoang Do Thanh Tung, “A new Indexing technique BioX + -tree for Bioinformatic XML data compression”, International Journal of Engineering and Advanced Technology (IJEAT), ISSN:2249-8958, Volume-8, Issue-5, june 2019, pp. 1-7. 108 Tài liệu tham khảo Tài liệu tiếng Việt [1]. Vương Quang Phương, Hoàng Đỗ Thanh Tùng, Phạm Thị Tiên, Đặng Thị Thu Trang: Một phương pháp tiền xử lý dữ liệu sinh học dựa trên công nghệ dữ liệu lớn kết hợp kho dữ liệu, Hội thảo Quốc gia lần thứ XIX: Một số vấn đề chọn lọc của CNTT và truyền thông – Hà Nội, 1-2/10/2016. Tài liệu tiếng Anh [2]. Alghamdi NS, Rahayu W, Pardede E. Semantic-based Structural and Content indexing for the efficient retrieval of queries over large XML data repositories. Journal of Future Generation Computer Systems. 212-31, 2014 [3]. Altschul SF, Gish W, Miller W, Myers EW, Lipman DJ.: Basic local alignment search tool, National Center for Biotechnology Information, National Library of Medicine, National Institutes of Health, Bethesda, MD (1990) [4]. Hoang Do Thanh Tung, , Keun Ho Ryu. “A ONCE-Updating Approach on Moving Object Indexing Methods”. Proceedings of the International Workshop on Conceptual Modeling for GIS, 25th ER2006 conference, Arizona, America, Lecture Notes in Computer Science, Vol.4231, pp.140- 149, Springer-Verlag, November, 2006. [5]. A. R. Schmidt, F. Waas, M. L. Kersten, D. Florescu, I. Manolescu, M.J. Carey, and R. Busse: The XML Benchmark Project. Technical Report INSR0103, CWI, Amsterdam, The Netherlands, April 2001 [6]. Altschul SF, Madden T, Alejandro A, Schaffer A, Zhang J, Zhang Z, Miller W, Lipman DJ.: Gapped BLAST and PSI-BLAST: a new generation of protein database search programs, National Center for Biotechnology Information, National Library of Medicine, National Institutes of Health, Bethesda, MD (1997) 109 [7]. Arion, A., A. Bonifati, I. Manolescu, A. Pugliese. XQueC: A query- conscious compressed XML database. ACM Trans. Internet Technol., 7: 10, 2007. [8]. Arroyuelo, D., F. Claude, S. Maneth, V. M¨Akinen, G. Navarro, K. Nguyen, J. Sir´En, N. V¨Alim¨Aki. Fast In-Memory XPath Search using Compressed Indexes. In Proceedings of the IEEE Twenty-Sixth International Conference on Data Engineering (ICDE 2010), California, USA, 2010. [9]. B. Salzberg and V.J. Tsotras. A Comparison of Access Methods for Time- Evolving Data. ACM Computing Surveys, Vol.31, No.2, June 1999. [10]. Baxevanis, A.D. and Ouellette, B.F.F., eds., Bioinformatics: A Practical Guide to the Analysis of Genes and Proteins, third edition. Wiley, ISBN 0- 471-478784, 2005. [11]. Berglund, A.Boag, S. Chamberlin, D. Fernandez, M.F.Kay, M.Robie “XML Path Language (XPath) 2.0” Technical Report W3C Working Draft, Version 2.0,World Wide Web Consortium, 2002. [12]. C. M. Procopiuc, P. K. Agarwal, and S. Har-Peled. STAR-Tree: An Efficient Self-Adjusting Index for Moving Objects. In Proceedings of the Workshop on Algorithm Engineering and Experiments, pp.178–193, ALENEX, January 2002. [13]. Califano A, Rigoutsos I.: FLASH: a fast look-up algorithm for string homology, International conference on intelligent systems for molecular biology, Bethesda, MD, 56-64, 1993 [14]. Cao X, Li SC, Ooi BC, Tung AKH.: Piers: an efficient model for similarity search in DNA sequence databases. Sigmod record, Special Issue (2004) [15]. Cheng, J., W. Ng. XQZip: Querying Compressed XML using Structural Indexing. International Conference on Extending Data Base Technology (EDBT) , 2004. [16]. Chun Zhang, Jeffrey Naughton, David DeWitt, Qiong Luo, and Guy Lohman, “On supporting containment queries in relational databases management systems” In Proceedings of the 2001 ACM SIGMOD 110 Conference, Santa Barbara, CA, May 2001. [17]. Chung J, Min CW, Shim K. APEX: an adaptive path index for XML data. Proceedings of ACM SIGMOD; 12132, 2002 [18]. Claverie, J.M and C. Notredame, Bioinformatics for Dummies. Wiley, ISBN 0-7645-1696-5, 2003 [19]. D. Pfoser, C. S. Jensen, and Y. Theodoridis. Novel Approaches in Query Processing for Moving Object Trajectories. In Proceedings of the 6th International Conference on Very Large Data Bases, pp.395–406, September 2000. [20]. D.Megginson.SAX: A Simple API for XML. 2000. [21]. Dietz P. Maintaining order in a linked list. Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, ACM. 122-127, 1982 [22]. Dietz, P.F and Sleator, D.D “Two algorithms for maintaining order in a list ”. In Conference Revord of the 19th Annual ACM Symposium on Theory of Computing (STOC). ACM Press, 1987. [23]. Durbin, R., S. Eddy, A. Krogh and G. Mitchison, Biological sequence analysis. Cambrige University Press. ISBN 0-521-62971-3, 1998 [24]. Fondrat C, Dessen P.: A Rapid access motif database (RAMdb) with a search algorithm for the retrieval patterns in nucleic acids or protein databanks. Comput Appl Biosci, 11(3): 273-279, 1995 [25]. G. Gottlob, C. Koch and R.Pichler, “Efficient algorithms for processing XPath queries” In VLDB Conference 2002, HongKong, 2002. [26]. G. Kollios, D. Gunopulos, and V. J. Tsotras. On Indexing Mobile Objects. In Proceedings of the ACM Symposium. on Principles of Database Systems, PODS, pp.261–272, June 1999. [27]. Grust T, Keulen MV, Teubner J. Accelerating XPath evalua-tion in any RDBMS. Journal of ACM Trans Database Syst. 91-131, 2004 111 [28]. Grust T, Van Keulen M. Tree awareness for relational DBMS kernels: Staircase join. Journal of Lecture Notes in Computer Science. 231-45, 2003 [29]. Greene, D: An implementation and performance analysis of spatial data access methods. Proceedings. Fifth International Conference on Data Engineering. pp. 606–615, 1989 [30]. Guttman. R-Trees: A Dynamic Index Structure For Spatial Searching. In Proceedings of ACMSIGMOD International Conference on Management of Data, pp.47–57, Boston, June 1984. [31]. H. D. Chon, D. Agrawal, and A. E. Abbadi. Storage and Retrieval of Moving Objects. In Mobile Data Management, pp.173–184, January 2001. [32]. H. Jiang, H. Lu, W. Wang, B. C. Ooi:XR-Tree: Indexing XML Data for Efficient Structural Joins. Proc. the 19th International Conference on Data Engineering (ICDE), pages 253-263, 2003 [33]. H. Samet. The Design and Analysis of Spatial Data Structures. Reading, MA:Addison-Wesley, 1990. [34]. Haifeng Jiang, Hongjun Lu, Wei Wang, Beng Chin Ooi.: XR-T ree: Indexing XML Data for Ef cient Structural Joins. Proceedings 19th International Conference on Data Engineering (Cat. No.03CH37405), 2003 [35]. Han JY, Liang ZP, Qian G. A multiple-depth structural in-dex for branching query. Journal of Information and Soft-ware Technology. 928-36, 2006 [36]. Haw S, Lee C. Data Storage Practices and Query Processing in XML Databases: A Survey. International Journal of Knowledge-Based Systems, Elsevier. 1317-40, 2011 [37]. Haw S, Lee C. Node labeling schemes in XML query opti-mization: a survey and trends. Journal of IETE Tech Rev.88-100, 2009 [38]. Hoang Do Thanh Tung, Young Jin Jung, Eung Jae Lee, Keun Ho Ryu. “Moving Point Indexing for Future Location Query”. Proceedings of the International Workshop on Conceptual Modeling for GIS, 23th ER2004 conference, Shanghai, China, Lecture Notes in Computer Science, Vol.3289, 112 pp.79-90, Springer-Verlag, November, 2004. [39]. I. Kamel and C. Faloutsos. Hilbert R-tree: An improved R-tree Using Fractals. In Proceedings of the 20th VLDB Conference, Chile, 1994. [40]. I. T atarinov, S. Viglas, K. Beyer, J. Shanmugasundaram, E. Shekita, and C. Zhang. Storing and querying ordered XML using a relational database system. In SIGMOD, pages 204– 215, 2002. [41]. In-Seon Jeong, Kyoung-Wook Park, Seung-Ho Kang, Hyeong-Seok Lim. An efficient similarity search based on indexing in large DNA databases, Computational Biology and Chemistry 34, 131-13, 2010 [42]. J. Shanmugasundaram et al., “A general technique for querying XML documents using a relational database system” SIGMOD Record, 2001. [43]. J. Tayeb, O. Ulusoy, and O.Wolfson. A Quadtree-Based Dynamic Attribute Indexing Method. The Computer Journal, Vol.41, No.3, pp.185–200, 1998. [44]. Kailing K, Kriegel H-P, Schonauer S, Seidl T.: Efficient similarity search for hierarchical data in large databases. In: Proc 9th int conf on extending database technology (EDBT 2004), Heraklion, Greece, 676-693, 2004 [45]. Kriegel H-P, Schonauer S.: Similarity search in tructured data. In: Proc 5th int conf on data warehousing and knowledge discovery (DaWaK’03), Prague, Czech Republic, Lecture notes in computer science (LNCS), (2003), vol 2737, 309-319, 2003 [46]. Lee HP, Tsai YT, Sheu TF, Tang CT.: An IDC-based algorithm for efficient homology filtration with guaranteed seriate coverage. In: Fourth IEEE symposium on bioinformatics and bioengineering (BIBE’04), Taichung, Taiwan, 200 (2004) [47]. Li Q, Moon B et al. Indexing and querying XML data for regular path expressions. Proceedings of the International Conference on Very Large Data Bases. p. 361-70, 2001 [48]. Lomet and B. Salzberg. Access Methods for Multiversion Data. In Proceedings of ACM SIGMOD Conference, pp.315-324, 1989. 113 [49]. M. Erwig, R.H. Gueting, M. Schneider, and M. Vazirgiannis. Abstract and Discrete Modeling of Spatio-Temporal Data Types. In Proceedings of the 6th ACM International Workshop on Advances in Geographic Information Systems, pp.131-136, 1998. [50]. M. Nascimento, and J. Silva. Towards Historical R-trees. In Proceedings of ACM Symposium on Applied Computing, pp.235-240, Atlanta, USA, February 1998. [51]. Michal Kr´atk´y. Indexing Graph Structured Data. PhD thesis, Faculty of Elec-trical Engineering and Computer Science, Technical University of Ostrava, 2004. [52]. Min, J.K., M.J. Park, C.W. Chung. XPRESS: a queriable compression for XML data. Proceedings of the 2003 ACM SIGMOD international conference on Management of data, ACM, San Diego, California, 122133, 2003. [53]. N. Beckmann, H.P. Kriegel, R. Schneider, and B. Seeger. The R*-tree: An Efficient and Robust Access Method For Points and Rectangles. In Proceedings of ACM-SIGMOD International Conference on Management of Data, pp.322–331, Atlantic City, May 1990. [54]. Nur'Aini Abdul Rashid, Rosni Abdullah, Abdullah Zawawi Haji Talib, Zalila Ali, IEEE.: Fast Dynamic Programming Based Sequence Alignment Algorithm, 2006 [55]. O’Neil P, O’Neil E, Pal S, Cseri I, Schaller G, Westbury N. Ordpaths: insert friendly XML node labels. Proceedings of the 2004 ACM SIGMOD International Conference on Man-agement of Data, SIGMOD ’04, ACM, New York. p. 903-8, 2004. [56]. Ong TH, Tan KL, Wang H.: Indexing genomic databases for fast homology searching. In: Proceedings of the 13th international conference on database and expert systems applications, Aix-en-Provence, France 871-880, 2002. [57]. Ooi BC, Pang HH, Wang H, Wong L, Yu C.: Fast filter-and-refine algorithms for subsequence selection. In: Proceedings of the 6th international database engineering and applications symposium (IDEAS’02), Edmonton, Canada, pp 243–254, July 2002 114 [58]. P. Agarwal, L. Arge, J. Erickson. Indexing Moving Points. Symposium on Principles of Database Systems, 2000. [59]. Pearson WR, Lipman DJ.: Improved tools for biological sequence comparision. Proc Natl Acad Sci USA 85 :2444-2448, 1988 [60]. Q. Li and B. Moon: Indexing and Querying XML Data for Regular Path Expressions. Proc. the 27th International Conference on Very Large Data Bases (VLDB), pages 361-370, 2001 [61]. Q. Li, B. Moon, et al. Indexing and querying XML data for regular path expressions. Proceedings of the International Conference on Very Large Data Bases, 361–370, 2001 [62]. Qian, B., H. Wang, J. Li, H. Gao, Z. Bao, Y. Gao, Y. Gu, L. Guo, Y. Li, J. Lu, Z. Ren, C. Wang, X. Zhang. Path-Based XML Stream Compression with XPath Query Support Web-Age Information Management. Springer Berlin / Heidelberg, 2012. [63]. Quanzhong Li, Bongki Moon, ”Indexing and Querying XML data for Regular Path Expression” In Proceedings of the 27th VLDB Conference, Roma, Italy, 2001. [64]. Rao P, Moon B. PRIX: indexing and querying XML using prufer sequences. Proceedings of ICDE, IEEE; 288300, 2004 [65]. S. Muthukrishnan and S. C. Sahinalp.: Approximate nearest neighbor and sequence comparison with block operations, 2000. [66]. S. Saltenis and C. S. Jensen. Indexing of Moving Objects for Location-Based Services. In Proceedings of the International Conference On Data Engineering, February 2002. [67]. S. Saltenis, C. S. Jensen, S. T. Leutenegger, and M. A. Lopez. Indexing the Positions of Continuously Moving Objects. In Proceedings of SIGMOD, 2000. [68]. S.-Y . Chien, Z. V agena, D. Zhang, V . Tsotras, and C. Zan-iolo. Efficient structural joins on indexed XML documents. International Conference on 115 Very Large Data Bases (VLDB), pages 263– 274, 2002 [69]. Samer Mahmoud Wohoush, Mahmoud Hassan Saheb.: Indexing for Large DNA Database Sequenes, International Journal of Biometrics and Bioinformatics (IJBB), Volume (5) : Issue (4). 2011 [70]. Sebastian Maneth, Diego Arroyuelo, Francisco Claude, Veli Mäkinen, Gonzalo Navarro, Kim Nguyễn, Jouni Sirén, Niko Välimäki: Fast in- memory XPath search using compressed indexes, Software Practice and Experience 45(3), January 2010 [71]. Somaye Nouri Monfared, Hasan Naderi, Mohammad Nazari Farokhi, Nasredin Niazy, Behzad Hosseini Chegeni: XML Retrieval: A Survey, International Journal of Computational Engineering Research (IJCER), ISSN (e): 2250 – 3005, Vol 04 - Issue 8, August 2014 [72]. Sreenivasaiah Pradeep Kumar, Do Han Kim: Current Trends and New Challenges of Databases and Web Applications for Systems Driven Biological Research, Frontiers in Physiology 1:147, December 2010 [73]. T. Grust, M. V. Keulen, and J. Teubner: Accelerating Xpath Evaluation in Any RDBMS. ACM Transactions on Database Systems, Vol. 29, No.1, pages 91-131, 2005. [74]. T. Kahveci, A. Singh Pacific Symposium, MAP.: Searching Large Genome Databases, Biocomputing 8 : 303 - 314. 2003 [75]. T. Sellis, N. Roussopoulos and C. Faloutsos. The R+-Tree: A Dynamic Index for Multi- Dimensional Objects. In Proceedings of the 13rd International Conference on Very Large Data Bases, pp.507-518, Brighton, England, September 1987. [76]. Taha Baydaa, Alwan Raad: Bioinformatics Data Compression and Retrieval Based on XML Structured Indexed Tree, Australian Journal of Basic and Applied Sciences 8(83):35-42, April 2014 [77]. Tamer Kahveci Ambuj K. Singh Department of Computer Science, University of California Santa Barbara .: An Efficient Index Structure for String Databases, CA 93106 {amer,ambuj}cs.ucsb.edu. 2001. 116 [78]. Tatarinov I, Viglas SD, Beyer K, Shanmugasundaram J, Shekita E, Zhang C. Storing and querying ordered XML using a relational database system. Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, SIGMOD ’02, ACM, New York. p. 204-15. 2002 [79]. Tatikonda S, Parthasarathy S, Goyder M. LCS-Trim: dy-namic programming meets XML indexing and querying. Proceedings of the 33rd International Conference on Very Large Data Bases. p. 63-74. 2007 [80]. Theo Haerder and Andreas Reuter. Principles of transaction-oriented database recovery. ACM Comput. Surv., 15(4):287–317, 1983. [81]. Tim Bray, Jean Paoli, C.M. Sperberg-Mc Queen “Extensible Markup Language(XML) 1.0”. W3C Recommendation, 2000. [82]. Tolani, P.M., J.R. Haritsa. XGRIND: A Query-friendly XML Compressor. IEEE 18th international conference on Data Engineering, 2000. [83]. Trißl, Silke and Leser, Ulf. Fast and practical indexing and querying of very large graphs. In SIGMOD '07: Proceedings of the 2007 ACM SIGMOD international conference on Management of data, pages 845–856, New York, NY, USA, 2007 [84]. V. Gaede and O. Gunther. Multidimensional Access Methods. ACM Computing Surveys, Vol.30, No.2, pp.170-231, June 1998. [85]. V.J.Tsotras, N. Kangelaris. The Snapshot Index, an I/O-Optimal Access Method for Timeslice Queries. Information Systems, Vol.20, No.3, 1995. [86]. Willams HE.: Fast ranking strategies for genomic databases, 1997 [87]. Williams H, Zobel J.: Indexing and retrieval for genomic databases. IEEE Trans Knowl Data Eng, 14(1):63–78, 2002 [88]. Xianyang Jiang, Peiheng Zhang, Xinchun Liu, Stephen S.-T.Yau.: Survey on index based homology search algorithms, Springer Science + Business Media, LLC (2007) 117 [89]. Y. Feng, A. Makinouchi: Efficient Evaluation of Partially- dimensional Range Queries Using Adaptive R*-tree. Proc. the 17th International Conference on Database and Expert Systems Applications (DEXA), LNCS 4080, pages 687-696, Springer-Verlag, 2006 [90]. Yannis Theodoridis, Michael Vazirgiannis, Timos Sellis. Spatio-Temporal Indexing for Large Multimedia Applications. International Conference on Multimedia Computing and Systems, 1996. [91]. Yaokai Feng, and Akifumi Makinouchi: A New Structure for Accelerating XPath Location Steps. IAENG International Journal of Computer Science, 38:2, IJCS_38_2_03, 2006. [23]. Yufei Tao and Dimitris Papadia. Efficent Historical R trees. In Proceedings of the 13rd IEEE Conference on Scientific and Statistical Database Management, pp.223-232, Fairfax Virginia, July, 2001. [93]. Yufei Tao and Dimitris Papadias. MV3R-Tree: A Spatio-Temporal Access Method for Timestamp and Interval Queries. In Proceedings of the 27th Very Large Data Bases Conference, pp.431-440, Rome, September, 2001. [94]. Yufei Tao, D. Papadias, J. Sun. The TPR*-Tree: An Optimized Spatio- Temporal Access Method for Predictive Queries. In Proceedings of the 29th Very Large Data Bases Conference, 2003. [95]. Zhang C, Naughton J, DeWitt D, Luo Q, Lohman G. On supporting containment queries in relational database man-agement systems. Journal of ACM SIGMOD Record, ACM. 425-36. 2001