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.

FAQ: Big data cho người mới bắt đầu

Cảm ơn TopDev và các bạn trẻ đã tổ chức và hỗ trợ tôi hoàn thành tốt buổi chia sẻ hôm thứ bảy 30/09/2017 vừa qua. Mặc dù trời mưa to, nhưng các bạn khán giả vẫn tham gia khá đầy đủ. Tuy có nhiều phần chưa đáp ứng được mong đợi của mọi người nhưng phần hỏi đáp luôn là phần sôi động nhất đã lắp được phần nào khoảng trống này. Hy vọng, mỗi bạn đều đem về được những kinh nghiệm thiết thực khi đụng đến công nghệ xử lý Big Data, cụ thể là Apache Spark. Bên dưới, tôi xin tổng hợp lại các câu hỏi thường gặp trong buổi chia sẻ này cùng với Slide chứa notebook về Spark bên trên. Nếu bạn nào có thêm câu hỏi, mình sẽ cập nhật vào bài viết này để thêm phần phong phú cho các bạn khác tìm hiểu và tham khảo.

Notebooks:

Các event trước:

Thế nào thì được gọi là Big Data?

Big Data thoả tính chất 5V thì được gọi là Big. Cá nhân mình thấy 3 điểm sau thì đã gọi là Big rồi.

  1. Dữ liệu phức tạp (unstructured data).
  2. Tốc độ phình to nhanh, tính theo giây.
  3. Không thể xử lý với các công nghệ trước đó.

Có cần phải học thêm bằng cấp nào không?

Các nhà tuyển dụng hiện tại xem kinh nghiệm quan trọng hơn bằng cấp. Một số công nghệ nên biết: Docker, PostgreSQL, MongoDB, Apache Spark, Bash shell, AWS, Kafka, Jenkins.

Nếu bạn có thêm các Certificate cloud computing sau thì cũng có thể tạo nên lợi thế riêng:

Continue reading “FAQ: Big data cho người mới bắt đầu”

Làm việc với Spark DataFrames – Truy vấn cơ bản

Spark DataFrames
Spark DataFrames

DataFrame là một kiểu dữ liệu collection phân tán, được tổ chức thành các cột được đặt tên. Về mặt khái niệm, nó tương đương với các bảng quan hệ (relational tables) đi kèm với các kỹ thuật tối ưu tính toán.

DataFrame có thể được xây dựng từ nhiều nguồn dữ liệu khác nhau như Hive table, các file dữ liệu có cấu trúc hay bán cấu trúc (csv, json), các hệ cơ sở dữ liệu phổ biến (MySQL, MongoDB, Cassandra), hoặc RDDs hiện hành. API này được thiết kế cho các ứng dụng Big Data và Data Science hiện đại. Kiểu dữ liệu này được lấy cảm hứng từ DataFrame trong Lập trình R và Pandas trong Python hứa hẹn mang lại hiệu suất tính toán cao hơn.

Spark DataFrames Performance
Spark DataFrames Performance

Trong bài viết này, tôi sẽ tiến hành thực nghiệm một vài truy vấn cơ bản để làm quen với kiểu dữ liệu DataFrames. Ở các bài viết sau, ta sẽ đi sâu hơn vào các truy vấn nâng cao và phức tạp hơn.

Continue reading “Làm việc với Spark DataFrames – Truy vấn cơ bản”

Kinh nghiệm làm việc với Big Data

Working with Big Data
Working with Big Data

Đã bao giờ bạn cảm thấy quá tải khi làm việc với Big Data chưa? Đã bao giờ bạn phải ngồi hàng giờ chỉ để transfer dữ liệu từ server này sang server khác chỉ để test thuật toán của mình? Hay những lúc chán chường khi nhìn script của mình bắt đầu chạy hàng giờ và cuối cùng phát hiện ra mình đã sai đâu đó? Mình nghĩ rằng tất cả những ai khi mới bắt đầu làm việc với Big Data đều có những cảm nhận như vậy. Trong bài viết này, tôi xin góp một chút kinh nghiệm của mình để làm việc với Big Data hiệu quả hơn, kể cả cá nhân hay làm việc nhóm.

Continue reading “Kinh nghiệm làm việc với Big Data”

