Ke YI
易珂
PhD in Computer Science
Duke University, 2006

Professor
Department of Computer Science and Engineering

Program Director of MSc Program in Big Data Technology



(852) 2358 8770
yike@ust.hk
Room 3547
Personal Web

---

Google Scholar
dWcZPFEAAAAJ

ORCID
0000-0002-2178-3716

Scopus ID
35800286800




Research Interest Publications Projects Teaching Assignment RPG Supervision Space used




Research Interest

---

Database systems
Parallel and distributed algorithms
Sampling
Differential privacy
Data streams



Publications

---

All Years 121 2022 1 2021 4 2020 6 2019 7 2018 2 2017 6 2016 95

---

Expand All Collapse All


2022 1

Intersection Joins Under Updates
Journal of Computer and System Sciences, v. 124, March 2022, p. 41-64
Tao, Yufei; Yi, Ke Article

2021 4

Approximate Range Counting Under Differential Privacy
Leibniz International Proceedings in Informatics, LIPIcs, v. 189, June 2021, article number 45
Huang, Ziyue; Yi, Ke Conference paper
Residual Sensitivity for Differentially Private Multi-Way Joins
SIGMOD/PODS '21: Proceedings of the 2021 International Conference on Management of Data, New York, NY, United States : Association for Computing Machinery, 2021, p. 432-444
Dong, Wei; Yi, Ke Conference paper
Secure Yannakakis: Join-Aggregate Queries over Private Data
SIGMOD/PODS '21: Proceedings of the 2021 International Conference on Management of Data, New York, NY, United States : Association for Computing Machinery, 2021, p. 1969-1981
Wang, Yilei; Yi, Ke Conference paper
Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries
SIGMOD/PODS '21: Proceedings of the 2021 International Conference on Management of Data / ACM. New York, NY, United States : ACM, 2021, p. 1465-1477
Qiu, Yuan; Wang, Yilei; Yi, Ke; Li, Feifei; Wu, Bin; Zhan, Chaoqun Conference paper

2020 6

Massively Parallel Join Algorithms
SIGMOD Record, v. 49, (3), September 2020, p. 6-17
Hu, Xiao; Yi, Ke Article
Small Summaries for Big Data
Small Summaries for Big Data / Graham Cormode, Ke Yi. New York: Cambridge University Press, 2020
Cormode, Graham; Yi, Ke Book
Maintaining Acyclic Foreign-Key Joins under Updates
SIGMOD '20: Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data / ACM SIGMOD. New York, USA : ACM, 2020, p. 1225-1239
Wang, Qichen; Yi, Ke Conference paper
Parallel Algorithms for Sparse Matrix Multiplication and Join-Aggregate Queries
PODS'20: Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems / ACM SIGMOD, ACM SIGACT and ACM SIGAI. New York, USA : ACM, 2020, p. 411-425
Hu, Xiao; Yi, Ke Conference paper
Querying Shared Data with Security Heterogeneity
SIGMOD '20: Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, Association for Computing Machinery. New York, USA : Association for Computing Machinery, 2020, p. 575-585
Cao, Yang; Fan, Wenfei; Wang, Yanghao; Yi, Ke Conference paper
Random sampling and size estimation over cyclic joins
Leibniz International Proceedings in Informatics, LIPIcs, v. 155, March 2020, article number 7
Chen, Yu; Yi, Ke Conference paper

2019 7

Output-Optimal Massively Parallel Algorithms for Similarity Joins
ACM Transactions on Database Systems, v. 44, (2), April 2019, article number 6
Hu, Xiao; Yi, Ke; Tao, Yufei Article
Randomized Algorithms for Tracking Distributed Count, Frequencies, and Ranks
Algorithmica, v. 81, (6), June 2019, p. 2222-2243
Huang, Zengfeng; Yi, Ke; Zhang, Qin Article
Technical perspective: Online model management via temporally biased sampling
SIGMOD Record, v. 48, (1), March 2019, p. 68
Yi, Ke Article
Wander Join and XDB: Online Aggregation via Random Walks
ACM Transaction On Database Systems, v.44, (1), January 2019, article number 2
Li, Feifei; Wu, Bin; Yi, Ke; Zhao, Zhuoyue Article
Instance and output optimal parallel algorithms for acyclic joins
Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 2019, p. 450-463
Hu, Xiao; Yi, Ke Conference paper
Optimal Sparsity-Sensitive Bounds for Distributed Mean Estimation
Advances in Neural Information Processing Systems 34 (NIPS 2019), v. 32, 2019
Huang, Zengfeng; Huang, Ziyue; Wang, Yilei; Yi, Ke Conference paper
Streaming HyperCube: A Massively Parallel Stream Join Algorithm
22nd International Conference on Extending Database Technology (EDBT), Lisbon, Portugal, 26-29 March 2019
Qiu, Yuan; Serafeim, Papadias; Yi, Ke Conference paper

2018 2

Tight Space Bounds for Two-Dimensional Approximate Range Counting
ACM Transactions on Algorithms, v. 14, (2), June 2018, article number 23
Wei, Zhewei; Yi, Ke Article
Random Sampling over Joins Revisited
Proceedings of the ACM SIGMOD International Conference on Management of Data, May 2018, p. 1525-1539
Zhao, Zhuoyue; Christensen, Robert; Li, Feifei; Hu, Xiao; Yi, Ke Conference paper

2017 6

On Improving Wireless Channel Utilization: A Collision Tolerance-Based Approach
IEEE Transactions on Mobile Computing, v. 16, (3), March 2017, article number 7469330, p. 787-800
Ji, Xiaoyu; He, Yuan; Wang, Jiliang; Wu, Kaishun; Liu, Daibo; Yi, Ke; Liu, Yunhao Article
The Communication Complexity of Distributed Epsilon-Approximations
SIAM Journal on Computing, v.46, (4), 2017, p. 1370-1394
Huang, Zengfeng; Yi, Ke Article
Wander Join and XDB: Online Aggregation via Random Walks
ACM SIGMOD Record, v. 46, (1), March 2017
Li, Feifei; Wu, Bin; Yi, Ke; Zhao, Zhuoyue Article
Output-optimal Parallel Algorithms for Similarity Joins
Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, v. Part F127745, May 2017, p. 79-90
Hu, Xiao; Tao, Yufei; Yi, Ke Conference paper
TUM: Towards Ubiquitous Multi-Device Localization for Cross-Device Interaction
Proceedings - IEEE INFOCOM, October 2017, article number 8057102
Xu, Han; Yang, Zheng; Zhou, Zimu; Yi, Ke; Peng, Chunyi Conference paper
Two-Level Sampling for Join Size Estimation
Proceedings of the ACM International Conference on Management of Data (SIGMOD 2017), v. Part F127746, May 2017, p. 759-774
Chen, Yu; Yi, Ke Conference paper

2016 9

Counting Triangles in Large Graphs by Random Sampling
IEEE Transactions on Knowledge and Data Engineering, v. 28, (8), August 2016, article number 7457266, p. 2013-2026
Wu, Bin; Yi, Ke; Li, Zhenguo Article
Exact and approximate flexible aggregate similarity search
VLDB Journal, v. 25, (3), June 2016, p. 317-338
Li, Feifei; Yi, Ke; Tao, Yufei; Yao, Bin; Li, Yang; Xie, Dong; Wang, Min Article
Nearest-Neighbor Searching Under Uncertainty II
ACM Transactions on Algorithms, v. 13, (1), October 2016, article number 3
Agarwal, Pankaj Kumar; Aronov, Boris; Har-Peled, Sariel Peled; Phillips, Jeff Mark; Yi, Ke; Zhang, Wuzhou Article
Quantiles Over Data Streams: Experimental Comparisons, New Analyses, and Further Improvements
VLDB Journal, v. 25, (4), August 2016, p. 449-472
Luo, Ge; Wang, Lu; Yi, Ke; Cormode, Graham Article
Indoor Localization via Multi-modal Sensing on Smartphones
UbiComp 2016 - Proceedings of the 2016 ACM International Joint Conference on Pervasive and Ubiquitous Computing, September 2016, p. 208-219
Xu, Han; Yang, Zheng; Zhou, Zimu; Shangguan, Longfei; Yi, Ke; Liu, Yunhao Conference paper
Spatial Online Sampling and Aggregation
Proceedings of the VLDB Endowment, v. 9, (3), Sep 2016, p. 84-95
Wang, Lu; Christensen, Robert; Li, Feifei; Yi, Ke Conference paper
Towards a Worst-case I/O-optimal Algorithm for Acyclic Joins
Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, v. 26-June-01-July-2016, June 2016, p. 135-150
Hu, Xiao; Yi, Ke Conference paper
Wander Join: Online Aggregation for Joins
Proceedings of the 2016 International Conference on Management of Data, v. 26-June-2016, June 2016, p. 2121-2124
Li, Feifei; Wu, Bin; Yi, Ke; Zhao, Zhuoyue Conference paper
Wander Join: Online Aggregation via Random Walks
Proceedings of the ACM SIGMOD International Conference on Management of Data, v. 26-June-2016, June 2016, p. 615-629
Li, Feifei; Wu, Bin; Yi, Ke; Zhao, Zhuoyue Conference paper

2015 4

Enhancing Wifi-based Localization with Visual Clues
Proceedings of the 2015 ACM International Joint Conference on Pervasive and Ubiquitous Computing, New York, NY, USA : ACM, 2015, p. 963-974
Xu, Han; Yang, Zheng; Zhou, Zimu; Shangguan, Longfei; Yi, Ke; Liu, Yunhao Conference paper
Persistent Data Sketching
SIGMOD '15: Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, v. 2015-May, May 2015, p. 795-810
Wei, Zhewei; Luo, Ge; Yi, Ke; Du, Xiaoyong; Wen, Jirong Conference paper
Piecewise Linear Approximation of Streaming Time Series Data with Max-error Guarantees
2015 IEEE 31st International Conference on Data Engineering (ICDE 2015), Institute of Electrical and Electronics Engineers (IEEE), 2015, p. 173-184
Luo, Ge; Yi, Ke; Cheng, Siu-Wing; Li, Zhenguo; Fan, Wei; He, Cheng; Mu, Yadong Conference paper
STORM: Spatio-Temporal Online Reasoning and Management of Large Spatio-Temporal Data
SIGMOD 2015: Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, v. 2015-May, May 2015, p. 1111-1116
Christensen, Robert; Wang, Lu; Li, Feifei; Yi, Ke; Tang, Jun; Villa, Natalee Conference paper

