Publications of Yufei Tao

In publications marked with '**', authors are ordered alphabetically, as is a convention of theory papers. In the other publications, authors are ordered by contribution.

Click here for a subset of papers that I consider the best.

• Joint work with Ru Wang.
  **Join Sampling under Acyclic Degree Constraints and (Cyclic) Subgraph Sampling.
  To appear in Proceedings of the 27th International Conference on Database Theory (ICDT), 2024.
  
  
• Joint work with Shiyuan Deng.
  **Subgraph Enumeration in Optimal I/O Complexity.
  To appear in Proceedings of the 27th International Conference on Database Theory (ICDT), 2024.
  
  
• Joint work with Xiao Hu.
  **Parallel Acyclic Joins: Optimal Algorithms and Cyclicity Separation.
  Journal of the ACM (JACM), 71(1): 6:1-6:44, 2024.
  
  
• Ru Wang, Shangqi Lu, and Yufei Tao.
  An Index for Set Intersection with Post-Filtering.
  To appear in IEEE Transactions on Knowledge and Data Engineering (TKDE).
  

• Joint work with Shiyuan Deng and Shangqi Lu.
  **On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms.
  Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), pages 99-111, 2023.
  
  
• Joint work with Shangqi Lu.
  **Indexing for Keyword Search with Structured Constraints.
  Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), pages 263-275, 2023.
  
  
• Joint work with Shiyuan Deng and Francesco Silvestri.
  **Enumerating Subgraphs of Constant Sizes in External Memory.
  Proceedings of the 26th International Conference on Database Theory (ICDT), pages 4:1-4:20, 2023.
  (Winner of the Best Paper Award)
  
  
• Joint work with Shiyuan Deng and Shangqi Lu.
  **Space-Query Tradeoffs in Range Subgraph Counting and Listing.
  Proceedings of the 26th International Conference on Database Theory (ICDT), pages 6:1-6:25, 2023.
  
  
• Joint work with Shangqi Lu.
  **Range Updates and Range Sum Queries on Multidimensional Points with Monoid Weights.
  Computational Geometry: Theory and Applications, 115:102030, 2023.
  
  
• Joint work with Shangqi Lu, Wim Martens, and Matthias Niewerth.
  **Partial Order Multiway Search.
  ACM Transactions on Database Systems (TODS), 48(4): 10:1-10:31, 2023.
  (Special issue of PODS'22).
  
  

• Joint work with Shangqi Lu.
  **Range Updates and Range Sum Queries on Multidimensional Points with Monoid Weights.
  Proceedings of the 33rd International Symposium on Algorithms and Computation (ISAAC), pages 57:1-57:16, 2022.
  Invited to Computational Geometry: Theory and Applications. Long version
  
  
• Yufei Tao, Hao Wu, and Shiyuan Deng.
  Cross-Space Active Learning on Graph Convolutional Networks.
  Proceedings of the 39th International Conference on Machine Learning (ICML), pages 21133-21145, 2022.
  
  
• Yufei Tao.
  Algorithmic Techniques for Independent Query Sampling.
  Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), pages 129-138, 2022.
  (GEMS of PODS)
  
  
• Joint work with Shangqi Lu, Wim Martens, and Matthias Niewerth.
  **Optimal Algorithms for Multiway Search on Partial Orders.
  Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), pages 175-187, 2022.
  Long version
  
  
• Yufei Tao.
  Parallel Acyclic Joins with Canonical Edge Covers.
  Proceedings of the 25th International Conference on Database Theory (ICDT), pages 9:1-9:19, 2022.
  
  
• Joint work with Bas Ketsman and Dan Suciu.
  **A Near-Optimal Parallel Algorithm for Joining Binary Relations.
  Logical Methods in Computer Science (LMCS), 18(2): 6:1-6:22, 2022.
  (Special issue of ICDT'20).
  
  
• Joint work with Ke Yi.
  **Intersection Joins under Updates.
  Journal of Computer and System Sciences (JCSS), 124: 41-64, 2022.
  
  
• Joint work with Abolfazl Asudeh, Das Gautam, HV Jagadish, Shangqi Lu, Azade Nazi, Nan Zhang, and Jianwen Zhao.
  **On Finding Rank Regret Representatives.
  ACM Transactions on Database Systems (TODS), 47(3): 10:1-10:37, 2022.
  
  
• Joint work with Rahul Saladi.
  **Generic Techniques for Building Top-k Structures.
  ACM Transactions on Algorithms, 18(4): 38:1-38:23, 2022.
  
  

• Joint work with Yu Wang.
  **New Algorithms for Monotone Classification.
  Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), pages 260-272, 2021.
  
  Remark: Problem 2 has been studied before under the name "isotonic regression"; please see the details here.
  
  
