Ke (Kevin) Yi
|
Assistant Professor Department of Computer Science
and Engineering Office: Room 3552 (via lifts 25, 26) Email: user name in the url@cse.ust.hk Phone: +852-2358 8770 |
[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
Tracking Distributed Data
Computing Statistical Summaries over Massive
Distributed Data
Dynamic Indexability and the Optimality of
B-trees and Hash Tables
Recent Publications
External memory algorithms and data structures (including database
indexing):
An Optimal Dynamic Data Structure for
Stabbing-Semigroup Queries, SICOMP'12
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, TALG
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:
Mergeable Summaries, PODS'12
Randomized Algorithms for Tracking Distributed
Count, Frequencies, and Ranks, PODS'12
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, Algorithmica
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:
Verifying Computations with Streaming
Interactive Proofs, VLDB'12
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:
Former students:
Grants
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
