MiDAS Depth Exam

2022 Depth Exam is scheduled for December 1st and 2nd, 2022.

2022 Depth Exam papers are available below!

Overview: MiDAS depth exam is a take home exam that covers the main areas of the group: (i) data management and (ii) data mining. These of course may span several subareas of the fields including data systems, indexing, query processing, algorithmic data mining, graph mining, etc. Note that the department requires that the depth exam is completed on a certain schedule (see www.bu.edu/cs/phd-program/phd-program-milestones).

Eligibility: In order for a PhD student to be eligible for the MiDAS depth exam they should (i) be advised or co-advised by a MiDAS faculty member, (ii) in their 2nd or 3rd year, and (iii) have discussed with their advisor about taking the depth exam.

Process: For every iteration of the depth exam MiDAS faculty will provide a list of ~24 papers that the candidates will have about two months to study. The exam will take place at a predefined date announced in this page. The exam will contain four (4) subjects, two (2) for each of the main areas. All four subjects will have the nature of an open research challenge rather than one of an exercise to solve, and each candidate will select to address any three (3) of these subjects. A depth exam will be evaluated on (a) the understanding of the research area, (b) the creativity, and ultimately (c) the correctness and the quality of the proposed approach. The take home exam will be returned in two (2) days.

Data Management

FPGA-based Data Partitioning

Kaan Kara, Jana Giceva, Gustavo Alonso
SIGMOD, 2017 | Download PDF

Updating a cracked database

Stratos Idreos, Martin L. Kersten, Stefan Manegold
SIGMOD, 2007 | Download PDF

LSM-based storage techniques: a survey

Chen Luo, Michael J. Carey
VLDB, 2020 | Download PDF

Bridging the Archipelago between Row-Stores and Column-Stores for Hybrid Workloads

Joy Arulraj, Andrew Pavlo, Prashanth Menon
SIGMOD, 2016 | Download PDF

Qd-tree: Learning Data Layouts for Big Data Analytics

Zongheng Yang, Badrish Chandramouli, Chi Wang, Johannes Gehrke, Yinan Li, Umar Farooq Minhas, Per-Åke Larson, Donald Kossmann, Rajeev Acharya
SIGMOD, 2020 | Download PDF

High-Performance Concurrency Control Mechanisms for Main-Memory Databases

Per-Åke Larson, Spyros Blanas, Cristian Diaconu, Craig Freedman, Jignesh M. Patel, Mike Zwilling
PVLDB, 2011 | Download PDF

Privacy integrated queries: an extensible platform for privacy-preserving data analysis

Frank McSherry
SIGMOD, 2009 | Download PDF

CryptDB: protecting confidentiality with encrypted query processing

Raluca A. Popa, Catherine M. S. Redfield, Nickolai Zeldovich, Hari Balakrishnan
SOSP, 2011 | Download PDF

Exact indexing of dynamic time warping

Eamonn J. Keogh, CA Ratanamahatana
Knowledge and information systems, 2005 | Download PDF

Efficient Top-k Query Evaluation on Probabilistic Data

Christopher Re, Nilesh N. Dalvi, Dan Suciu
ICDE, 2007 | Download PDF

Executing SQL over encrypted data in the database-service-provider model

Hakan Hacigümüs, Balakrishna R. Iyer, Chen Li, Sharad Mehrotra
SIGMOD, 2002 | Download PDF

Boosting the Accuracy of Differentially Private Histograms Through Consistency

Michael Hay, Vibhor Rastogi, Gerome Miklau, Dan Suciu
VLDB, 2010 | Download PDF

Data Mining

Efficient Frequent Directions Algorithm for Sparse Matrices

Mina Ghashami, Edo Liberty, Jeff M. Phillips
KDD, 2016 | Download PDF

Aggregating inconsistent information: Ranking and clustering

Nir Ailon, Moses Charikar, Alantha Newman
ACM, 2008 | Download PDF

Min-Wise Independent Permutations

Andrei Z. Broder, Moses Charikar, Alan M. Frieze, Michael Mitzenmacher
Journal of Computer and System Sciences, 2000 | Download PDF

Maximizing the Spread of Influence through a social network

David Kempe, Jon M. Kleinberg, Eva Tardos
Theory of Computing, 2015 | Download PDF

The Generalized Mean Densest Subgraph Problem

Nate Veldt, Austin R. Benson, Jon M. Kleinberg
KDD, 2021 | Download PDF

Retrieving Top Weighted Triangles in Graphs

Raunak Kumar, Paul Liu, Moses Charikar, Austin R. Benson
WSDM, 2020 | Download PDF

Worst-case optimal join algorithms

Hung Q. Ngo, Ely Porat, Christopher Ré, Atri Rudra
Journal of the ACM, 2018 | Download PDF

Color-Coding

Noga Alon, Raphael Yuster, Uri Zwick
Journal of the ACM, 1995 | Download PDF

The Space Complexity of Approximating the Frequency Moments

Noga Alon, Yossi Matias, Mario Szegedy
Journal of Computer and System Sciences, 1999 | Download PDF

Analyzing Graph Structure via Linear Measurements

Kook Jin Ahn, Sudipto Guha, Andrew McGregor
SODA, 2012 | Download PDF

Parallel Graph Decompositions Using Random Shifts

Gary L. Miller, Richard Peng, Shen Chen Xu
SPAA, 2013 | Download PDF

Computing classic closeness centrality, at scale

Edith Cohen, Daniel Delling, Thomas Pajor, Renato F. Werneck
COSN, 2014 | Download PDF