• Joint work with Miao Qiao.
  **Two-Attribute Skew Free, Isolated CP Theorem, and Massively Parallel Joins.
  Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), pages 166-180, 2021.
  
  
• Joint work with Shangqi Lu.
  **Towards Optimal Dynamic Indexes for Approximate (and Exact) Triangle Counting.
  Proceedings of the 24th International Conference on Database Theory (ICDT), pages 6:1-6:23, 2021.
  
  
• Jianwen Zhao and Yufei Tao.
  Minimum Vertex Augmentation.
  Proceedings of the VLDB Endowment (PVLDB), 14(9): 1454-1466, 2021.
  
  
• Joint work with Casper Kejlberg-Rasmussen, Konstantinos Tsakalidis, Kostas Tsichlas, and Jeonghun Yoon.
  **I/O-Efficient 2-d Orthogonal Range Skyline and Attrition Priority Queues.
  Computational Geometry: Theory and Applications, 93:101689, 2021.

• Yufei Tao and Shangqi Lu.
  From Online to Non-i.i.d. Batch Learning.
  Proceedings of the 26th ACM International Conference On Knowledge Discovery and Data Mining (SIGKDD), pages 328-337, 2020.
  
  
• Yufei Tao.
  A Simple Parallel Algorithm for Natural Joins on Binary Relations.
  Proceedings of the 23rd International Conference on Database Theory (ICDT), pages 25:1-25:18, 2020.
  See the long version for improved results and enhanced presentation.
  
  
• Jianzhong Qi, Yufei Tao, Yanchuan Chang, and Rui Zhang.
  Packing R-Trees with Space-Filling Curves: Theoretical Optimality, Empirical Efficiency, and Bulk-Loading Parallelizability.
  ACM Transactions on Database Systems (TODS), 45(3): 14:1-14:47, 2020.
  
  

• Yufei Tao, Yuanbing Li, and Guoliang Li.
  Interactive Graph Search.
  Proceedings of ACM Conference on Management of Data (SIGMOD), pages 1393-1410, 2019.
  
  
• Joint work with Yu Wang.
  **Distribution-Sensitive Bounds on Relative Approximations of Geometric Ranges.
  Proceedings of the 35th Symposium on Computational Geometry (SoCG), pages 57:1-57:14, 2019.
  
  
• Xiao Hu, Ke Yi, and Yufei Tao.
  Output-Optimal Massively Parallel Algorithms for Similarity Joins.
  ACM Transactions on Database Systems (TODS), 44(2): 6:1-6:36, 2019.
  (Special issue of PODS'17).
  
  
• Joint work with Xiaocheng Hu and Cheng Sheng.
  **Building an Optimal Point-Location Structure in O(sort(n)) I/Os.
  Algorithmica, 81(5): 1921-1937, 2019.
  
  
• Joint work with Saladi Rahul.
  **A Guide to Designing Top-k Indexes.
  SIGMOD Record (the Database Principles Column), 48(2): 6-17, 2019.
  
  

• Yufei Tao.
  Entity Matching with Active Monotone Classification.
  Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), pages 49-62, 2018.
  (Winner of the Best Paper Award)
  (A short version for the SIGMOD Research Highlight Award)
  
  
• Junhao Gan and Yufei Tao.
  Fast Euclidean OPTICS with Bounded Precision in Low Dimensional Space.
  Proceedings of ACM Conference on Management of Data (SIGMOD), pages 1067-1082, 2018.
  
  
• Sibo Wang and Yufei Tao.
  Efficient Algorithms for Finding Approximate Heavy Hitters in Personalized PageRanks.
  Proceedings of ACM Conference on Management of Data (SIGMOD), pages 1113-1127, 2018.
  
  
• Dong Deng, Yufei Tao, and Guoliang Li.
  Overlap Set Similarity Joins with Theoretical Guarantees.
  Proceedings of ACM Conference on Management of Data (SIGMOD), pages 905-920, 2018.
  
  
• Yufei Tao.
  Massively Parallel Entity Matching with Linear Classification in Low Dimensional Space.
  Proceedings of the 21st International Conference on Database Theory (ICDT), pages 20:1-20:19, 2018.
  
  
• Jianzhong Qi, Yufei Tao, Yanchuan Chang, and Rui Zhang.
  Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability.
  Proceedings of the VLDB Endowment (PVLDB), 11(5): 621-634, 2018.
  
  
