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.

Papers marked with * use alphabetic ordering of authors.

Journal Papers

  1. Zengfeng Huang and Ke Yi.* "The Communication Complexity of Distributed epsilon-Approximations." SIAM Journal on Computing, 46(4):1370-1394, 2017. [pdf]
  2. 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]
  3. 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]
  4. 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]
  5. 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]
  6. 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]
  7. Rasmus Pagh, Zhewei Wei, Ke Yi, and Qin Zhang.* "Cache-Oblivious Hashing." Algorithmica, 69(4):864-883, August 2014. [pdf]
  8. 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]
  9. 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]
  10. 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]
  11. Ke Yi and Qin Zhang.* "Optimal Tracking of Distributed Heavy Hitters and Quantiles." Algorithmica, 65(1):206-223, January 2013. [pdf]
  12. Pankaj K. Agarwal, Siu-Wing Cheng, and Ke Yi.* "Range Searching on Uncertain Data." ACM Transactions on Algorithms, 8(4):43, September 2012. [pdf]
  13. Ke Yi. "Dynamic Indexability and the Optimality of B-Trees." Journal of the ACM, 59(4):21, August 2012 (invited). [pdf]
  14. 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]
  15. Ke Yi and Qin Zhang.* "Multi-Dimensional Online Tracking." ACM Transactions on Algorithms, 8(2):12, April 2012. [pdf]
  16. 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]
  17. 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]
  18. Graham Cormode, S. Muthukrishnan, and Ke Yi.* "Algorithms for Distributed Functional Monitoring." ACM Transactions on Algorithms, 7(2):21, March 2011. [pdf]
  19. Micha Streppel and Ke Yi.* "Approximate Range Searching in External Memory." Algorithmica, 59(2):115-128, February 2011. [pdf]
  20. 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]
  21. 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]
  22. Feifei Li, Ke Yi, and Wangchao Le. "Top-k Queries on Temporal Data." The VLDB Journal, 19(5):715-733, October 2010. [pdf] [code]
  23. 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]
  24. 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]
  25. 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]
  26. Lars Arge, Vasilis Samoladas, and Ke Yi.* "Optimal External Memory Planar Point Enclosure." Algorithmica, 54(3):337-352, July 2009. [pdf]
  27. 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]
  28. 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]
  29. 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]
  30. 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]

Conference Papers

  1. Yu Chen and Ke Yi.* "Two-Level Sampling for Join Size Estimation." ACM SIGMOD International Conference on Management of Data (SIGMOD), May 2017. [pdf]
  2. 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]
  3. Han Xu, Zheng Yang, Zimu Zhou, Ke Yi, Chunyi Peng. "TUM: Towards Ubiquitous Multi-Device Localization for Cross-Device Interaction." IEEE INFOCOM, May, 2017. [pdf]
  4. Han Xu, Zheng Yang, Zimu Zhou, Longfei Shangguan, Ke Yi, and Yunhao Liu. "Indoor localization via multi-modal sensing on smartphones." UbiComp, September 2016. [pdf]
  5. 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] Best paper award.
  6. 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]
  7. 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]
  8. Han Xu, Zheng Yang, Zimu Zhou, Longfei Shangguan, Ke Yi, Yunhao Liu. "Enhancing WiFi-based Localization with Visual Clues." UbiComp, September 2015. [pdf]
  9. 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]
  10. 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]
  11. Zengfeng Huang and Ke Yi.* "The Communication Complexity of Distributed epsilon-Approximations." IEEE Symposium on Foundations of Computer Science (FOCS), October 2014. [pdf]
  12. Zhewei Wei and Ke Yi.* "Equivalence between Priority Queues and Sorting in External Memory." European Symposium on Algorithms (ESA), September 2014. [pdf]
  13. 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]
  14. 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]
  15. 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]
  16. 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]
  17. Charalampos Papamanthou, Elaine Shi, Roberto Tamassia, and Ke Yi.* "Streaming Authenticated Data Structures." International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT), May 2013. [pdf]
  18. Zhewei Wei and Ke Yi.* "The Space Complexity of 2-Dimensional Approximate Range Counting." ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2013. [pdf]
  19. 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]
  20. Graham Cormode, Justin Thaler, and Ke Yi.* "Verifying Computations with Streaming Interactive Proofs." International Conference on Very Large Data Bases (VLDB), August 2012. [pdf]
  21. 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]
  22. 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]
  23. 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]
  24. 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]
  25. 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]
  26. Zhewei Wei and Ke Yi.* "Beyond Simple Aggregates: Indexing for Summary Queries." ACM Symposium on Principles of Database Systems (PODS), June 2011. [pdf] [slides]
  27. Zengfeng Huang, Ke Yi, Yunhao Liu, and Guihai Chen. "Optimal Sampling Algorithms for Frequency Estimation in Distributed Data." IEEE INFOCOM, April 2011. [pdf]
  28. 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]
  29. Jian Li, Ke Yi, and Qin Zhang.* "Clustering with Diversity." International Colloquium on Automata, Languages and Programming (ICALP), July 2010. [pdf] [slides]
  30. 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]
  31. 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]
  32. 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]
  33. Rasmus Pagh, Zhewei Wei, Ke Yi, and Qin Zhang.*"Cache-Oblivious Hashing." ACM Symposium on Principles of Database Systems (PODS), June 2010. [pdf] [slides]
  34. 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]
  35. Ke Yi and Qin Zhang.* "On the Cell Probe Complexity of Dynamic Membership." ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2010. [pdf] [slides]
  36. 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]
  37. 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]
  38. 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]
  39. 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]
  40. 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]
  41. 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]
  42. 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]
  43. Ke Yi and Qin Zhang.* "Multi-Dimensional Online Tracking." ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2009. [pdf] [slides]
  44. 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]
  45. 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]
  46. 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]
  47. Graham Cormode, S. Muthukrishnan, and Ke Yi.* "Algorithms for Distributed Functional Monitoring." ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2008. [pdf] [slides]
  48. 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]
  49. Micha Streppel and Ke Yi.* "Approximate Range Searching in External Memory." International Symposium on Algorithms and Computation (ISAAC), December 2007. [pdf] [slides]
  50. 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]
  51. 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]
  52. 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.)
  53. Pankaj K. Agarwal, Lars Arge, and Ke Yi.* "I/O-Efficient Batched Union-Find and Its Applications to Terrain Analysis." ACM Symposium on Computational Geometry (SoCG), June 2006. [pdf] [slides] [code]
  54. 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]
  55. 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]
  56. 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]
  57. 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]
  58. Lars Arge, Vasilis Samoladas, and Ke Yi.* "Optimal External Memory Planar Point Enclosure." European Symposium on Algorithms (ESA), September 2004. [pdf] [slides]
  59. 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]
  60. 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]
  61. 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]
  62. 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]
  63. 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]

Short Papers and System Demontrations

  1. 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.
  2. 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. Best demonstration award.
  3. Graham Cormode and Ke Yi.* "Tracking Distributed Aggregates over Time-Based Sliding Windows." ACM Symposium on Principles of Distributed Computing (PODC), June 2011.
  4. 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.
  5. Yinan Li, Bingsheng He, Qiong Luo, and Ke Yi. "Tree Indexing on Flash Disks." International Conference on Data Engineering (ICDE), March 2009.
  6. Ke Yi, Xiang Lian, FeiFei Li, and Lei Chen. "A Concise Representation of Range Queries." International Conference on Data Engineering (ICDE), March 2009.
  7. 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. Short paper.