Cấu trúc dữ liệu không gian nhanh cho tìm kiếm lân cận gần nhất giữa các mặt cầu không đồng đều

Question

Cho một không gian liên tục (euclide) k có chiều dài di chuyển/tăng trưởng/thu hẹp không thể đoán trước được Tôi cần phải lặp lại tìm các hypersphere có bề mặt gần nhất đã cho phối hợp. Nếu một số hyperspheres có cùng khoảng cách với tọa độ của tôi, thì quả cầu lớn nhất sẽ thắng. (Tổng số hyperspheres được đảm bảo duy trì như nhau theo thời gian.)

Suy nghĩ đầu tiên của tôi là sử dụng KDTree nhưng nó sẽ không tính đến khối lượng không đồng đều của hyperspheres. Vì vậy, tôi đã nhìn xa hơn và tìm thấy BVH (Phân cấp khối lượng bị ràng buộc) và BIH (Phân cấp khoảng thời gian bị ràng buộc), có vẻ như là lừa. Ít nhất trong không gian 2/3 chiều. Tuy nhiên trong khi tìm kiếm khá nhiều thông tin và hình dung trên BVHs tôi hầu như không thể tìm thấy bất cứ điều gì trên BIHs.

yêu cầu cơ bản của tôi là một k chiều cấu trúc dữ liệu không gian mà mất khối lượng vào tài khoản và là một trong hai siêu nhanh để xây dựng (off-line) hoặc động với hầu như không mất thăng bằng.

Với các yêu cầu của tôi ở trên, bạn sẽ đi đến cấu trúc dữ liệu nào? Bất kỳ người nào khác mà tôi thậm chí không đề cập đến?

---

Chỉnh sửa 1: Quên đề cập: cho phép các trình tạo hậu quả (chồng lên nhau)

Chỉnh sửa 2: Có vẻ như thay vì "khoảng cách" (và "khoảng cách phủ định" cụ thể) chỉ số được mô tả của tôi khớp với số power of a point tốt hơn nhiều.

Answer 1

Tôi mong đợi một QuadTree/Octree/generalized thành 2^K-tree cho thứ nguyên K của bạn sẽ thực hiện thủ thuật; không gian phân vùng đệ quy, và có lẽ bạn có thể dừng khi một K-subcube (hoặc K-rectangle brick nếu các phân chia không đồng đều) không chứa một hypersphere, hoặc chứa một hoặc nhiều hypersphere sao cho phân vùng không tách biệt bất kỳ, hoặc cách khác chứa trung tâm của chỉ một hypersphere (có lẽ dễ dàng hơn).

Việc chèn và xóa các thực thể trong các cây như vậy rất nhanh, do đó kích thước thay đổi hypersphere chỉ gây ra một cặp hoạt động xóa/chèn. (Tôi nghi ngờ bạn có thể tối ưu hóa điều này nếu kích thước hình cầu của bạn thay đổi theo phân vùng đệ quy bổ sung cục bộ nếu quả cầu nhỏ hơn hoặc kết hợp khối K cục bộ nếu nó phát triển).

Tôi chưa từng làm việc với họ, nhưng bạn cũng có thể xem xét binary space partitions. Chúng cho phép bạn sử dụng cây nhị phân thay cho cây k để phân vùng không gian của bạn. Tôi hiểu rằng KDTrees là một trường hợp đặc biệt của điều này.

Nhưng trong mọi trường hợp, tôi cho rằng thuật toán chèn/xóa cho 2^K cây và/hoặc BSP/KDTrees được hiểu rõ và nhanh chóng. Vì vậy, thay đổi kích thước hypersphere gây ra hoạt động xóa/chèn nhưng những người đang nhanh chóng. Vì vậy, tôi không hiểu sự phản đối của bạn đối với cây KD.

Tôi nghĩ hiệu suất của tất cả những điều này đều giống nhau.

Answer 2

Tôi sẽ sử dụng phần mở rộng R * Tree cho SQLite. Một bảng thông thường sẽ có dữ liệu 1 hoặc 2 chiều. Truy vấn SQL có thể kết hợp nhiều bảng để tìm kiếm ở các thứ nguyên cao hơn.

Công thức với khoảng cách phủ định hơi lạ.Khoảng cách là tích cực trong hình học, vì vậy có thể không có nhiều lý thuyết hữu ích để sử dụng.

Công thức khác chỉ sử dụng khoảng cách dương tính có thể hữu ích. Đọc về không gian hyperbolic. Điều này có thể giúp cung cấp ý tưởng cho các cách khác để mô tả khoảng cách.