2014 5

Cache-oblivious hashing
Algorithmica, v. 69, (4), 2014, p. 864-883
Pagh, Rasmus; Wei, Zhewei; Yi, Ke; Zhang, Qin Article
Indexing for Summary Queries: Theory and Practice
ACM Transactions on Database Systems, v. 39, (1), January 2014, article number a2
Yi, Ke; Wang, Lu; Wei, Zhewei Article
Equivalence between priority queues and sorting in external memory
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), v. 8737 LNCS, 2014, p. 830-841
Wei, Zhewei; Yi, Ke Conference paper
Robust Set Reconciliation
Proceedings of the ACM SIGMOD International Conference on Management of Data, 2014, p. 135-146
Chen, Di; Konrad, Christian; Yi, Ke; Yu, Wei; Zhang, Qin Conference paper
The Communication Complexity of Distributed Epsilon-approximations
Proceedings - Annual IEEE Symposium on Foundations of Computer Science, December 2014, article number 6979044, p. 591-600
Huang, Zengfeng; Yi, Ke Conference paper

2013 8

Efficient external memory structures for range-aggregate queries
Computational Geometry: Theory and Applications, v. 46, (3), April 2013, p. 358-370
Agarwal, Pankaj K.; Arge, Lars; Govindarajan, Sathish; Yang, Jun; Yi, Ke Article
Mergeable Summaries
ACM transactions on database systems, v.38, (4), November 2013
Agarwal, Pankaj K.; Cormode, Graham; Huang, Zengfeng; Phillips, Jeff M.; Wei, Zhewei; Yi, Ke Article
Optimal Tracking of Distributed Heavy Hitters and Quantiles
Algorithmica, v. 65, (1), January 2013, p. 206-223
Yi, Ke; Zhang, Qin Article
Nearest Neighbor Searching under Uncertainty II
Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, New York, NY, USA : ACM, 2013, p. 115-126
Agarwal, P.K.; Aronov, B.; Har-peled, S.; Phillips, J.M.; Yi, K.; Zhang, W. Conference paper
Quantiles over Data Streams: An Experimental Study
Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, New York, NY, USA : ACM, 2013, p. 737-748
Wang, Lu; Luo, Ge; Yi, Ke; Cormode, Graham Conference paper
Streaming Authenticated Data Structures
Lecture Notes in Computer Science, v. 7881, 2013, p. 353-370
Papamanthou, Charalampos; Shi, Elaine; Tamassia, Roberto; Yi, Ke Conference paper
The Space Complexity of 2-Dimensional Approximate Range Counting
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, v. 2013, 2013, p. 252-264
Wei, Zhewei; Yi, Ke Conference paper
Voice over the Dins: Improving Wireless Channel Utilization with Collision Tolerance
2013 21st IEEE International Conference on Network Protocols (ICNP), Editors: Xiaoming Fu, Volker Hilt, Tilman Wolf, Lixia Zhang, and Zhi-Li Zhang. Institute of Electrical and Electronics Engineers (IEEE), 2013
Ji, Xiaoyu; He, Yuan; Wang, Jiliang; Wu, Kaishun; Yi, Ke; Liu, Yunhao Conference paper

2012 9

AN OPTIMAL DYNAMIC DATA STRUCTURE FOR STABBING-SEMIGROUP QUERIES
SIAM journal on computing, v. 41, (1), 2012, p. 104-127
Agarwal, Pankaj K.; Arge, Lars; Kaplan, Haim; Molad, Eyal; Tarjan, Robert E.; Yi, Ke Article
Continuous Sampling from Distributed Streams
Journal of the Association for Computing Machinery, v. 59, (2), 2012, Apr, Article number 10
Cormode, Graham; Muthukrishnan, S.; Yi, Ke; Zhang, Qin Article
Dynamic Indexability and the Optimality of B-Trees
Journal of the Association for Computing Machinery, v. 59, (4), 2012, Aug, Article number 21
Yi, Ke Article
Range Searching on Uncertain Data
ACM transactions on algorithms, v. 8, (4), September 2012, Article 43
Agarwal, Pankaj K.; Cheng, Siu-Wing; Yi, Ke Article
Building Wavelet Histograms on Large Data in MapReduce
Proceedings of the VLDB Endowment, v.5, (2), 2011, p.109-120
Jestes, Jeffrey; Yi, Ke; Li, Feifei Conference paper
Mergeable summaries
Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2012, p. 23-34
Agarwal, Pankaj Kumar; Cormode, Graham; Huang, Zengfeng; Phillips, Jeff Mark; Wei, Zhewei; Yi, Ke Conference paper
Randomized algorithms for tracking distributed count, frequencies, and ranks
Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2012, p. 295-305
Huang, Zengfeng; Yi, Ke; Zhang, Qin Conference paper
Tracking distributed aggregates over time-based sliding windows
Lecture Notes in Computer Science, v. 7338, 2012, p. 416-430
Cormode, Graham; Yi, Ke Conference paper
Verifying Computations with Streaming Interactive Proofs
Proceedings of the VLDB Endowment, v.5, (1), 2011, p.25-36
Cormode, Graham; Thaler, Justin; Yi, Ke Conference paper

2011 9

Algorithms for Distributed Functional Monitoring
ACM transactions on algorithms, v. 7, (2), March 2011, Article no.: 21
Cormode, Graham; Muthukrishnan, S.; Yi, Ke Article
Approximate Range Searching in External Memory
Algorithmica, v. 59, (2), February 2011, p. 115-128
Streppel, Micha; Yi, Ke Article
Semantics of Ranking Queries for Probabilistic Data
IEEE transactions on knowledge and data engineering, v. 23, (12), December 2011, p. 1903-1917
Jestes, Jeffrey; Cormode, Graham; Li, Feifei; Yi, Ke Article
The world in a nutshell: Concise range queries
IEEE transactions on knowledge and data engineering, v. 23, (1), 2011, Article number 5416721, p. 139-154
Yi, Ke; Lian, Xiang; Li, Feifei; Chen, Lei Article
Beyond simple aggregates: Indexing for summary queries
Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 2011, p. 117-128
Wei, Zhewei; Yi, Ke Conference paper
Brief Announcement: Tracking distributed aggregates over time-based sliding windows
Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, v. 2011, 2011, p. 213-214
Cormode, Graham; Yi, Ke Conference paper
Flexible aggregate similarity search
Proceedings - ACM-SIGMOD International Conference on Management of Data, June 2011, p. 1009-1020
Li, Yang; Li, Feifei; Yi, Ke; Yao, Bin; Wang, Min Conference paper
Optimal Sampling Algorithms for Frequency Estimation in Distributed Data
Proceedings - IEEE INFOCOM, April 2011, p. 1997-2005
Huang, Zengfeng; Yi, Ke; Liu, Yunhao; Chen, Guihai Conference paper
Sampling based algorithms for quantile computation in sensor networks
The 2011 ACM SIGMOD/PODS Conference, Athens, Greece. Proceedings - ACM-SIGMOD International Conference on Management of Data, New York, USA, Juen 2011, p. 745-756
Huang, Zengfeng; Wang, Lu; Yi, Ke; Liu, Yunhao Conference paper

2010 14

Efficient and Accurate Nearest Neighbor and Closest Pair Search in High-Dimensional Space
ACM transactions on database systems, v. 35, (3), 2010, JUL
Tao, Yufei; Yi, Ke; Sheng, Cheng; Kalnis, Panos Article
I/O-efficient batched union-find and its applications to terrain analysis
ACM Transactions on Algorithms, v. 7, (1), 2010
Agarwal, P.K.; Arge, L.; Yi, K. Article
Multidimensional online tracking
ACM Transactions on Algorithms, v. 8, (2), April 2012, article number 12
Yi, Ke; Zhang, Qin Article
Sliding-window top-k queries on uncertain streams
VLDB JOURNAL, v. 19, (3), 2010, JUN, p. 411-435
Jin, Cheqing; Yi, Ke; Chen, Lei; Yu, Jeffrey Xu; Lin, Xuemin Article
Top-k queries on temporal data
VLDB JOURNAL, v. 19, (5), 2010, OCT, p. 715-733
Li, Feifei; Yi, Ke; Le, Wangchao Article
Tree Indexing on Solid State Drives
Proceedings of the VLDB Endowment, v. 3, (1-2), September 2010, p. 1195-1206
Li, Yinan; He, Bingsheng; Yang, Robin Jun; Luo, Qiong; Yi, Ke Article
Cache-oblivious hashing
Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2010, p. 297-304
Pagh, Rasmus; Wei, Zhewei; Yi, Ke; Zhang, Qin Conference paper
Clustering with Diversity
Lecture Notes in Computer Science, v. 6198, 2010, p. 188-200
Li, Jian; Yi, Ke; Zhang, Qin Conference paper
Correlation Hiding by Independence Masking
International Conference on Data Engineering (ICDE), 2010, p. 964-967
Tao, Yufei; Pei, Jian; Li, Jiexing; Xiao, Xiaokui; Yi, Ke; Xing, Zhengzheng Conference paper
Logging every footstep: Quantile summaries for the entire history
Proceedings of the ACM SIGMOD International Conference on Management of Data, 2010, p. 639-650
Tao, Y.; Yi, K.; Sheng, C.; Pei, J.; Li, F. Conference paper
On the cell probe complexity of dynamic membership
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2010, p. 123-133
Yi, K.; Zhang, Q. Conference paper
Optimal sampling from distributed streams
Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2010, p. 77-86
Cormode, Graham; Muthukrishnan, S.; Yi, Ke; Zhang, Qin Conference paper
Probabilistic string similarity joins
Proceedings of the ACM SIGMOD International Conference on Management of Data, 2010, p. 327-338
Jestes, J.; Li, F.; Yan, Z.; Yi, K. Conference paper
The hardness and approximation algorithms for L-diversity
Advances in Database Technology - EDBT 2010 - 13th International Conference on Extending Database Technology, Proceedings, 2010, p. 135-146
Xiao, X.; Yi, K.; Tao, Y. Conference paper

2009 12

