Bài toán nearest neighbor và R-tree indexing

Từ cây B tới R-tree lập chỉ mục không gian: chèn điểm, tách nút tràn, tìm kiếm và con đường tới cây tương đồng SS-tree.

KhóCấu trúc dữ liệu ~60 phút

Ôn lại trước khi học

Ký hiệu Big-O và các lớp tăng trưởng Chiều dữ liệu và chiều tính toán

Giới thiệu

Bài này học R-tree từ ý tưởng cây B. Bạn dùng nó để tìm điểm bản đồ khi dữ liệu đổi liên tục.

Kiến thức cần nhớ

Vì sao cần R-tree

Duyệt hết mỗi truy vấn là không tưởng với dữ liệu lớn.
K-d tree đuối ở chiều cao và dữ liệu động.
Cần cây luôn cân bằng như cây B nhưng cho nhiều chiều.
Ví dụ đời thường: như cần tủ hồ sơ tự cân, thêm bớt vẫn gọn.

Ôn cây B

Mọi lá cùng độ sâu nên cây luôn cân bằng.
Nút tràn thì tách và đẩy khóa giữa lên cha.
Tách gộp cục bộ, không cần xoay phức tạp.
R-tree giữ cơ chế này, chỉ thay khóa số bằng hộp không gian.

Hộp bao MBR và chèn điểm

Mỗi nút lưu hộp chữ nhật bao trọn mọi con của nó.
Các hộp anh em được phép giao nhau.
Chèn: chọn nhánh phải nới ít diện tích nhất rồi đi xuống lá.
Nút tràn thì tách sao cho tổng diện tích 2 hộp mới nhỏ nhất.

Tìm kiếm và giới hạn

Chỉ lặn vào con có hộp giao với miền hỏi.
Lân cận: thăm hộp gần trước để có ứng viên tốt sớm.
Hộp chồng chéo nặng thì phải lặn nhiều nhánh nên chậm.
Ví dụ đời thường: như tìm nhà trong nhiều khu vực chồng lấn phải gõ nhiều cửa.

Ví dụ

Input: chèn điểm mới vào R-tree. Output: các hộp cha nới ra vừa đủ bao điểm.
Giải thích: bất biến hộp cha luôn bao trọn con.
Input: truy vấn vùng chỉ giao 1 nhánh. Output: chỉ thăm nhánh đó, cắt nhánh còn lại.
Giải thích: hộp không giao thì cả cây con không thể chứa đáp án.

💻 Bài tập

Ngôn ngữ: C++. Nộp vào day-070/. Làm việc với hình chữ nhật 2D Rect { double x1, y1, x2, y2; }.

Bài 1: Hàm hình học cho R-tree

Hàm	Yêu cầu
`double area(Rect)`
`Rect combine(Rect a, Rect b)`	Hộp nhỏ nhất bao cả 2
`double enlargement(Rect box, Rect add)`	`area(combine) - area(box)`
`bool intersects(Rect a, Rect b)`	Chạm cạnh tính là giao
`double minDist(Rect r, Point p)`	Khoảng cách nhỏ nhất từ điểm tới hộp, bằng 0 nếu điểm nằm trong

combine({0,0,1,1}, {2,2,3,3}) -> {0,0,3,3}
enlargement({0,0,2,2}, {1,1,3,3}) -> 5
minDist({0,0,1,1}, (3,1)) -> 2

Bài 2: R-tree chèn và truy vấn vùng

class RTree {
 public:
  RTree(int M = 8, int m = 3);            // tối đa M, tối thiểu m mục mỗi nút
  void insert(const Rect &r, int id);
  std::vector<int> search(const Rect &q) const;
  int height() const;
  bool check() const;   // mọi lá cùng độ sâu, hộp cha bao trọn hộp con, số mục trong [m, M] trừ gốc
};

chooseLeaf: chọn con cần nới diện tích ít nhất, hòa thì chọn hộp nhỏ hơn.
Tách nút tràn bằng quadratic split (Guttman).
Tách lan lên gốc thì tạo gốc mới.

Chèn 10^4 hộp nhỏ ngẫu nhiên -> check = true
search khớp quét tuyến tính trên 1000 truy vấn

Bài 3: Nearest neighbor trên R-tree (nâng cao)

int nearest(Point p): best-first search, dùng min-heap theo minDist của hộp. Dừng khi phần tử đầu heap xa hơn đáp án tốt nhất.
Dữ liệu: 50.000 cửa hàng (điểm = hộp suy biến). So thời gian với k-d tree ngày 69 và quét tuyến tính.
Đếm số nút thăm trung bình. Thử M = 4, 8, 16, 32.

✅ Tiêu chí hoàn thành

Test hàm hình học pass.
check() đúng sau 10^4 lần chèn.
search và nearest khớp quét tuyến tính.
Bảng thời gian theo M có số thật.

❓ Câu hỏi ôn tập

R-tree khác k-d tree ở điểm nào?
Hộp bao MBR là gì?
Chèn tràn thì tách nút thế nào?
Khi nào hộp chồng chéo làm truy vấn chậm?

🌕 Bạn đã hoàn thành ngày 70. Làm hết bài tập phía trên rồi sang ngày tiếp theo.

Ngày 69

Nearest neighbor và region search trên k-d tree

Ngày 71

Decorator thực tế: thư viện vào-ra và tự viết decorator