• Joint work with Xiaocheng Hu, Yi Yang, and Shuigeng Zhou.
  **Semi-Group Range Sum Revisited: Query-Space Lower Bound Tightened.
  Algorithmica, 80(4): 1315-1329, 2018.
  
  
• Joint work with Junhao Gan.
  **An I/O-Efficient Algorithm for Computing Vertex Separators on Multi-Dimensional Grid Graphs and Its Applications.
  Journal of Graph Algorithms and Applications (JGAA), 22(2): 297-327, 2018.
  
  

• Joint work with Junhao Gan.
  **Dynamic Density Based Clustering.
  Proceedings of ACM Conference on Management of Data (SIGMOD), pages 1493-1507, 2017.
  
  
• Joint work with Xiao Hu and Ke Yi.
  **Output-Optimal Parallel Algorithms for Similarity Joins.
  Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), pages 79-90, 2017.
  Long version
  
  
• Joint work with Junhao Gan.
  **On the Hardness and Approximation of Euclidean DBSCAN.
  ACM Transactions on Database Systems (TODS), 42(3), 2017.
  (Special issue of SIGMOD'15).
  The homepage of approximate DBSCAN
  
  
• Yufei Tao, Xiaocheng Hu, and Miao Qiao.
  Stream Sampling over Windows with Worst-Case Optimality and l-Overlap Independence.
  Very Large Data Base Journal (VLDBJ), 26(4): 493-510, 2017.
  
  

• Miao Qiao, Junhao Gan, and Yufei Tao.
  Range Thresholding on Streams.
  Proceedings of ACM Conference on Management of Data (SIGMOD), pages 571-582, 2016.
  
  
• Joint work with Saladi Rahul.
  **Efficient Top-k Indexing via General Reductions.
  Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), pages 277-288, 2016.
  See the long version for improved results and enhanced presentation.
  
  
• Joint work with Xiaocheng Hu and Miao Qiao.
  **I/O-Efficient Join Dependency Testing, Loomis-Whitney Join, and Triangle Enumeration.
  Journal of Computer and System Sciences (JCSS), 82(8): 1300-1315, 2016.
  
  
• Feifei Li, Ke Yi, Yufei Tao, Bin Yao, Yang Li, Dong Xie, and Min Wang.
  Exact and Approximate Flexible Aggregate Similarity Search.
  Very Large Data Base Journal (VLDBJ), 25(3): 317-338, 2016.

• Joint work with Junhao Gan.
  **DBSCAN Revisited: Mis-Claim, Un-Fixability, and Approximation.
  Proceedings of ACM Conference on Management of Data (SIGMOD), pages 519-530, 2015.
  (Winner of the Best Paper Award)
  Long Version
  The homepage of approximate DBSCAN
  
  
• Mingwang Tang, Feifei Li, and Yufei Tao.
  Distributed Online Tracking.
  Proceedings of ACM Conference on Management of Data (SIGMOD), pages 2047-2061, 2015.
  
  
• Joint work with Xiaocheng Hu and Miao Qiao.
  **Join Dependency Testing, Loomis-Whitney Join, and Triangle Enumeration.
  Proceedings of the 34th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), pages 291-301, 2015.
  Long version (with similified analysis, improved presentation, and a lower bound remark)
  
  
• Joint work with Xiaocheng Hu and Miao Qiao.
  **External Memory Stream Sampling.
  Proceedings of the 34th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), pages 229-239, 2015.
  
  
• Joint work with Saladi Rahul.
  **On Top-k Range Reporting in 2D Space.
  Proceedings of the 34th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), pages 265-275, 2015.
  
  
• Joint work with Xiaocheng Hu, Yi Yang, Shengyu Zhang, and Shuigeng Zhou.
  **The I/O Complexity of Dynamic Distinct Counting.
  Proceedings of the 18th International Conference on Database Theory (ICDT), pages 265-276, 2015.
  
  
• Wei Cao, Jian Li, Yufei Tao, and Zhize Li.
  On Top-k Selection in Multi-Armed Bandits and Hidden Bipartite Graphs.
  Proceedings of the 29th Annual Conference on Neural Information Processing Systems (NIPS), 2015.
  

• Joint work with Xiaocheng Hu, Yi Yang, and Shuigeng Zhou.
  **Finding Approximate Partitions and Splitters in External Memory.
  Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 287-295, 2014.
  
  
• Yufei Tao.
  A Dynamic I/O-Efficient Structure for One-Dimensional Top-k Range Reporting.
  Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS), pages 256-265, 2014.
  Long version
  
  
• Joint work with Xiaocheng Hu and Miao Qiao.
  **Independent Range Sampling.
  Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS), pages 246-255, 2014.
  
  
