intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Báo cáo nghiên cứu khoa học: " Ứng dụng cây QR tạo chỉ mục trong cơ sở dữ liệu không gian"

Chia sẻ: Nguyễn Phương Hà Linh Halinh | Ngày: | Loại File: PDF | Số trang:8

Thêm vào BST
Báo xấu
93
lượt xem 7
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài báo này đề cập đến khái niệm và một số phương pháp đánh chỉ mục trong cơ sở dữ liệu không gian (spatial datadase – SDB). Là một trong những mô hình cơ sở dữ liệu được quan tâm hiện nay, SDB cho phép xử lý các đối tượng dữ liệu không gian, chẳng hạn dữ liệu bản đồ, dữ liệu multimedia...

Chủ đề:

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

Lưu

Nội dung Text: Báo cáo nghiên cứu khoa học: " Ứng dụng cây QR tạo chỉ mục trong cơ sở dữ liệu không gian"

  1. Tạp chí Khoa học ĐHQGHN, Khoa học Tự nhiên và Công nghệ 27 (2011) 14-21 Ứng dụng cây QR tạo chỉ mục trong cơ sở dữ liệu không gian Dư Phương Hạnh* Trường Đại học Công nghệ, Đại học Quốc gia Hà Nội, 144 Xuan Thủy, Hà Nội, Việt Nam Nhận ngày 7 tháng 01 năm 2011 Tóm tắt. Bài báo này đề cập đến khái niệm và một số phươ ng pháp đánh chỉ mục trong cơ sở d ữ liệu không gian (spatial datadase – SDB). Là một trong những mô hình cơ sở dữ liệu được quan tâm hiện nay, SDB cho phép xử lý các đ ối tượng d ữ liệu không gian, chẳng h ạn dữ liệu bản đồ, d ữ liệu multimedia... để từ đó có thể xây dựng nên những kho dữ liệu không gian. Một trong những bài toán cơ bản trong SDB chính là vi ệc tối ưu hoá quá trình lưu trữ dữ liệu và truy vấn. Trong bài báo này, chúng tôi sẽ trình bày về hai ph ương pháp đánh chỉ mục điển hình liên quan đến vấn đ ề đánh chỉ mục giải bài toán trên, R-tree và Q-tree. Từ đó, ý tưởng kết hợp hai phương pháp này s ẽ chính là định hướng chủ đạo cho việc tối ưu hoá lưu trữ dữ liệu cũng như truy vấn trên cơ sở d ữ liệu không gian. Từ khóa: Spatial database, spatial indexing, R-tree, Q-tree, QR-Tree. 1. Giới thiệu∗ Warehouse (SDW). Các nghiên cứu trên lĩnh vực này đã thu được rất nhiều thành tựu, tuy Các nghiên cứu về công nghệ cũng như ứng nhiên cũng còn không ít khó khăn và thách thứ c dụng trong lĩnh vực cơ sở dữ liệu (CSDL) đang đòi hỏi phải có các giải pháp mới. tăng tr ưởng với một sức mạnh đáng kinh ngạc. Bài báo này trình bày một phương pháp Cùng với sự tăng trưởng nhanh chóng của đánh chỉ mục trên SDB, là sự kết hợp giữa hai lượng thông tin cũng như sự đa dạng về thể loại phương pháp đánh chỉ mục phổ biến là Q-tree thông tin cần lưu trữ và xử lý, chúng ta ngày và R-tree, kết hợp các ưu điểm của cả hai càng nhận ra những hạn chế của các Hệ q uản trị phương pháp này cũng như giảm thiểu nhượ c cơ sở dữ liệu quan hệ truyền thống, và nhu cầu điểm của chúng, nhằm tăng hiệu suất thực thi cần phải có các hệ q uản trị cơ sở dữ liệu với các các phép toán. dịch vụ phù hợp chính là yếu tố thúc đẩ y những nghiên cứu mới trong lĩnh vực này. Một trong các mô hình cơ sở dữ liệu đ ược quan tâm nhất 2. Khái niệm cơ bản hiện nay chính là mô hình cơ sở dữ liệu không Phần này sẽ đ ược tập trung trình bày những gian - Spatial DataBase (SDB) xử lý các đ ối khái niệm cơ bản liên quan đ ến mô hình SDB. tượng dữ liệu không gian, chẳng hạn dữ liệu bản đồ, dữ liệu multimedia... và mở rộng hơn 2.1. Dữ liệu không gian nữa là kho dữ liệu không gian - Spatial Data Thuật ngữ d ữ liệu không gian (spatial data) _______ được sử dụng theo nghĩa rộng, bao gồm các ∗ Tác giả liên hệ. ĐT: 84-4-37547813. E-mail: hanhdp@vnu.edu.vn 14
  2. D.P. Hạnh / Tạp chí Khoa học ĐHQGHN, Khoa học Tự nhiên và Công nghệ 27 (2011) 14-21 15 điểm đa chiều, các đ ường thẳng, hình khối... và hợp của các đoạn thẳng; quốc gia, thành phố có thể được biểu diễn dưới dạng các hình đa giác... các đối tượng hình học nói chung. Mỗi đ ối tượng dữ liệu này chiếm một vùng không gian (spatial extent) được đặc trưng bởi hai thuộ c 2.2. Các phương pháp truy vấn phổ biến trên tính vị trí (location) và biên (boundary). Dưới dữ liệu không gian góc nhìn từ một hệ q uản trị cơ sở dữ liệu, có th ể a) Truy vấn theo phạm vi không gian phân chia dữ liệu không gian thành hai kiểu: dữ (Spatial range queries): liệu điểm (point data) và d ữ liệu vùng (region Giả sử chúng ta có yêu cầu truy vấn “Đưa data) [1] ra tên tất cả các thành phố xuất hiện trong Dữ liệu điểm; Với kiểu dữ liệu này, không phạm vi 1000km quanh Hà Nội” hoặc “Đưa ra gian ứng với một điểm được đăc trưng bởi tọa tên các con sông chảy qua khu vực Bắc Bộ”. độ của nó; theo trực giác thì nó không chiếm Một truy vấn theo ki ểu này sẽ chứa một vùng một vùng không gian hay một đơn vị thể tích liên đới (với các thuộc tính vị trí và biên tương nào cả. Dữ liệu điểm là tập hợp các điểm trong ứng), và kết quả trả về sẽ là một vùng bao trùm không gian nhiều chiều, đ ược l ưu trữ trong phạm vi không gian đ ã chỉ ra trong truy vấn CSDL dựa trên các tọa đ ộ được tính toán trự c hoặc là một tập hợp các vùng thuộc trong phạ m tiếp, hoặc được sinh ra nhờ q uá trình chuyển vi không gian đã chỉ ra trong truy vấn. Kiểu hóa dữ li ệu thu được từ các phép đ o khiến cho truy vấn theo phạm vi đ ược sử dụng trong các việc lưu trữ và thực hiện truy vấn trở nên d ễ ứng dụng trên nhiều lĩnh vực đa dạng bao gồ m dàng hơn. Chẳng hạn Raster data là một ví dụ truy vấn quan hệ, truy vấn GIS, truy vấn dữ liệu đi ểm đ ược lưu trữ trực ti ếp thông qua CAD/CAM [1] các bit maps hoặc pixel maps (chẳng hạn như ảnh vệ tinh, hoặc phim điện não đ ồ 3 chiều, …). b) Truy vấn dựa trên các láng giềng gần Trong khi đó, feature vectors data được lưu trữ nhất (Nearest neighbor queries): thông qua các dữ liệu đ ược trích chọn, chuyển Với một yêu cầu chẳng hạn như “Đưa ra tên đổi từ một đối tượng dữ liệu điểm (thu đ ược từ 19 thành phồ gần Hà Nội nhất”, chúng ta ảnh, văn b ản...). Có thể t hấ y rằng, sử dụng các thường muốn kết quả trả về đ ược sắp xếp theo dữ liệu đã đ ược bi ểu diễn đ ể trả lời các truy vấn thứ tự nào đó về khoảng cách. Đây là dạng truy luôn dễ dàng hơn sử dụng ảnh hoặc ký hiệu vấn được sử dụng nhiều nhất đ ối với dữ liệu nguyên bản. multimedia. Trong trường hợp này, dữ liệu Dữ liệu vùng: được xác định dựa trên tập multimedia (chẳng hạn là ảnh) được biểu diễn các vùng không gian (spatial extents), trong đó dưới dạng một điểm, và dữ liệu tương tự cần mỗi vùng đ ược đặc trưng bởi hai thuộc tính vị tìm kiếm được tính toán theo khoảng cách gần trí và biên. Dữ liệu vùng được lưu trữ trong nhất tới điểm biểu diễn đối tượng truy vấn. [1] CSDL như một đối tượng hình học đơn giản, c) Truy vấn liên kết không gian (Spatial join xấp xỉ đúng với đối t ượng dữ liệu thực sự. Việc queries): mô tả các phép xấp xỉ đó đ ược đặc tả thông qua Các yêu cầu truy vấn thông thường thuộc vector dữ liệu, được xây dựng từ các điểm, các dạng này là “Đưa ra các thành phố cách nhau đoạn thẳng, các hình đa giác, hình cầu, hình không quá 200km” hoặc “Đưa ra tên các con ống... Rất nhiều ví dụ dữ liệu vùng đ ược đưa ra phố gần hồ”. Các dạng truy vấn này thường rất trong các ứng dụng địa lý, chẳng hạn đường xá, mất thời gian đ ể tính toán. Nếu chúng ta xem sông ngòi có thể đ ược biểu diễn dưới dạng tập xét một quan hệ trong đó mỗi một phần tử là
  3. D.P. Hạnh / Tạp chí Khoa học ĐHQGHN, Khoa học Tự nhiên và Công nghệ 27 (2011) 14-21 16 một đi ểm biểu diễn một thành phố hoặc một cái thể. Hiện chưa có đ ược sự nhất trí rằng cấu trúc hồ thì truy vấn trên có thể được thực hiện bằng đánh chỉ số nào là tốt nhất, tuy nhiên R tree là phép nối quan hệ này với chính nó với điều cấu trúc được sử dụng rộng rãi và đã xuất hiện kiện nối chỉ ra khoảng cách giữa hai phần tử trong các b ản DBMS thương mại, do tính đơn tương ứng. Đương nhiên, nếu các thành phố và giản và khả năng áp dụng cho cả hai dạng dữ liệu điểm và vùng. hồ được biểu diễn chi ti ết hơn và có vùng không gian của chúng, ngữ nghĩa của truy vấn (chúng ta tìm kiếm hai thành phố mà trung tâm 3.1. Q - tree của chúng cách nhau 200km hay hai thành phố Q - tree [3] là phương pháp đánh chỉ số dựa mà biên của chúng cách nhau 200km) và việc trên đ ường cong Space-Filling Curves để sắp thực thi truy vấn đ ều trở nên phức tạp hơn xếp các điểm dữ liệu. Việc đánh chỉ số đ ượ c nhiều. [1] thực hiện dựa trên việc phân chia không gian dữ liệu một cách đệ q uy, nhưng khác với R-tree, 3. Q-Tree, R-Tree và QR-Tree phương pháp này đ ược thực hiện độc lập đối với tập dữ li ệu thực sự. Space-Filling Curves Rất nhiều cấu trúc đánh chỉ số trên CSDL được xây dựng dựa trên giả thiết rằng mọi giá không gian đã đ ược đ ề xuất, một số được thiết trị thuộc tính nào đó đều có thể biểu diễn bởi kế chủ yếu dành cho tập dữ liệu điểm mặc dù một số bit xác định nào đó gọi là k bit, do đó số chúng cũng có thể áp dụng cho kiểu dữ liệu lượng các giá trị thuộc về cùng một chiều dữ vùng. Cấu trúc index dành cho dữ liệu điểm có liệu có thể đạt tới nhiều nhất là 2k. Để đơn giản, thể kể tới Grid files, HB tree, KD tree, Point hình vẽ dưới đây mô phỏng một tập dữ liệu 2- Quad tree và SR tree... Các kiến trúc khác như chiều mặc dù thực tế là phương pháp này có th ể Region Quad tree, R tree và SKD tree áp dụng áp dụng với dữ liệu có số chiều bất kỳ. Hình v ẽ cho dữ li ệu vùng, tuy nhiên chúng cũng có th ể thứ nhất sử dụng 2 bit để biểu diễn giá trị thuộ c áp dụng cho dữ liệu điểm [2, 3]. tính; hình thứ hai s ử dụng 3 bit; và hình thứ b a Region Quad tree (Q-tree) và R-tree là hai là đường cong Hilbert với 3 bit. hướng tiếp cận khác nhau và có rất nhiều biến Hình 1. Space-Filling Curves.
  4. D.P. Hạnh / Tạp chí Khoa học ĐHQGHN, Khoa học Tự nhiên và Công nghệ 27 (2011) 14-21 17 Trên ý tưởng này, Q-tree là phương pháp và 11 (góc phần tư bên phải phía trên). Trên phân chia một cách đệ q uy không gian dữ liệu hình vẽ, chúng ta có thể thấ y rằng nếu không thành các góc phần tư, được minh họa trong gian dữ liệu không đ ược phân bố một cách đ ối hình vẽ 3: Trong cấu trúc này, mỗi nút có 4 con xứng thì cây Q-tree s ẽ bị lệch, bởi vì Q-tree lần lượt ứng với các góc phần tư 00 (góc phần không phải là một cấu trúc cây cân bằng, do đó tư bên trái phía dưới), 01 (góc phần t ư bên trái trên những tập dữ liệu lớn, hiệu suất truy cập dữ liệu sẽ kém hiệu quả. phía trên), 10 (góc phần tư bên phải phía dưới) Hình 2. Cấu trúc đánh chỉ mục Q-tree. Một mặt khác, trong các ứng dụng đòi hỏi hình 4. Đơn gi ản nhất, hình khối thường đượ c việc l ưu trữ dữ liệu có tính chất liên t ục (chẳng sử dụng là hình chữ nhật nhỏ nhất chứa dữ liệu hạn dữ liệu về một đối tượng chuyển động) thay (Minimum Bounding Rectangle – MBR). Như vì các dữ liệu xác định, chúng ta gặp phải một vậ y, chính các MBR được lưu trữ trên cấu trúc vấn đ ề rất khó đ ể cân nhắc b ởi vì: việc sử dụng cây chứ không phải bản thân dữ liệu. CÁc nút cây Q-tree có độ sâu càng lớn thì đ ộ chính xác không phải lá được biểu di ễn bởi cặp (R, child- biểu di ễn dữ liệu càng tốt, tuy nhiên nó lại pointer) trong đó R là MBR của đ ối tượng và khiến cho việc xây dựng cấu trúc này trở nên child-pointer là con trỏ trỏ tới nút con; các nút kém hiệu quả trên cả phương diện không gian là được biểu diễn bởi cặp (R, obj-pointer) trong lưu trữ và thời gian xử lý các thao tác. đó R là MBR của đối tượng và obj-pointer là con trỏ trỏ tới mô tả chi ti ết của đ ối tượng. Mỗi nút trong cây tương ứng với một trang b ộ nhớ. 3.2. R-tree Và mặc dù các MBR có thể chồng chéo lên R-tree là phương pháp phân chia không nhau, tức là các nút có thể chứa dữ liệu gi ống gian dữ liệu thành các khối có thể lồng nhau nhau, nhưng mỗi đ ối tượng dữ liệu phải đượ c hoặc chồng chéo lên nhau, được minh họa trong lưu trữ trọn vẹn trên một nút lá.
  5. D.P. Hạnh / Tạp chí Khoa học ĐHQGHN, Khoa học Tự nhiên và Công nghệ 27 (2011) 14-21 18 Hình 3. Cấu trúc đánh chỉ mục R-tree. Chúng ta có thể thấ y R-tree là một biến thể 1) Tốc đ ộ t hực hiện xây dựng cây Q-tree của B+ tree và nó là một cây cân bằng. Truy nhỏ hơn nhi ều so với R-tree bởi vì việc phân nhiên, do các MBR có thể chồng chéo lên nhau chia, rồi lựa chọn MBR, sau đó chèn lần lượt từng nút vào R-tree là rất tốn kém thời gian và sự chồng chéo này gia tăng khi lượng dữ liệu gia tăng nên cấu trúc này có yếu điểm là kéo 2) Tuy nhiên việc đánh chỉ số theo Q-tree theo s ự gia tăng các truy cập tìm kiếm không không phù hợp với các tập dữ li ệu lớn do tính cần thiết. Thêm nữa, chúng ta bắt buộc phải tiến không cân bằng của nó. hành tìm kiếm tại mọi mức của cây, ngay cả Cả hai cấu trúc này đều có các bi ến thể với trong các trường hợp không có (hoặc có rất ít) rất nhiều cải tiến, tuy nhiên, chúng vẫn không đối tượng dữ liệu thỏa mãn yêu cầu. thể đ ộc lập đáp ứng các đòi hỏi về tốc đ ộ thự c thi của các ứng dụng thời gian thực. Như vậ y, 3.3. Kết hợp R-tree và Q-tree giải pháp kết hợp hai phương pháp này với nhau (hybrid) đ ể tận dụng ưu đi ểm của cả hai Q-tree và R-tree đ ều có các ưu điểm và phương pháp, bổ trợ cho nhau dường như là nhược đi ểm riêng, phụ thuộc cả vào các tình một giải pháp hợp lý. Hình vẽ 5 minh họa việc huống và các thao tác khác nhau. sử dụng QR-tree. Hình 4. Cấu trúc đánh chỉ mục sử dụng QR-tree.
  6. D.P. Hạnh / Tạp chí Khoa học ĐHQGHN, Khoa học Tự nhiên và Công nghệ 27 (2011) 14-21 19 4. Tối ưu hoá quá trình đánh chỉ mục phương pháp QR-Tree để giải quyết vấn đ ề trên. 4.1. Các công trình liên quan Trong phương pháp này, R-Tree được áp dụng không chỉ ở mức lá của Q-Tree mà còn Rất nhiều các cải tiến về k ỹ thuật đánh chỉ kết hợp với cả các nút không phải là lá của Q- mục đ ã được công b ố nhằm tăng hiệu quả thự c Tree. Điều này có nghĩa là nếu một đối tượng thi truy vấn. thuộc về nhiều vùng dữ li ệu khác nhau (như D. Pfoser[4] đã đ ưa ra STR-tree (Spatio- trường hợp 6 và 7 trong hình 5) thì mức cha của Temporal R-tree) và TB-tree (Trajectory- nó sẽ đ ược xem xét liệu nó có thể chứa toàn b ộ Bandle tree) và chỉ ra rằng hai cấu trúc này đối tượng dữ liệu này hay không. Việc kiểm tra hiệu quả hơn hẳn so với các cấu trúc trước đó này cứ ti ếp tục cho đến gốc (root). Một đ ối trong lĩnh vực lưu trữ các đ ối tượng chuyển tượng O được định nghĩa là thuộc về vùng động. Tao và Papadias [5] đề xuất MV3R-tree không gian con S nếu O hoàn toàn nằm trong S (Multi Version 3D R-tree), là sự kết hợp giữa và S là vùng không gian con nhỏ nhất chứa O. B-tree và 3D-tree. Như vậy, các đ ối tượng nằm tương đối xa nhau QR-Tree được đề xuất b ởi Manolopoulos, sẽ đ ược lưu trữ trên các nhánh khác nhau, nhờ Y. năm 1996 là cấu trúc gồm hai tầng: áp dụng đó giảm thiểu sự chồng chéo giữa các MBR. Q-tree ở tầng thứ nhất đ ể phân chia không gian Lúc này, một đ ối tượng cụ thể được gắn một dữ li ệu, sau đó tầng thứ hai áp dụng R-tree trên chỉ số duy nhất nên hiệu suất của quá trình chèn các vùng dữ liệu đã đ ược chia nhỏ bởi Q-tree. dữ liệu vào cây sẽ tăng lên (do việc thời gian Cũng với phương pháp kết hợp R-tree và Q- xây dựng lại cây đ ược rút ngắn); mỗi phép toán tree, K. Chakarabarti và S.Mehrotra [6] đã đưa sẽ được thực hiện trên một tập các vùng dữ liệu ra một cấu trúc cây lai được sử dụng cho việc tối thiểu (do không có chứa các dữ li ệu lặp sinh đánh chỉ mục với dữ liệu có số chiều lớn. Yuni ra do sự chồng chéo các vùng không gian) nên Xia và Sunil Prabhakar [7] đã đề xuất Q+Rtree việc truy cập dữ liệu sẽ nhanh hơn, thời gian áp dụng trong các bài toán đ ối tượng chuyển đáp ứng yêu cầu truy vấn được rút ngắn. động, cải tiến hiệu suất thực thi trong cả hai Cụ thể hơn, Q-tree đ ược sử dụng để phân thao tác cập nhật và truy vấn. chia thô toàn bộ dữ liệu và lưu trữ trong b ộ nhớ chính. R-tree sẽ đ ược sử dụng đ ể duy trì cấu 4.2.Phương pháp QR-Tree cải tiến trúc logic của cây, được thể hiện dưới dạng một QR-Tree mặc dù có ưu điểm rõ ràng nhưng bảng chỉ số mà mỗi dòng trong đó tương ứng nó vẫn tồn tại điểm yếu. Nhìn vào hình vẽ 1.5, với một nút của cây R-tree. Mọi cây R-tree có thể thấy rõ ràng rằng hai đối tượng 6 và 7 tương ứng với các nút của Q-tree được lưu trữ xuất hiện tại cả hai nút. Như vậ y mỗi khi cần trong cùng một bảng chỉ số. Mỗi dòng trong cập nhật nội dung, xóa hoặc truy vấn dữ liệu, bảng này có chứa một thuộc tính có tên chúng ta vẫn phải thực hiện lặp lại công việc ở ‘Partition’ đ ể chỉ ra vùng không gian con có tất cả hai nhánh chứa 6 và 7, gây ảnh hưởng tới chứa nút đó. Bằng cách t ổ chức như vậy, một tốc độ thực thi của các.phép toán. Phương pháp cây R-tree tương ứng với một vùng không gian QR cải tiến đ ược xây dựng dựa trên nền tảng là con Q-tree có thể đ ược tham chiếu tới nhờ vào
  7. D.P. Hạnh / Tạp chí Khoa học ĐHQGHN, Khoa học Tự nhiên và Công nghệ 27 (2011) 14-21 20 Lời cảm ơn giá trị của thuộc tính ‘Partition’ của các nút của cây Q-tree. Để chèn một đối tượng với MBR Công trình này được tài trợ một phần từ đ ề của nó, trước tiên ta thêm vào bảng dữ liệu, lấ y tài mang mã s ố: QC.08.03, Đại học Quốc gia ra ID của đối tượng này rồi gọi một hàm thự c Hà Nội. hiện việc định vị vị trí của nó trên Q-tree; vị trí tìm đ ược có thể là nút gốc, nút lá hoặc một nút cha trong cây. Dựa vào vị trí này, kết hợp với Tài liệu tham khảo bảng chỉ số ta có thể truy cập tới cây R-tree và [1] Raghu Ramakrishnan/Johannes Gehrke. xác định được root của cây R-tree đó. Cứ như Database Management Systems, McGraw Hill, vậy, quá trình lặp lại trên các nhánh con của cây 2sd edition. tới khi gặp nút lá có triển vọng nhất thì tiến [2] Manolopoulos, Y. (1996). QR-tree-a hybrid spatial data structure, Proceedings of the 1st hành chèn MBR và ID của đối tượng, và cuối International Conference on Geographic cùng là cây R-tree nếu cần thiết. Information Systems in Urban, Regional and Environmental Planning, Samos Island, Greece, pp. 3–7. 5. Kết luận [3] Rauber A., Tomish P., Riedel H., and Kouba Z. Integrating Geo-Spatial Data into OLAP SDB đã và đang thu hút được nhi ều nghiên Systems Using a Set-based Quad-Tree Representation. In Proc. of the 4th Int. Conf. cứu trong thời gian gần đ ây, nhất là khi những onInformation technology for Balanced dịch vụ trong lĩnh vực GIS hay multimedia Automation Systems in Production and ngày càng phát tri ển. Với những dữ liệu có yêu Transportation, BASYS, 2000. cầu l ưu trữ lớn như vậ y, bài toán tối ưu hoá quá [4] D. Pfoser, C. S .Jensen, and Y. Theodoridis. Novel approaches in query processing for trình đánh chỉ mục cho những dữ li ệu đó là một moving objects. Proceedings of the 26th bài toán thời sự và liên quan mật thiết đ ến hiệu International Conference on Very Large Databases (VLDB), September 2000. năng của những truy vấn trong SDB. Dựa trên [5] Papdias D., Kalnis P., Zhang J., and Tao Y. hai phương pháp đánh chỉ mục R-Tree, Q-Tree Efficient OLAP Operations in Spatial Data và phương pháp lai QR-Tree kết hợp những ưu Warehouse. In Proc. of the 6th International điểm t ừ hai phương pháp trên, chúng tôi đã đề Symposium on Spatial and Temporal Databases, SSTD, 2001. xuất cải tiến phương pháp đánh chỉ mục QR- [6] K. Chakarabarti and S.Mehrotra. The hybrid Tree đ ể giảm thiểu hơn nữa sự chồng chéo tree: An index structure for high dimensional trong lưu trữ dữ liệu nhằm nâng cao hi ệu năng feature spaces. Proceedings of he Fourteenth thực thi truy vấn và các phép toán khác. Những International Conference on data engineering (ICDE’99), 1999. kết quả thực nghi ệm trong thời gian tới của [7] Yuni Xia, Sunil Prabhakar. Q+Rtree: Efficient nhóm tác giả sẽ cho phép kiểm chứng những ưu Indexing for Moving Object Databases. In Proc. điểm thu đ ược từ những đề xuất lý thuyết của of the 8th International Symposium on Spatial and Temporal Databases, SSTD, 2004. phương pháp này.
  8. D.P. Hạnh / Tạp chí Khoa học ĐHQGHN, Khoa học Tự nhiên và Công nghệ 27 (2011) 14-21 21 Using QR-Tree for Spatial Database Indexing Du Phuong Hanh U niversity of Engineering and Technology, VNU, 144 Xuân Thủy, Hanoi, Vietnam This paper presents several indexing methods for the spatial datawarehouse (SDW). Actually, SDW is considered as one of most interresting models for manipulating the sptial entities like digital maps, multimedia,… For the SDW, the query optimization is very important due of the mass of spatial data.Thus, this paper investigates the two modern techniques, Q-Tree and R-Tree, for indexing the spatial data in order to improve the performance of the query optimizer. Then, the hybrid approach using QR-Tree will be mostly considered for optimizing the data storage query optimization for spatial database.
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

LV.11: Bộ Luận Văn Tốt Nghiệp Chuyên Ngành Tài Chính Ngân Hàng
172 tài liệu
835 lượt tải
THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
8=>2