3D phân nhóm Algorithm

Question

Vấn đề Bản Tuyên Bố: Tôi có vấn đề sau đây:

Hiện có hơn một tỷ điểm trong không gian 3D. Mục đích là để tìm các điểm N hàng đầu có số lượng hàng xóm lớn nhất trong khoảng cách nhất định R. Một điều kiện khác là khoảng cách giữa hai điểm của N điểm trên đó phải lớn hơn R. Phân phối các điểm đó không đồng nhất. Nó là rất phổ biến mà một số khu vực của không gian chứa rất nhiều điểm.

Mục tiêu: Để tìm một thuật toán có thể mở rộng tốt cho nhiều bộ xử lý và có yêu cầu bộ nhớ nhỏ.

Suy nghĩ: Phân tách không gian bình thường không đủ cho loại sự cố này do phân phối không đồng đều. phân rã không gian bất thường phân chia đồng đều số điểm có thể giúp chúng ta giải quyết vấn đề. Tôi thực sự sẽ đánh giá cao nếu ai đó có thể làm sáng tỏ một số cách giải quyết vấn đề này.

Answer 1

Tôi không có câu trả lời rõ ràng cho bạn, nhưng tôi có đề xuất về cách tiếp cận có thể mang lại giải pháp.

Tôi nghĩ rằng nó đáng để điều tra locality-sensitive hashing. Tôi nghĩ rằng chia các điểm đồng đều và sau đó áp dụng loại LSH này cho mỗi bộ nên dễ dàng song song. Nếu bạn thiết kế thuật toán băm của mình sao cho kích thước thùng được xác định theo điều khoản của R, có vẻ như đối với một tập hợp điểm được chia thành các nhóm, các điểm thỏa mãn tiêu chí của bạn có khả năng tồn tại trong các nhóm đầy đủ nhất. Đã thực hiện điều này tại địa phương, có lẽ bạn có thể áp dụng một số loại chiến lược kiểu bản đồ-giảm để kết hợp các thùng không gian từ các thuật toán LSH khác nhau song song theo cách từng bước, sử dụng thực tế là bạn có thể bắt đầu để loại trừ các phần của không gian vấn đề của bạn bằng cách giảm toàn bộ nhóm. Rõ ràng, bạn sẽ phải cẩn thận về các trường hợp cạnh trải rộng các nhóm khác nhau, nhưng tôi nghi ngờ rằng ở mỗi giai đoạn sáp nhập, bạn có thể áp dụng các kích thước/độ lệch thùng khác nhau để loại bỏ hiệu ứng này (ví dụ: thực hiện các nhóm tương đương không gian tương đương) như các nhóm liền kề). Tôi tin rằng phương pháp này có thể được sử dụng để giữ cho các yêu cầu bộ nhớ nhỏ (tức là bạn không cần phải lưu trữ nhiều hơn các điểm tại bất kỳ thời điểm nào, và bạn luôn hoạt động trên các tập con nhỏ (ish)).

Nếu bạn đang tìm kiếm loại phỏng đoán thì tôi nghĩ kết quả này sẽ mang lại một giải pháp "tốt" ngay tức khắc - tức là nó sẽ cung cấp cho bạn một số điểm có thể xảy ra mà bạn có thể kiểm tra đáp ứng tiêu chí của mình. Nếu bạn đang tìm kiếm câu trả lời chính xác, thì bạn sẽ phải áp dụng một số phương pháp khác để cắt không gian tìm kiếm khi bạn bắt đầu hợp nhất các nhóm song song.

Một ý nghĩ khác mà tôi có là điều này có thể liên quan đến việc tìm kiếm metric k-center. Nó chắc chắn không phải là vấn đề chính xác, nhưng có lẽ một số phương pháp được sử dụng trong việc giải quyết được áp dụng trong trường hợp này. Vấn đề ở đây là giả sử bạn có một số liệu có thể là, trong trường hợp của bạn, thì trong trường hợp của bạn, sự hiện diện của một tỷ điểm khiến nó trở nên không mong muốn và khó thực hiện bất kỳ kiểu tra cứu toàn cầu nào (ví dụ: sắp xếp khoảng cách giữa điểm). Như tôi đã nói, chỉ là một ý nghĩ, và có lẽ là một nguồn cảm hứng hơn nữa.

Answer 2

Dưới đây là một số phần có thể có của giải pháp. Có nhiều lựa chọn khác nhau ở mỗi giai đoạn, sẽ phụ thuộc vào Ncluster, về tốc độ thay đổi dữ liệu, và về những gì bạn muốn làm với các phương tiện.

3 bước: định lượng, hộp, chữ K.

1) định lượng: giảm tọa độ XYZ đầu vào để nói 8 bit mỗi, bằng cách lấy 2^8 phần trăm riêng X, Y, Z. Điều này sẽ tăng tốc toàn bộ luồng mà không mất nhiều chi tiết. Bạn có thể sắp xếp tất cả 1G điểm, hay chỉ là một 1M ngẫu nhiên, để có được 8-bit x0 < x1 < ... x256, y0 < y1 < ... y256, z0 < z1 < ... z256 với 2^(30-8) điểm trong mỗi phạm vi. Để lập bản đồ phao X -> 8 bit x, tìm kiếm nhị phân chưa được kiểm tra nhanh chóng — xem Bentley, Pearls p. 95.