• Joint work with Peyman Afshani, Cheng Sheng, and Bryan T. Wilkinson.
  **Concurrent Range Reporting in Two-Dimensional Space.
  Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 983-994, 2014.
  
  
• Yufei Tao.
  Dynamic Ray Stabbing.
  ACM Transactions on Algorithms, 11(2), 2014.
  
  
• Yufei Tao and Cheng Sheng.
  I/O-Efficient Bundled Range Aggregation.
  IEEE Transactions on Knowledge and Data Engineering (TKDE), 26(6): 1521-1531, 2014.
  
  
• Yufei Tao, Cheng Sheng, Chin-Wan Chung, and Jong-Ryul Lee.
  Range Aggregation with Set Selection.
  IEEE Transactions on Knowledge and Data Engineering (TKDE), 26(5): 1240-1252, 2014.
  
  
• Yufei Tao and Cheng Sheng.
  Fast Nearest Neighbor Search with Keywords.
  IEEE Transactions on Knowledge and Data Engineering (TKDE), 26(4): 878-888, 2014.
  
  
• Yufei Tao, Yi Yang, Xiaocheng Hu, Cheng Sheng, and Shuigeng Zhou.
  Instance Level Worst-Case Query Bounds on R-trees.
  Very Large Data Base Journal (VLDBJ), 23(4): 591-607, 2014.
  
  
• Dong-Wan Choi, Chin-Wan Chung, and Yufei Tao.
  Maximizing Range Sum in External Memory.
  ACM Transactions on Databases Systems (TODS), 39(3), 2014.
  
  
• Xiaocheng Hu, Yufei Tao, and Chin-Wan Chung.
  I/O-Efficient Algorithms on Triangle Listing and Counting.
  ACM Transactions on Databases Systems (TODS), 39(4): 27, 2014.
  (Special issue of SIGMOD'13)
  
  

• Yufei Tao, Xiaocheng Hu, Dong-Wan Choi, and Chin-Wan Chung.
  Approximate MaxRS in Spatial Databases.
  Proceedings of the VLDB Endowment (PVLDB), 6(13): 1546-1557, 2013.
  
  
• Yufei Tao, Wenqing Lin, and Xiaokui Xiao.
  Minimal MapReduce Algorithms.
  Proceedings of ACM Conference on Management of Data (SIGMOD), pages 529-540, 2013.
  
  
• Xiaocheng Hu, Yufei Tao, and Chin-Wan Chung.
  Massive Graph Triangulation.
  Proceedings of ACM Conference on Management of Data (SIGMOD), pages 325-336, 2013.
  (Winner of the Best Paper Award)
  
  This program implements all the algorithms examined in the experiments of our paper.
  Click here for the program's manual.
  
  
• Wangchao Le, Feifei Li, Yufei Tao, and Robert Christensen.
  Optimal Splitters for Temporal and Multi-Version Databases.
  Proceedings of ACM Conference on Management of Data (SIGMOD), pages 109-120, 2013.
  
  
• Joint Work with Casper Kejlberg-Rasmussen, Konstantinos Tsakalidis, Kostas Tsichlas, and Jeonghun Yoon.
  **I/O-Efficient Planar Range Skyline and Attrition Priority Queues.
  Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS), pages 103-114, 2013.
  
  
• Joint Work with Xiaocheng Hu, Cheng Sheng, Yi Yang, and Shuigeng Zhou.
  **Output-Sensitive Skyline Algorithms in External Memory.
  Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 887-900, 2013.
  
  
• Bin Jiang, Jian Pei, Yufei Tao, and Xuemin Lin.
  Clustering Uncertain Data Based on Probability Distribution Similarity.
  IEEE Transactions on Knowledge and Data Engineering (TKDE), 25(4): 751-763, 2013.
  
  

• Dong-Wan Choi, Chin-Wan Chung, and Yufei Tao.
  A Scalable Algorithm for Maximizing Range Sum in Spatial Databases.
  Proceedings of the VLDB Endowment (PVLDB), 5(11): 1088-1099, 2012.
  Long version
  
  
• Cheng Sheng, Nan Zhang, Yufei Tao, and Xin Jin.
  Optimal Algorithms for Crawling a Hidden Database in the Web.
  Proceedings of the VLDB Endowment (PVLDB), 5(11): 1112-1123, 2012.
  
  
• Yufei Tao.
  Stabbing Horizontal Segments with Vertical Rays.
  Proceedings of the 28th Symposium on Computational Geometry (SoCG), pages 313-322, 2012.
  Long version
  
  
• Yufei Tao.
  Indexability of 2D Orthogonal Range Search Revisited: Constant Redundancy and Weak Indivisibility.
  Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS), pages 131-142, 2012.
  Long version
  
  
