Khoảng cách là phương pháp MBR tính toán độ tương đồng. Đối với một số thước độ khoảng cách thực, khoảng cách từ điểm A đến điểm B, ký hiệu bằng d(A,B), có bốn đặc điểm như sau:
Được định nghĩa tốt (Well-defined) – Khoảng cách giữa hai điểm luôn được định nghĩa và là số thực không âm, d(A,B) ≥ 0.
Đồng nhất (Identity) – Khoảng cách từ một điểm đến chính nó luôn bằng không, nên d(A, A) = 0.
Giao hoán (Commutativity) – Hướng không tạo sự khác biệt, do đó khoảng cách từ A đến B giống như từ B đến A: d(A,B) = d(B,A). Đặc điểm này loại trừ đường một chiều, ví dụ.
Bất đẳng thức tam giác (Triangle Inequality) – Việc thăm điểm trung gian C trên đường từ A đến B không bao giờ rút ngắn khoảng cách, do đó d(A,B) ≤ d(A,C) + d(C,B).
Đối với MBR, các điểm chắc chắn là dữ liệu trong cơ sở dữ liệu. Định nghĩa này của khoảng cách là cơ sở để tính toán độ tương đồng, nhưng MBR hoạt động khá tốt khi một số ràng buộc này được nhẹ nhàng nới lỏng.
Ví dụ, hàm khoảng cách trong nghiên cứu trường hợp định nghĩa tin tức không thay đổi được sao cho khoảng cách từ tin tức A đến B không luôn giống khoảng cách từ B đến A. Nhưng phép đo độ tương đồng có lợi cho mục đích phân loại.
Sự thật rằng khoảng cách được định nghĩa tốt ngụ ý rằng mỗi dữ liệu có láng giềng ở đâu đó trong cơ sở dữ liệu và MBR cần láng giềng để hoạt động. Tính chất đồng nhất làm khoảng cách phù hợp với khái niệm trực giác rằng dữ liệu tương đồng nhất với một dữ liệu cho trước là bản ghi ban đầu chính nó.
Tính giao hoán và Bất đẳng thức tam giác làm cho các láng giềng gần nhất cục bộ và được định nghĩa tốt. Việc thêm dữ liệu mới vào cơ sở dữ liệu sẽ không làm bản ghi hiện có gần hơn. Độ tương đồng là vấn đề dành riêng cho chỉ hai dữ liệu tại một thời điểm. Mặc dù thước độ khoảng cách có thể khám phá láng giềng gần nhất được định nghĩa tốt, tập hợp láng giềng gần nhất có thể có một số đặc điểm đặc biệt.
Tập láng giềng phụ thuộc vào cách hàm khoảng cách dữ liệu kết hợp các hàm khoảng cách trường. Thực tế, láng giềng gần thứ hai dùng hàm tổng là láng giềng xa nhất dùng Euclid v.v. So với thước đo tổng hoặc chuẩn hóa, thước đo Euclid tend to ưu tiên láng giềng nơi tất cả các trường tương đối gần.
Hàm tổng, Euclid, và chuẩn hóa cũng có thể bao gồm trọng số để mỗi trường đóng góp lượng khác nhau cho hàm khoảng cách dữ liệu. MBR thường tạo kết quả tốt khi một số trọng số bằng 1. Tuy nhiên, đôi khi trọng số có thể dùng để bao gồm kiến thức tiên nghiệm, bao gồm trường cụ thể bị nghi ngờ có hiệu ứng lớn trên phân loại.