[CV] [Publications] [Programming team]

Research Interests

Algorithms on massive data; external memory algorithms; data structures; database algorithms; algorithms on distributed data; data streams; computational geometry.

Exploiting the rich interdependence between theory and practice is the main theme of my research. I always strive to design algorithms with nice theoretical guarantees that also work well in practice. I like simple algorithms with nontrivial and elegant analyses. I like theories that bring insights to how things should be done in practice (this includes lower bounds!).

I belong to both the Theoretical Computer Science group and the Database group at HKUST.

I am the coordinator of the theory seminar. If you are interested in giving a talk, please drop me a line.

Overview slides on some topics of my recent interests

Recent Publications

External memory algorithms and data structures (including database indexing):
An Optimal Dynamic Data Structure for Stabbing-Semigroup Queries, SICOMP
Beyond Simple Aggregates: Indexing for Summary Queries, PODS'11
Flexible Aggregate Similarity Search, SIGMOD'11
Tree Indexing on Solid State Drives, VLDB'10
Cache-Oblivious Hashing, PODS'10
On the Cell Probe Complexity of Dynamic Membership, SODA'10
Dynamic External Hashing: The Limit of Buffering, SPAA'09
Dynamic Indexability and the Optimality of B-trees, PODS'09, JACM
Indexing Uncertain Data, PODS'09
Efficient and Accurate Nearest Neighbor and Closest Pair Search in High Dimensional Space, SIGMOD'09, TODS'10
I/O-Efficient Batched Union-Find and Its Applications to Terrain Analysis, SoCG'06, TALG'10

Algorithms on distributed data:
Building Wavelet Histograms on Large Data in MapReduce, VLDB'12
Sampling Based Algorithms for Quantile Computation in Sensor Networks, SIGMOD'11
Optimal Sampling Algorithms for Frequency Estimation in Distributed Data, INFOCOM'11
Continuous Sampling from Distributed Streams, PODS'10, JACM
Optimal Tracking of Distributed Heavy Hitters and Quantiles, PODS'09
Ranking Distributed Probabilistic Data, SIGMOD'09
Multi-Dimensional Online Tracking, SODA'09, TALG
Algorithms for Distributed Functional Monitoring, SODA'08, TALG'11

Miscellaneous topics on databases:
Logging Every Footstep: Quantile Summaries for the Entire History, SIGMOD'10
Probabilistic String Similarity Joins, SIGMOD'10
Small Synopses for Group-By Query Verification on Outsourced Data Streams, TODS'09
Sliding-Window Top-k Queries on Uncertain Streams, VLDB'08, VLDBJ'10
Finding Frequent Items in Probabilistic Data, SIGMOD'08
Proof-Infused Streams: Enabling Authentication of Sliding Window Queries on Streams, VLDB'07

Full list here with slides and code.

Students

I am currently working with the following great students:

• Zengfeng Huang (PhD, since Fall 2008)
• Zhewei Wei (PhD, since Fall 2008)
• Lu Wang (PhD, since Fall 2009)
• Luo Ge (PhD, since Spring 2010)

Former students:

• Qin Zhang (PhD, 2010; now postdoc at MADALGO, University of Aarhus)
• Ching-Hin Lau (MPhil, 2009; now at Thomson Reuters)
• Wenqi Zhu (MPhil, 2008; now at Morgan Stanley)

Grants

• HKUST Research Project Competition, "Communication-Efficient Algorithms for Tracking Distributed Data Streams", 2011.
  
• Google Faculty Research Award, "Computing Statistical Summaries with MapReduce", 2010.

Teaching

Now:	COMP3721: Theory of Computation
---------------
Fall 2011:	COMP3711: Design and Analysis of Algorithms
Spring 2011:	COMP272: Theory of Computation
Fall 2010:	COMP670S: Data Stream Algorithms
Spring 2010:	COMP573: Computational Geometry
Fall 2009:	COMP271: Design and Analysis of Algorithms COMP670R: Topics in Theory: Hashing
Spring 2009:	COMP271: Design and Analysis of Algorithms
Fall 2008:	COMP271: Design and Analysis of Algorithms
Spring 2008:	COMP670Q: I/O-Efficient Algorithms and Data Structures

Programming Team

I am the coach of the HKUST programming team. Contact me if you are interested in solving challenging algorithmic problems (and traveling to places for free!).

Last update: today