Mục tiêu của tôi là viết một thuật toán đường ngắn nhất cho mạng lưới đường.Cơ sở dữ liệu đồ thị có tốt hơn cho các thuật toán đường đi ngắn nhất không?
Hiện tại kiến trúc của tôi giống như vậy: Tôi lưu trữ tất cả dữ liệu trong cơ sở dữ liệu PostgreSQL được kích hoạt PostGIS. Tôi thực hiện một SELECT * FROM ways, mất ít hơn 3 giây trên một bảng với 100.000 cạnh (cách) và sau đó tôi sẽ áp dụng thuật toán đường ngắn nhất (Java, Ruby hoặc bất kỳ thứ gì) cho biểu đồ đã nằm trong bộ nhớ. Thao tác thứ hai có thể mất khoảng 1,5 giây trên biểu đồ có 100.000 cạnh.
Vì vậy, phải mất:
- 2-3 giây để tải tất cả các cách từ cơ sở dữ liệu vào bộ nhớ và tạo ra một biểu đồ (nút được lưu trữ trong một bảng với cách (cạnh));
- 1-1,5 giây để tính đường đi ngắn nhất trên biểu đồ đã có trong bộ nhớ.
này rất giống với những gì pgRouting làm (theo tôi biết nó sử dụng C Boost để lưu trữ các đồ thị trong bộ nhớ), ngoại trừ pgRouting mất khoảng 2 giây trong tổng số để tính toán một con đường ngắn nhất trên cùng một tập dữ liệu (có , nó nhanh, nhưng nó là một hộp đen cho tôi, vì vậy tôi cần của riêng tôi).
Nhưng gần đây tôi đã tìm thấy về Cơ sở dữ liệu đồ thị và về Neo4j. Trên trang web của họ, họ tuyên bố rằng "Vẫn có thể thực hiện các tính toán này ở tốc độ thứ hai trên đồ thị của hàng triệu con đường và điểm tham chiếu trong nhiều trường hợp để từ bỏ phương pháp tiếp cận bình thường của các chỉ mục precomputing với các cửa hàng K/V và có thể đặt định tuyến vào con đường quan trọng với khả năng thích nghi với điều kiện sống và xây dựng các dịch vụ không gian cá nhân và năng động cao.
Câu hỏi đặt ra là: Cơ sở dữ liệu đồ thị có nhanh hơn với vấn đề cụ thể của tôi không?
Vấn đề có các thuộc tính sau:
- cơ sở dữ liệu bao gồm một bảng (cách);
- truy vấn duy nhất vào cơ sở dữ liệu là lấy tất cả các cách vào bộ nhớ (để tạo biểu đồ);
- Tôi không cần khả năng mở rộng, tức là có khả năng biểu đồ sẽ không phát triển.