Trải nghiệm tập dữ liệu Big Data ở đâu

repository
repository

Nếu bạn đang là một newbie và có mong muốn trang bị cho mình một chút kinh nghiệm về xử lý Big Data để có thể theo đuổi sự nghiệp như một data scientist thì bạn sẽ đặt câu hỏi đầu tiên đó là “Lấy dữ liệu Big Data ở đâu để mà thực tập?”.

Hiện nay, bạn không cần phải là một thành viên của một công ty hay tổ chức nào để được quyền truy xuất vào tập dữ liệu Big Data của họ. Đã có nhiều tập dữ liệu Big Data được public ra công chúng cho các nhà nghiên cứu làm phân tích và xử lý thông tin trực tiếp mà không đòi hỏi bất kỳ quyền hạn nào. Dưới đây, tôi xin liệt kê danh sách các nguồn dữ liệu Big Data mà bạn có thể download về.

  1. KDNuggets repository
  2. Data.gov 
  3. US Census Bureau 
  4. European Union Open Data Portal 
  5. Data.gov.uk 
  6. The CIA World Factbook 
  7. Healthdata.gov 
  8. NHS Health and Social Care Information Centre 
  9. Amazon Web Services public datasets 
  10. Facebook Graph 
  11. Gapminder 
  12. Google Trends 
  13. Google Finance 
  14. Google Books Ngrams 
  15. National Climatic Data Center 
  16. DBPedia 
  17. Topsy 
  18. Likebutton 
  19. New York Times 
  20. Freebase 
  21. Million Song Data Set 

Tham khảo thêm:

Lập trình Spark với Scala

stackoverflow
stackoverflow

Với chế độ cài đặt Standalone, Spark có thể xử lý được một tập dữ liệu khổng lồ dù cho bạn đang sử dụng một chiếc laptop có RAM chỉ khoảng 4-8GB. Trong bài viết này, tôi sẽ hướng dẫn mọi người lập trình Spark với Scala.

Cho trước tập dữ liệu là các bài post trên stackoverflow.com, nhiệm vụ của chúng ta là xây dựng một mô hình phân lớp để dự đoán xem câu hỏi của user khi post lên thuộc nhóm nào, nhờ vậy mà trang web có thể đưa ra những tags gợi ý thông minh hơn cho user.

Continue reading “Lập trình Spark với Scala”

5 Machine Learning APIs tốt nhất dành cho Data Science

Machine learning API
Machine learning API

Với sự phát triển và tiến bộ nhanh chóng về các thuật toán Machine Learning như hiện nay, nếu không có sự hỗ trợ mạnh mẽ từ các API của các nhà khổng lồ về lĩnh vực này thì các developer thiên về kĩ thuật như chúng ta sẽ khó có thể xây dựng được những ứng dụng thông minh để đem lại trải nghiệm cao cho người dùng.

Với nhiều sự lựa chọn cho các nhiều loại tập dữ liệu khác nhau như hiện nay, cuộc đua tranh giải Machine Learning API tốt nhất vẫn còn đang diễn ra, ai là người nhanh hơn sẽ giành chiến thắng. Dưới đây, tôi xin đưa ra 5 Machine Learning APIs tốt nhất dành cho Data Science để mọi người tham khảo.

Continue reading “5 Machine Learning APIs tốt nhất dành cho Data Science”

Lập trình MapReduce với Python

Trong bài viết này, ta sẽ thiết kế và cài đặt các thuật toán MapReduce cho các tác vụ xử lý dữ liệu thông thường. Mô hình lập trình MapReduce được đề xuất trong một bài báo năm 2004 từ một nhóm nghiên cứu tại Google. MapReduce là một mô hình đơn giản để xử lý song song các tập dữ liệu lớn (Big Data).

MapReduce
MapReduce

Bài viết này giúp bạn làm quen với tư duy lập trình MapReduce. Ta sẽ sử dụng tập dữ liệu nhỏ để dễ kiểm tra kết quả thực thi cũng như để quan sát hoạt động bên trong MapReduce như thế nào. Mọi tập tin và dữ liệu liên quan đến bài viết được lưu tại Github: https://github.com/ongxuanhong/MapReduce-with-Python.

Continue reading “Lập trình MapReduce với Python”