Khái niệm cơ bản
Cấu trúc dữ liệu động học (kinetic data structure) là cấu trúc dữ liệu được cài đặt để theo dõi một thuộc tính của hệ thống hình học đang chuyển động liên tục. Ví dụ: cấu trúc lồi động học (kinetic convex hull) theo dõi bao lồi của n điểm chuyển động.
Phát triển cấu trúc dữ liệu động học được thúc đẩy bởi các bài toán hình học tính toán liên quan đến vật thể chuyển động liên tục, ví dụ: phát hiện va chạm hoặc khả năng nhìn thấy trong robot, hoạt hình, đồ họa máy tính.
Tổng quan
Cấu trúc dữ liệu động học áp dụng cho hệ thống có tập giá trị thay đổi theo hàm của thời gian, theo cách được gọi là "called fashion". Hệ thống có các giá trị, và với mỗi giá trị v của hệ thống, v = f(t). Cấu trúc dữ liệu động học cho phép truy vấn hệ thống tại thời gian ảo hiện tại t, và hai thao tác bổ sung:
- advance(t): Tiến hệ thống đến thời gian t.
- change(v, f(t)): Thay đổi quỹ đạo của giá trị v thành f(t), tính từ thời gian hiện tại.
Các thao tác bổ sung khác cũng được hỗ trợ. Ví dụ, thường cài đặt với tập điểm. Trong trường hợp này, cấu trúc thường cho phép chèn và xóa điểm.
Đối chiếu với cấu trúc dữ liệu truyền thống
Cấu trúc dữ liệu động học cho phép giá trị lưu trữ thay đổi liên tục theo thời gian. Về nguyên tắc, có thể xấp xỉ bằng cách lấy mẫu vị trí điểm tại các khoảng thời gian cố định, xóa và chèn lại từng điểm vào cấu trúc dữ liệu "tĩnh" (truyền thống). Tuy nhiên, cách tiếp cận này dễ bị lấy mẫu quá nhiều (oversampling) hoặc quá ít (undersampling) tùy thuộc vào khoảng thời gian, và có thể lãng phí tài nguyên tính toán.
Phương pháp Chứng chỉ (Certificates approach)
Phương pháp chung sau có thể dùng để xây dựng cấu trúc dữ liệu động học:
- Lưu trữ cấu trúc dữ liệu trên hệ thống tại thời gian hiện tại t. Cấu trúc này cho phép truy vấn tại thời gian ảo hiện tại.
- Bổ sung chứng chỉ (certificates) cho cấu trúc dữ liệu. Chứng chỉ là các điều kiện mà cấu trúc dữ liệu chính xác. Tất cả chứng chỉ đều đúng lúc này, và cấu trúc dữ liệu chỉ ngừng chính xác khi một chứng chỉ không còn đúng.
- Tính thời gian thất bại của mỗi chứng chỉ (khi nó không còn đúng).
- Lưu trữ các chứng chỉ trong hàng đợi ưu tiên (priority queue), khóa bởi thời gian thất bại.
- Để tiến đến thời gian t, xem chứng chỉ có thời gian thất bại nhỏ nhất. Nếu nó thất bại trước t, xóa/pop khỏi hàng đợi, sửa cấu trúc dữ liệu để chính xác tại thời điểm thất bại, cập nhật chứng chỉ. Lặp lại cho đến khi chứng chỉ có thời gian thất bại nhỏ nhất thất bại sau t. Khi đó tất cả chứng chỉ đúng tại t, cấu trúc dữ liệu có thể trả lời truy vấn chính xác tại t.
Các loại sự kiện (Events)
Thất bại chứng chỉ được gọi là "sự kiện" (events). Sự kiện là nội bộ (internal) nếu thuộc tính được duy trì bởi cấu trúc dữ liệu động học không thay đổi tại thời điểm xảy ra sự kiện. Sự kiện là bên ngoài (external) nếu thuộc tính đó thay đổi tại thời điểm xảy ra sự kiện.
Hiệu năng
Khi cài đặt phương pháp chứng chỉ, có bốn thước đo hiệu năng. Một lượng được coi là nhỏ nếu nó là hàm polylogarithmic của n, hoặc O(n^ε) với ε rất nhỏ, trong đó n là số đối tượng.