Optimal External Memory Planar Point Enclosure
Algorithmica, v. 54, (3), 2009, JUL, p. 337-352
Arge, Lars; Samoladas, Vasilis; Yi, Ke Article
Quality and efficiency in high dimensional Nearest neighbor search
SIGMOD '09 Proceedings of the 2009 ACM SIGMOD International Conference on Management of data, v. 2009, Jun-Jul, p. 563-575
Tao, Y.; Yi, K.; Sheng, C.; Kalnis, P. Article
Small Synopses for Group-By Query Verification on Outsourced Data Streams
ACM transactions on database systems, v. 34, (3), 2009, Aug, Article number 15
Yi, Ke; Li, Feifei; Cormode, Graham; Hadjieleftheriou, Marios; Kollios, George; Srivastava, Divesh Article
A Concise Representation of Range Queries
International Conference on Data Engineering (ICDE), 2009, p. 1179-1182
Yi, Ke; Lian, Xiang; Li, Feifei; Chen, Lei Conference paper
Change (detection) you can believe in: Finding distributional shifts in data streams
Lecture Notes in Computer Science, v. 5772, 2009, p. 21-34
Dasu, T.; Krishnan, S.; Lin, D.; Venkatasubramanian, S.; Yi, K. Conference paper
Dynamic external hashing: The limit of buffering?
Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2009, p. 253-259
Wei, Z.; Yi, K.; Zhang, Q. Conference paper
Dynamic indexability and lower bounds for dynamic one-dimensional range query indexes
Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2009, p. 187-196
Yi, K. Conference paper
Indexing uncertain data
Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2009, p. 137-146
Agarwal, P.K.; Cheng, S.W.; Tao, Y.; Yi, K. Conference paper
Multi-dimensional online tracking
Proceedings of ACM_SIAM Symposium on Discrete Algorithms, v. 2009, 2009, p. 1098-1107
Yi, Ke; Zhang, Qin Conference paper
Optimal tracking of distributed heavy hitters and quantiles
Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2009, p. 167-174
Yi, K.; Zhang, Q. Conference paper
Ranking distributed probabilistic data
SIGMOD-PODS'09 - Proceedings of the International Conference on Management of Data and 28th Symposium on Principles of Database Systems, 2009, p. 361-373
Li, F.; Yi, K.; Jestes, J. Conference paper
Tree Indexing on Flash Disks
Proceedings - International Conference on Data Engineering, 2009, p. 1303-1306
Li, Yinan; He, Bingsheng; Luo, Qiong; Yi, Ke Conference paper

2008 8

A dynamic data structure for top-k queries on uncertain data
Theoretical Computer Science, v. 407, (1-3), 2008, NOV 6, p. 310-317
Chen, Jiang; Yi, Ke Article
Efficient Processing of Top-k Queries in Uncertain Databases with x-Relations
IEEE transactions on knowledge and data engineering, v. 20, (12), 2008, Dec, p. 1669-1682, article number 4515868
Yi, Ke; Li, Feifei; Kollios, George; Srivastava, Divesh Article
Finding frequent items in probabilistic data
SIGMOD '08 Proceedings of the 2008 ACM SIGMOD international conference on Management of data, v. 2008, Jun, p. 819-831
Zhang, Q.; Li, F.; Yi, K. Article
The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree
ACM transactions on algorithms, v. 4, (1), 2008, MAR
Arge, Lars; De Berg, Mark; Haverkort, Herman; Yi, Ke Article
Algorithms for Distributed Functional Monitoring
ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1076-1085, January 2008
Cormode, Graham; Muthukrishnan, S.; Yi, Ke Conference paper
Efficient Processing of Top-k Queries on Uncertain Databases
Proceedings of the 24th International Conference on Data Engineering, Cancun, Mexico, 7-12 April 2008, 2008, p. 1406-1408
Yi, Ke; Li, Feifei; Kollios, George; Srivastava, Divesh Conference paper
Randomized synopses for query assurance on data streams
Proceedings - International Conference on Data Engineering, 2008, p. 416-425
Yi, K.; Li, F.; Hadjielefthriou, M.; Kollios, G.; Srivastava, D. Conference paper
Sliding-Window Top-k Queries on Uncertain Streams
Proceedings of the VLDB Endowment, v. 1, (1), 2008, p. 301-312
Jin, Cheqing; Yi, Ke; Chen, Lei; Yu, Jeffrey Xu; Lin, Xuemin Conference paper

2007 4

Approximate range searching in external memory
Lecture Notes in Computer Science, v. 4835, 2007, p. 536-548
Streppel, M.; Yi, K. Conference paper
Dynamic structures for top-k queries on uncertain data
Lecture Notes in Computer Science, v. 4835, 2007, p. 427-438
Chen, J.; Yi, K. Conference paper
Proof-Infused Streams: Enabling Authentication of Sliding Window Queries on Streams
International Conference on Very Large Data Bases (VLDB), pages 147-158, Vienna, Austria, September 2007
Li, Feifei; Yi, Ke; Hadjieleftheriou, Marios; Kollios, George Conference paper
TerraStream: From Elevation Data to Watershed Hierarchies
ACM International Symposium on Advances in Geographic Information Systems (ACM GIS), November 2007
Danner, Andrew; Moelhave, Thomas; Yi, Ke; Agarwal, Pankaj; Arge, Lars; Mitasova, Helena Conference paper

2006 2

An Information-Theoretic Approach to Detecting Changes in Multi-Dimensional Data Streams
Proc. Symposium on the Interface of Statistics, Computing Science, and Applications (Interface), May 2006
Dasu, Tamraparni; Krishnan, Shankar; Venkatasubramanian, Suresh; Yi, Ke Conference paper
I/O-Efficient Batched Union-Find and Its Applications to Terrain Analysis
Proc. Annual Symposium on Computational Geometry (SoCG), June 2006
Agarwal, Pankaj K.; Arge, Lars; Yi, Ke Conference paper

2005 4

Optimal Lexicographic Shaping of Aggregate Streaming Data
IEEE Transactions on Computers, v. 54, (4), 2005, p. 398–408
Anastasiadis, Stergios V.; Varman, Peter; Vitter, Jeffrey S.; Yi, Ke Article
An Optimal Dynamic Interval Stabbing-Max Data Structure?
Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2005
Agarwal, Pankaj K.; Arge, Lars; Yi, Ke Conference paper
BOXes: Efficient Maintenance of Order-Based Labeling for Dynamic XML Data
Proc. International Conference on Data Engineering (ICDE), April 2005, p. 285–296
Silberstein, Adam; He, Hao; Yi, Ke; Yang, Jun Conference paper
I/O-Efficient Construction of Constrained Delaunay Triangulations
Proc. Annual European Symposium on Algorithms (ESA), October 2005
Agarwal, Pankaj K.; Arge, Lars; Yi, Ke Conference paper

2004 3

Incremental Maintenance of XML Structural Indexes
Proc. ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2004
Yi, Ke; He, Hao; Stanoi, Ioana; Yang, Jun Conference paper
Optimal External-Memory Planar Point Enclosure
Proc. Annual European Symposium on Algorithms (ESA), September 2004
Arge, Lars; Samoladas, Vasilis; Yi, Ke Conference paper
The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree
Proc. ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2004
Arge, Lars; Berg, Mark de; Haverkort, Herman; Yi, Ke Conference paper

2003 2

Efficient Maintenance of Materialized Top-k Views
Proc. International Conference on Data Engineering (ICDE), March 2003
Yi, Ke; Yu, Hai; Yang, Jun; Xia, Gangqiang; Chen, Yuguo Conference paper
I/O-Efficient Structures for Orthogonal Range-Max and Stabbing-Max Queries
Proc. Annual European Symposium on Algorithms (ESA), September 2003
Agarwal, Pankaj K.; Arge, Lars; Yang, Jun; Yi, Ke Conference paper

2002 1

Lexicographically Optimal Smoothing for Broadband Traffic Multiplexing
Proc. ACM Symposium on Principles of Distributed Computing (PODC), July 2002
Anastasiadis, Stergios; Varman, Peter; Vitter, Jeffrey S.; Yi, Ke Conference paper

1991 1

Semantics of Ranking Queries for Probabilistic Data
IEEE Transactions on Communications, v. 39, (12), 1991, p. 1794-1801
Jestes, Jeffrey; Cormode, Graham; Li, Feifei; Yi, Ke Article


Expand All Collapse All


Article 1

Intersection Joins Under Updates
Journal of Computer and System Sciences, v. 124, March 2022, p. 41-64
Tao, Yufei; Yi, Ke


Expand All Collapse All


Conference paper 4

Approximate Range Counting Under Differential Privacy
Leibniz International Proceedings in Informatics, LIPIcs, v. 189, June 2021, article number 45
Huang, Ziyue; Yi, Ke
Residual Sensitivity for Differentially Private Multi-Way Joins
SIGMOD/PODS '21: Proceedings of the 2021 International Conference on Management of Data, New York, NY, United States : Association for Computing Machinery, 2021, p. 432-444
Dong, Wei; Yi, Ke
Secure Yannakakis: Join-Aggregate Queries over Private Data
SIGMOD/PODS '21: Proceedings of the 2021 International Conference on Management of Data, New York, NY, United States : Association for Computing Machinery, 2021, p. 1969-1981
Wang, Yilei; Yi, Ke
Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries
SIGMOD/PODS '21: Proceedings of the 2021 International Conference on Management of Data / ACM. New York, NY, United States : ACM, 2021, p. 1465-1477
Qiu, Yuan; Wang, Yilei; Yi, Ke; Li, Feifei; Wu, Bin; Zhan, Chaoqun


Expand All Collapse All


Article 1

Massively Parallel Join Algorithms
SIGMOD Record, v. 49, (3), September 2020, p. 6-17
Hu, Xiao; Yi, Ke

Book 1

Small Summaries for Big Data
Small Summaries for Big Data / Graham Cormode, Ke Yi. New York: Cambridge University Press, 2020
Cormode, Graham; Yi, Ke

Conference paper 4

Maintaining Acyclic Foreign-Key Joins under Updates
SIGMOD '20: Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data / ACM SIGMOD. New York, USA : ACM, 2020, p. 1225-1239
Wang, Qichen; Yi, Ke
Parallel Algorithms for Sparse Matrix Multiplication and Join-Aggregate Queries
PODS'20: Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems / ACM SIGMOD, ACM SIGACT and ACM SIGAI. New York, USA : ACM, 2020, p. 411-425
Hu, Xiao; Yi, Ke
Querying Shared Data with Security Heterogeneity
SIGMOD '20: Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, Association for Computing Machinery. New York, USA : Association for Computing Machinery, 2020, p. 575-585
Cao, Yang; Fan, Wenfei; Wang, Yanghao; Yi, Ke
Random sampling and size estimation over cyclic joins
Leibniz International Proceedings in Informatics, LIPIcs, v. 155, March 2020, article number 7
Chen, Yu; Yi, Ke


