My Favorite Publications

Remember the notational conventions: (i) in publications marked with '**', authors are ordered alphabetically, as is a convention of theory papers; and (ii) in the other publications, authors are ordered by contribution.

Back to my home or publication page.

1. 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.
   
   
2. Joint work with Ke Yi.
   **Intersection Joins under Updates.
   Journal of Computer and System Sciences (JCSS), 124: 41-64, 2022.
   
   
3. 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.
   
   
4. Yufei Tao.
   A Simple Parallel Algorithm for Natural Joins on Binary Relations.
   Proceedings of the 23rd International Conference on Database Theory (ICDT), 25:1-25:18, 2020.
   See the long version for improved results and enhanced presentation.
   
   
5. 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.
   
   
6. Yufei Tao.
   Entity Matching with Active Monotone Classification.
   Proceedings of the 37th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS), pages 49-62, 2018.
   (Winner of the Best Paper Award)
   
   
7. 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.
   
   
8. 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.
   
   
9. Joint work with Junhao Gan.
   **On the Hardness and Approximation of Euclidean DBSCAN.
   ACM Transactions on Database Systems (TODS), 42(3), 2017.
   Short version in SIGMOD'15 (best-paper award winner).
   The homepage of approximate DBSCAN
   
   
10. Joint work with Junhao Gan.
    **Dynamic Density Based Clustering.
    Proceedings of ACM Conference on Management of Data (SIGMOD), pages 1493-1507, 2017.
    
    
11. Miao Qiao, Junhao Gan, and Yufei Tao.
    Range Thresholding on Streams.
    Proceedings of ACM Conference on Management of Data (SIGMOD), pages 571-582, 2016.
    
    
12. Joint work with Saladi Rahul.
    **Efficient Top-k Indexing via General Reductions.
    Proceedings of the 35th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS), pages 277-288, 2016.
    See the long version for improved results and enhanced presentation.
    
    
13. 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.
    Short version in PODS'15.
    
    
14. 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.
    
    
15. Yufei Tao.
    Dynamic Ray Stabbing.
    ACM Transactions on Algorithms, 11(2), 2014.
    Short version in SoCG'12.
    
    
16. 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.
    
    
17. Yufei Tao, Wenqing Lin, and Xiaokui Xiao.
    Minimal MapReduce Algorithms.
    Proceedings of ACM Conference on Management of Data (SIGMOD), pages 529-540, 2013.
    
    
18. 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.
    
    
19. 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
    
    
20. Joint Work with Cheng Sheng.
    **Worst-case I/O-efficient Skyline Algorithms.
    ACM Transactions on Databases Systems (TODS), 37(4), 2012.
    Short version in PODS'11.
    
    
21. 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.
    Short version in SIGMOD'10.
    
    
22. 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.
    
    
23. 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.
    
    
24. 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.
    
    
25. 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.
    Short version in SIGMOD'09.
    
    
26. Xiaokui Xiao, Yufei Tao, and Nick Koudas.
    Transparent Anonymization: Thwarting Adversaries Who Know the Algorithm.
    ACM Transactions on Databases Systems (TODS), 35(2), 2010.
    
    
27. 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.
    
    
28. Yufei Tao, Xiaokui Xiao, and Reynold Cheng.
    Range Search on Multidimensional Uncertain Data.
    ACM Transactions on Databases Systems (TODS), 32(3), 2007.
    Short version in VLDB'05.
    
    
29. 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.
    
    
30. 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.
    Short version in SIGMOD'03.
    
    
31. 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.
    
    
32. 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.
    
    
33. 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.
    
    
34. 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.
    
    
35. Yufei Tao and Dimitris Papadias.
    Spatial Queries in Dynamic Environments.
    ACM Transactions on Databases Systems (TODS), 28(2): 101-139, 2003.
    Short versions in SIGMOD'02 and VLDB'02.
    
    
36. 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.
    Short version in ICDE'02.