Associate Professor, Electrical and Computer Engineering, UIUC
Ph.D. Electrical Engineering, Stanford University, 2009
M. S. Electrical Engineering, Stanford University 2005
B.S. Electrical Engineering, Stanford University 2005
259 Coordinated Science Lab
Aug Our work received a new NSF grant!
May Du’s GreenMap: MapReduce with Ultra High Efficiency Power Delivery accepted to HotCloud 2015
Apr Qiaomin presented Priority Algorithm for Near-data Scheduling: Throughput and Heavy-Traffic Optimality at Infocom 2015
Mar Qiaomin won the Yi-Min Wang and Pi-Yu Chung Endowed Research Award for 2015!
Feb Qiaomin’s Power of d Choices for Large-Scale Bin Packing: A Loss Model accepted to Sigmetrics 2015
Feb Qiaomin presented Near-data Scheduling at CSL student conference 2015
Our current focus is on performance, scalability and energy efficiency of data-intensive clouds. Other themes include compressed measurement, network algorithms and imaging.
You can check out our complete list of publications. Below is an overview of our projects.
Power-of-d choices, asymptotic independence and distributed scheduling
Stateless randomized load balancing is a natural fit for distributed schedulers and scalable high-performance. Power-of-two choices is a well-known randomized routing algorithm. However, we found that two choices are not enough for general service time distributions:
- Randomized Load Balancing with General Service Time Distributions [Sigmetrics 2010],
- Decay of Tails at Equilibrium for FIFO Join the Shortest Queue Networks [Annals of Applied Probability 2013],
and we need power-of-d choices where d depends on the service time distribution. For a heavy-tailed distribution with parameter ß, only d > ß / (ß-1) brings a qualitative change in performance.
To remove the dependence on service time distribution, we proposed the Join-Idle-Queue (JIQ) algorithm, which uses reverse information balancing and outperforms power-of-d:
- Join-Idle-Queue: A Novel Load Balancing Algorithm for Dynamically Scalable Web Services [Performance 2011] Best Paper Award.
We proved the asymptotic independence property in order to study power-of-d choices with general service time distributions:
which we also used to study the problem of virtual machine assignment:
- Power of d Choices for Large-Scale Bin Packing: A Loss Model [Sigmetrics 2015].
Data, Data, and Data
Data placement and data popularity induce a random load distribution on a system, which makes scheduling in data-intensive clouds a fundamentally different problem from other large-scale clusters: A scheduler needs to be robust with respect to load distributions.
We first studied the data placement problem with a given scheduler,
- DARE: Adaptive Data Replication for Efficient Cluster Scheduling [Cluster 2011],
and then the scheduling problem with a given data placement. Our priority algorithm is the only known algorithm that is heavy-traffic optimal for all load distributions.
- Degree-Guided Map-Reduce Task Assignment with Data Locality Constraint [ISIT 2012]
- Priority Algorithm for Near-data Scheduling: Throughput and Heavy-Traffic Optimality [Infocom 2015].
Workload and Meta-data
In order to understand the characteristics of data-processing applications, we analyzed workloads from production clusters:
- A Storage-Centric Analysis of MapReduce Workloads: File Popularity, Temporal Locality and Arrival Patterns [IISWC 2012]
- Metadata Traces and Workload Models for Evaluating Big Storage Systems [UCC 2012].
We also studied efficient trace generation to enable fast and reliable evaluation of a large system in a small test bed:
- Generating Request Streams on Big Data using Clustered Renewal Processes [Performance 2013]
- A Model-Based Namespace Metadata Benchmark for HDFS [ICAC:MBDS 2014].
Compressed Measurement (or Counter Braids)
- Robust Counting via Counter Braids: An Error-Resilient Network Measurement Architecture [Infocom 2009]
- Counter Braids: Asymptotic Optimality of the Message Passing Decoding Algorithm [Allerton 2008]
- Counter Braids: A Novel Counter Architecture for Per-Flow Measurement [Sigmetrics 2008] Best Paper Award
- Detailed Network Measurements Using Sparse Graph Counters: The Theory [Allerton 2007]
Water-fat separation, MRI and a Jigsaw Puzzle
- JIGSAW: Joint Inhomogeneity estimation via Global Segment Assembly for Water-fat separation [TMI 2011]
- Message Passing for In-vivo Field Map Estimation in MRI [ISBI 2010]
- W. Lu, Y. Lu, “JIGSAW: Joint Inhomogeneity estimation via Global Segment Assembly for Water-fat separation,” Patent number 7952353. (Licensed by General Electric Healthcare, 2009)
Current: Qiaomin Xie, Ali Yekkehkhany, Du Su
Past (An Unofficial List):
David Stein (M.S.), LinkedIn
Mindi Yuan (M.S.)
Cristina Abad (Ph.D.) (Advisor: Roy Campbell), Escuela Superior Polit´ecnica del Litoral
Mayank Pundir (M.S.) (Advisor: Roy Campbell), Facebook
Victor Brakauskas (B.S.)
Caleb Qian (B.S.)
- ECE598YL / CS598 — Cloud Computing: Systems and Algorithms
- ECE 313 — Probability with Engineering Applications
Honors and Awards
- ACM SIGMETRICS Rising star award (2016)
- Center of Advanced Study Fellow (2014)
- NSF Career Award (2012)
- Best Paper Award at IFIP Performance conference (2011)
- Best Paper Award at ACM SIGMETRICS (2008)
- Stanford Graduate Fellowship Award (2005)
- Frederick Emmons Terman Engineering Scholastic Award, School of Engineering, Stanford University (2004)
- Gold medal, Individual 4th, Singapore Mathematical Olympiad (1999)