Expand All Collapse All


Article 4

Output-Optimal Massively Parallel Algorithms for Similarity Joins
ACM Transactions on Database Systems, v. 44, (2), April 2019, article number 6
Hu, Xiao; Yi, Ke; Tao, Yufei
Randomized Algorithms for Tracking Distributed Count, Frequencies, and Ranks
Algorithmica, v. 81, (6), June 2019, p. 2222-2243
Huang, Zengfeng; Yi, Ke; Zhang, Qin
Technical perspective: Online model management via temporally biased sampling
SIGMOD Record, v. 48, (1), March 2019, p. 68
Yi, Ke
Wander Join and XDB: Online Aggregation via Random Walks
ACM Transaction On Database Systems, v.44, (1), January 2019, article number 2
Li, Feifei; Wu, Bin; Yi, Ke; Zhao, Zhuoyue

Conference paper 3

Instance and output optimal parallel algorithms for acyclic joins
Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 2019, p. 450-463
Hu, Xiao; Yi, Ke
Optimal Sparsity-Sensitive Bounds for Distributed Mean Estimation
Advances in Neural Information Processing Systems 34 (NIPS 2019), v. 32, 2019
Huang, Zengfeng; Huang, Ziyue; Wang, Yilei; Yi, Ke
Streaming HyperCube: A Massively Parallel Stream Join Algorithm
22nd International Conference on Extending Database Technology (EDBT), Lisbon, Portugal, 26-29 March 2019
Qiu, Yuan; Serafeim, Papadias; Yi, Ke


Expand All Collapse All


Article 1

Tight Space Bounds for Two-Dimensional Approximate Range Counting
ACM Transactions on Algorithms, v. 14, (2), June 2018, article number 23
Wei, Zhewei; Yi, Ke

Conference paper 1

Random Sampling over Joins Revisited
Proceedings of the ACM SIGMOD International Conference on Management of Data, May 2018, p. 1525-1539
Zhao, Zhuoyue; Christensen, Robert; Li, Feifei; Hu, Xiao; Yi, Ke


Expand All Collapse All


Article 3

On Improving Wireless Channel Utilization: A Collision Tolerance-Based Approach
IEEE Transactions on Mobile Computing, v. 16, (3), March 2017, article number 7469330, p. 787-800
Ji, Xiaoyu; He, Yuan; Wang, Jiliang; Wu, Kaishun; Liu, Daibo; Yi, Ke; Liu, Yunhao
The Communication Complexity of Distributed Epsilon-Approximations
SIAM Journal on Computing, v.46, (4), 2017, p. 1370-1394
Huang, Zengfeng; Yi, Ke
Wander Join and XDB: Online Aggregation via Random Walks
ACM SIGMOD Record, v. 46, (1), March 2017
Li, Feifei; Wu, Bin; Yi, Ke; Zhao, Zhuoyue

Conference paper 3

Output-optimal Parallel Algorithms for Similarity Joins
Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, v. Part F127745, May 2017, p. 79-90
Hu, Xiao; Tao, Yufei; Yi, Ke
TUM: Towards Ubiquitous Multi-Device Localization for Cross-Device Interaction
Proceedings - IEEE INFOCOM, October 2017, article number 8057102
Xu, Han; Yang, Zheng; Zhou, Zimu; Yi, Ke; Peng, Chunyi
Two-Level Sampling for Join Size Estimation
Proceedings of the ACM International Conference on Management of Data (SIGMOD 2017), v. Part F127746, May 2017, p. 759-774
Chen, Yu; Yi, Ke


Expand All Collapse All


Article 4

Counting Triangles in Large Graphs by Random Sampling
IEEE Transactions on Knowledge and Data Engineering, v. 28, (8), August 2016, article number 7457266, p. 2013-2026
Wu, Bin; Yi, Ke; Li, Zhenguo
Exact and approximate flexible aggregate similarity search
VLDB Journal, v. 25, (3), June 2016, p. 317-338
Li, Feifei; Yi, Ke; Tao, Yufei; Yao, Bin; Li, Yang; Xie, Dong; Wang, Min
Nearest-Neighbor Searching Under Uncertainty II
ACM Transactions on Algorithms, v. 13, (1), October 2016, article number 3
Agarwal, Pankaj Kumar; Aronov, Boris; Har-Peled, Sariel Peled; Phillips, Jeff Mark; Yi, Ke; Zhang, Wuzhou
Quantiles Over Data Streams: Experimental Comparisons, New Analyses, and Further Improvements
VLDB Journal, v. 25, (4), August 2016, p. 449-472
Luo, Ge; Wang, Lu; Yi, Ke; Cormode, Graham

Conference paper 5

Indoor Localization via Multi-modal Sensing on Smartphones
UbiComp 2016 - Proceedings of the 2016 ACM International Joint Conference on Pervasive and Ubiquitous Computing, September 2016, p. 208-219
Xu, Han; Yang, Zheng; Zhou, Zimu; Shangguan, Longfei; Yi, Ke; Liu, Yunhao
Spatial Online Sampling and Aggregation
Proceedings of the VLDB Endowment, v. 9, (3), Sep 2016, p. 84-95
Wang, Lu; Christensen, Robert; Li, Feifei; Yi, Ke
Towards a Worst-case I/O-optimal Algorithm for Acyclic Joins
Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, v. 26-June-01-July-2016, June 2016, p. 135-150
Hu, Xiao; Yi, Ke
Wander Join: Online Aggregation for Joins
Proceedings of the 2016 International Conference on Management of Data, v. 26-June-2016, June 2016, p. 2121-2124
Li, Feifei; Wu, Bin; Yi, Ke; Zhao, Zhuoyue
Wander Join: Online Aggregation via Random Walks
Proceedings of the ACM SIGMOD International Conference on Management of Data, v. 26-June-2016, June 2016, p. 615-629
Li, Feifei; Wu, Bin; Yi, Ke; Zhao, Zhuoyue


Expand All Collapse All


Conference paper 4

Enhancing Wifi-based Localization with Visual Clues
Proceedings of the 2015 ACM International Joint Conference on Pervasive and Ubiquitous Computing, New York, NY, USA : ACM, 2015, p. 963-974
Xu, Han; Yang, Zheng; Zhou, Zimu; Shangguan, Longfei; Yi, Ke; Liu, Yunhao
Persistent Data Sketching
SIGMOD '15: Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, v. 2015-May, May 2015, p. 795-810
Wei, Zhewei; Luo, Ge; Yi, Ke; Du, Xiaoyong; Wen, Jirong
Piecewise Linear Approximation of Streaming Time Series Data with Max-error Guarantees
2015 IEEE 31st International Conference on Data Engineering (ICDE 2015), Institute of Electrical and Electronics Engineers (IEEE), 2015, p. 173-184
Luo, Ge; Yi, Ke; Cheng, Siu-Wing; Li, Zhenguo; Fan, Wei; He, Cheng; Mu, Yadong
STORM: Spatio-Temporal Online Reasoning and Management of Large Spatio-Temporal Data
SIGMOD 2015: Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, v. 2015-May, May 2015, p. 1111-1116
Christensen, Robert; Wang, Lu; Li, Feifei; Yi, Ke; Tang, Jun; Villa, Natalee


Expand All Collapse All


Article 2

Cache-oblivious hashing
Algorithmica, v. 69, (4), 2014, p. 864-883
Pagh, Rasmus; Wei, Zhewei; Yi, Ke; Zhang, Qin
Indexing for Summary Queries: Theory and Practice
ACM Transactions on Database Systems, v. 39, (1), January 2014, article number a2
Yi, Ke; Wang, Lu; Wei, Zhewei

Conference paper 3

Equivalence between priority queues and sorting in external memory
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), v. 8737 LNCS, 2014, p. 830-841
Wei, Zhewei; Yi, Ke
Robust Set Reconciliation
Proceedings of the ACM SIGMOD International Conference on Management of Data, 2014, p. 135-146
Chen, Di; Konrad, Christian; Yi, Ke; Yu, Wei; Zhang, Qin
The Communication Complexity of Distributed Epsilon-approximations
Proceedings - Annual IEEE Symposium on Foundations of Computer Science, December 2014, article number 6979044, p. 591-600
Huang, Zengfeng; Yi, Ke


Expand All Collapse All


Article 3

Efficient external memory structures for range-aggregate queries
Computational Geometry: Theory and Applications, v. 46, (3), April 2013, p. 358-370
Agarwal, Pankaj K.; Arge, Lars; Govindarajan, Sathish; Yang, Jun; Yi, Ke
Mergeable Summaries
ACM transactions on database systems, v.38, (4), November 2013
Agarwal, Pankaj K.; Cormode, Graham; Huang, Zengfeng; Phillips, Jeff M.; Wei, Zhewei; Yi, Ke
Optimal Tracking of Distributed Heavy Hitters and Quantiles
Algorithmica, v. 65, (1), January 2013, p. 206-223
Yi, Ke; Zhang, Qin

Conference paper 5

Nearest Neighbor Searching under Uncertainty II
Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, New York, NY, USA : ACM, 2013, p. 115-126
Agarwal, P.K.; Aronov, B.; Har-peled, S.; Phillips, J.M.; Yi, K.; Zhang, W.
Quantiles over Data Streams: An Experimental Study
Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, New York, NY, USA : ACM, 2013, p. 737-748
Wang, Lu; Luo, Ge; Yi, Ke; Cormode, Graham
Streaming Authenticated Data Structures
Lecture Notes in Computer Science, v. 7881, 2013, p. 353-370
Papamanthou, Charalampos; Shi, Elaine; Tamassia, Roberto; Yi, Ke
The Space Complexity of 2-Dimensional Approximate Range Counting
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, v. 2013, 2013, p. 252-264
Wei, Zhewei; Yi, Ke
Voice over the Dins: Improving Wireless Channel Utilization with Collision Tolerance
2013 21st IEEE International Conference on Network Protocols (ICNP), Editors: Xiaoming Fu, Volker Hilt, Tilman Wolf, Lixia Zhang, and Zhi-Li Zhang. Institute of Electrical and Electronics Engineers (IEEE), 2013
Ji, Xiaoyu; He, Yuan; Wang, Jiliang; Wu, Kaishun; Yi, Ke; Liu, Yunhao


