Big data computing

Course's objectives

This course presents advanced algorithmic and programming tools for analyzing large or very large datasets. Emphasis will be on some of the major algorithmic techniques used in large-scale data applications and partly on computational paradigms that support or complement them. The course will address both the necessary foundational aspects and the practical application of the proposed techniques. As much as possible, these will be demonstrated and applied to realistic scenarios during more applied, problem - solving lectures, that will see the supervised teamwork of students and istructor to address real problem instances using or adapting the tools and techniques taught in the course. Below follows a brief syllabus, highlighting the main techniques presented in the course. Reference applications, use cases (e.g., large-scale classification or clustering, recommender systems etc.) and possible development tools (e.g., Python's scikit package) can change over different editions of the course and will be specified on the course's Web site.

Course's  syllabus for academic year 2017/2018

• Large scale computation and  mining large graphs
  

• Mining graphs that may not fit in main memory
• Standard approaches and Map Reduce - like paradigm. Solving basic problems using Apache Spark
• MapReduce/Hadoop - like algorithms for triangle counting and connected components
  
• A quick tour of community detection in large graphs

• Hashing and sampling techniques for neighborhood search
  

• Neighborhood search and the curse of dimensionality in euclidean spaces
  
• Reducing dimensions in euclidean spaces via hashing
• Extensions to different metrics
  
• Efficient neighborhood search via hashing and bucketing
• Reducing search space via sampling
  

• Dimensionality reduction

• SVD and basic approach
• Sparsification techniques and CUR
• Random projections
  

• Sketching and sampling for streams of data
  

• Estimating frequency moments in sliding windows
  
• Sketching algorithms for heavy hitters tracking
• Sketching techniques for join size estimation
  
• Sketching techniques for large graph mining, with application to neighborhood search, and analysis of community structure
• Distributed algorithms in following MapReduce paradigm
  
• Graph semi-streaming algorithms