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.
|
Building Wavelet Histograms on Large Data
in MapReduce Jeffrey Jestes, Ke Yi, and Feifei Li To appear in International Conference on Very Large Data Bases (VLDB), August 2012. |
|
Verifying Computations with Streaming
Interactive Proofs Graham Cormode, Justin Thaler, and Ke Yi* To appear in International Conference on Very Large Data Bases (VLDB), August 2012. |
|
Beyond Simple Aggregates: Indexing for Summary
Queries [slides] Zhewei Wei and Ke Yi* ACM Symposium on Principles of Database Systems (PODS), June 2011. |
|
Sampling Based Algorithms for Quantile
Computation in Sensor Networks [slides]
Zengfeng Huang, Lu Wang, Ke Yi, and Yunhao Liu ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2011. |
|
Flexible Aggregate Similarity
Search Yang Li, Feifei Li, Ke Yi, Bin Yao, and Min Wang ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2011. |
|
Optimal Sampling Algorithms for Frequency
Estimation in Distributed Data Zengfeng Huang, Ke Yi, Yunhao Liu, and Guihai Chen IEEE INFOCOM, April 2011. |
|
Tree Indexing on Solid State
Drives Yinan Li, Bingsheng He, Robin Jun Yang, Qiong Luo, and Ke Yi International Conference on Very Large Data Bases (VLDB), September 2010. |
|
Clustering with Diversity [slides] Jian Li, Ke Yi, and Qin Zhang* International Colloquium on Automata, Languages and Programming (ICALP), July 2010. [full version] |
|
Optimal Sampling from Distributed
Streams [slides] Graham Cormode, S. Muthukrishnan, Ke Yi, and Qin Zhang* ACM Symposium on Principles of Database Systems (PODS), June 2010. Full version to appear in JACM. |
|
Cache-Oblivious Hashing [slides] Rasmus Pagh, Zhewei Wei, Ke Yi, and Qin Zhang* ACM Symposium on Principles of Database Systems (PODS), June 2010. |
|
Logging Every Footstep: Quantile
Summaries for the Entire History Yufei Tao, Ke Yi, Cheng Sheng, Jian Pei, and Feifei Li ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2010. |
|
Probabilistic String Similarity Joins
[slides]
[code]
Jeffrey Jestes, Feifei Li, Zhepeng Yan, and Ke Yi* ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2010. |
|
The Hardness and Approximation Algorithms for L-Diversity Xiaokui Xiao, Ke Yi, and Yufei Tao International Conference on Extending Data Base Technology (EDBT), March 2010. |
|
On the Cell Probe Complexity of
Dynamic Membership [slides] Ke Yi and Qin Zhang* ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2010. |
|
Dynamic
External Hashing: The Limit of Buffering [slides] Zhewei Wei, Ke Yi, and Qin Zhang* ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), August 2009. |
|
Dynamic
Indexability and Lower Bounds for Dynamic One-Dimensional Range Query
Indexes [slides] Ke Yi ACM Symposium on Principles of Database Systems (PODS), June 2009. Full version to appear in JACM. |
|
Optimal Tracking of Distributed Heavy Hitters and Quantiles [slides] Ke Yi and Qin Zhang* ACM Symposium on Principles of Database Systems (PODS), June 2009. Full version to appear in Algorithmica. |
|
Indexing Uncertain Data [slides] Pankaj K. Agarwal, Siu-Wing Cheng, Yufei Tao, and Ke Yi* ACM Symposium on Principles of Database Systems (PODS), June 2009. Full version to appear in TALG. |
|
Quality and Efficiency in
High Dimensional Nearest Neighbor Search [code]
Yufei Tao, Ke Yi, Cheng Sheng, and Panos Kalnis ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2009. Full version in TODS, 2010. |
|
Ranking Distributed Probabilistic Data [slides] [code]
Feifei Li, Ke Yi, and Jeffrey Jestes ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2009. |
|
Semantics of Ranking Queries for Probabilistic Data
and Expected Ranks [slides] [code] Graham Cormode, Feifei Li, and Ke Yi* International Conference on Data Engineering (ICDE), March 2009. Full version to appear in TKDE. |
|
Multi-Dimensional Online Tracking
[slides] Ke Yi and Qin Zhang* ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2009. Full version to appear in TALG. |
|
Sliding-Window Top-k Queries on
Uncertain Streams [ppt]
Cheqing Jin, Ke Yi, Lei Chen, Jeffrey Xu Yu, and Xuemin Lin International Conference on Very Large Data Bases (VLDB), August 2008. Full version in VLDBJ, 2010. |
|
Finding Frequent
Items in Probabilistic Data [slides] [code]
Qin Zhang, Feifei Li, and Ke Yi ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2008. |
|
Randomized Synopses for
Query Assurance on Data Streams [pptx] [code] Ke Yi, Feifei Li, Marios Hadjieleftheriou, George Kollios, and Divesh Srivastava International Conference on Data Engineering (ICDE), April 2008. Full version in TODS, 2009. |
|
Algorithms for Distributed Functional
Monitoring [pptx] Graham Cormode, S. Muthukrishnan, and Ke Yi* ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2008. Full version in TALG, 2011. |
|
Dynamic Structures for Top-k Queries on Uncertain
Data [pptx] Jiang Chen and Ke Yi* International Symposium on Algorithms and Computation (ISAAC), December 2007. Full version in TCS, 2008. |
|
Approximate Range Searching in External
Memory [pptx] Micha Streppel and Ke Yi* International Symposium on Algorithms and Computation (ISAAC), December 2007. Full version in Algorithmica, 2011. |
|
TerraStream: From
Elevation Data to Watershed
Hierarchies [ppt] Andrew Danner, Thomas Mølhave, Ke Yi, Pankaj K. Agarwal, Lars Arge, and Helena Mitasova ACM International Symposium on Advances in Geographic Information Systems (ACM GIS), November 2007. |
|
Proof-Infused Streams: Enabling
Authentication of Sliding Window Queries on
Streams [pptx] Feifei Li, Ke Yi, Marios Hadjieleftheriou, and George Kollios International Conference on Very Large Data Bases (VLDB), September 2007. |
|
Restricted Strip
Covering and the Sensor Cover
Problem [ppt] Adam L. Buchsbaum, Alon Efrat, Shaili Jain, Suresh Venkatasubramanian, and Ke Yi* ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2007. (The results of this paper have been improved by this paper in FOCS'09.) |
|
I/O-Efficient Batched
Union-Find and Its Applications to Terrain Analysis [ppt] [code] Pankaj K. Agarwal, Lars Arge, and Ke Yi* ACM Symposium on Computational Geometry (SoCG), June 2006. Full version in TALG, 2010. |
|
An Information-Theoretic Approach to
Detecting Changes in Multi-Dimensional Data Streams Tamraparni Dasu, Shankar Krishnan, Suresh Venkatasubramanian, and Ke Yi* Symposium on the Interface of Statistics, Computing Science, and Applications (Interface), May, 2006. |
|
I/O-Efficient Construction
of Constrained Delaunay Triangulations [ppt] Pankaj K. Agarwal, Lars Arge, and Ke Yi* Annual European Symposium on Algorithms (ESA), October 2005. [full version] |
|
BOXes: Efficient Maintenance
of Order-Based Labeling for Dynamic XML Data [ppt] Adam Silberstein, Hao He, Ke Yi, and Jun Yang International Conference on Data Engineering (ICDE), April 2005. |
|
An Optimal Dynamic
Interval Stabbing-Max Data Structure? [ppt] Pankaj K. Agarwal, Lars Arge, and Ke Yi* ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2005. Full version to appear in SICOMP. |
|
Optimal External Memory Planar
Point Enclosure [ppt] Lars Arge, Vasilis Samoladas, and Ke Yi* Annual European Symposium on Algorithms (ESA), September 2004. Full version in Algorithmica, 2009. |
|
The Priority R-Tree:
A Practically Efficient and Worst-Case Optimal R-Tree [ppt] [code] Lars Arge, Mark de Berg, Herman Haverkort, and Ke Yi* ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2004. Full version in TALG, 2008. |
|
Incremental Maintenance of XML
Structural Indexes [ppt] Ke Yi, Hao He, Ioana Stanoi, and Jun Yang ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2004. |
|
I/O-Efficient
Structures for Orthogonal Range-Max and Stabbing-Max Queries [ppt] Pankaj K. Agarwal, Lars Arge, Jun Yang, and Ke Yi* Annual European Symposium on Algorithms (ESA), September 2003. |
|
Efficient
Maintenance of Materialized Top-k Views [slides] Ke Yi, Hai Yu, Jun Yang, Gangqiang Xia, and Yuguo Chen International Conference on Data Engineering (ICDE), March 2003. |
|
Lexicographically Optimal Smoothing for
Broadband Traffic Multiplexing Stergios V. Anastasiadis, Peter Varman, Jeffrey S. Vitter, and Ke Yi* ACM Symposium on Principles of Distributed Computing (PODC), July 2002. Full version in TC, 2005. |
|
Continuous Sampling from Distributed Streams Graham Cormode, S. Muthukrishnan, Ke Yi, and Qin Zhang* To appear in Journal of the ACM. |
|
Dynamic Indexability and the Optimality of B-Trees Ke Yi To appear in Journal of the ACM. |
| An Optimal Dynamic Data Structure for
Stabbing-Semigroup Queries Pankaj K. Agarwal, Lars Arge, Haim Kaplan, Eyal Molad, Robert E. Tarjan, and Ke Yi* To appear in SIAM Journal on Computing. |
|
Multi-Dimensional Online Tracking Ke Yi and Qin Zhang* To appear in ACM Transactions on Algorithms. |
|
Range Searching on Uncertain Data Pankaj K. Agarwal, Siu-Wing Cheng, and Ke Yi* To appear in ACM Transactions on Algorithms. |
|
Optimal Tracking of Distributed Heavy Hitters and
Quantiles Ke Yi and Qin Zhang* To appear in Algorithmica. |
|
Semantics
of Ranking Queries for Probabilistic Data Jeffrey Jestes, Graham Cormode, Feifei Li, and Ke Yi. IEEE Transactions on Knowledge and Data Engineering, 23(12):1903-1917, October 2011. |
|
Algorithms
for Distributed Functional Monitoring Graham Cormode, S. Muthukrishnan, and Ke Yi* ACM Transactions on Algorithms, 7(2), Article 21, March 2011. |
|
Approximate
Range Searching in External Memory Micha Streppel and Ke Yi* Algorithmica, 59(2):115-128, February 2011. |
|
The
World in a Nutshell: Concise Range Queries Ke Yi, Xiang Lian, Feifei Li, and Lei Chen IEEE Transactions on Knowledge and Data Engineering, 23(1):139-154, January 2011. |
|
I/O-Efficient
Batched Union-Find and Its Applications to Terrain Analysis Pankaj K. Agarwal, Lars Arge, and Ke Yi* ACM Transactions on Algorithms, 7(1), Article 11, November 2010. |
|
Top-k
Queries on Temporal Data [code] Feifei Li, Ke Yi, and Wangchao Le The VLDB Journal, 19(5):715-733, October 2010. |
|
Efficient
and Accurate Nearest Neighbor and Closest Pair Search in High
Dimensional Space [code]
Yufei Tao, Ke Yi, Cheng Sheng, and Panos Kalnis ACM Transactions on Database Systems, 35(3), Article 20, July 2010. |
|
Sliding-Window
Top-k Queries on Uncertain Streams
Cheqing Jin, Ke Yi, Lei Chen, Jeffrey Xu Yu, and Xuemin Lin The VLDB Journal, 19(3):411-435, June 2010. |
|
Small
Synopses for Group-By Query Verification on Outsourced Data Streams Ke Yi, Feifei Li, Graham Cormode, Marious Hadjieleftheriou, George Kollios, and Divesh Srivastava ACM Transactions on Database Systems, 34(3), Article 15, August 2009. |
|
Optimal External Memory Planar Point Enclosure Lars Arge, Vasilis Samoladas, and Ke Yi* Algorithmica, 54(3):337-352, July 2009. |
|
Efficient Processing of Top-k Queries in Uncertain Databases with
x-Relations [code] Ke Yi, Feifei Li, George Kollios, and Divesh Srivastava IEEE Transactions on Knowledge and Data Engineering, 20(12):1669-1682, December 2008. |
|
A
Dynamic Data Structure for Top-k Queries on Uncertain Data Jiang Chen and Ke Yi* Theoretical Computer Science, 407(1-3):310-317, November 2008. |
|
The
Priority R-Tree: A Practically Efficient and Worst-Case Optimal
R-Tree Lars Arge, Mark de Berg, Herman Haverkort, and Ke Yi* ACM Transactions on Algorithms, 4(1), Article 9, March 2008. |
|
Optimal Lexicographic Shaping of Aggregate Streaming
Data Stergios V. Anastasiadis, Peter Varman, Jeffrey S. Vitter, and Ke Yi* IEEE Transactions on Computers, 54(4):398-408, April 2005. |
|
Tracking Distributed Aggregates over Time-Based Sliding Windows Graham Cormode and Ke Yi* ACM Symposium on Principles of Distributed Computing (PODC), June 2011. Brief announcement. |
|
Hiding Correlation by Independence Masking Yufei Tao, Jian Pei, Jiexing Li, Xiaokui Xiao, Ke Yi, Zhengzheng Xing International Conference on Data Engineering (ICDE), March 2010. Short paper. |
|
Tree Indexing on Flash Disks Yinan Li, Bingsheng He, Qiong Luo, and Ke Yi International Conference on Data Engineering (ICDE), March 2009. Short paper. Full version to appear in PVLDB. |
|
A Concise Representation of Range Queries Ke Yi, Xiang Lian, FeiFei Li, and Lei Chen International Conference on Data Engineering (ICDE), March 2009. Short paper. Full version to appear in TKDE. |
|
Efficient Processing of Top-k Queries in Uncertain Databases Ke Yi, Feifei Li, George Kollios, and Divesh Srivastava International Conference on Data Engineering (ICDE), April 2008. Short paper. Full version in TKDE, 2008. |
|
R-Trees Ke Yi Encyclopedia of Algorithms, Ming-Yang Kao, Ed., Springer. |
|
I/O-Efficient Algorithms for Processing Massive Spatial Data Ke Yi Ph.D. Dissertation, Duke University, August, 2006. |