Expand All Collapse All


Article 4

AN OPTIMAL DYNAMIC DATA STRUCTURE FOR STABBING-SEMIGROUP QUERIES
SIAM journal on computing, v. 41, (1), 2012, p. 104-127
Agarwal, Pankaj K.; Arge, Lars; Kaplan, Haim; Molad, Eyal; Tarjan, Robert E.; Yi, Ke
Continuous Sampling from Distributed Streams
Journal of the Association for Computing Machinery, v. 59, (2), 2012, Apr, Article number 10
Cormode, Graham; Muthukrishnan, S.; Yi, Ke; Zhang, Qin
Dynamic Indexability and the Optimality of B-Trees
Journal of the Association for Computing Machinery, v. 59, (4), 2012, Aug, Article number 21
Yi, Ke
Range Searching on Uncertain Data
ACM transactions on algorithms, v. 8, (4), September 2012, Article 43
Agarwal, Pankaj K.; Cheng, Siu-Wing; Yi, Ke

Conference paper 5

Building Wavelet Histograms on Large Data in MapReduce
Proceedings of the VLDB Endowment, v.5, (2), 2011, p.109-120
Jestes, Jeffrey; Yi, Ke; Li, Feifei
Mergeable summaries
Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2012, p. 23-34
Agarwal, Pankaj Kumar; Cormode, Graham; Huang, Zengfeng; Phillips, Jeff Mark; Wei, Zhewei; Yi, Ke
Randomized algorithms for tracking distributed count, frequencies, and ranks
Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2012, p. 295-305
Huang, Zengfeng; Yi, Ke; Zhang, Qin
Tracking distributed aggregates over time-based sliding windows
Lecture Notes in Computer Science, v. 7338, 2012, p. 416-430
Cormode, Graham; Yi, Ke
Verifying Computations with Streaming Interactive Proofs
Proceedings of the VLDB Endowment, v.5, (1), 2011, p.25-36
Cormode, Graham; Thaler, Justin; Yi, Ke


Expand All Collapse All


Article 4

Algorithms for Distributed Functional Monitoring
ACM transactions on algorithms, v. 7, (2), March 2011, Article no.: 21
Cormode, Graham; Muthukrishnan, S.; Yi, Ke
Approximate Range Searching in External Memory
Algorithmica, v. 59, (2), February 2011, p. 115-128
Streppel, Micha; Yi, Ke
Semantics of Ranking Queries for Probabilistic Data
IEEE transactions on knowledge and data engineering, v. 23, (12), December 2011, p. 1903-1917
Jestes, Jeffrey; Cormode, Graham; Li, Feifei; Yi, Ke
The world in a nutshell: Concise range queries
IEEE transactions on knowledge and data engineering, v. 23, (1), 2011, Article number 5416721, p. 139-154
Yi, Ke; Lian, Xiang; Li, Feifei; Chen, Lei

Conference paper 5

Beyond simple aggregates: Indexing for summary queries
Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 2011, p. 117-128
Wei, Zhewei; Yi, Ke
Brief Announcement: Tracking distributed aggregates over time-based sliding windows
Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, v. 2011, 2011, p. 213-214
Cormode, Graham; Yi, Ke
Flexible aggregate similarity search
Proceedings - ACM-SIGMOD International Conference on Management of Data, June 2011, p. 1009-1020
Li, Yang; Li, Feifei; Yi, Ke; Yao, Bin; Wang, Min
Optimal Sampling Algorithms for Frequency Estimation in Distributed Data
Proceedings - IEEE INFOCOM, April 2011, p. 1997-2005
Huang, Zengfeng; Yi, Ke; Liu, Yunhao; Chen, Guihai
Sampling based algorithms for quantile computation in sensor networks
The 2011 ACM SIGMOD/PODS Conference, Athens, Greece. Proceedings - ACM-SIGMOD International Conference on Management of Data, New York, USA, Juen 2011, p. 745-756
Huang, Zengfeng; Wang, Lu; Yi, Ke; Liu, Yunhao


Expand All Collapse All


Article 6

Efficient and Accurate Nearest Neighbor and Closest Pair Search in High-Dimensional Space
ACM transactions on database systems, v. 35, (3), 2010, JUL
Tao, Yufei; Yi, Ke; Sheng, Cheng; Kalnis, Panos
I/O-efficient batched union-find and its applications to terrain analysis
ACM Transactions on Algorithms, v. 7, (1), 2010
Agarwal, P.K.; Arge, L.; Yi, K.
Multidimensional online tracking
ACM Transactions on Algorithms, v. 8, (2), April 2012, article number 12
Yi, Ke; Zhang, Qin
Sliding-window top-k queries on uncertain streams
VLDB JOURNAL, v. 19, (3), 2010, JUN, p. 411-435
Jin, Cheqing; Yi, Ke; Chen, Lei; Yu, Jeffrey Xu; Lin, Xuemin
Top-k queries on temporal data
VLDB JOURNAL, v. 19, (5), 2010, OCT, p. 715-733
Li, Feifei; Yi, Ke; Le, Wangchao
Tree Indexing on Solid State Drives
Proceedings of the VLDB Endowment, v. 3, (1-2), September 2010, p. 1195-1206
Li, Yinan; He, Bingsheng; Yang, Robin Jun; Luo, Qiong; Yi, Ke

Conference paper 8

Cache-oblivious hashing
Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2010, p. 297-304
Pagh, Rasmus; Wei, Zhewei; Yi, Ke; Zhang, Qin
Clustering with Diversity
Lecture Notes in Computer Science, v. 6198, 2010, p. 188-200
Li, Jian; Yi, Ke; Zhang, Qin
Correlation Hiding by Independence Masking
International Conference on Data Engineering (ICDE), 2010, p. 964-967
Tao, Yufei; Pei, Jian; Li, Jiexing; Xiao, Xiaokui; Yi, Ke; Xing, Zhengzheng
Logging every footstep: Quantile summaries for the entire history
Proceedings of the ACM SIGMOD International Conference on Management of Data, 2010, p. 639-650
Tao, Y.; Yi, K.; Sheng, C.; Pei, J.; Li, F.
On the cell probe complexity of dynamic membership
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2010, p. 123-133
Yi, K.; Zhang, Q.
Optimal sampling from distributed streams
Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2010, p. 77-86
Cormode, Graham; Muthukrishnan, S.; Yi, Ke; Zhang, Qin
Probabilistic string similarity joins
Proceedings of the ACM SIGMOD International Conference on Management of Data, 2010, p. 327-338
Jestes, J.; Li, F.; Yan, Z.; Yi, K.
The hardness and approximation algorithms for L-diversity
Advances in Database Technology - EDBT 2010 - 13th International Conference on Extending Database Technology, Proceedings, 2010, p. 135-146
Xiao, X.; Yi, K.; Tao, Y.


Expand All Collapse All


Article 3

Optimal External Memory Planar Point Enclosure
Algorithmica, v. 54, (3), 2009, JUL, p. 337-352
Arge, Lars; Samoladas, Vasilis; Yi, Ke
Quality and efficiency in high dimensional Nearest neighbor search
SIGMOD '09 Proceedings of the 2009 ACM SIGMOD International Conference on Management of data, v. 2009, Jun-Jul, p. 563-575
Tao, Y.; Yi, K.; Sheng, C.; Kalnis, P.
Small Synopses for Group-By Query Verification on Outsourced Data Streams
ACM transactions on database systems, v. 34, (3), 2009, Aug, Article number 15
Yi, Ke; Li, Feifei; Cormode, Graham; Hadjieleftheriou, Marios; Kollios, George; Srivastava, Divesh

Conference paper 9

A Concise Representation of Range Queries
International Conference on Data Engineering (ICDE), 2009, p. 1179-1182
Yi, Ke; Lian, Xiang; Li, Feifei; Chen, Lei
Change (detection) you can believe in: Finding distributional shifts in data streams
Lecture Notes in Computer Science, v. 5772, 2009, p. 21-34
Dasu, T.; Krishnan, S.; Lin, D.; Venkatasubramanian, S.; Yi, K.
Dynamic external hashing: The limit of buffering?
Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2009, p. 253-259
Wei, Z.; Yi, K.; Zhang, Q.
Dynamic indexability and lower bounds for dynamic one-dimensional range query indexes
Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2009, p. 187-196
Yi, K.
Indexing uncertain data
Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2009, p. 137-146
Agarwal, P.K.; Cheng, S.W.; Tao, Y.; Yi, K.
Multi-dimensional online tracking
Proceedings of ACM_SIAM Symposium on Discrete Algorithms, v. 2009, 2009, p. 1098-1107
Yi, Ke; Zhang, Qin
Optimal tracking of distributed heavy hitters and quantiles
Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2009, p. 167-174
Yi, K.; Zhang, Q.
Ranking distributed probabilistic data
SIGMOD-PODS'09 - Proceedings of the International Conference on Management of Data and 28th Symposium on Principles of Database Systems, 2009, p. 361-373
Li, F.; Yi, K.; Jestes, J.
Tree Indexing on Flash Disks
Proceedings - International Conference on Data Engineering, 2009, p. 1303-1306
Li, Yinan; He, Bingsheng; Luo, Qiong; Yi, Ke


Expand All Collapse All


Article 4

A dynamic data structure for top-k queries on uncertain data
Theoretical Computer Science, v. 407, (1-3), 2008, NOV 6, p. 310-317
Chen, Jiang; Yi, Ke
Efficient Processing of Top-k Queries in Uncertain Databases with x-Relations
IEEE transactions on knowledge and data engineering, v. 20, (12), 2008, Dec, p. 1669-1682, article number 4515868
Yi, Ke; Li, Feifei; Kollios, George; Srivastava, Divesh
Finding frequent items in probabilistic data
SIGMOD '08 Proceedings of the 2008 ACM SIGMOD international conference on Management of data, v. 2008, Jun, p. 819-831
Zhang, Q.; Li, F.; Yi, K.
The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree
ACM transactions on algorithms, v. 4, (1), 2008, MAR
Arge, Lars; De Berg, Mark; Haverkort, Herman; Yi, Ke

Conference paper 4

