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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:27

Thêm vào BST

Báo xấu

37
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đề tài nghiên cứu phương pháp đánh chỉ số dựa trên phương pháp R-tree đế nhằm tăng hiệu quả các truy vấn Xpath trên dữ liệu XML, thông qua dữ liệu trung gian được chuyển đổi về dạng tọa độ số của các tags. Dữ liệu XML mục tiêu là từ một tài liệu XML tin sinh học, sử dụng phương pháp chuyển đổi dữ liệu văn bản có cấu trúc XML về dữ liệu dạng số mà biểu diễn được trên không gian 2 chiều (có thể mở rộng lên nhiều chiều).

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tóm tắt luận án Tiến sĩ Toán học: Phương pháp đánh chỉ số cho tài liệu XML tin sinh học dựa trên R-Tree

BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ ------------------------------- ĐINH ĐỨC LƢƠNG PHƢƠNG PHÁP ĐÁNH CHỈ SỐ CHO TÀI LIỆU XML TIN SINH HỌC DỰA TRÊN R-TREE Chuyên ngành: Cơ sở toán học cho tin học Mã số: 9 46 01 10 TÓM TẮT LUẬN ÁN TIẾN SĨ TOÁN HỌC Hà Nội - 2019
Công trình đƣợc hoàn thành tại: Học viện Khoa học và Công nghệ - Viện Hàn lâm Khoa học và Công nghệ Việt Nam Ngƣời hƣớng dẫn khoa học 1: TS. Hoàng Đỗ Thanh Tùng Ngƣời hƣớng dẫn khoa học 2: PGS.TS. Đặng Hữu Đạo Phản biện 1: Phản biện 2: Phản biện 3: Luận án được bảo vệ trước Hội đồng chấm luận án tiến sĩ, họp tại Học viện Khoa học và Công nghệ - Viện Hàn lâm Khoa học và Công nghệ Việt Nam vào hồi giờ, ngày tháng năm Có thể tìm hiểu luận án tại: - Thư viện Học viện Khoa học và Công nghệ - Thư viện Quốc gia Việt Nam
Danh mục các công trình của tác giả liên quan đến Luận án 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 (SCOPUS). 5 Dinh Duc Luong, Vuong Quang Phuong, Hoang Do Thanh Tung, “A new Indexing technique XR+tree for Bioinformatic XML data compression”, International Journal of Engineering and Advanced Technology (IJEAT), ISSN: 2249-8958 (Online), Volume-8, Issue-5, June 2019, pp. 1-7 (SCOPUS).
MỞ ĐẦU Tài liệu XML là dữ liệu văn bản có cấu trúc, hay còn gọi là dữ liệu bán cấu trúc, chúng đã phổ biến hàng thập kỷ nay vì khả năng lưu trữ dữ liệu rất linh hoạt và dễ dàng chia sẻ, sử dụng qua internet. Trước đây, các tài liệu XML thường có kích thước không lớn, nhưng những năm gần đây bắt đầu xuất hiện các tài liệu XML tin sinh học có kích thước rất lớn có thể lên tới Giga, Tera Byte bởi sự phát triển như vũ bảo của công nghệ sinh học trong kỷ nguyên này. Dữ liệu đó có thể tìm thấy từ các nguồn dữ liệu uy tín như SRA (công khai các trình tự được giải mã), NCBI Genome (các loài đã được giải trình tự), ensembl.org (tổng hợp rất nhiều dữ liệu thành BioMart)… Các tài liệu XML tin sinh học là dữ liệu gồm có 2 phần, dữ liệu sinh học (DNA, Protein, phân loài,…) và các dữ liệu mô tả dữ liệu sinh học. Cấu trúc dữ liệu được định nghĩa theo các thẻ (tag) và các cấu trúc dữ liệu này thường linh hoạt, có thể khác biệt bởi vì chúng được tùy biến theo các cá nhân, tổ chức sinh học thực hiện. Vì có kích thước lớn như vậy, các tài liệu cơ bản phải lưu trữ và khai thác trên đĩa cứng, hoặc trong hệ thống lưu trữ phân tán, trước khi có thế truy xuất 1 phần nhỏ để đưa lên bộ nhớ chính (RAM) mỗi khi cần phân tích sâu hơn. Cơ chế truy xuất đĩa cứng là tuần tự và thời gian tiêu tốn chậm hơn rất nhiều lần so với truy xuất trên RAM. Do vậy, các phương pháp truy vấn cần truy xuất đĩa cứng luôn tìm cách sao cho tối thiểu số lần cần truy xuất đĩa cứng và tối đa tận dụng bộ nhớ chính, như là Cache, Buffer. Các truy xuất thực thi theo thuật toán của các truy vấn đặc thù, được thiết kế để đạt kết quả mong muốn trong thời gian ngắn và phù hợp với truy vấn. Ví dụ: 1. Truy vấn Xpath cho 01 tài liệu XML (tìm kiếm chính xác): trích xuất tất cả các dữ liệu có tags có quan hệ cùng nguồn gốc/anh em với nhau của 1 loại Chuột Bạch hoặc trích xuất toàn bộ các dữ liệu là hậu duệ của heo giống Châu Phi. 1. Truy vấn tương đồng cho dữ liệu các đoạn DNA (tìm kiếm xấp xỉ): tìm kiếm tất cả các Gen tương đồng với 1 đoạn Gen mẫu của một loài mới. Giải pháp truyền thống cho các truy vấn như trên là lựa chọn và cài đặt các phương pháp đánh chỉ số (indexing) phù hợp một số loại dữ liệu và truy vấn đặc thù. Các phương pháp này có nhưng gặp nhiều hạn chế với dữ liệu văn bản kích thước lớn như vậy. Với dữ liệu văn bản, kích thước dữ liệu chỉ số sinh ra thường cũng rất lớn, thậm chí lớn hơn nhiều so với dữ liệu gốc, như vậy gây nên các vấn đề: (1) lưu trữ dữ liệu chỉ số này là vấn đề nan giải, (2) Nén dữ liệu và khai thác dữ liệu đồng thời kém hiệu quả. Hơn nữa, nếu chỉ số là dữ liệu văn bản thì vấn đề tốc độ truy vấn vẫn là vấn đề khó giải quyết. Do vậy, các nghiên cứu gần đây về đánh chỉ số một tài liệu XML có xu hướng: - Tách tài liệu XML thành 2 phần dữ liệu và áp dụng các phương pháp đánh chỉ số khác nhau cho phù hợp với dạng dữ liệu và loại truy vấn đặc thù. Cụ thể là: 1. Phương pháp đánh chỉ số dữ liệu cấu trúc (dữ liệu các thẻ) và hỗ trợ các truy vấn đặc thù như Xpath. 1
2. Phương pháp đánh chỉ số dữ liệu sinh học (như các đoạn DNA) và hỗ trợ các truy vấn đặc thù như tìm kiếm các chuỗi DNA tương đồng. - Chuyển đổi dữ liệu văn bản gốc về dạng số nhằm mục đích: 1. Giảm kích thước dữ liệu gốc ban đầu. 2. Áp dụng các phương pháp đánh chỉ số phù hợp. 3. Cải thiện tốc độ các truy vấn. Các vấn đề cần giải quyết rất rộng gồm tin học và sinh học, vì vậy nghiên cứu của luận án tập trung giải bài toán Phương pháp đánh chỉ số hỗ trợ cho các truy vấn đặc thù về tốc độ bằng cách giảm số lần cần truy cập đĩa cứng mà vẫn đạt được kết quả mong đợi. Kết quả luận án đã giải bài toán Phương pháp đánh chỉ số dữ liệu cấu trúc (dữ liệu các thẻ) và hỗ trợ các truy vấn Xpath. Ngoài ra, với bài toán Phương pháp đánh chỉ số dữ liệu sinh học (như các đoạn DNA) và hỗ trợ các truy vấn đặc thù như tìm kiếm các chuỗi DNA tương đồng, luận án đã khảo sát được phương pháp và có định hướng cho nghiên cứu tiếp theo. Cụ thể mục tiêu và kết quả của luận án như sau. Mục tiêu thực hiện của luận án: - Nghiên cứu phương pháp đánh chỉ số dựa trên phương pháp R-tree đế nhằm tăng hiệu quả các truy vấn Xpath trên dữ liệu XML, thông qua dữ liệu trung gian được chuyển đổi về dạng tọa độ số của các tags. Dữ liệu XML mục tiêu là từ một tài liệu XML tin sinh học. - Sử dụng phương pháp chuyển đổi dữ liệu văn bản có cấu trúc XML về dữ liệu dạng số mà biểu diễn được trên không gian 2 chiều (có thể mở rộng lên nhiều chiều). Mục tiêu là nhằm giảm kích thước dữ liệu gốc và áp dụng được phương pháp đánh chỉ số đề xuất. Kết quả đạt được của luận án như sau: - Bằng thực nghiệm đã chỉ ra rằng phương pháp chuyển đổi dữ liệu XML tin sinh học về dữ liệu không gian là có hiệu quả về giảm kích thước với tỷ lệ khá tốt nói chung. Tuy nhiên, tỷ lệ nén không có có kểt quả tốt đồng đều giữa các thực nghiệm với dạng tài liệu XML tin sinh học DNA, Protein, và cây phân loài… - Đề xuất được phương pháp đánh chỉ số BioX-tree và phương pháp mở rộng BioX+ tree. Các phương pháp đề xuất (cải tiến phương pháp R-tree) đã chứng tỏ hiệu quả hơn phương pháp R-tree khi áp dụng để đánh chỉ số dữ liệu chuyển đồi từ dữ liệu XML qua các thực nghiệm. Đặc biệt, các truy vấn anh em, hoặc các truy vấn có tận dụng truy vấn anh em trong thuật toán, có kết quả tốt. Lý thuyết và thực nghiệm đã chứng mình được rằng: các truy vấn đã giảm được các bước duyệt cây dư thừa trên cây chỉ số (lưu trữ trên đĩa cứng), nhờ đó giảm số lần truy xuất trên đĩa cứng để lấy dữ liệu lên bộ nhớ chính, mà vẫn có được kết quả như mong muốn. 2
Chƣơng 1. TỔNG QUAN 1.1. Tin sinh học và các nguồn dữ liệu 1.1.1. Tin sinh học Tin sinh học (BioInformatics) là một lĩnh vực khoa học sử dụng các công nghệ của các ngành toán học ứng dụng, tin học, thống kê, khoa học máy tính, sinh học, hóa học, vật lý… và toán sinh học. Tin sinh học thường gắn liền với sinh học tính toán (computational biology) hoặc sinh học hệ thống (system biology). 1.1.2. Các nguồn dữ liệu - Cơ sở dữ liệu NCBI - Cơ sở dữ liệu EMBL/EBI - Cơ sở dữ liệu DDBJ 1.1.3. Vấn đề tin sinh học và cơ sở dữ liệu sinh học Có thể thấy rằng cơ sở dữ liệu sinh học chứa đựng một lượng khổng lồ các thông tin như: chuỗi DNA, protein, chức năng, cây phân loài,... và được bổ sung liên tục làm cho kích thước của chúng tăng lên một cách nhanh chóng, đặc biệt với sự phát triển của các kỹ thuật sinh học hiện nay. Cơ sở dữ liệu sinh học có thể được lưu trữ trên máy tính, tuy nhiên, các bài toán tìm kiếm hay truy vấn dữ liệu trên CSDL lớn như trên thường khó thực hiện được bởi các yếu tố liên quan đến không gian và thời gian truy xuất. Hiện nay bài toán đánh chỉ số để tăng tốc độ xử lý dữ liệu tin sinh học đang được rất nhiều nhà nghiên cứu quan tâm, và có ý nghĩa lớn trong thực tế. 1.2. Các phƣơng pháp đánh chỉ số dữ liệu sinh học và tin sinh học 1.2.1. Chỉ số và mô hình bộ nhớ ngoài Cơ sở dữ liệu hoàn chỉnh thường không phù hợp với bộ nhớ chính (RAM) của hệ thống máy tính. Do đó, cơ sở dữ liệu hoàn chỉnh thường được lưu trữ trên các ổ đĩa cứng. Truy cập vào ổ đĩa này sẽ chậm hơn so với truy cập vào bộ nhớ chính hơn 100.000 lần, đó là nút thắt cổ chai của các hệ quản trị cơ sở dữ liệu. Đo lường hiệu quả của một thuật toán chính là tính toán số lượng I/O để thực hiện một hành động. Chỉ số (index) trong cơ sở dữ liệu là một cấu trúc tra cứu đặc biệt mà công cụ tìm kiếm cơ sở dữ liệu có thể sử dụng để tăng nhanh thời gian và hiệu suất truy xuất dữ liệu thông qua việc giảm thiểu số lượng các block mà chúng ta cần phải truy cập để trả lời một câu truy vấn, đồng thời giảm thiểu số lượng các block được sử dụng để lưu trữ cơ sở dữ liệu nếu có thể. 1.2.2. Các phƣơng pháp đánh chỉ số cho dữ liệu sinh học Có hai nhóm chính: - Nhóm 1: Các phương pháp thực hiện so sánh các trình tự bằng cách so sánh các phân đoạn trong chuỗi có thể và tối ưu hóa sự giống nhau. - Nhóm 2: Các phương pháp có sử dụng sự biến đổi đặc biệt để xây dựng chỉ số. 3
1.2.3. Các phƣơng pháp đánh chỉ số cho dữ liệu tin sinh học Có rất nhiều loại tài liệu tin sinh học được lưu trữ dưới nhiều định dạng khác nhau, trong luận án này, tác giả sẽ tập trung vào dữ liệu dạng XML có kích thước lớn, đây là một trong những chuẩn đầu ra cho người dùng có thể tải về từ các nguồn dữ liệu nêu phía trên. Các phương pháp XGrind [78], Xpress [52], XQzip [15], XQueC [7], Arroyuelo et al. [8], Qian et al. [62], Dietz [21] Li and Moon in XISS [61] đã được tác giả nghiên cứu và sẽ trình bày phân tích kĩ hơn các ưu nhược điểm ở các phần tiếp theo. 1.3. Phƣơng pháp đánh chỉ số tài liệu XML 1.3.1. Tài liệu XML và Xpath - Tài liệu XML: XML (eXtensible Markup Language) [77] là một mô hình dữ liệu phân cấp có nguồn gốc SGML, nó cho phép mô hình hóa một tài liệu như một cấu trúc cây. - Xpath: Cấu trúc 1 tài liệu XML có thể hình dung như 1 cái cây với nhiều cành và nhánh nhỏ khác nhau. Một trục cho biết node nào liên quan đến node bối cảnh, nên được đưa vào tìm kiếm. Đặc tả XPath [11] liệt kê một họ gồm 13 trục trong Bảng 1.1: Bảng 1.1: Các trục Xpath Tên trục Mô tả Self Bản thân node bối cảnh parent Cha mẹ của node bối cảnh, nếu tồn tại child Con cái của node bối cảnh, nếu tồn tại ancestor Tổ tiên của node bối cảnh, nếu tồn tại ancestor-or-self Tổ tiên của node bối cảnh và chính nó descendant Hậu duệ của node bối cảnh descendant-or-self Hậu duệ của node bối cảnh và chính nó following Các node trong tài liệu XML sau node bối cảnh, không bao gồm con cháu following-sibling Các node anh em sau node bối cảnh preceding Các node trong XML trước node bối cảnh, không bao gồm tổ tiên preceding-sibling Các anh em trước của node bối cảnh attribute Thuộc tính của node bối cảnh namespace Không gian tên node bối cảnh trực thuộc Vị từ cũng có thể được xác định ở mỗi bước trong đường dẫn để hạn chế tập hợp các node xuất phát tại một bước. Nói cách khác, các vị từ cho phép phân định chính xác hơn các dữ liệu quan tâm, dẫn đến các kết quả nhỏ hơn và có thể sử dụng nhiều hơn. Một số phương pháp đánh chỉ số được mô tả dưới đây: 1.3.1.1. Đánh số trên lược đồ Tài liệu XML sẽ được xây dựng lên dạng cây với quan hệ phân cấp cha con, sau đó các tag name tương ứng sẽ được đánh 2 chỉ số theo quy tắc duyệt cây theo giá trị trước, duyệt cây theo giá trị sau (cặp giá trị này sẽ tạo thành NodeID) và đánh số thứ tự cho từng tag name của tài liệu XML [22][63]: - Duyệt cây theo giá trị trước (pre order): là thứ tự đọc tuần tự từ trên xuống dưới của các node, tức là các node sẽ được đánh số tăng dần từ trên xuống dưới cây cho đến hết. 4
- Duyệt cây theo giá trị sau (post order): là thứ tự đọc tuần tự được đánh số tăng dần từ trái qua phải trên cây. 1.3.1.2. Phép nối có cấu trúc Cách đơn giản nhất để cải tiến và đánh giá các truy vấn đường dẫn là chia các biểu thức lớn thành nhiều biểu thức nhỏ hơn (gọi là biểu thức con) và thực hiện tìm kiếm kết quả ở các bước con đó. Hạn chế của nó là chúng ta cần xác định mối quan hệ A-D cho từng cặp node, có thể chúng phải tìm rất nhiều lần và lặp đi lặp lại việc xem xét một phần tử trong các bước khác nhau, điều này gây tốn chi phí tài nguyên và thời gian không cần thiết. 1.3.1.3. Chuyển đổi lên không gian đa chiều Cách tiếp cận này cố gắng chuyển đổi các đường dẫn và mối quan hệ A-D từ tài liệu XML đầu vào thành các bộ dữ liệu đa chiều. Ý tưởng chính là để tránh các phép nối có cấu trúc có thể không tối ưu với nhiều trường hợp đa dạng gây chậm khi thực hiện, và cũng là để tận dụng các cấu trúc dữ liệu đa chiều đang tỏ ra hiệu quả hơn như trên cây R-tree. Các công trình trong [37] và [51] đề xuất một phương pháp lập chỉ số mới cho các cây XML dựa trên các bộ dữ liệu đa chiều gọi là MDX (Multidimensional Approach to Indexing XML). 1.3.1.4. Ánh xạ sang cơ sở dữ liệu quan hệ Trong [36] trình bày một phương pháp được thiết kế đặc biệt cho các truy vấn Xpath và các biểu thức đường dẫn, trong đó biểu diễn các node của file XML đầu vào với 5 chiều: entry(E) = {pre(E); post(E); par(E); att(E); tag (E)}. Với một node E, pre và post là giá trị duyệt cây theo giá trị trước, duyệt cây theo giá trị sau; par là giá trị duyệt cây theo giá trị trước của node cha mẹ của node E; att là cờ trạng thái, tag chứa tag name của node. Việc truy vấn Xpath sẽ dựa trên cơ sở của truy vấn cửa sổ và biểu diễn dưới dạng truy vấn SQL (Structured Query Language). Vì các node được biểu diễn trong không gian 5 chiều nên giải pháp đề xuất này sử dụng R-tree để đánh chỉ số vì chúng được nhiều nghiên cứu đánh giá là có kết quả tốt trong truy vấn Xpath. 1.4. Phƣơng pháp R-tree 1.4.1. Khái niệm R-tree Phương pháp R-tree được xây dựng để truy xuất nhanh các vùng không gian, bằng cách chia nhỏ không gian thành các vùng nhớ và tạo chỉ số cho các vùng không gian nhớ nhỏ này, sau đó áp dụng lý thuyết cây đồ thị để quản lý. R-tree là phương pháp phân chia không gian dữ liệu thành các khố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 5
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, 6
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 7
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ả”. 8
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ó. 9
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. 10
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. 11
Đầ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. Tìm node anh em của entry E, N’ được tìm thấy 2. if (N’ còn chỗ trống để thêm entry e) then 3. Thêm entry E vào N’ 4. else 5. Tìm ngược từ dưới lên trên đến khi thấy node cha Q. 6. Đi qua đường dẫn bên phải gần nhất từ node cha Q để đến node P có level 1 7. if node không là lá P không đầy 8. entry E sẽ được thêm vào node lá trong P 9. else 10. 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. 12. endif 13. 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 12
Đầ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 13
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 14
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 15
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 16
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 17