Cây tìm kiếm nhị phân đa chiều được sử dụng cho tìm kiếm liên kết

Bài báo này phát triển cây tìm kiếm nhị phân đa chiều (hay còn gọi là cây k-d, trong đó k là số chiều của không gian tìm kiếm) như một cấu trúc dữ liệu để lưu trữ thông tin được truy xuất thông qua các tìm kiếm liên kết. Cây k-d được định nghĩa và các ví dụ được đưa ra. Nó cho thấy khá hiệu quả trong yêu cầu lưu trữ. Một lợi thế đáng kể của cấu trúc này là một cấu trúc dữ liệu duy nhất có thể xử lý nhiều loại truy vấn một cách rất hiệu quả. Nhiều thuật toán tiện ích đã được phát triển; thời gian chạy trung bình đã chứng minh của chúng trong một tệp chứa n bản ghi là: chèn, O(log n); xóa gốc, O(n^(k-1)/k); xóa một nút ngẫu nhiên, O(log n); và tối ưu hóa (đảm bảo hiệu suất logarithmic của các tìm kiếm), O(n log n). Các thuật toán tìm kiếm được đưa ra cho các truy vấn tìm kiếm khớp một phần với t khóa được chỉ định [thời gian chạy tối đa đã chứng minh là O(n^(k-t)/k)] và cho các truy vấn hàng xóm gần nhất [thời gian chạy trung bình quan sát được thực nghiệm là O(log n)] . Những hiệu suất này vượt xa so với các thuật toán tốt nhất hiện tại cho những nhiệm vụ này. Một thuật toán được trình bày để xử lý bất kỳ truy vấn giao nhau tổng quát nào. Trọng tâm chính của bài báo này là lý thuyết. Tuy nhiên, chúng tôi cảm thấy rằng cây k-d có thể rất hữu ích trong nhiều ứng dụng, và các ví dụ về các ứng dụng tiềm năng được đưa ra.