MultiBooks - Tổng hợp IT - PC part 12

Tham khảo tài liệu multibooks - tổng hợp it - pc part 12, công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
MultiBooks - Tổng hợp IT - PC part 125. Hình 2.18 chỉ ra cách làm không đúng khi chèn chữ nhật R11. Tiếp cận nàykhông khả thi vì nút biểu diễn nhóm chứa chữ nhật R11 có thể là chỉ chứa duyError!nhất một chữ nhật. 2.5.2 Xoá trong cây R-Trees Việc xóa các đối tượng từ cây R-Trees có thể gây ra một nút trong cây R-Tree trở nên thiếu hụt (underflow). Nhắc lại rằng một R-Tree bậc k phải bao gồm ít nhất K/2 hình chữ nhật trong nó. Khi chúng ta xoá một hình chữ nhật từ một R-Tree, chúng ta phải đảm bảo rằng nút đó không bị thiếu hụt. Ví dụ, xem xét R-Trees như hình 2.15 trình bày trên. Giả thiết chúng ta muốn xoá chữ nhật R9. Nút chứa R9 chỉ còn lại một nút trong nó nếu thực hiện xoá R9, kết quả là nút này sẽ phảnánh một điều kiện hụt. Trong trường hợp này chúng ta phải tạo ra nhóm logic mới.Một khả năng là sắp xếp lại các nhóm như sau: Group Rectangles G1 R1, R2, R3 G2 R4, R6, R7 G3 R5, R8Cây R mới là kết quả của việc xóa nút R9, nó được thể hiện trên hình 2.19. Error!2.6 So sánh các cấu trúc dữ liệuTrong chương này ta đã khảo sát 4 loại cấu trúc dữ liệu: cây k-d, cây tứ phân điểm,cây tứ phân MX và cây R. Mỗi chúng đều có ưu điểm và nhược điểm nhất định.· Cây tứ phân điểm rất dễ cài đặt. Tuy nhiên, cây tứ phân điểm có k nút thì cóthể có độ cao là k, như vậy làm tăng độ phức tạp cho chèn và tìm kiếm (nó có thểlà O(k)). Hơn nữa mỗi so sánh đòi hỏi so sánh hai tọa độ.Việc xóa nút trong câyloại này là khá khó khăn. vì việc tìm kiếm nút ứng viên thay thế cho nút đang xóathông thường là không đơn giản. Cuối cùng truy vấn khoảng trong cây này cầnO(2Ön), n là tổng số bản ghi trong cây.· Cây k-d rất dễ cài đặt. Tuy nhiên, cây k-d chứa k nút có thể có độ cao k, dovậy chèn và tìm kiếm có thể phức tạp. Trong thực tế đường dẫn từ gốc tới lá củacây loại này dài hơn trong cây tứ phân điểm bởi vì cây này là cây nhị phân. Độphức tạp tồi nhất của tìm kiếm dải trong cây k-d là: Error!. Khi k=2, thì độ phức tạp còn Error!như cây tứ phân điểm.· Cây tứ phân MX đảm bảo có độ cao nhất là O(n), trong đó vùng được biểudiễn có (2nx2n) tế bào. Nói cách khác việc chèn, xóa và tìm kiếm trong cây loại nàycần thời gian là O(n). Tìm kiếm dải của cây này rất hiệu quả - O(N+2h), trong đó Nlà tổng số điểm kết quả truy vấn và h là độ cao của cây.· Tương tự với cây R. Tuy nhiên, cây R có thể có nhiều chữ nhật lưu trongcùng nút, nó phù hợp với xâm nhập đĩa từ bằng giảm độ cao của cây.· Một bất lợi của cây R là các chữ nhật bao kết hợp với các nút khác nhau cóthể phủ lên nhau. Như vậy, việc tìm kiếm trong cây R thay vì đi theo một vết nhưcác cây khác, là phải đi theo nhiều vết trong cây. Trường hợp này lại làm tăng sốlần thâm nhập đĩa.· Tổng thể, cây R hiệu quả hơn cây k-d và cây tứ phân điểm trong các ứngdụng đa phương tiện bởi vì ứng dụng loại này đòi hỏi dung lượng đĩa rất lớn phảixâm nhập. Tuy nhiên nếu chỉ số nhỏ thì sử dụng cây tứ phân MX sẽ hiệu quả hơn.Chương 3CƠ SỞ DỮ LIỆU ẢNHChương này sẽ trình bày CSDL ảnh là gì? Sự khác nhau về truy vấn giữa CSDLảnh với CSDL văn bản.Các định nghĩa trừu tượng về nội dung ảnh được đề xuất. Mô tả nội dung ảnh cóthể thực hiện bằng tay hay tự động. Cả hai trường hợp đều cần cấu trúc dữ liệu đểlưu trữ. Một vài kỹ thuật xử lý ảnh được khảo sát.Ba kỹ thuật tổng quát để hiện thực CSDL ảnh sẽ được trình bày. Chúng bao gồm,thứ nhất, CSDL ảnh được cài đặt bằng cách mở rộng mô hình quan hệ theo phươngpháp đối tượng-quan hệ. Thứ hai, cài đặt bằng các cấu trúc dữ liệu n chiều như môtả trong chương trước. Cuối cùng là cài đặt bằng phương pháp biến đổi ảnh.Vài chục năm gần đây nhiều cơ quan tham gia thu thập dữ liệu ảnh. NASA thuthập lượng lớn ảnh trái đất. US và nhiều nước khác lưu trữ ảnh hộ chiếu. Các bệnhviện có vô số ảnh chụp X quang và ảnh cắt lớp.Trong mô hình dữ liệu quan hệ truy vấn thường thực hiện với văn bản. TrongCSDL ảnh, với yêu cầu tìm ảnh của ai đó thì câu truy vấn là “Cho trước ảnh mẫu,hãy tìm kiếm mọi ảnh trong CSDL gần giống ảnh mẫu và cho biết các thuộc tínhcủa ảnh cho lại”. Hai đặc tính quan trọng của truy vấn này là: câu truy vấn có ảnhkèm theo. Thứ hai, truy vấn hỏi ảnh “tương tự”. ,Trong trường hợp này phải xácđịnh thế nào là tương tự.3.1 Ảnh thôPhát biểu phi hình thức thì nội dung ảnh bao gồm các đối tượng trong ảnh mà tacho nó là quan trọ ...