Algorithms for Distributed Functional Monitoring
ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1076-1085, January 2008
Cormode, Graham; Muthukrishnan, S.; Yi, Ke
Efficient Processing of Top-k Queries on Uncertain Databases
Proceedings of the 24th International Conference on Data Engineering, Cancun, Mexico, 7-12 April 2008, 2008, p. 1406-1408
Yi, Ke; Li, Feifei; Kollios, George; Srivastava, Divesh
Randomized synopses for query assurance on data streams
Proceedings - International Conference on Data Engineering, 2008, p. 416-425
Yi, K.; Li, F.; Hadjielefthriou, M.; Kollios, G.; Srivastava, D.
Sliding-Window Top-k Queries on Uncertain Streams
Proceedings of the VLDB Endowment, v. 1, (1), 2008, p. 301-312
Jin, Cheqing; Yi, Ke; Chen, Lei; Yu, Jeffrey Xu; Lin, Xuemin


Expand All Collapse All


Conference paper 4

Approximate range searching in external memory
Lecture Notes in Computer Science, v. 4835, 2007, p. 536-548
Streppel, M.; Yi, K.
Dynamic structures for top-k queries on uncertain data
Lecture Notes in Computer Science, v. 4835, 2007, p. 427-438
Chen, J.; Yi, K.
Proof-Infused Streams: Enabling Authentication of Sliding Window Queries on Streams
International Conference on Very Large Data Bases (VLDB), pages 147-158, Vienna, Austria, September 2007
Li, Feifei; Yi, Ke; Hadjieleftheriou, Marios; Kollios, George
TerraStream: From Elevation Data to Watershed Hierarchies
ACM International Symposium on Advances in Geographic Information Systems (ACM GIS), November 2007
Danner, Andrew; Moelhave, Thomas; Yi, Ke; Agarwal, Pankaj; Arge, Lars; Mitasova, Helena


Expand All Collapse All


Conference paper 2

An Information-Theoretic Approach to Detecting Changes in Multi-Dimensional Data Streams
Proc. Symposium on the Interface of Statistics, Computing Science, and Applications (Interface), May 2006
Dasu, Tamraparni; Krishnan, Shankar; Venkatasubramanian, Suresh; Yi, Ke
I/O-Efficient Batched Union-Find and Its Applications to Terrain Analysis
Proc. Annual Symposium on Computational Geometry (SoCG), June 2006
Agarwal, Pankaj K.; Arge, Lars; Yi, Ke


Expand All Collapse All


Article 1

Optimal Lexicographic Shaping of Aggregate Streaming Data
IEEE Transactions on Computers, v. 54, (4), 2005, p. 398–408
Anastasiadis, Stergios V.; Varman, Peter; Vitter, Jeffrey S.; Yi, Ke

Conference paper 3

An Optimal Dynamic Interval Stabbing-Max Data Structure?
Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2005
Agarwal, Pankaj K.; Arge, Lars; Yi, Ke
BOXes: Efficient Maintenance of Order-Based Labeling for Dynamic XML Data
Proc. International Conference on Data Engineering (ICDE), April 2005, p. 285–296
Silberstein, Adam; He, Hao; Yi, Ke; Yang, Jun
I/O-Efficient Construction of Constrained Delaunay Triangulations
Proc. Annual European Symposium on Algorithms (ESA), October 2005
Agarwal, Pankaj K.; Arge, Lars; Yi, Ke


Expand All Collapse All


Conference paper 3

Incremental Maintenance of XML Structural Indexes
Proc. ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2004
Yi, Ke; He, Hao; Stanoi, Ioana; Yang, Jun
Optimal External-Memory Planar Point Enclosure
Proc. Annual European Symposium on Algorithms (ESA), September 2004
Arge, Lars; Samoladas, Vasilis; Yi, Ke
The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree
Proc. ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2004
Arge, Lars; Berg, Mark de; Haverkort, Herman; Yi, Ke


Expand All Collapse All


Conference paper 2

Efficient Maintenance of Materialized Top-k Views
Proc. International Conference on Data Engineering (ICDE), March 2003
Yi, Ke; Yu, Hai; Yang, Jun; Xia, Gangqiang; Chen, Yuguo
I/O-Efficient Structures for Orthogonal Range-Max and Stabbing-Max Queries
Proc. Annual European Symposium on Algorithms (ESA), September 2003
Agarwal, Pankaj K.; Arge, Lars; Yang, Jun; Yi, Ke


Expand All Collapse All


Conference paper 1

Lexicographically Optimal Smoothing for Broadband Traffic Multiplexing
Proc. ACM Symposium on Principles of Distributed Computing (PODC), July 2002
Anastasiadis, Stergios; Varman, Peter; Vitter, Jeffrey S.; Yi, Ke


Expand All Collapse All


Article 1

Semantics of Ranking Queries for Probabilistic Data
IEEE Transactions on Communications, v. 39, (12), 1991, p. 1794-1801
Jestes, Jeffrey; Cormode, Graham; Li, Feifei; Yi, Ke


Expand All Collapse All


2016 9

Counting Triangles in Large Graphs by Random Sampling
IEEE Transactions on Knowledge and Data Engineering, v. 28, (8), August 2016, article number 7457266, p. 2013-2026
Wu, Bin; Yi, Ke; Li, Zhenguo Article
Exact and approximate flexible aggregate similarity search
VLDB Journal, v. 25, (3), June 2016, p. 317-338
Li, Feifei; Yi, Ke; Tao, Yufei; Yao, Bin; Li, Yang; Xie, Dong; Wang, Min Article
Nearest-Neighbor Searching Under Uncertainty II
ACM Transactions on Algorithms, v. 13, (1), October 2016, article number 3
Agarwal, Pankaj Kumar; Aronov, Boris; Har-Peled, Sariel Peled; Phillips, Jeff Mark; Yi, Ke; Zhang, Wuzhou Article
Quantiles Over Data Streams: Experimental Comparisons, New Analyses, and Further Improvements
VLDB Journal, v. 25, (4), August 2016, p. 449-472
Luo, Ge; Wang, Lu; Yi, Ke; Cormode, Graham Article
Indoor Localization via Multi-modal Sensing on Smartphones
UbiComp 2016 - Proceedings of the 2016 ACM International Joint Conference on Pervasive and Ubiquitous Computing, September 2016, p. 208-219
Xu, Han; Yang, Zheng; Zhou, Zimu; Shangguan, Longfei; Yi, Ke; Liu, Yunhao Conference paper
Spatial Online Sampling and Aggregation
Proceedings of the VLDB Endowment, v. 9, (3), Sep 2016, p. 84-95
Wang, Lu; Christensen, Robert; Li, Feifei; Yi, Ke Conference paper
Towards a Worst-case I/O-optimal Algorithm for Acyclic Joins
Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, v. 26-June-01-July-2016, June 2016, p. 135-150
Hu, Xiao; Yi, Ke Conference paper
Wander Join: Online Aggregation for Joins
Proceedings of the 2016 International Conference on Management of Data, v. 26-June-2016, June 2016, p. 2121-2124
Li, Feifei; Wu, Bin; Yi, Ke; Zhao, Zhuoyue Conference paper
Wander Join: Online Aggregation via Random Walks
Proceedings of the ACM SIGMOD International Conference on Management of Data, v. 26-June-2016, June 2016, p. 615-629
Li, Feifei; Wu, Bin; Yi, Ke; Zhao, Zhuoyue Conference paper

2015 4

Enhancing Wifi-based Localization with Visual Clues
Proceedings of the 2015 ACM International Joint Conference on Pervasive and Ubiquitous Computing, New York, NY, USA : ACM, 2015, p. 963-974
Xu, Han; Yang, Zheng; Zhou, Zimu; Shangguan, Longfei; Yi, Ke; Liu, Yunhao Conference paper
Persistent Data Sketching
SIGMOD '15: Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, v. 2015-May, May 2015, p. 795-810
Wei, Zhewei; Luo, Ge; Yi, Ke; Du, Xiaoyong; Wen, Jirong Conference paper
Piecewise Linear Approximation of Streaming Time Series Data with Max-error Guarantees
2015 IEEE 31st International Conference on Data Engineering (ICDE 2015), Institute of Electrical and Electronics Engineers (IEEE), 2015, p. 173-184
Luo, Ge; Yi, Ke; Cheng, Siu-Wing; Li, Zhenguo; Fan, Wei; He, Cheng; Mu, Yadong Conference paper
STORM: Spatio-Temporal Online Reasoning and Management of Large Spatio-Temporal Data
SIGMOD 2015: Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, v. 2015-May, May 2015, p. 1111-1116
Christensen, Robert; Wang, Lu; Li, Feifei; Yi, Ke; Tang, Jun; Villa, Natalee Conference paper

2014 5

Cache-oblivious hashing
Algorithmica, v. 69, (4), 2014, p. 864-883
Pagh, Rasmus; Wei, Zhewei; Yi, Ke; Zhang, Qin Article
Indexing for Summary Queries: Theory and Practice
ACM Transactions on Database Systems, v. 39, (1), January 2014, article number a2
Yi, Ke; Wang, Lu; Wei, Zhewei Article
Equivalence between priority queues and sorting in external memory
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), v. 8737 LNCS, 2014, p. 830-841
Wei, Zhewei; Yi, Ke Conference paper
Robust Set Reconciliation
Proceedings of the ACM SIGMOD International Conference on Management of Data, 2014, p. 135-146
Chen, Di; Konrad, Christian; Yi, Ke; Yu, Wei; Zhang, Qin Conference paper
The Communication Complexity of Distributed Epsilon-approximations
Proceedings - Annual IEEE Symposium on Foundations of Computer Science, December 2014, article number 6979044, p. 591-600
Huang, Zengfeng; Yi, Ke Conference paper

2013 8

