Cấu trúc dữ liệu để truy xuất hiệu quả phần tử gần nhất từ ​​một tập hợp

Question

tl; dr Làm thế nào để một số thứ như Mathematica Nearest được triển khai hiệu quả?

Mathematica có một chức năng gọi là Nearest mà sẽ mất một danh sách "những điều" (họ có thể con số, tọa độ trong không gian ba chiều n, chuỗi, vv), và sẽ trả về một đối tượng NearestFunction. Đối tượng này là một hàm, khi được áp dụng cho x, sẽ trả về phần tử danh sách gần nhất với x bởi một số chỉ số khoảng cách. Chỉ số khoảng cách có thể được chuyển thành tham số cho Nearest: theo mặc định, nó sử dụng khoảng cách Euclide cho dữ liệu số và một số khoảng cách chỉnh sửa cho chuỗi.

---

Ví dụ (điều này hy vọng sẽ làm cho các câu hỏi rõ ràng hơn):

nf = Nearest[{92, 64, 26, 89, 39, 19, 66, 58, 65, 39}];

nf[50] sẽ trở lại 58, yếu tố gần gũi nhất với 50. nf[50, 2] sẽ trả lại {58, 39}, hai yếu tố gần nhất.

---

Câu hỏi: một cách hiệu quả để thực hiện chức năng này là gì? Loại cấu trúc dữ liệu nào là NearestFunction có khả năng sử dụng nội bộ? Sự phức tạp tốt nhất có thể của việc tính toán một phần tử gần nhất cho các loại dữ liệu khác nhau là gì? Để có một danh sách đơn giản các số phân loại chúng và thực hiện tìm kiếm nhị phân sẽ hoạt động, nhưng Nearest hoạt động với dữ liệu đa chiều cũng như với hàm khoảng cách tùy ý, vì vậy tôi cho rằng nó sử dụng một cái gì đó tổng quát hơn. Nhưng tôi sẽ không ngạc nhiên nếu nó hóa ra là chuyên môn cho một số loại dữ liệu/chức năng khoảng cách.

Answer 1

Đối với các chức năng khoảng cách được xử lý tốt, có nhiều cấu trúc dữ liệu được tối ưu hóa đặc biệt cho việc này. Đối với dữ liệu đa chiều, các k-d tree (và khác binary space partitioning trees) có thể cung cấp cho xuất sắc nearest-neighbor searches, thường là trong thời gian sublinear. Bạn cũng có thể muốn xem xét metric trees, là cấu trúc cây được tối ưu hóa để lưu trữ các điểm trong một số không gian số liệu theo cách hỗ trợ các tìm kiếm lân cận gần nhất. Tùy thuộc vào không gian số liệu cụ thể (khoảng cách Euclide, khoảng cách chỉnh sửa, v.v.), các cấu trúc dữ liệu khác nhau có thể ít nhiều phù hợp.

Đối với các chức năng khoảng cách tùy ý mà không có giới hạn về hành vi (ví dụ, chẳng hạn như bất đẳng thức tam giác), thì tốt nhất bạn có thể làm là tìm kiếm tuyến tính, vì hàm khoảng cách có thể là vô hạn cho tất cả điểm trừ một điểm cụ thể trong tập hợp.

Hy vọng điều này sẽ hữu ích!

Answer 2

Nó hoàn toàn phụ thuộc vào dữ liệu và số liệu. Đọc tất cả về nó tại đây: Nearest Neighbour Search