Publications [My DBLP entry]

Disclaimers: The materials below have been provided by the author(s) as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the author(s) or by other copyright holders, notwithstanding that they have offered their works here electronically. All persons copying this information should adhere to the terms and constraints invoked by each author's copyright. These materials may not be re-posted without the explicit permission of the copyright holder. Other restrictions to copying individual reports may apply.

Book

  1. Graham Cormode and Ke Yi. Small Summaries for Big Data. Cambridge University Press, 2020. [pdf]

Conference Papers

  1. Wei Dong, Qiyao Luo, Giulia Fanti, Elaine Shi, and Ke Yi. "Almost Instance-optimal Clipping for Summation Problems in the Shuffle Model of Differential Privacy." ACM Conference on Computer and Communications Security (CCS), October 2024. [pdf]
  2. Yuting Liang and Ke Yi. "Smooth Sensitivity for Geo-Privacy." ACM Conference on Computer and Communications Security (CCS), October 2024. [pdf]
  3. Dajun Sun, Wei Dong, and Ke Yi. "Confidence Intervals for Private Query Processing." International Conference on Very Large Data Bases (VLDB), August 2024. [pdf]
  4. Juanru Fang and Ke Yi. "Privacy Amplification by Sampling under User-level Differential Privacy." ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2024. [pdf]
  5. Binyang Dai, Xiao Hu, Ke Yi. "Reservoir Sampling over Joins." ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2024. [pdf] Best paper honorable mention.
  6. Qiyao Luo, Yilei Wang, Ke Yi, Sheng Wang, and Feifei Li. "Secure Sampling for Approximate Multi-party Query Processing. " ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2024. [pdf]
  7. Wei Dong, Zijun Chen, Qiyao Luo, Elaine Shi, and Ke Yi. "Continual Observation of Joins under Differential Privacy." ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2024. [pdf]
  8. Yuting Liang and Ke Yi. "Concentrated Geo-Privacy." ACM Conference on Computer and Communications Security (CCS), November 2023. [pdf] [full] [code]
  9. Qichen Wang, Xiao Hu, Binyang Dai, and Ke Yi. "Change Propagation Without Joins." International Conference on Very Large Data Bases (VLDB), August 2023. [full] [code]
  10. Wei Dong, Dajun Sun, and Ke Yi. "Better than Composition: How to Answer Multiple Relational Queries under Differential Privacy. " ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2023. [pdf] [code]
  11. Wei Dong and Ke Yi. "Universal Private Estimators." ACM Symposium on Principles of Database Systems (PODS), June 2023. [pdf]
  12. Wei Dong, Qiyao Luo, and Ke Yi. "Continual Observation under User-level Differential Privacy." IEEE Symposium on Security and Privacy (S&P), May 2023. [pdf]
  13. Wei Dong, Yuting Liang, and Ke Yi. "Differentially Private Covariance Revisited." Conference on Neural Information Processing Systems (NeurIPS), December 2022. [full version] [code]
  14. Qiyao Luo, Yilei Wang, and Ke Yi. "Frequency Estimation in the Shuffle Model with Almost a Single Message." ACM Conference on Computer and Communications Security (CCS), November 2022. [pdf] [code]
  15. Juanru Fang, Wei Dong, and Ke Yi. "Shifted Inverse: A General Mechanism for Monotonic Functions under User Differential Privacy." ACM Conference on Computer and Communications Security (CCS), November 2022. [pdf] [code]
  16. Ziyue Huang, Yuan Qiu, Ke Yi, and Graham Cormode. "Frequency Estimation Under Multiparty Differential Privacy: One-shot and Streaming." International Conference on Very Large Data Bases (VLDB), September 2022. [pdf]
  17. Yuan Qiu, Wei Dong, Ke Yi, Bin Wu, and Feifei Li. "Releasing Private Data for Numerical Queries." ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), August 2022. [pdf]
  18. Wei Dong, Juanru Fang, Ke Yi, Yuchao Tao, and Ashwin Machanavajjhala. "R2T: Instance-optimal Truncation for Differentially Private Query Evaluation with Foreign Keys." ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2022. [pdf] [code] Best paper award.
  19. Qichen Wang and Ke Yi. "Conjunctive Queries with Comparisons." ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2022. [pdf] [code] Best paper honorable mention.
  20. Wei Dong and Ke Yi. "A Nearly Instance-optimal Differentially Private Mechanism for Conjunctive Queries." ACM Symposium on Principles of Database Systems (PODS), June 2022. [full version] [code]
  21. Yilei Wang and Ke Yi. "Query Evaluation by Circuits." ACM Symposium on Principles of Database Systems (PODS), June 2022. [full version]
  22. Ziyue Huang, Yuting Liang, and Ke Yi. "Instance-optimal Mean Estimation Under Differential Privacy." Conference on Neural Information Processing Systems (NeurIPS), December 2021. [full version]
  23. Yilei Wang and Ke Yi. "Secure Yannakakis: Join-Aggregate Queries over Private Data." ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2021. [pdf] [code]
  24. Wei Dong and Ke Yi. "Residual Sensitivity for Differentially Private Multi-Way Joins." ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2021. [full version] [code]
  25. Yuan Qiu, Yilei Wang, Ke Yi, Feifei Li, Bin Wu, and Chaoqun Zhan. "Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries." ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2021. [full version]
  26. Ziyue Huang and Ke Yi. "Approximate Range Counting Under Differential Privacy." International Symposium on Computational Geometry (SoCG), June 2021. [full version]
  27. Xiao Hu and Ke Yi. "Parallel Algorithms for Sparse Matrix Multiplication and Join-Aggregate Queries." ACM Symposium on Principles of Database Systems (PODS), June 2020. [pdf]
  28. Qichen Wang and Ke Yi. "Maintaining Acyclic Foreign-Key Joins Under Updates." ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2020. [pdf] [code]
  29. Yang Cao, Wenfei Fan, Yanghao Wang, and Ke Yi. "Querying Shared Data with Security Heterogeneity." ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2020. [pdf]
  30. Yu Chen and Ke Yi. "Random Sampling and Size Estimation over Cyclic Joins." International Conference on Database Theory (ICDT), March 2020. [pdf]
  31. Zengfeng Huang, Ziyue Huang, Yilei Wang, and Ke Yi. "Optimal Sparsity-Sensitive Bounds for Distributed Mean Estimation." Conference on Neural Information Processing Systems (NeurIPS), December 2019. [pdf]
  32. Xiao Hu and Ke Yi. "Instance and Output Optimal Parallel Algorithms for Acyclic Joins." ACM Symposium on Principles of Database Systems (PODS), June 2019. [paper] [full version]
  33. Zhuoyue Zhao, Robert Christensen, Feifei Li, Xiao Hu, and Ke Yi. "Random Sampling over Joins Revisited." ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2018. [pdf]
  34. Yu Chen and Ke Yi. "Two-Level Sampling for Join Size Estimation." ACM SIGMOD International Conference on Management of Data (SIGMOD), May 2017. [pdf]
  35. Xiao Hu, Yufei Tao, and Ke Yi. "Output-optimal Parallel Algorithms for Similarity Joins." ACM Symposium on Principles of Database Systems (PODS), May 2017. [pdf]
  36. Han Xu, Zheng Yang, Zimu Zhou, Ke Yi, Chunyi Peng. "TUM: Towards Ubiquitous Multi-Device Localization for Cross-Device Interaction." INFOCOM, May, 2017. [pdf]
  37. Han Xu, Zheng Yang, Zimu Zhou, Longfei Shangguan, Ke Yi, and Yunhao Liu. "Indoor localization via multi-modal sensing on smartphones." ACM International Joint Conference on Pervasive and Ubiquitous Computing (UbiComp), September 2016. [pdf]
  38. Feifei Li, Bin Wu, Ke Yi, and Zhuoyue Zhao. "Wander Join: Online Aggregation via Random Walks." ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2016. [pdf] [slides] [code] Best paper award.
  39. Xiao Hu and Ke Yi. "Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins." ACM Symposium on Principles of Database Systems (PODS), June 2016. [pdf]
  40. Lu Wang, Robert Christensen, Feifei Li, and Ke Yi. "Spatial Online Sampling and Aggregation." International Conference on Very Large Data Bases (VLDB), August 2016. [pdf]
  41. Han Xu, Zheng Yang, Zimu Zhou, Longfei Shangguan, Ke Yi, Yunhao Liu. "Enhancing WiFi-based Localization with Visual Clues." UbiComp, September 2015. [pdf]
  42. Zhewei Wei, Ge Luo, Ke Yi, Xiaoyong Du, and Ji-Rong Wen. "Persistent Data Sketching." ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2015. [pdf]
  43. Ge Luo, Ke Yi, Siu-Wing Cheng, Zhenguo Li, Wei Fan, Cheng He, and Yadong Mu. "Piecewise Linear Approximation of Streaming Time Series Data with Max-error Guarantees." IEEE International Conference on Data Engineering (ICDE), April 2015. [pdf] [code]
  44. Zengfeng Huang and Ke Yi. "The Communication Complexity of Distributed epsilon-Approximations." IEEE Symposium on Foundations of Computer Science (FOCS), October 2014. [pdf]
  45. Zhewei Wei and Ke Yi. "Equivalence between Priority Queues and Sorting in External Memory." European Symposium on Algorithms (ESA), September 2014. [pdf]
  46. Di Chen, Christian Konrad, Ke Yi, Wei Yu, and Qin Zhang. "Robust Set Reconciliation." ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2014. [pdf]
  47. Xiaoyu Ji, Yuan He, Jiliang Wang, Kaishun Wu, Ke Yi, and Yunhao Liu. "Voice Over the Dins: Improving Wireless Channel Utilization with Collision Tolerance." IEEE International Conference on Network Protocols (ICNP), October 2013. [pdf]
  48. Lu Wang, Ge Luo, Ke Yi, and Graham Cormode. "Quantiles over Data Streams: An Experimental Study." ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2013. [pdf]
  49. Pankaj K. Agarwal, Boris Aronov, Sariel Har-Peled, Jeff M. Phillips, Ke Yi, and Wuzhou Zhang. "Nearest-Neighbor Searching Under Uncertainty II." ACM Symposium on Principles of Database Systems (PODS), June 2013. [pdf]
  50. Charalampos Papamanthou, Elaine Shi, Roberto Tamassia, and Ke Yi. "Streaming Authenticated Data Structures." EUROCRYPT, May 2013. [pdf]
  51. Zhewei Wei and Ke Yi. "The Space Complexity of 2-Dimensional Approximate Range Counting." ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2013. [pdf]
  52. Jeffrey Jestes, Ke Yi, and Feifei Li. "Building Wavelet Histograms on Large Data in MapReduce." International Conference on Very Large Data Bases (VLDB), August 2012. [pdf]
  53. Graham Cormode, Justin Thaler, and Ke Yi. "Verifying Computations with Streaming Interactive Proofs." International Conference on Very Large Data Bases (VLDB), August 2012. [pdf]
  54. Graham Cormode and Ke Yi. "Tracking Distributed Aggregates over Time-Based Sliding Windows." International Conference on Scientific and Statistical Database Management (SSDBM), June 2012. [pdf]
  55. Pankaj K. Agarwal, Graham Cormode, Zengfeng Huang, Jeff M. Phillips, Zhewei Wei, and Ke Yi. "Mergeable Summaries." ACM Symposium on Principles of Database Systems (PODS), May 2012. [pdf] Test-of-Time award.
  56. Zengfeng Huang, Ke Yi, and Qin Zhang. "Randomized Algorithms for Tracking Distributed Count, Frequencies, and Ranks." ACM Symposium on Principles of Database Systems (PODS), May 2012. [pdf]
  57. Zengfeng Huang, Lu Wang, Ke Yi, and Yunhao Liu. "Sampling Based Algorithms for Quantile Computation in Sensor Networks." ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2011. [pdf] [slides]
  58. Yang Li, Feifei Li, Ke Yi, Bin Yao, and Min Wang. "Flexible Aggregate Similarity Search." ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2011. [pdf]
  59. Zhewei Wei and Ke Yi. "Beyond Simple Aggregates: Indexing for Summary Queries." ACM Symposium on Principles of Database Systems (PODS), June 2011. [pdf] [slides]
  60. Zengfeng Huang, Ke Yi, Yunhao Liu, and Guihai Chen. "Optimal Sampling Algorithms for Frequency Estimation in Distributed Data." INFOCOM, April 2011. [pdf]
  61. Yinan Li, Bingsheng He, Robin Jun Yang, Qiong Luo, and Ke Yi. "Tree Indexing on Solid State Drives." International Conference on Very Large Data Bases (VLDB), September 2010. [pdf]
  62. Jian Li, Ke Yi, and Qin Zhang. "Clustering with Diversity." International Colloquium on Automata, Languages and Programming (ICALP), July 2010. [pdf] [slides]
  63. Yufei Tao, Ke Yi, Cheng Sheng, Jian Pei, and Feifei Li. "Logging Every Footstep: Quantile Summaries for the Entire History." ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2010. [pdf]
  64. Jeffrey Jestes, Feifei Li, Zhepeng Yan, and Ke Yi. "Probabilistic String Similarity Joins." ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2010. [pdf] [slides] [code]
  65. Graham Cormode, S. Muthukrishnan, Ke Yi, and Qin Zhang. "Optimal Sampling from Distributed Streams." ACM Symposium on Principles of Database Systems (PODS), June 2010. [pdf] [slides]
  66. Rasmus Pagh, Zhewei Wei, Ke Yi, and Qin Zhang. "Cache-Oblivious Hashing." ACM Symposium on Principles of Database Systems (PODS), June 2010. [pdf] [slides]
  67. Xiaokui Xiao, Ke Yi, and Yufei Tao. "The Hardness and Approximation Algorithms for L-Diversity." International Conference on Extending Data Base Technology (EDBT), March 2010. [pdf]
  68. Ke Yi and Qin Zhang. "On the Cell Probe Complexity of Dynamic Membership." ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2010. [pdf] [slides]
  69. Zhewei Wei, Ke Yi, and Qin Zhang. "Dynamic External Hashing: The Limit of Buffering." ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), August 2009. [pdf] [slides]
  70. Yufei Tao, Ke Yi, Cheng Sheng, and Panos Kalnis. "Quality and Efficiency in High Dimensional Nearest Neighbor Search." ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2009. [pdf] [code]
  71. Feifei Li, Ke Yi, and Jeffrey Jestes. "Ranking Distributed Probabilistic Data." ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2009. [pdf] [slides] [code]
  72. Ke Yi. "Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes." ACM Symposium on Principles of Database Systems (PODS), June 2009. [pdf] [slides]
  73. Ke Yi and Qin Zhang. "Optimal Tracking of Distributed Heavy Hitters and Quantiles." ACM Symposium on Principles of Database Systems (PODS), June 2009. [pdf] [slides]
  74. Pankaj K. Agarwal, Siu-Wing Cheng, Yufei Tao, and Ke Yi. "Indexing Uncertain Data." ACM Symposium on Principles of Database Systems (PODS), June 2009. [pdf] [slides]
  75. Graham Cormode, Feifei Li, and Ke Yi. "Semantics of Ranking Queries for Probabilistic Data and Expected Ranks." International Conference on Data Engineering (ICDE), March 2009. [pdf] [slides] [code]
  76. Ke Yi and Qin Zhang. "Multi-Dimensional Online Tracking." ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2009. [pdf] [slides]
  77. Cheqing Jin, Ke Yi, Lei Chen, Jeffrey Xu Yu, and Xuemin Lin. "Sliding-Window Top-k Queries on Uncertain Streams." International Conference on Very Large Data Bases (VLDB), August 2008. [pdf] [slides]
  78. Qin Zhang, Feifei Li, and Ke Yi. "Finding Frequent Items in Probabilistic Data." ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2008. [pdf] [slides] [code]
  79. Ke Yi, Feifei Li, Marios Hadjieleftheriou, George Kollios, and Divesh Srivastava. "Randomized Synopses for Query Assurance on Data Streams." International Conference on Data Engineering (ICDE), April 2008. [pdf] [slides] [code]
  80. Graham Cormode, S. Muthukrishnan, and Ke Yi. "Algorithms for Distributed Functional Monitoring." ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2008. [pdf] [slides]
  81. Jiang Chen and Ke Yi. "Dynamic Structures for Top-k Queries on Uncertain Data." International Symposium on Algorithms and Computation (ISAAC), December 2007. [pdf] [slides]
  82. Micha Streppel and Ke Yi. "Approximate Range Searching in External Memory." International Symposium on Algorithms and Computation (ISAAC), December 2007. [pdf] [slides]
  83. Andrew Danner, Thomas Mølhave, Ke Yi, Pankaj K. Agarwal, Lars Arge, and Helena Mitasova. "TerraStream: From Elevation Data to Watershed Hierarchies." ACM International Symposium on Advances in Geographic Information Systems (ACM GIS), November 2007. [pdf] [slides]
  84. Feifei Li, Ke Yi, Marios Hadjieleftheriou, and George Kollios. "Proof-Infused Streams: Enabling Authentication of Sliding Window Queries on Streams." International Conference on Very Large Data Bases (VLDB), September 2007. [pdf] [slides]
  85. Adam L. Buchsbaum, Alon Efrat, Shaili Jain, Suresh Venkatasubramanian, and Ke Yi. "Restricted Strip Covering and the Sensor Cover Problem." ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2007. [pdf] (The results of this paper have been improved by this paper in FOCS'09.)
  86. Pankaj K. Agarwal, Lars Arge, and Ke Yi. "I/O-Efficient Batched Union-Find and Its Applications to Terrain Analysis." International Symposium on Computational Geometry (SoCG), June 2006. [pdf] [slides] [code]
  87. Tamraparni Dasu, Shankar Krishnan, Suresh Venkatasubramanian, and Ke Yi. "An Information-Theoretic Approach to Detecting Changes in Multi-Dimensional Data Streams." Symposium on the Interface of Statistics, Computing Science, and Applications (Interface), May, 2006. [pdf]
  88. Pankaj K. Agarwal, Lars Arge, and Ke Yi. "I/O-Efficient Construction of Constrained Delaunay Triangulations." European Symposium on Algorithms (ESA), October 2005. [pdf] [full version] [slides]
  89. Adam Silberstein, Hao He, Ke Yi, and Jun Yang. "BOXes: Efficient Maintenance of Order-Based Labeling for Dynamic XML Data." International Conference on Data Engineering (ICDE), April 2005. [pdf] [slides]
  90. Pankaj K. Agarwal, Lars Arge, and Ke Yi. "An Optimal Dynamic Interval Stabbing-Max Data Structure?" ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2005. [pdf] [slides]
  91. Lars Arge, Vasilis Samoladas, and Ke Yi. "Optimal External Memory Planar Point Enclosure." European Symposium on Algorithms (ESA), September 2004. [pdf] [slides]
  92. Lars Arge, Mark de Berg, Herman Haverkort, and Ke Yi. "The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree." ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2004. [pdf] [slides] [code]
  93. Ke Yi, Hao He, Ioana Stanoi, and Jun Yang. "Incremental Maintenance of XML Structural Indexes." ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2004. [pdf] [slides]
  94. Pankaj K. Agarwal, Lars Arge, Jun Yang, and Ke Yi. "I/O-Efficient Structures for Orthogonal Range-Max and Stabbing-Max Queries." European Symposium on Algorithms (ESA), September 2003. [pdf] [slides]
  95. Ke Yi, Hai Yu, Jun Yang, Gangqiang Xia, and Yuguo Chen. "Efficient Maintenance of Materialized Top-k Views." International Conference on Data Engineering (ICDE), March 2003. [pdf] [slides]
  96. Stergios V. Anastasiadis, Peter Varman, Jeffrey S. Vitter, and Ke Yi. "Lexicographically Optimal Smoothing for Broadband Traffic Multiplexing." ACM Symposium on Principles of Distributed Computing (PODC), July 2002. [pdf]

Journal Papers

  1. Wei Dong, Juanru Fang, Ke Yi, Yuchao Tao, and Ashwin Machanavajjhala. "Instance-optimal Truncation for Differentially Private Query Evaluation with Foreign Keys." ACM Transactions on Database Systems, 49(4):13, November 2024 (invited). [pdf]
  2. Wei Dong and Ke Yi. "Query Evaluation under Differential Privacy." SIGMOD Record, 52(3):6-17, September, 2023 (invited). [pdf]
  3. Tianjing Zeng, Zhewe Wei, Ge Luo, Ke Yi, Xiaoyong Du, and Jirong Wen. "Persistent Summaries." ACM Transactions on Database Systems, 47(3):11, April 2022. [pdf]
  4. Yufei Tao and Ke Yi. "Intersection Joins under Updates." Journal of Computer and System Sciences, 124:41-64, March 2022. [pdf]
  5. Xiao Hu and Ke Yi. "Massively Parallel Join Algorithms." SIGMOD Record, 49(3):6-17, December 2020 (invited). [pdf].
  6. Zengfeng Huang, Ke Yi, and Qin Zhang. "Randomized Algorithms for Tracking Distributed Count, Frequencies, and Ranks." Algorithmica, 81:2222-2243, June 2019. [pdf]
  7. Xiao Hu, Ke Yi, and Yufei Tao. "Output-optimal Massively Parallel Algorithms for Similarity Joins." ACM Transactions on Database Systems, 44(2):6, April 2019 (invited). [pdf]
  8. Feifei Li, Bin Wu, Ke Yi, and Zhuoyue Zhao. "Wander Join and XDB: Online Aggregation via Random Walks." ACM Transactions on Database Systems, 44(1):2, January 2019 (invited). [pdf]
  9. Zhewei Wei and Ke Yi. "Tight Space Bounds for Two-Dimensional Approximate Range Counting." ACM Transactions on Algorithms, 14(2):23, June 2018. [pdf]
  10. Zengfeng Huang and Ke Yi. "The Communication Complexity of Distributed epsilon-Approximations." SIAM Journal on Computing, 46(4):1370-1394, 2017. [pdf]
  11. Xiaoyu Ji, Yuan He, Jiliang Wang, Kaishun Wu, Daibo Liu, Ke Yi, and Yunhao Liu. "On Improving Wireless Channel Utilization: A Collision Tolerance-Based Approach." IEEE Transactions on Mobile Computing, 16(3):787-800, March 2017. [pdf]
  12. Pankaj K. Agarwal, Boris Aronov, Sariel Har-Peled, Jeff Phillips, Ke Yi, and Wuzhou Zhang. "Nearest-Neighbor Searching Under Uncertainty II." ACM Transactions on Algorithms, 13(1):3, October 2016. [pdf]
  13. Bin Wu, Ke Yi, and Zhenguo Li. "Counting Triangles in Large Graphs by Random Sampling." IEEE Transactions on Knowledge and Data Engineering, 28(8):2013-2026, August 2016. [pdf]
  14. Ge Luo, Lu Wang, Ke Yi, and Graham Cormode. "Quantiles over Data Streams: Experimental Comparisons, New Analyses, and Further Improvements." The VLDB Journal, 25(4):449-472, August 2016. [pdf]
  15. Feifei Li, Ke Yi, Yufei Tao, Bin Yao, Dong Xie, and Min Wang. "Exact and Approximate Flexible Aggregate Similarity Search." The VLDB Journal, 25(3):317-338, June 2016. [pdf]
  16. Rasmus Pagh, Zhewei Wei, Ke Yi, and Qin Zhang. "Cache-Oblivious Hashing." Algorithmica, 69(4):864-883, August 2014. [pdf]
  17. Ke Yi, Lu Wang, and Zhewei Wei. "Indexing for Summary Queries: Theory and Practice." ACM Transactions on Database Systems, 39(1):2, January 2014. [pdf]
  18. Pankaj K. Agarwal, Graham Cormode, Zengfeng Huang, Jeff M. Phillips, Zhewei Wei, and Ke Yi. "Mergeable Summaries." ACM Transactions on Database Systems, 38(4):26, November 2013 (invited). [pdf]
  19. Pankaj K. Agarwal, Lars Arge, Sathish Govindarajan, Jun Yang, and Ke Yi. "Efficient External Memory Structures for Range-Aggregate Queries." Computational Geometry: Theory and Applications, 46(3):358-370, April 2013. [pdf]
  20. Ke Yi and Qin Zhang. "Optimal Tracking of Distributed Heavy Hitters and Quantiles." Algorithmica, 65(1):206-223, January 2013. [pdf]
  21. Pankaj K. Agarwal, Siu-Wing Cheng, and Ke Yi. "Range Searching on Uncertain Data." ACM Transactions on Algorithms, 8(4):43, September 2012. [pdf]
  22. Ke Yi. "Dynamic Indexability and the Optimality of B-Trees." Journal of the ACM, 59(4):21, August 2012 (invited). [pdf]
  23. Graham Cormode, S. Muthukrishnan, Ke Yi, and Qin Zhang. "Continuous Sampling from Distributed Streams." Journal of the ACM, 59(2):10, April 2012 (invited). [pdf]
  24. Ke Yi and Qin Zhang. "Multi-Dimensional Online Tracking." ACM Transactions on Algorithms, 8(2):12, April 2012. [pdf]
  25. Pankaj K. Agarwal, Lars Arge, Haim Kaplan, Eyal Molad, Robert E. Tarjan, and Ke Yi. "An Optimal Dynamic Data Structure for Stabbing-Semigroup Queries." SIAM Journal on Computing, 41(1):104-127, January 2012. [pdf]
  26. Jeffrey Jestes, Graham Cormode, Feifei Li, and Ke Yi. "Semantics of Ranking Queries for Probabilistic Data." IEEE Transactions on Knowledge and Data Engineering, 23(12):1903-1917, December 2011. [pdf]
  27. Graham Cormode, S. Muthukrishnan, and Ke Yi. "Algorithms for Distributed Functional Monitoring." ACM Transactions on Algorithms, 7(2):21, March 2011. [pdf]
  28. Micha Streppel and Ke Yi. "Approximate Range Searching in External Memory." Algorithmica, 59(2):115-128, February 2011. [pdf]
  29. Ke Yi, Xiang Lian, Feifei Li, and Lei Chen. "The World in a Nutshell: Concise Range Queries." IEEE Transactions on Knowledge and Data Engineering, 23(1):139-154, January 2011. [pdf]
  30. Pankaj K. Agarwal, Lars Arge, and Ke Yi. "I/O-Efficient Batched Union-Find and Its Applications to Terrain Analysis." ACM Transactions on Algorithms, 7(1):11, November 2010. [pdf]
  31. Feifei Li, Ke Yi, and Wangchao Le. "Top-k Queries on Temporal Data." The VLDB Journal, 19(5):715-733, October 2010. [pdf] [code]
  32. Yufei Tao, Ke Yi, Cheng Sheng, and Panos Kalnis. "Efficient and Accurate Nearest Neighbor and Closest Pair Search in High Dimensional Space." ACM Transactions on Database Systems, 35(3):20, July 2010. [pdf] [code]
  33. Cheqing Jin, Ke Yi, Lei Chen, Jeffrey Xu Yu, and Xuemin Lin. "Sliding-Window Top-k Queries on Uncertain Streams." The VLDB Journal, 19(3):411-435, June 2010. [pdf]
  34. Ke Yi, Feifei Li, Graham Cormode, Marious Hadjieleftheriou, George Kollios, and Divesh Srivastava. "Small Synopses for Group-By Query Verification on Outsourced Data Streams." ACM Transactions on Database Systems, 34(3): 15, August 2009. [pdf]
  35. Lars Arge, Vasilis Samoladas, and Ke Yi. "Optimal External Memory Planar Point Enclosure." Algorithmica, 54(3):337-352, July 2009. [pdf]
  36. Ke Yi, Feifei Li, George Kollios, and Divesh Srivastava. "Efficient Processing of Top-k Queries in Uncertain Databases with x-Relations." IEEE Transactions on Knowledge and Data Engineering, 20(12):1669-1682, December 2008. [pdf] [code]
  37. Jiang Chen and Ke Yi. "A Dynamic Data Structure for Top-k Queries on Uncertain Data." Theoretical Computer Science, 407(1-3):310-317, November 2008. [pdf]
  38. Lars Arge, Mark de Berg, Herman Haverkort, and Ke Yi. "The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree." ACM Transactions on Algorithms, 4(1):9, March 2008. [pdf]
  39. Stergios V. Anastasiadis, Peter Varman, Jeffrey S. Vitter, and Ke Yi. "Optimal Lexicographic Shaping of Aggregate Streaming Data." IEEE Transactions on Computers, 54(4):398-408, April 2005. [pdf]

Short Papers and System Demontrations

  1. Jianzhe Yu, Wei Dong, Juanru Fang, Dajun Sun, and Ke Yi. "DOP-SQL: A General-purpose, High-utility, and Extensible Private SQL System." International Conference on Very Large Data Bases (VLDB), August, 2024. System demonstration.
  2. Binyang Dai, Qichen Wang, and Ke Yi. "SparkSQL+: Next-generation Query Planning over Spark." ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2023. System demonstration. [pdf]
  3. Qichen Wang, Chaoqi Zhang, Danish Alsayed, Ke Yi, Bin Wu, Feifei Li, and Chaoqun Zhan. "Cquirrel: Continuous Query Processing over Acyclic Relational Schemas." International Conference on Very Large Data Bases (VLDB), August 2021. System demonstration. [pdf]
  4. Yuan Qiu, Serafeim Papadias, and Ke Yi. "Streaming HyperCube: A Massively Parallel Stream Join Algorithm." International Conference on Extending Database Technology (EDBT), March 2019.
  5. Feifei Li, Bin Wu, Ke Yi, and Zhuoyue Zhao. "Wander Join: Online Aggregation for Joins." ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2016. System demonstration.
  6. Robert Christensen, Lu Wang, Feifei Li, Ke Yi, Jun Tang, and Natalee Villa. "STORM: Spatio-Temporal Online Reasoning and Management of Large Spatio-Temporal Data." ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2015. System demonstration: Best demonstration award.
  7. Graham Cormode and Ke Yi. "Tracking Distributed Aggregates over Time-Based Sliding Windows." ACM Symposium on Principles of Distributed Computing (PODC), June 2011.
  8. Yufei Tao, Jian Pei, Jiexing Li, Xiaokui Xiao, Ke Yi, Zhengzheng Xing. "Hiding Correlation by Independence Masking." International Conference on Data Engineering (ICDE), March 2010.
  9. Yinan Li, Bingsheng He, Qiong Luo, and Ke Yi. "Tree Indexing on Flash Disks." International Conference on Data Engineering (ICDE), March 2009.
  10. Ke Yi, Xiang Lian, FeiFei Li, and Lei Chen. "A Concise Representation of Range Queries." International Conference on Data Engineering (ICDE), March 2009.
  11. Ke Yi, Feifei Li, George Kollios, and Divesh Srivastava. "Efficient Processing of Top-k Queries in Uncertain Databases." International Conference on Data Engineering (ICDE), 2008.