cách sắp xếp dữ liệu địa lý để tìm kiếm nhanh

Question

Tôi có một số đối tượng được bản địa hóa địa lý (tôi có cho mỗi đối tượng vĩ độ + kinh độ). Ứng dụng của tôi cần hiển thị các đối tượng cách vị trí GPS của thiết bị di động 3 km. Tôi có hàng ngàn đối tượng và chúng được bản địa hóa ở khu vực rộng lớn (ví dụ, một số tiểu bang của Hoa Kỳ, một số quốc gia nhỏ), có nghĩa là trong danh sách các đối tượng của tôi có thể đặt ở NYC và một ở Miami nhưng tôi cũng có thể đối tượng rất gần (vài mét).

Hiện tại, Ứng dụng của tôi thực hiện tìm kiếm lặp lại. Đối với mỗi đối tượng tôi tính toán khoảng cách với vị trí GPS và nếu khoảng cách là < = 3KM thì tôi giữ đối tượng khác mà tôi bỏ qua nó. Thuật toán này không hiệu quả lắm và tôi đang tìm một thuật toán sẽ cho hiệu năng tốt hơn.

Tôi giả sử có cách sắp xếp đối tượng bằng cách sử dụng phối cảnh địa lý và bên cạnh để tìm nhanh hơn các đối tượng nằm xung quanh vị trí GPS.

Ý tưởng hiện tại của tôi chỉ là tính toán hình chữ nhật với "điểm cực", Bắc/Nam/Đông/Tây (từ 3km vị trí GPS) để giới hạn vùng tìm kiếm. Tiếp theo tôi sẽ tính toán khoảng cách chỉ cho các đối tượng bên trong hộp này. Tôi nghĩ rằng một cái gì đó tốt hơn có thể được thực hiện nhưng tôi không có ý tưởng ...

Bất kỳ đề nghị sẽ được đánh giá ;-) Cảm ơn,

SEB.

Answer 1

Âm thanh như một nearest neighbor search, nhưng không phải với tối đa số nước láng giềng (như trong KNN), nhưng với một khoảng cách ngưỡng tối đa.

Cách tiếp cận chung là đặt các đối tượng vào một cấu trúc dữ liệu đặc biệt để cho phép loại bỏ các phần lớn của không gian tìm kiếm nhanh chóng. Tuy nhiên, chúng thường được thực hiện với không gian euclide trong tâm trí, và không phải cho mặt phẳng hình cầu (lat/lon-) (các vấn đề xung quanh). Do đó, có lẽ bạn sẽ cần phải chuyển đổi tọa độ của bạn để tọa độ 3d trong một hệ thống Descartes so với trung tâm của quả cầu trước khi bạn có thể áp dụng một trong những cấu trúc dữ liệu sau đây để tìm kiếm một cách hiệu quả cho các đối tượng của bạn:

• Octree
• kd-tree

Answer 2

những câu trả lời khác nhắc đến chỉ số không gian là chính xác, nhưng không nhất thiết phải là giải pháp dễ nhất cho bạn.

Tôi sẽ xem xét điều gì đó đơn giản hơn: Nhóm các mục theo quốc gia, sau đó theo tiểu bang, vùng, thành phố và cuối cùng - theo một vài địa danh ở các thành phố đông đúc (nơi bạn có nhiều đối tượng). Sau đó, bạn chỉ cần thực hiện một vài truy vấn (kiểm tra xem quốc gia nào tôi đang ở, trạng thái, vùng, v.v.) để giới hạn bản thân đối với một tập hợp các đối tượng rất nhỏ mà không cần triển khai cấu trúc dữ liệu nâng cao trong ứng dụng dành cho thiết bị di động của bạn .

Answer 3

Một cách để thực hiện điều này mà không có cơ sở dữ liệu chuyên ngành sẽ xuất hiện để sắp xếp hai bản sao dữ liệu của bạn - một lần theo kinh độ, một lần theo vĩ độ. Bất cứ điều gì mà tìm kiếm nhị phân tìm kiếm để đóng trên cả lat và dài, là gần gũi.

Tương tự, bạn có thể sử dụng cây thông thường (nhanh) hoặc đỏ đen (biến thiên thấp).

Nhưng có thể có lợi thế khi sử dụng cây r hoặc cây kd. Những gì tôi đã mô tả có lẽ chỉ dành cho việc tránh sử dụng các phụ thuộc mới hoặc tránh viết mã một cơ sở dữ liệu mới từ đầu.