Efficient external memory structures for range-aggregate queries
Computational Geometry: Theory and Applications, v. 46, (3), April 2013, p. 358-370
Agarwal, Pankaj K.; Arge, Lars; Govindarajan, Sathish; Yang, Jun; Yi, Ke Article
Mergeable Summaries
ACM transactions on database systems, v.38, (4), November 2013
Agarwal, Pankaj K.; Cormode, Graham; Huang, Zengfeng; Phillips, Jeff M.; Wei, Zhewei; Yi, Ke Article
Optimal Tracking of Distributed Heavy Hitters and Quantiles
Algorithmica, v. 65, (1), January 2013, p. 206-223
Yi, Ke; Zhang, Qin Article
Nearest Neighbor Searching under Uncertainty II
Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, New York, NY, USA : ACM, 2013, p. 115-126
Agarwal, P.K.; Aronov, B.; Har-peled, S.; Phillips, J.M.; Yi, K.; Zhang, W. Conference paper
Quantiles over Data Streams: An Experimental Study
Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, New York, NY, USA : ACM, 2013, p. 737-748
Wang, Lu; Luo, Ge; Yi, Ke; Cormode, Graham Conference paper
Streaming Authenticated Data Structures
Lecture Notes in Computer Science, v. 7881, 2013, p. 353-370
Papamanthou, Charalampos; Shi, Elaine; Tamassia, Roberto; Yi, Ke Conference paper
The Space Complexity of 2-Dimensional Approximate Range Counting
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, v. 2013, 2013, p. 252-264
Wei, Zhewei; Yi, Ke Conference paper
Voice over the Dins: Improving Wireless Channel Utilization with Collision Tolerance
2013 21st IEEE International Conference on Network Protocols (ICNP), Editors: Xiaoming Fu, Volker Hilt, Tilman Wolf, Lixia Zhang, and Zhi-Li Zhang. Institute of Electrical and Electronics Engineers (IEEE), 2013
Ji, Xiaoyu; He, Yuan; Wang, Jiliang; Wu, Kaishun; Yi, Ke; Liu, Yunhao Conference paper

2012 9

AN OPTIMAL DYNAMIC DATA STRUCTURE FOR STABBING-SEMIGROUP QUERIES
SIAM journal on computing, v. 41, (1), 2012, p. 104-127
Agarwal, Pankaj K.; Arge, Lars; Kaplan, Haim; Molad, Eyal; Tarjan, Robert E.; Yi, Ke Article
Continuous Sampling from Distributed Streams
Journal of the Association for Computing Machinery, v. 59, (2), 2012, Apr, Article number 10
Cormode, Graham; Muthukrishnan, S.; Yi, Ke; Zhang, Qin Article
Dynamic Indexability and the Optimality of B-Trees
Journal of the Association for Computing Machinery, v. 59, (4), 2012, Aug, Article number 21
Yi, Ke Article
Range Searching on Uncertain Data
ACM transactions on algorithms, v. 8, (4), September 2012, Article 43
Agarwal, Pankaj K.; Cheng, Siu-Wing; Yi, Ke Article
Building Wavelet Histograms on Large Data in MapReduce
Proceedings of the VLDB Endowment, v.5, (2), 2011, p.109-120
Jestes, Jeffrey; Yi, Ke; Li, Feifei Conference paper
Mergeable summaries
Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2012, p. 23-34
Agarwal, Pankaj Kumar; Cormode, Graham; Huang, Zengfeng; Phillips, Jeff Mark; Wei, Zhewei; Yi, Ke Conference paper
Randomized algorithms for tracking distributed count, frequencies, and ranks
Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2012, p. 295-305
Huang, Zengfeng; Yi, Ke; Zhang, Qin Conference paper
Tracking distributed aggregates over time-based sliding windows
Lecture Notes in Computer Science, v. 7338, 2012, p. 416-430
Cormode, Graham; Yi, Ke Conference paper
Verifying Computations with Streaming Interactive Proofs
Proceedings of the VLDB Endowment, v.5, (1), 2011, p.25-36
Cormode, Graham; Thaler, Justin; Yi, Ke Conference paper

2011 9

Algorithms for Distributed Functional Monitoring
ACM transactions on algorithms, v. 7, (2), March 2011, Article no.: 21
Cormode, Graham; Muthukrishnan, S.; Yi, Ke Article
Approximate Range Searching in External Memory
Algorithmica, v. 59, (2), February 2011, p. 115-128
Streppel, Micha; Yi, Ke Article
Semantics of Ranking Queries for Probabilistic Data
IEEE transactions on knowledge and data engineering, v. 23, (12), December 2011, p. 1903-1917
Jestes, Jeffrey; Cormode, Graham; Li, Feifei; Yi, Ke Article
The world in a nutshell: Concise range queries
IEEE transactions on knowledge and data engineering, v. 23, (1), 2011, Article number 5416721, p. 139-154
Yi, Ke; Lian, Xiang; Li, Feifei; Chen, Lei Article
Beyond simple aggregates: Indexing for summary queries
Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 2011, p. 117-128
Wei, Zhewei; Yi, Ke Conference paper
Brief Announcement: Tracking distributed aggregates over time-based sliding windows
Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, v. 2011, 2011, p. 213-214
Cormode, Graham; Yi, Ke Conference paper
Flexible aggregate similarity search
Proceedings - ACM-SIGMOD International Conference on Management of Data, June 2011, p. 1009-1020
Li, Yang; Li, Feifei; Yi, Ke; Yao, Bin; Wang, Min Conference paper
Optimal Sampling Algorithms for Frequency Estimation in Distributed Data
Proceedings - IEEE INFOCOM, April 2011, p. 1997-2005
Huang, Zengfeng; Yi, Ke; Liu, Yunhao; Chen, Guihai Conference paper
Sampling based algorithms for quantile computation in sensor networks
The 2011 ACM SIGMOD/PODS Conference, Athens, Greece. Proceedings - ACM-SIGMOD International Conference on Management of Data, New York, USA, Juen 2011, p. 745-756
Huang, Zengfeng; Wang, Lu; Yi, Ke; Liu, Yunhao Conference paper

2010 14

Efficient and Accurate Nearest Neighbor and Closest Pair Search in High-Dimensional Space
ACM transactions on database systems, v. 35, (3), 2010, JUL
Tao, Yufei; Yi, Ke; Sheng, Cheng; Kalnis, Panos Article
I/O-efficient batched union-find and its applications to terrain analysis
ACM Transactions on Algorithms, v. 7, (1), 2010
Agarwal, P.K.; Arge, L.; Yi, K. Article
Multidimensional online tracking
ACM Transactions on Algorithms, v. 8, (2), April 2012, article number 12
Yi, Ke; Zhang, Qin Article
Sliding-window top-k queries on uncertain streams
VLDB JOURNAL, v. 19, (3), 2010, JUN, p. 411-435
Jin, Cheqing; Yi, Ke; Chen, Lei; Yu, Jeffrey Xu; Lin, Xuemin Article
Top-k queries on temporal data
VLDB JOURNAL, v. 19, (5), 2010, OCT, p. 715-733
Li, Feifei; Yi, Ke; Le, Wangchao Article
Tree Indexing on Solid State Drives
Proceedings of the VLDB Endowment, v. 3, (1-2), September 2010, p. 1195-1206
Li, Yinan; He, Bingsheng; Yang, Robin Jun; Luo, Qiong; Yi, Ke Article
Cache-oblivious hashing
Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2010, p. 297-304
Pagh, Rasmus; Wei, Zhewei; Yi, Ke; Zhang, Qin Conference paper
Clustering with Diversity
Lecture Notes in Computer Science, v. 6198, 2010, p. 188-200
Li, Jian; Yi, Ke; Zhang, Qin Conference paper
Correlation Hiding by Independence Masking
International Conference on Data Engineering (ICDE), 2010, p. 964-967
Tao, Yufei; Pei, Jian; Li, Jiexing; Xiao, Xiaokui; Yi, Ke; Xing, Zhengzheng Conference paper
Logging every footstep: Quantile summaries for the entire history
Proceedings of the ACM SIGMOD International Conference on Management of Data, 2010, p. 639-650
Tao, Y.; Yi, K.; Sheng, C.; Pei, J.; Li, F. Conference paper
On the cell probe complexity of dynamic membership
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2010, p. 123-133
Yi, K.; Zhang, Q. Conference paper
Optimal sampling from distributed streams
Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2010, p. 77-86
Cormode, Graham; Muthukrishnan, S.; Yi, Ke; Zhang, Qin Conference paper
Probabilistic string similarity joins
Proceedings of the ACM SIGMOD International Conference on Management of Data, 2010, p. 327-338
Jestes, J.; Li, F.; Yan, Z.; Yi, K. Conference paper
The hardness and approximation algorithms for L-diversity
Advances in Database Technology - EDBT 2010 - 13th International Conference on Extending Database Technology, Proceedings, 2010, p. 135-146
Xiao, X.; Yi, K.; Tao, Y. Conference paper

2009 12

Optimal External Memory Planar Point Enclosure
Algorithmica, v. 54, (3), 2009, JUL, p. 337-352
Arge, Lars; Samoladas, Vasilis; Yi, Ke Article
Quality and efficiency in high dimensional Nearest neighbor search
SIGMOD '09 Proceedings of the 2009 ACM SIGMOD International Conference on Management of data, v. 2009, Jun-Jul, p. 563-575
Tao, Y.; Yi, K.; Sheng, C.; Kalnis, P. Article
Small Synopses for Group-By Query Verification on Outsourced Data Streams
ACM transactions on database systems, v. 34, (3), 2009, Aug, Article number 15
Yi, Ke; Li, Feifei; Cormode, Graham; Hadjieleftheriou, Marios; Kollios, George; Srivastava, Divesh Article
A Concise Representation of Range Queries
International Conference on Data Engineering (ICDE), 2009, p. 1179-1182
Yi, Ke; Lian, Xiang; Li, Feifei; Chen, Lei Conference paper
Change (detection) you can believe in: Finding distributional shifts in data streams
Lecture Notes in Computer Science, v. 5772, 2009, p. 21-34
Dasu, T.; Krishnan, S.; Lin, D.; Venkatasubramanian, S.; Yi, K. Conference paper
Dynamic external hashing: The limit of buffering?
Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2009, p. 253-259
Wei, Z.; Yi, K.; Zhang, Q. Conference paper
Dynamic indexability and lower bounds for dynamic one-dimensional range query indexes
Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2009, p. 187-196
Yi, K. Conference paper
Indexing uncertain data
Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2009, p. 137-146
Agarwal, P.K.; Cheng, S.W.; Tao, Y.; Yi, K. Conference paper
Multi-dimensional online tracking
Proceedings of ACM_SIAM Symposium on Discrete Algorithms, v. 2009, 2009, p. 1098-1107
Yi, Ke; Zhang, Qin Conference paper
Optimal tracking of distributed heavy hitters and quantiles
Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2009, p. 167-174
Yi, K.; Zhang, Q. Conference paper
Ranking distributed probabilistic data
SIGMOD-PODS'09 - Proceedings of the International Conference on Management of Data and 28th Symposium on Principles of Database Systems, 2009, p. 361-373
Li, F.; Yi, K.; Jestes, J. Conference paper
Tree Indexing on Flash Disks
Proceedings - International Conference on Data Engineering, 2009, p. 1303-1306
Li, Yinan; He, Bingsheng; Luo, Qiong; Yi, Ke Conference paper

