The solution for Nearest Neighbors Search – Part 1

Bài viết được sự cho phép của tác giả Kiên Nguyễn

Nearest Neighbors Search (Tìm kiếm người hàng xóm gần nhất trong khu dân cư) là bài toán phổ biến được nhiều người biết tới. Vấn đề đặt ra trong bài toán này cũng là vấn đề mà các hãng gọi xe lớn như Grab, Uber, GoJerk đã giải quyết.

Đặt xe ở vị trí A, tìm tài xế gần nhất trong phạm vi 3km hoặc mở rộng hơn nếu không có tài xế.

Giải quyết tốt bài toán này cho ta phương án hoàn hảo để thiết kế các hệ thống lớn như đặt xe với Uber hay Lift. Phát triển các ứng dụng hẹn hò dựa theo vị trí như Tinder, …

1. Về Nearest Neighbors Search

Nearest Neighbors Search is the optimization problem of finding the point in a given set that is closest (or most similar) to a given point. Closeness is typically expressed in terms of a dissimilarity function: the less similar the objects, the larger the function values.

Nearest Neighbors Search là bài toán tối ưu tìm kiếm một điểm gần nhất (hoặc tương tự như vậy) khi đã có một điểm xác định trước. Mức độ tìm kiếm thường được thể hiện dưới dạng hàm không giống nhau: các đối tượng càng ít giống nhau, giá trị hàm càng lớn.

Về độ rộng của square tìm kiếm, có thể là circle (tròn) hoặc rectrangle (vuông). Tìm kiếm một hoặc tất cả các điểm trong phạm vi đã được định sẵn. Solution cơ bản nhất để giải quyết bài toán này là tìm kiếm theo hệ trục tọa độ x,y

Tìm kiếm tất cả các điểm nằm trong khoảng từ x1 -> x2 và từ y1 -> y2.

2. SQL Database và Binary Search Tree

Trường hợp sử dụng SQL Database relation, ta có thể lưu toàn bộ x,y với table id

id || X || y
unique || lattitude || longitude

Lúc này, nếu muốn tìm kiếm một point trong circle hay retrangle, có thể sử dụng SQL BETWEEN. Cách làm này ổn với điều kiện dữ liệu tìm kiếm không quá lớn. Nếu tập dữ liệu tìm kiếm lớn và không gian tìm kiếm rộng, slowdown peformance là chuyện đương nhiên và có thể nhìn thấy trước được.

SELECT id FROM table WHERE x BETWEEN x1 AND x2 AND y BETWEEN y1 AND y2

Một cách khác có thể sử dụng cho bài toán Nearest Neighbors Search là sử dụng Binary Search Tree (BST).

Nguồn ảnh / Source: geeksforgeeks.org

Với BST, bài toán chuyển thành Find the closest element. Tìm node có giá trị gần nhất với giá trị input.

// For above binary search tree
Input : k = 4
Output : 4

Input : k = 18
Output : 17

Input : k = 12
Output : 9

Áp dụng Sort trên BST, ta có phương án giải quyết

• If target value K is present in given BST, then it’s the node having minimum absolute difference.
• If target value K is less than the value of current node then move to the left child.
• If target value K is greater than the value of current node then move to the right child.

• Nếu giá K tồn tại trên BST, thì bản thân Node đó là node có độ sai lệnh nhỏ nhất
• Nếu K nhỏ hơn giá tị Node hiện tại, di chuyển nó về phía bên trái của cây BST
• Nếu giá trị K lớn hơn giá tị Node hiện tại, di chuyển nó phía bên phải của cây BST

3. Giải pháp khác?

Cả hai solutions SQL Database và Binary Search Tree đều là giải pháp cơ bản để giải quyết bài toán Nearest Neighbors Search. Tuy nhiên, với lượng dữ liệu lớn và tần suất tìm kiếm cao.

Rõ ràng ta cần một giải pháp tốt hơn để giới hạn không gian tìm kiếm. Giới hạn được không gian tìm kiếm sẽ tăng tốc thời gian phản hồi. Giải pháp khác được đề cập tới ở đây là R-Trees (Range Querying).

Solution sử dụng R-Trees sẽ được viết ở bài viết thứ hai trên Kieblog.

4. Tham khảo

• Thiết kế Distributed File System với GFS Phần 1
• Nearest neighbor search – Wikipedia
• Find the closest element in Binary Search Tree – GeeksforGeeks

My pleasure when you’re here to read – Have a good mood – Happy Coding!

Bài viết gốc được đăng tải tại kieblog.vn

Có thể bạn quan tâm:

• Trò chuyện cùng Phú Trần – Solution Architect tại Sendo và tìm hiểu con đường sự nghiệp của Solution Architect
• Đâu là điểm khác biệt giữa Solution Architect và Software Architect?
• Big data là gì? Trò chuyện cùng CTO của Datamart Solutions để hiểu hơn về data

Xem thêm Việc làm Developer hấp dẫn trên Station D