• Joint Work with Cheng Sheng.
  **Dynamic Top-K Range Reporting in External Memory.
  Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS), pages 121-130, 2012.
  
  
• Joint Work with Cheng Sheng.
  **Worst-case I/O-efficient Skyline Algorithms.
  ACM Transactions on Databases Systems (TODS), 37(4), 2012.
  (Special Issue of PODS'11)
  
  
• Cheng Sheng, Yufei Tao, and Jianzhong Li.
  Exact and Approximate Algorithms for the Most Connected Vertex Problem.
  ACM Transactions on Databases Systems (TODS), 37(2), 2012.
  
  

• Yufei Tao, Cheng Sheng, and Jian Pei.
  On k-Skip Shortest Paths.
  Proceedings of ACM Conference on Management of Data (SIGMOD), pages 421-432, 2011.
  Erratum
  
  
• Yufei Tao, Stavros Papadopoulos, Cheng Sheng, and Kostas Stefanidis.
  Nearest Keyword Search in XML Documents.
  Proceedings of ACM Conference on Management of Data (SIGMOD), pages 589-600, 2011.
  
  
• Joint Work with Cheng Sheng.
  **On Finding Skylines in External Memory.
  Proceedings of the 30th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS), pages 107-116, 2011.
  Long version
  
  
• Joint Work with Cheng Sheng.
  **FIFO Indexes for Decomposable Problems.
  Proceedings of the 30th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS), pages 25-35, 2011.
  
  
• Joint Work with Cheng Sheng.
  **New Results on Two-dimensional Orthogonal Range Aggregation in External Memory.
  Proceedings of the 30th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS), pages 129-139, 2011.
  
  
• Gabriel Ghinita, Panos Kalnis, and Yufei Tao.
  Anonymous Publication of Sensitive Transactional Data.
  IEEE Transactions on Knowledge and Data Engineering (TKDE), 23(2): 161-174, 2011.
  
  

• Yufei Tao, Ke Yi, Cheng Sheng, Jian Pei, and Feifei Li.
  Logging Every Footstep: Quantile Summaries for the Entire History.
  Proceedings of ACM Conference on Management of Data (SIGMOD), pages 639-650, 2010.
  A modified version covering also small M/H in the lower bound proof.
  
  
• Yufei Tao, Cheng Sheng, and Jianzhong Li.
  Finding Maximum Degrees in Hidden Bipartite Graphs.
  Proceedings of ACM Conference on Management of Data (SIGMOD), pages 891-902, 2010.
  Long version
  
  
• Xiaokui Xiao, Ke Yi, and Yufei Tao.
  The Hardness and Approximation Algorithms for l-diversity.
  Proceedings of the 13th conference on Extending Data Base Technology (EDBT), pages 135-146, 2010.
  
  
• 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 Databases Systems (TODS), 35(3), 2010.
  
  
• Xiaokui Xiao, Yufei Tao, and Nick Koudas.
  Transparent Anonymization: Thwarting Adversaries Who Know the Algorithm.
  ACM Transactions on Databases Systems (TODS), 35(2), 2010.
  
  
• Sze Man Yuen, Yufei Tao, Xiaokui Xiao, Jian Pei, and Donghui Zhang.
  Superseding Nearest Neighbor Search on Uncertain Spatial Databases.
  IEEE Transactions on Knowledge and Data Engineering (TKDE), 22(7): 1041-1055, 2010.
  
  

• Yufei Tao, Ke Yi, Cheng Sheng, and Panos Kalnis.
  Quality and Efficiency in High Dimensional Nearest Neighbor Search.
  Proceedings of ACM Conference on Management of Data (SIGMOD), pages 563-576, 2009.
  Long version
  
  
• Xiaokui Xiao, Yufei Tao, and Minghua Chen.
  Optimal Random Perturbation at Multiple Privacy Levels.
  Proceedings of the VLDB Endowment (PVLDB), 2(1): 814-825, 2009.
  
  
• Joint Work with Agarwal K. Pankaj, Siu-Wing Cheng, and Ke Yi.
  **Indexing Uncertain Data.
  Proceedings of the 28th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS), pages 137-146, 2009.
  
  
• Yufei Tao, Ling Ding, Xuemin Lin, and Jian Pei.
  Distance-Based Representative Skyline.
  Proceedings of the 25th IEEE International Conference on Data Engineering (ICDE), pages 892-903, 2009.
  The long version (faster algorithms and stronger geometric results).
  
  