2008 8

A dynamic data structure for top-k queries on uncertain data
Theoretical Computer Science, v. 407, (1-3), 2008, NOV 6, p. 310-317
Chen, Jiang; Yi, Ke Article
Efficient Processing of Top-k Queries in Uncertain Databases with x-Relations
IEEE transactions on knowledge and data engineering, v. 20, (12), 2008, Dec, p. 1669-1682, article number 4515868
Yi, Ke; Li, Feifei; Kollios, George; Srivastava, Divesh Article
Finding frequent items in probabilistic data
SIGMOD '08 Proceedings of the 2008 ACM SIGMOD international conference on Management of data, v. 2008, Jun, p. 819-831
Zhang, Q.; Li, F.; Yi, K. Article
The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree
ACM transactions on algorithms, v. 4, (1), 2008, MAR
Arge, Lars; De Berg, Mark; Haverkort, Herman; Yi, Ke Article
Algorithms for Distributed Functional Monitoring
ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1076-1085, January 2008
Cormode, Graham; Muthukrishnan, S.; Yi, Ke Conference paper
Efficient Processing of Top-k Queries on Uncertain Databases
Proceedings of the 24th International Conference on Data Engineering, Cancun, Mexico, 7-12 April 2008, 2008, p. 1406-1408
Yi, Ke; Li, Feifei; Kollios, George; Srivastava, Divesh Conference paper
Randomized synopses for query assurance on data streams
Proceedings - International Conference on Data Engineering, 2008, p. 416-425
Yi, K.; Li, F.; Hadjielefthriou, M.; Kollios, G.; Srivastava, D. Conference paper
Sliding-Window Top-k Queries on Uncertain Streams
Proceedings of the VLDB Endowment, v. 1, (1), 2008, p. 301-312
Jin, Cheqing; Yi, Ke; Chen, Lei; Yu, Jeffrey Xu; Lin, Xuemin Conference paper

2007 4

Approximate range searching in external memory
Lecture Notes in Computer Science, v. 4835, 2007, p. 536-548
Streppel, M.; Yi, K. Conference paper
Dynamic structures for top-k queries on uncertain data
Lecture Notes in Computer Science, v. 4835, 2007, p. 427-438
Chen, J.; Yi, K. Conference paper
Proof-Infused Streams: Enabling Authentication of Sliding Window Queries on Streams
International Conference on Very Large Data Bases (VLDB), pages 147-158, Vienna, Austria, September 2007
Li, Feifei; Yi, Ke; Hadjieleftheriou, Marios; Kollios, George Conference paper
TerraStream: From Elevation Data to Watershed Hierarchies
ACM International Symposium on Advances in Geographic Information Systems (ACM GIS), November 2007
Danner, Andrew; Moelhave, Thomas; Yi, Ke; Agarwal, Pankaj; Arge, Lars; Mitasova, Helena Conference paper

2006 2

An Information-Theoretic Approach to Detecting Changes in Multi-Dimensional Data Streams
Proc. Symposium on the Interface of Statistics, Computing Science, and Applications (Interface), May 2006
Dasu, Tamraparni; Krishnan, Shankar; Venkatasubramanian, Suresh; Yi, Ke Conference paper
I/O-Efficient Batched Union-Find and Its Applications to Terrain Analysis
Proc. Annual Symposium on Computational Geometry (SoCG), June 2006
Agarwal, Pankaj K.; Arge, Lars; Yi, Ke Conference paper

2005 4

Optimal Lexicographic Shaping of Aggregate Streaming Data
IEEE Transactions on Computers, v. 54, (4), 2005, p. 398–408
Anastasiadis, Stergios V.; Varman, Peter; Vitter, Jeffrey S.; Yi, Ke Article
An Optimal Dynamic Interval Stabbing-Max Data Structure?
Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2005
Agarwal, Pankaj K.; Arge, Lars; Yi, Ke Conference paper
BOXes: Efficient Maintenance of Order-Based Labeling for Dynamic XML Data
Proc. International Conference on Data Engineering (ICDE), April 2005, p. 285–296
Silberstein, Adam; He, Hao; Yi, Ke; Yang, Jun Conference paper
I/O-Efficient Construction of Constrained Delaunay Triangulations
Proc. Annual European Symposium on Algorithms (ESA), October 2005
Agarwal, Pankaj K.; Arge, Lars; Yi, Ke Conference paper

2004 3

Incremental Maintenance of XML Structural Indexes
Proc. ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2004
Yi, Ke; He, Hao; Stanoi, Ioana; Yang, Jun Conference paper
Optimal External-Memory Planar Point Enclosure
Proc. Annual European Symposium on Algorithms (ESA), September 2004
Arge, Lars; Samoladas, Vasilis; Yi, Ke Conference paper
The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree
Proc. ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2004
Arge, Lars; Berg, Mark de; Haverkort, Herman; Yi, Ke Conference paper

2003 2

Efficient Maintenance of Materialized Top-k Views
Proc. International Conference on Data Engineering (ICDE), March 2003
Yi, Ke; Yu, Hai; Yang, Jun; Xia, Gangqiang; Chen, Yuguo Conference paper
I/O-Efficient Structures for Orthogonal Range-Max and Stabbing-Max Queries
Proc. Annual European Symposium on Algorithms (ESA), September 2003
Agarwal, Pankaj K.; Arge, Lars; Yang, Jun; Yi, Ke Conference paper

2002 1

Lexicographically Optimal Smoothing for Broadband Traffic Multiplexing
Proc. ACM Symposium on Principles of Distributed Computing (PODC), July 2002
Anastasiadis, Stergios; Varman, Peter; Vitter, Jeffrey S.; Yi, Ke Conference paper

1991 1

Semantics of Ranking Queries for Probabilistic Data
IEEE Transactions on Communications, v. 39, (12), 1991, p. 1794-1801
Jestes, Jeffrey; Cormode, Graham; Li, Feifei; Yi, Ke Article






Teaching Assignment

---

2021-22 Winter 0 2021-22 Fall 4 2020-21 Summer 3 2020-21 Spring 5 2020-21 Winter 0 2020-21 Fall 5

---

COMP4981 Final Year Project
COMP4981H Final Year Thesis
COMP5711 Introduction to Advanced Algorithmic Techniques
MSBD5003 Big Data Computing


COMP4981 Final Year Project
COMP4981H Final Year Thesis
CPEG4901 Computer Engineering Final Year Project in COMP


COMP2711 Discrete Mathematical Tools for Computer Science
COMP4981 Final Year Project
COMP4981H Final Year Thesis
CPEG4901 Computer Engineering Final Year Project in COMP
SCIE4500 IRE Research Project II


COMP4981 Final Year Project
COMP4981H Final Year Thesis
COMP5711 Introduction to Advanced Algorithmic Techniques
CPEG4901 Computer Engineering Final Year Project in COMP
MSBD5003 Big Data Computing


No Teaching Assignments


No Teaching Assignments






Research Postgraduate (RPG) Supervision From January 2019 to December 2022 (As of 30 January 2022)

---

All Supervisions Current RPGs Graduated RPGs

---

Current RPGs

---

Doctor of Philosophy SUN, Dajun
Computer Science and Engineering( 2021 - )

FANG, Juanru
Computer Science and Engineering( 2020 - )

LIANG, Yuting
Computer Science and Engineering( 2020 - )

WEI, Shuqing (co-supervision)
Intelligent Transportation( 2020 - )

LUO, Qiyao
Computer Science and Engineering( 2019 - )

QIU, Yuan
Computer Science and Engineering( 2019 - )

DONG, Wei
Computer Science and Engineering( 2018 - )

HUANG, Ziyue
Computer Science and Engineering( 2018 - )

WANG, Qichen
Computer Science and Engineering( 2017 - )

WANG, Yilei
Computer Science and Engineering( 2017 - )

---

Master of Philosophy CHEN, Bingnan
Computer Science and Engineering( 2021 - )

---

Graduated RPGs

---

Doctor of Philosophy CHEN, Yu
Computer Science and Engineering( Completed in 2019 )

HU, Xiao
Computer Science and Engineering( Completed in 2019 )

---

Master of Philosophy CAO, Junhong
Computer Science and Engineering( Completed in 2019 )

ZHANG, Haoqian
Computer Science and Engineering( Completed in 2019 )









ProjectsFrom January 2020 to December 2022

---

All Projects 7 Leading Projects 6 Participating Projects 1

---

Approximate Query Evaluation under Updates


數據修改下的近似查詢 Leading


RGC - General Research Fund


Project Team (HKUST)
YI Ke (Lead)


2021 -




Output-sensitive Algorithms for Parallel Acyclic Joins


輸出相關的無環連接并行算法 Leading


RGC - General Research Fund


Project Team (HKUST)
YI Ke (Lead)


2020 -




Swarm Intelligence Emerges based on the Internet - Topic 2: Pattern mining and prediction for crowd behaviors


基于互聯網的群智涌現機理與計算方法-課題二：群體行為的模式理解與預測 Participating


Ministry of Science and Technology of the People's Republic of China


Project Team (HKUST)
CHEN Lei (Lead)
SONG Yangqiu
WANG Wei
YI Ke


2020 -




Worst-case Optimal Stream Join Algorithms


最壞情況下最優數據流連接算法 Leading


RGC - General Research Fund


Project Team (HKUST)
YI Ke (Lead)


2019 -




On the Relationship between the External Memory Model and the BSP


對于外存計算模型和BSP之關系的研究 Leading


RGC - General Research Fund


Project Team (HKUST)
YI Ke (Lead)


2018 - 2021




Massive data algorithms Leading


Wuxi SenseHuge Technology Limited


Project Team (HKUST)
YI Ke (Lead)


2015 -




Real-time communication-efficient tracking of urban data with precision guarantees Leading


Microsoft Research Asia


Project Team (HKUST)
YI Ke (Lead)
CHEN Lei
QU Huamin


2014 - 2021