Thuật toán giao thoa ellipsoid nhanh

Question

Giả sử tôi có 1 triệu hình ellipsoids N chiều tùy ý, được định hướng tùy ý phân tán ngẫu nhiên qua không gian N chiều. Với một tập hợp các elipsoid phụ, tôi muốn "nhanh" xác định tập hợp tất cả các elipsoid mà các elipsoids từ tập đầu tiên cắt nhau.

Có một thuật toán cho việc này. Nó là gì? Độ phức tạp "O" là gì?

Answer 1

Độ phức tạp "O" bị từ lời nguyền về thứ nguyên nếu bạn đang cho phép dữ liệu N chiều. (Xem this wikipedia article để biết thêm về điều đó). Tôi khuyên bạn nên vay từ mô phỏng vật lý và chia vấn đề này thành "giai đoạn rộng" và một giai đoạn hẹp:

• Giai đoạn rộng thận trọng tìm thấy tập hợp các cặp hình elip chồng chéo mạnh hơn.
• Giai đoạn hẹp cắt tỉa tập hợp các cặp bầu dục có khả năng trùng lặp với các cặp thực sự trùng lặp.

Giai đoạn hẹp là vấn đề hình học tính toán đơn giản để kiểm tra giao điểm giữa các dấu ba chấm tùy ý. Đối với giai đoạn rộng, bạn sẽ muốn sử dụng một cấu trúc không gian như một băm không gian, cây không gian (R-tree, Kd-tree, X-tree, UB-tree, ...), hoặc cấu trúc ad-hoc một số thuộc tính đặc biệt của dữ liệu bạn đang tải (chẳng hạn như cây không cân bằng hoặc băm).

Phương pháp phổ biến hiện tại là cây Kd. Có rất nhiều tài liệu và các phiên bản đã mã hóa của cây Kd có thể cấu hình dễ dàng, vì vậy tôi khuyên bạn nên xem trực tuyến. (Lợi thế của việc sử dụng hầu hết cấu trúc cây là nếu thiết lập bạn đang tìm giao lộ với tương đối nhỏ gọn, bạn có thể tìm kiếm thông qua cây chỉ một lần và tìm giao lộ mà không cần phải thực hiện nhiều lần duyệt cây . Điều này sẽ giúp với các mẫu truy cập cache (có thể từ bộ nhớ chính hoặc đĩa). Các thuật toán tương tự có thể xử lý các truy vấn thành viên khác nhau. Nó có khả năng bạn đang làm việc mà sẽ được hưởng lợi rất nhiều từ các thuộc tính thiết lập truy vấn nhỏ gọn, tuy nhiên.

Cây Kd sẽ không khắc phục được sự cố của bạn cho tất cả các ellipsoids - ví dụ: nếu bạn có một elipsoid có kích thước N có trục chính từ (0, 0, 0, 0, ...) đến (1, 1, 1, 1, ...) nhưng với trục phụ nhỏ hoặc không quan trọng (và từ đó không giao nhau nhiều) sẽ vẫn cần phải là một nút bao phủ [0,1] trong tất cả các thứ nguyên N. Nếu elipsoid của bạn rơi vào [0,1]^n, thì mỗi ellipsoid sẽ kiểm tra giao điểm với ellipsoid bất tiện nói trên. Tuy nhiên, với dữ liệu thế giới thực (và thậm chí là tổng hợp nhiều nhất trừ khi bạn đang thực sự cố gắng để làm cho cây Kd chậm), phương pháp Kd-tree sẽ là một chiến thắng.

Nếu bạn mong đợi Kd-tree là một thành công cho ellipsoids nghìn chiều, rất có thể bạn nên sử dụng tìm kiếm vũ lực tốt hơn. (Tuy nhiên, ...

Một triệu mục nhập không quá tệ nếu bạn đã thực hiện tối ưu hóa, nhưng nếu bạn đang thực hiện nhiều truy vấn (hàng triệu), nó sẽ là chậm (theo thứ tự 10 giây hoặc tệ hơn). Tôi đã nhìn thấy một số con số tuyệt vời xuất phát từ mã vector được tối ưu hóa tốt, tuy nhiên. (Ngay cả khi vận chuyển một số sản phẩm sử dụng chiến lược này.) Với sự kết hợp bộ nhớ cache phù hợp, việc ép buộc brute chỉ mất vài phần nghìn giây. Điều này có nghĩa là ASM hoặc nội tại vectơ trong C/C++ - không chắc chắn ngôn ngữ nào bạn đang làm việc.

Đối với hầu hết dữ liệu, O phức tạp (bỏ qua lời nguyền về chiều) nên được phân bổ theo O (m log n) cho các truy vấn (một khi cây được xây dựng), trong đó m là số dấu ba chấm trong bộ truy vấn và n là số dấu ba chấm trong tập dữ liệu.Tự xây dựng dữ liệu không được tệ hơn O (n log n). Nhân tất cả mọi thứ bằng Exp (d) trong đó d là chiều - đó là cách nó đi với loại điều này.