• Xiaobing Wu, Yufei Tao, Raymond Chi-Wing Wong, Ling Ding, and Jeffrey Xu Yu.
  Finding the Influence Set through Skylines.
  Proceedings of 12th International Conference on Extending Database Technology (EDBT), pages 1030-1041, 2009.
  
  
• Yufei Tao, Hekang Chen, Xiaokui Xiao, Shuigeng Zhou, and Donghui Zhang.
  ANGEL: Enhancing the Utility of Generalization for Privacy Preserving Publication.
  IEEE Transactions on Knowledge and Data Engineering (TKDE), 21(7): 1073-1087, 2009.
  
  

• Xiaokui Xiao and Yufei Tao.
  Dynamic Anonymization: Accurate Statistical Analysis with Privacy Preservation.
  Proceedings of ACM Conference on Management of Data (SIGMOD), pages 107-120, 2008.
  
  
• Jiexing Li, Yufei Tao, and Xiaokui Xiao.
  Preservation of Proximity Privacy in Publishing Numerical Sensitive Data.
  Proceedings of ACM Conference on Management of Data (SIGMOD), pages 437-486, 2008.
  
  
• Xiaokui Xiao and Yufei Tao.
  Output Perturbation with Query Relaxation.
  Proceedings of the VLDB Endowment (PVLDB), 1(1): 857-868, 2008.
  
  
• Gabriel Ghinita, Yufei Tao, and Panos Kalnis.
  On the Anonymization of Sparse High-Dimensional Data.
  Proceedings of the 24th IEEE International Conference on Data Engineering (ICDE), pages 715-724, 2008.
  
  
• Yufei Tao, Xiaokui Xiao, Jiexing Li, and Donghui Zhang.
  On Anti-Corruption Privacy Preserving Publication.
  Proceedings of the 24th IEEE International Conference on Data Engineering (ICDE), pages 725-734, 2008.
  
  
• Man Lung Yiu, Yufei Tao, and Nikos Mamoulis.
  The B^dual-Tree: Indexing Moving Objects by Space Filling Curves in the Dual Space.
  Very Large Data Base Journal (VLDBJ), 17(3): 379-400. 2008.
  
  
• Yufei Tao and Xiaokui Xiao.
  Primal or Dual: Which Promises Faster Spatiotemporal Search?
  Very Large Data Base Journal (VLDBJ), 17(5): 1253-1270, 2008.
  
  

• Xiaokui Xiao and Yufei Tao.
  m-Invariance: Towards Privacy Preserving Re-publication of Dynamic Datasets.
  Proceedings of ACM Conference on Management of Data (SIGMOD), pages 689-700, 2007.
  
  
• Raymond Chi-Wing Wong, Yufei Tao, Ada Wai-Chee Fu, and Xiaokui Xiao.
  On Efficient Spatial Matching.
  Proceedings of the 33rd Very Large Data Bases conference (VLDB), pages 579-590, 2007.
  
  
• Yufei Tao, Xiaokui Xiao, and Reynold Cheng.
  Range Search on Multidimensional Uncertain Data.
  ACM Transactions on Databases Systems (TODS), 32(3), 2007.
  
  
