Distance oracle – Truy vấn nhanh khoảng cách giữa hai điểm bất kỳ trên đồ thị

Đại ý: Sự bùng nổ thông tin mạng xã hội làm nảy sinh nhu cầu khai thác sự tương tác giữa: Subscribers, Groups, People, Objects, etc. Trong đó, tính toán nền tảng để phân tích đồ thị là tìm đường đi ngắn nhất giữa các node bất kỳ. Đối với đồ thị lớn hơn 10 triệu node, khả năng tính toán của hệ thống hiện tại sẽ bị quá tải. Do đó, giới nghiên cứu đề xuất Distance oracle là một cấu trúc dữ liệu giúp cho việc tính toán và truy vấn khoảng cách trên đồ thị được nhanh hơn với 4 điều kiện sau:

  • Tiền xử lý nên bằng O(n) hoặc O(nlogn).
  • Không gian lưu trữ ít hơn O(n^2).
  • Thời gian truy vấn nhanh hơn O(m + nlogn).
  • Độ tin cậy: khoảng cách xấp xỉ được càng gần khoảng cách thực tế càng tốt.

Trong bài báo “A Geometric Distance Oracle for Large Real-World Graphs“. Nhóm tác giả đã cài đặt nhiều nền tảng lý thuyết tính toán xấp xỉ khoảng cách khác nhau trên đồ thị thực tế để so sánh như: GoogleNews, Facebook SB, Call Graph I, … Kết quả xấp xỉ đạt được có độ sai biệt nhỏ so với khoảng cách thực tế. Từ nghiên cứu này, ta có thêm một hướng tiếp cận để xử lý Big Data bằng cách xấp xỉ tính toán thay vì xử lý trực tiếp bằng các phương pháp trước đây (lưu trữ đồ thị bằng ma trận kề O(n^2), tìm đường đi ngắn nhất bằng thuật toán Dijkstra O(m + nlogn)).

benchmark_graphs

Keywords: distance oracle, graph analysis, graph theory, metric space, social network analysis.

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Đăng xuất / Thay đổi )

Connecting to %s