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, following the
convention of theoretical computer science.
 On the Cell Probe Complexity of
Dynamic Membership
Ke Yi and Qin Zhang*
Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA),
Austin, TX, January 2010.
|
Dynamic
External Hashing: The Limit of Buffering [slides]
Zhewei Wei, Ke Yi, and Qin Zhang*
Proc. ACM Symposium on Parallelism in Algorithms and Architectures
(SPAA), pages 253-259, Calgary, Canada, August 2009.
|
Dynamic
Indexability and Lower Bounds for Dynamic One-Dimensional Range Query
Indexes [slides]
Ke Yi
Proc. ACM Symposium on Principles of Database
Systems (PODS), pages 187-196, Providence, RI, June 2009.
Invited to JACM.
|
Optimal Tracking of Distributed Heavy Hitters and Quantiles [slides]
Ke Yi and Qin Zhang*
Proc. ACM Symposium on Principles of Database
Systems (PODS), pages 167-174, Providence, RI, June 2009.
|
Indexing Uncertain Data [slides]
Pankaj K. Agarwal, Siu-Wing Cheng, Yufei Tao, and Ke Yi*
Proc. ACM Symposium on Principles of Database
Systems (PODS), pages 137-146, Providence, RI, June 2009.
|
Quality and Efficiency in
High Dimensional Nearest Neighbor Search [code]
Yufei Tao, Ke Yi, Cheng Sheng, and Panos Kalnis
Proc. ACM SIGMOD International Conference on Management of
Data (SIGMOD), pages 563-576, Providence, RI, June 2009.
|
Ranking Distributed Probabilistic Data [slides]
Feifei Li, Ke Yi, and Jeffrey Jestes
Proc. ACM SIGMOD International Conference on Management of
Data (SIGMOD), pages 361-374, Providence, RI, June 2009.
|
Semantics of Ranking Queries for Probabilistic Data
and Expected Ranks [slides]
Graham Cormode, Feifei Li, and Ke Yi*
Proc. International Conference on Data Engineering
(ICDE), pages 305-316, Shanghai, China, March 2009.
Invited to TKDE.
|
Multi-Dimensional Online Tracking
[slides]
Ke Yi and Qin Zhang*
Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1098-1107, New York,
NY, January 2009.
|
Sliding-Window Top-k Queries on
Uncertain Streams [ppt]
Cheqing Jin, Ke Yi, Lei Chen, Jeffrey Xu Yu, and Xuemin Lin
Proc. International Conference on Very Large Data Bases
(VLDB), pages 301-312, Auckland, New Zealand, August 2008.
|
Finding Frequent
Items in Probabilistic Data [slides] [code]
Qin Zhang, Feifei Li, and Ke Yi
Proc. ACM SIGMOD International Conference on Management of
Data (SIGMOD), pages 819-832, Vancouver, Canada, June 2008. |
Randomized Synopses for
Query Assurance on Data Streams [pptx] [code]
Ke Yi, Feifei Li, Marios Hadjieleftheriou, George
Kollios, and Divesh Srivastava
Proc. International Conference on Data Engineering
(ICDE), pages 416-425, Cancun, Mexico, April 2008. |
Algorithms for Distributed Functional
Monitoring [pptx]
Graham Cormode, S. Muthukrishnan, and Ke Yi*
Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), pages
1076-1085, San Francisco, CA, January 2008.
|
Dynamic Structures for Top-k Queries on Uncertain
Data [pptx]
Jiang Chen and Ke Yi*
Proc. International Symposium on Algorithms and Computation
(ISAAC), pages 427-438, Sendai, Japan, December 2007.
|
Approximate Range Searching in External
Memory [pptx]
Micha Streppel and Ke Yi*
Proc. International Symposium
on Algorithms and Computation (ISAAC), pages 536-548,
Sendai, Japan, December 2007.
|
TerraStream: From
Elevation Data to Watershed
Hierarchies [ppt]
Andrew Danner, Thomas Mølhave, Ke Yi, Pankaj K. Agarwal, Lars Arge,
and Helena Mitasova
Proc. ACM International Symposium
on Advances in Geographic Information Systems (ACM GIS),
Seattle, WA, November 2007.
|
Proof-Infused Streams: Enabling
Authentication of Sliding Window Queries on
Streams [pptx]
Feifei Li, Ke Yi, Marios Hadjieleftheriou,
and George Kollios
Proc. International Conference on Very Large Data Bases
(VLDB), pages 147-158,
Vienna, Austria, September 2007.
|
Restricted Strip
Covering and the Sensor Cover
Problem [ppt]
Adam L. Buchsbaum, Alon Efrat, Shaili Jain, Suresh Venkatasubramanian,
and Ke Yi*
Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), pages
1056-1065, New
Orleans, LA, January 2007.
|
I/O-Efficient Batched
Union-Find and Its Applications to Terrain Analysis [ppt] [code]
Pankaj K. Agarwal, Lars Arge, and Ke Yi*
Proc. Annual Symposium on Computational Geometry (SoCG), pages
167-176, Sedona, AZ, June 2006.
|
I/O-Efficient Construction
of Constrained Delaunay Triangulations [ppt]
Pankaj K. Agarwal, Lars Arge, and Ke Yi*
Proc. Annual European Symposium on Algorithms (ESA), pages
355-366, Mallorca, Spain, October 2005.
|
BOXes: Efficient Maintenance
of Order-Based Labeling for Dynamic XML Data [ppt]
Adam Silberstein, Hao He, Ke Yi, and Jun Yang
Proc. International Conference on Data Engineering
(ICDE), pages 285-296, Tokyo, Japan, April 2005.
|
An Optimal Dynamic
Interval Stabbing-Max Data Structure? [ppt]
Pankaj K. Agarwal, Lars Arge, and Ke Yi*
Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), pages
803-812, Vancouver, BC, Canada, January 2005.
|
Optimal External Memory Planar
Point Enclosure [ppt]
Lars Arge, Vasilis Samoladas, and Ke Yi*
Proc. Annual European Symposium on Algorithms (ESA),
pages 40-52, Bergen, Norway, September 2004.
|
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*
Proc. ACM SIGMOD International Conference on
Management of Data (SIGMOD), pages 347-358, Paris, France, June 2004.
|
Incremental Maintenance of XML
Structural Indexes [ppt]
Ke Yi, Hao He, Ioana Stanoi, and Jun Yang
Proc. ACM SIGMOD International Conference on
Management of Data (SIGMOD), pages 491-502, Paris, France, 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*
Proc. Annual European Symposium on Algorithms (ESA), pages 7-18,
Budapest, Hungary, September 2003. |
Efficient
Maintenance of Materialized Top-k Views [slides]
Ke Yi, Hai Yu, Jun Yang, Gangqiang Xia, and Yuguo Chen
Proc. International Conference on Data Engineering
(ICDE), pages 189-200, Bangalore, India, March 2003.
|
Lexicographically Optimal Smoothing for
Broadband Traffic Multiplexing
Stergios V. Anastasiadis, Peter Varman, Jeffrey S. Vitter, and Ke Yi*
Proc. ACM Symposium on Principles of Distributed
Computing (PODC), pages 68-77, Monterey, CA, July 2002.
|
Algorithms for Distributed Functional Monitoring
Graham Cormode, S. Muthukrishnan, and Ke Yi*
To appear in ACM Transactions on Algorithms. Preliminary version in SODA '08.
|
Approximate Range Searching in External Memory
Micha Streppel and Ke Yi*
To appear in Algorithmica. Preliminary version in ISAAC '07.
|
I/O-Efficient Batched Union-Find and Its Applications to Terrain
Analysis
Pankaj K. Agarwal, Lars Arge, and Ke Yi*
To appear in ACM Transactions on Algorithms. Preliminary version in SoCG '06.
|
The World in a Nutshell: Concise Range Queries
Ke Yi, Xiang Lian, Feifei Li, and Lei Chen
To appear in IEEE Transactions on Knowledge and Data Engineering.
Preliminary version in ICDE '09 (short paper).
|
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. Preliminary version in ICDE '08.
|
Optimal External Memory Planar Point Enclosure
Lars Arge, Vasilis Samoladas, and Ke Yi*
Algorithmica, 54(3):337-352, July 2009. Preliminary version in
ESA '04.
|
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.
Preliminary version in ICDE '08 (short paper).
|
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.
Preliminary version in ISAAC '07.
|
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.
Preliminary version in SIGMOD '04.
|
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. Preliminary version in PODC '02.
|