• Yufei Tao, Dimitris Papadias, Xiang Lian, and Xiaokui Xiao.
  Multi-dimensional Reverse kNN Search.
  Very Large Data Base Journal (VLDBJ), 16(3): 293-316, 2007.
  (Special Issue of VLDB'04)
  
  
• Yufei Tao, Xiang Lian, Dimitris Papadias, and Marios Hadjieleftheriou.
  Random Sampling for Continuous Streams with Arbitrary Updates.
  IEEE Transactions on Knowledge and Data Engineering (TKDE), 19(1): 96-110, 2007.
  
  
• Yufei Tao, Xiaokui Xiao, and Jian Pei.
  Efficient Skyline and Top-k Retrieval in Subspaces.
  IEEE Transactions on Knowledge and Data Engineering (TKDE), 19(8): 1072-1088, 2007.
  
  

• Xiaokui Xiao and Yufei Tao.
  Personalized Privacy Preservation.
  Proceedings of ACM Conference on Management of Data (SIGMOD), pages 229-240, 2006.
  
  
• Xiaokui Xiao and Yufei Tao.
  Anatomy: Simple and Effective Privacy Preservation.
  Proceedings of the 32nd Very Large Data Bases conference (VLDB), pages 139-150, 2006.
  
  
• Donghui Zhang, Yang Du, Tian Xia, and Yufei Tao.
  Progressive Computation of the Min-Dist Optimal-Location Query.
  Proceedings of the 32nd Very Large Data Bases conference (VLDB), pages 643-654, 2006.
  
  
• Yufei Tao, Xiaokui Xiao, and Shuigeng Zhou.
  Mining Distance-based Outliers from Large Databases in Any Metric Space.
  Proceedings of the 12th ACM International Conference On Knowledge Discovery and Data Mining (SIGKDD), pages 394-403, 2006.
  
  
• Jian Pei, Yidong Yuan, Xuemin Lin, Wen Jin, Martin Ester, Qing Liu, Wei Wang, Yufei Tao, Jeffrey Xu Yu, Qing Zhang.
  Towards multidimensional subspace skyline analysis.
  ACM Transactions on Database Systems (TODS) 31(4): 1335-1381, 2006.
  
  
• Yufei Tao, Xiaokui Xiao, and Jian Pei.
  SUBSKY: Efficient Computation of Skylines in Subspaces.
  Proceedings of the 23rd IEEE International Conference on Data Engineering (ICDE), 2006.
  Long version
  
  
• Yufei Tao and Dimitris Papadias.
  Maintaining Sliding Window Skylines on Data Streams.
  IEEE Transactions on Knowledge and Data Engineering (TKDE), 18(2): 377-391, 2006.
  
  
• Yufei Tao, Man Lung Yiu, and Nikos Mamoulis.
  Reverse Nearest Neighbor Search in Metric Spaces.
  IEEE Transactions on Knowledge and Data Engineering (TKDE), 18(9): 1239-1252, 2006.
  
  

• Yufei Tao, Man Lung Yiu, Dimitris Papadias, Marios Hadjieleftheriou, and Nikos Mamoulis.
  RPJ: Producing Fast Join Results on Streams through Rate-based Optimization.
  Proceedings of ACM Conference on Management of Data (SIGMOD), pages 371-382, 2005.
  
  
• Yufei Tao, Reynold Cheng, Xiaokui Xiao, Wang Kay Ngai, Ben Kao, and Sunil Prabhakar.
  Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions.
  Proceedings of the 31st Very Large Data Bases conference (VLDB), pages 922-933, 2005.
  Long version
  
  
• Jian Pei, Wen Jin, Martin Ester, and Yufei Tao.
  Catching the Best Views of Skyline: A Semantic Approach Based on Decisive Subspaces.
  Proceedings of the 31st Very Large Data Bases conference (VLDB), pages 253-264, 2005.
  
  
• Yufei Tao, Dimitris Papadias, Jian Zhai, and Qing Li.
  Venn Sampling: A Novel Prediction Technique for Moving Objects.
  Proceedings of the 21st IEEE International Conference on Data Engineering (ICDE), pages 680-691, 2005.
  
  
• Dimitris Papadias, Yufei Tao, Fu Greg, and Bernhard Seeger.
  Progressive Skyline Computation in Database Systems.
  ACM Transactions on Databases Systems (TODS), 30(1): 41-82, 2005.
  (Special issue of SIGMOD'03)
  
  
• Dimitris Papadias, Yufei Tao, Kyriakos Mouratidis, and Chun Kit Hui.
  Aggregate Nearest Neighbor Queries in Spatial Databases.
  ACM Transactions on Databases Systems (TODS), 30(2), 529-576, 2005.
  
  
• Kyriakos Mouratidis, Dimitris Papadias, Spiridon Bakiras, and Yufei Tao.
  A Threshold-Based Algorithm for Continuous Monitoring of k Nearest Neighbors.
  IEEE Transactions on Knowledge and Data Engineering (TKDE), 17(11): 1451-1464, 2005.
  
  

• Yufei Tao, Christos Faloutsos, Dimitris Papadias, and Bin Liu.
  Prediction and Indexing of Moving Objects with Unknown Motion Patterns.
  Proceedings of ACM Conference on Management of Data (SIGMOD), pages 611-622, 2004.
  
  
• Yufei Tao, Dimitris Papadias, and Xiang Lian.
  Reverse kNN Search in Arbitrary Dimensionality.
  Proceedings of the 31st Very Large Data Bases conference (VLDB), pages 744-755, 2004.
  Long version
  
  
• Yufei Tao, George Kollios, Jeffrey Considine, Feifei Li, and Dimitris Papadias.
  Spatio-Temporal Aggregation Using Sketches.
  Proceedings of the 20th IEEE International Conference on Data Engineering (ICDE), pages 214-225, 2004.
  
  
• Jimeng Sun, Dimitris Papadias, Yufei Tao, and Bin Liu.
  Querying about the Past, the Present, and the Future in Spatio-Temporal.
  Proceedings of the 20th IEEE International Conference on Data Engineering (ICDE), pages 202-213, 2004.
  
  
• Nikos Mamoulis, Huiping Cao, George Kollios, Marios Hadjieleftheriou, Yufei Tao, and David W. Cheung.
  Mining, Indexing, and Querying Historical Spatiotemporal Data.
  Proceedings of the 10th ACM International Conference On Knowledge Discovery and Data Mining (SIGKDD), pages 236-245, 2004.
  
  
• Yufei Tao, Jun Zhang, Dimitris Papadias, and Nikos Mamoulis
  An Efficient Cost Model for Optimization of Nearest Neighbor Search in Low and Medium Dimensional Spaces.
  IEEE Transactions on Knowledge and Data Engineering (TKDE). 16(10): 1169-1184, 2004.
  
  
• Yufei Tao and Dimitris Papadias.
  Range Aggregate Processing in Spatial Databases.
  IEEE Transactions on Knowledge and Data Engineering (TKDE), 16(12): 1555-1570, 2004.
  
  

• Dimitris Papadias, Yufei Tao, Greg Fu, and Bernhard Seeger.
  An Optimal and Progressive Algorithm for Skyline Queries.
  Proceedings of ACM Conference on Management of Data (SIGMOD), pages 467-478, 2003.
  Long version
  
  
• Jun Zhang, Manli Zhu, Dimitris Papadias, Yufei Tao, and Dik Lun Lee.
  Location-based Spatial Queries.
  Proceedings of ACM Conference on Management of Data (SIGMOD), pages 443-454, 2003.
  
  
• Yufei Tao, Dimitris Papadias, and Jimeng Sun.
  The TPR*-Tree: An Optimized Spatio-Temporal Access Method for Predictive Queries.
  Proceedings of the 29th Very Large Data Bases conference (VLDB), pages 790-801, 2003.
  
  
• Dimitris Papadias, Jun Zhang, Nikos Mamoulis, and Yufei Tao.
  Query Processing in Spatial Network Databases.
  Proceedings of the 29th Very Large Data Bases conference (VLDB), pages 802-813, 2003.
  
  
• Yufei Tao, Jimeng Sun, and Dimitris Papadias.
  Selectivity Estimation for Predictive Spatio-Temporal Queries.
  Proceedings of the 20th IEEE International Conference on Data Engineering (ICDE), pages 417-428, 2003.
  Long version
  
  
• Yufei Tao and Dimitris Papadias.
  Spatial Queries in Dynamic Environments.
  ACM Transactions on Databases Systems (TODS), 28(2): 101-139, 2003.
  
  
• Yufei Tao, Jimeng Sun, and Dimitris Papadias.
  Analysis of Predictive Spatio-Temporal Queries.
  ACM Transactions on Databases Systems (TODS), 28(4): 295-336, 2003.
  
  

• Yufei Tao and Dimitris Papadias.
  Time-parameterized Queries in Spatio-temporal Databases.
  Proceedings of ACM Conference on Management of Data (SIGMOD), pages 334-345, 2002.
  Long version
  
  
• Yufei Tao, Dimitris Papadias, and Qiongmao Shen.
  Continuous Nearest Neighbor Search.
  Proceedings of the 28th Very Large Data Bases conference (VLDB), pages 287-298, 2002.
  Long version
  
  
• Yufei Tao and Dimitris Papadias.
  Adaptive Index Structures.
  Proceedings of the 28th Very Large Data Bases conference (VLDB), pages 418-429, 2002.
  
  
• Yufei Tao, Dimitris Papadias, and Jun Zhang.
  Cost Models for Overlapping and Multi-Version B-Trees.
  Proceedings of the 19th IEEE International Conference on Data Engineering (ICDE), pages 191-200, 2002.
  Long version
  
  
• Dimitris Papadias, Yufei Tao, Panos Kalnis, and Jun Zhang.
  Indexing Spatio-Temporal Data Warehouses.
  Proceedings of the 19th IEEE International Conference on Data Engineering (ICDE), pages 166-175, 2002.
  
  
• Yufei Tao, Dimitris Papadias, and Jun Zhang.
  Aggregate Processing of Planar Points.
  Proceedings of 8th International Conference on Extending Database Technology (EDBT), pages 682-700, 2002.
  Long version
  
  
• Yufei Tao, Dimitris Papadias, and Jun Zhang.
  Cost Models for Overlapping and Multi-Version Structures.
  ACM Transactions on Databases Systems (TODS), 27(3): 299-342, 2002.

• Yufei Tao and Dimitris Papadias.
  The MV3R-Tree: A Spatio-Temporal Access Method for Timestamp and Interval Queries.
  Proceedings of the 27th Very Large Data Bases conference (VLDB), pages 431-440, 2001.