Triển khai R-Tree Java

Question

Tôi đã tìm kiếm vài ngày qua để thực hiện ổn định R-Tree với sự hỗ trợ của các kích thước không giới hạn (20 hoặc hơn là đủ). Tôi chỉ tìm thấy số này http://sourceforge.net/projects/jsi/ nhưng chúng chỉ hỗ trợ 2 thứ nguyên.

Tùy chọn khác sẽ là triển khai đa chiều của cây theo khoảng thời gian.

Có lẽ tôi hoàn toàn sai với ý tưởng sử dụng R-Tree hoặc Intervall-Tree cho vấn đề của tôi vì vậy tôi trình bày ngắn gọn vấn đề, bạn có thể gửi cho tôi những suy nghĩ của bạn về điều này.

Vấn đề tôi cần giải quyết là một số loại tìm kiếm lân cận gần nhất. Tôi có một bộ ăng-ten và phòng và cho mỗi ăng-ten một khoảng số nguyên. Ví dụ. ăng ten 1, min -92, max -85. Trong thực tế, nó có thể được đại diện như phòng -> thiết lập của antennas -> khoảng thời gian cho ăng-ten. Ý tưởng là mỗi phòng trải dài một hộp trong R-Tree qua kích thước của ăng-ten và trong mỗi kích thước theo khoảng thời gian.

Nếu tôi nhận được truy vấn có N-Ăng-ten và các giá trị cho mỗi ăng-ten thì tôi chỉ có thể trình bày Thông tin dưới dạng điểm truy vấn trong phòng và truy xuất các phòng "gần nhất" tới điểm.

Hy vọng bạn có ý tưởng về vấn đề và ý tưởng của mình.

Answer 1

Tôi không hoàn toàn rõ ràng về vấn đề chính xác của bạn là gì, nhưng R-Tree hoặc cây khoảng cách sẽ không hoạt động tốt trong 20 thứ nguyên. Đó không phải là một số lượng lớn các kích thước, nhưng nó đủ lớn để lời nguyền về chiều kích bắt đầu xuất hiện.

Để xem ý tôi là gì, hãy xem xét việc chỉ xem xét tất cả những người hàng xóm của một hộp, kể cả những người ở góc và cạnh. Với 20 thứ nguyên, bạn sẽ có 3 - 1 hoặc 3,486,784,400 hộp lân cận. (Bạn nhận được điều đó bằng cách nhận ra rằng dọc theo mỗi trục, hàng xóm có thể là -1 đơn vị, 0 đơn vị hoặc đơn vị +1, nhưng (0,0,0) không phải là hàng xóm vì nó đại diện cho hộp ban đầu.)

Tôi xin lỗi, nhưng bạn cần phải chấp nhận tìm kiếm bạo lực, hoặc người nào khác phân tích vấn đề của bạn tốt hơn và đưa ra một giải pháp thông minh hơn.

Answer 2

Lưu ý rằng R-Trees có thể làm suy giảm nghiêm trọng khi bạn có dữ liệu rời rạc. Điều đầu tiên bạn thực sự cần tìm ra là một biểu diễn dữ liệu thích hợp, sau đó kiểm tra xem các truy vấn của bạn có hoạt động trên một tập con của dữ liệu hay không.

R-Trees sẽ chỉ thực hiện truy vấn của bạn nhanh hơn. Nếu họ không làm việc ở nơi đầu tiên, nó sẽ không giúp được gì. Bạn nên kiểm tra cách tiếp cận của mình mà không cần sử dụng R-Trees trước. Trừ khi bạn nhấn một lượng lớn dữ liệu (100.000 đối tượng), việc quét tuyến tính trong bộ nhớ có thể dễ dàng vượt trội hơn R-Tree, đặc biệt khi bạn cần một số lớp bộ điều hợp vì nó không được tích hợp tốt với mã của bạn.

Cách tiếp cận rõ ràng ở đây là chỉ cần sử dụng hình chữ nhật giới hạn và quét tuyến tính qua chúng. Nếu chúng hoạt động, bạn có thể lưu trữ MBR trong R-Tree để có được một số cải tiến về hiệu suất. Nhưng nếu nó không hoạt động với quét tuyến tính, nó sẽ không hoạt động với R-Tree hoặc (nó sẽ không hoạt động nhanh hơn.)

Answer 3

Tôi đã tìm thấy thực hiện R * -Tree này trong Java mà dường như để cung cấp nhiều tính năng:

https://github.com/davidmoten/rtree

Bạn có thể muốn kiểm tra xem!

Answer 4

Một triển khai tốt khác trong Java là ELKI: https://elki-project.github.io/.