Added: Kd trees chia bất kỳ đám mây điểm vào hộp kích thước khác nhau, đều có ~ Leafsize chỉ — tốt hơn nhiều so với việc tách X Y Z như trên. Nhưng bạn sẽ phải cuộn mã cây Kd của riêng mình để chỉ chia hộp 16M nói đầu tiên và chỉ giữ số lượng, chứ không phải chỉ số.

2) hộp: đếm số điểm trong mỗi hộp 3d, [xj .. xj + 1, yj .. yj + 1, zj .. zj + 1]. Hộp trung bình sẽ có 2^(30-3 * 8) điểm; phân phối sẽ phụ thuộc vào cách dữ liệu được gộp lại. Nếu một số hộp quá lớn hoặc có quá nhiều điểm, bạn có thể a) chia chúng thành 8, b) theo dõi trung tâm của các điểm trong mỗi hộp, trên toàn thế giới chỉ lấy điểm giữa hộp.

3) K-means clustering trên trung tâm hộp 2^(3 * 8). (Google song song "k có nghĩa là -> 121k lượt truy cập.) Điều này phụ thuộc rất lớn vào K aka Ncluster, cũng trên bán kính của bạn R. Một cách tiếp cận thô sơ sẽ là phát triển một số heap trong 27 * Ncluster nói hầu hết các điểm, sau đó lấy những điểm lớn nhất tùy theo giới hạn Bán kính của bạn. (Tôi muốn bắt đầu bằng số Minimum spanning tree, rồi xóa các liên kết dài nhất K-1 để nhận các cụm K.) Xem thêm Color quantization.

Tôi sẽ tạo Nbit, tại đây 8, một thông số ngay từ đầu.

Ncluster của bạn là gì?

Đã thêm: nếu điểm của bạn đang di chuyển đúng lúc, hãy xem collision-detection-of-huge-number-of-circles trên SO.

Answer 3

Chỉ là một ý tưởng. Tạo biểu đồ có các điểm và cạnh đã cho giữa các điểm khi khoảng cách < R.

Tạo loại biểu đồ này tương tự như phân tách không gian. Câu hỏi của bạn có thể được trả lời bằng tìm kiếm cục bộ trong biểu đồ. Đầu tiên là đỉnh với mức độ tối đa, thứ hai là việc tìm kiếm tập đỉnh tối đa chưa kết nối.

Tôi nghĩ rằng việc tạo biểu đồ và tìm kiếm có thể được thực hiện song song. Cách tiếp cận này có thể có yêu cầu bộ nhớ lớn. Tách miền và làm việc với biểu đồ cho khối lượng nhỏ hơn có thể làm giảm nhu cầu bộ nhớ.

Answer 4

Sử dụng Octree. Đối với dữ liệu 3D có miền giá trị giới hạn, quy mô rất tốt với tập hợp dữ liệu khổng lồ.

Nhiều người trong số các phương pháp nói trên như địa phương băm nhạy cảm là phiên bản gần đúng thiết kế cho nhiều cao chiều mà bạn không thể chia hợp lý nữa.

Tách tại mỗi cấp thành 8 thùng (2^d cho d = 3) hoạt động rất tốt. Và kể từ khi bạn có thể dừng lại khi có quá ít điểm trong một tế bào, và xây dựng một cây sâu hơn, nơi có rất nhiều điểm mà nên phù hợp với yêu cầu của bạn khá tốt.

Để biết thêm chi tiết, xem Wikipedia:

https://en.wikipedia.org/wiki/Octree

Ngoài ra, bạn có thể cố gắng xây dựng một R-tree. Nhưng cây R cố gắng cân bằng, khiến việc tìm ra những khu vực dày đặc nhất trở nên khó khăn hơn. Đối với nhiệm vụ cụ thể của bạn, hạn chế này của Octree thực sự hữu ích! Cây R đặt rất nhiều nỗ lực vào việc giữ độ sâu cây bằng nhau ở khắp mọi nơi, để mỗi điểm có thể được tìm thấy gần như cùng một lúc. Tuy nhiên, bạn chỉ quan tâm đến các khu vực dày đặc, mà sẽ được tìm thấy trên những con đường dài nhất trong Octree mà không cần phải nhìn vào các điểm thực tế được nêu ra!

Answer 5

Tôi cũng khuyên bạn nên sử dụng octree. Khung OctoMap rất tốt trong việc xử lý các đám mây điểm 3D lớn. Nó không lưu trữ tất cả các điểm trực tiếp, nhưng cập nhật mật độ chiếm dụng của mỗi nút (còn gọi là hộp 3D). Sau khi cây được xây dựng, bạn có thể sử dụng một trình lặp đơn giản để tìm nút có mật độ cao nhất. Nếu bạn muốn mô hình mật độ điểm hoặc phân phối bên trong các nút, OctoMap rất dễ sử dụng.

Here bạn có thể xem cách mở rộng mô hình phân phối điểm bằng mô hình phẳng.