[Home] [Publication] [Activities]

Papers

1. Quantum Data Sketches
   Q. Zhang and M. Heidari (by contribution)
   Proc. International Conference on Database Theory (ICDT 25), to appear. Barcelona, Spain, March 2025.
   
   • We propose succinct quantum data sketches to support basic database operations such as search and selection.
   • We view our work as an initial step towards the development of quantum data management model.

2. Computing Approximate Graph Edit Distance via Optimal Transport
   Q. Cheng, D. Yan, T. Wu, Z. Huang, and Q. Zhang (by contribution)
   Proc. ACM SIGMOD International Conference on Management of Data (SIGMOD 25), to appear. Berlin, Germany, June 2025.
   
   
3. Parallel Best Arm Identification in Heterogeneous Environments
   with N. Karpov
   Proc. ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 24), pages 53-64. Nantes, France, June 2024.
   
   • We have shown a separation between the homogeneous collaborative learning (CL) model and the heterogeneous CL model for adaptive algorithms .

4. Communication-Efficient Collaborative Regret Minimization in Multi-Armed Bandits
   with N. Karpov
   Proc. AAAI Conference on Artificial Intelligence (AAAI 24), pages 13076-13084. Vancouver, Canada. February 2024.
   
   
5. MinJoin++: A Fast Algorithm for String Similarity Joins under Edit Distance
   with N. Karpov and H. Zhang
   VLDB Journal. 33(2): 281-299 (2024)
   
   
6. Communication-Efficient Collaborative Best Arm Identification
   with N. Karpov
   Proc. AAAI Conference on Artificial Intelligence (AAAI 23), pages 8203-8210. Washington, D.C., USA. February 2023.
   
   
7. SyncSignature: A Simple, Efficient, Parallelizable Framework for Tree Similarity Joins.
   with N. Karpov
   Proc. VLDB Endow. 16(2): 330-342 (2022).
   
   
8. Meta Proximal Policy Optimization for Cooperative Multi-Agent Continuous Control
   B. Fang, Z. Peng, H. Sun, and Q. Zhang (by contribution)
   Proc. International Joint Conference on Neural Networks (IJCNN 22), pages 1-8. Padova, Italy, July 2022.
   
   
9. Technical perspective: Can data structures treat us fairly?
   Q. Zhang
   Communications of the ACM 65(8): 82, 2022.
   
   
10. Instance-Sensitive Algorithms for Pure Exploration in Multinomial Logit Bandit
    with N. Karpov
    Proc. AAAI Conference on Artificial Intelligence (AAAI 22), pages 7096-7103. Vancouver, February-March 2022.
    
    
11. Technical Perspective: Fair Near Neighbor Search via Sampling
    Q. Zhang
    SIGMOD Record 50(1): 41, 2021.
    
    
12. Learning to Cluster via Same-Cluster Queries
    with Y. Li and Y. Song
    Proc. ACM International Conference on Information and Knowledge Management (CIKM 21), pages 978-987. Virtual conference, November 2021.
    
    
13. Batched Coarse Ranking in Multi-Armed Bandits
    with N. Karpov
    Proc. Annual Conference on Neural Information Processing Systems (NeurIPS 20). Virtual conference, December 2020.
    
    
14. Collaborative Top Distribution Identifications with Limited Interaction (preliminary full version, 47 pages)
    with N. Karpov and Y. Zhou
    Proc. IEEE Symposium on Foundations of Computer Science (FOCS 20), pages 160-171. Virtual conference, November 2020.
    
    • We have shown a separation on the top-1 arm identification and top-k arm identifications in the collaborative learning model.

15. Multinomial Logit Bandit with Low Switching Cost (preliminary full version, 25 pages)
    with K. Dong, Y. Li, and Y. Zhou
    Proc. International Conference on Machine Learning (ICML 20), pages 2607-2615. Virtual conference, July 2020.
    
    
16. MinSearch: An Efficient Algorithm for Similarity Search under Edit Distance
    with H. Zhang
    Proc. ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD 20), pages 566-576. Virtual conference, August 2020.
    
    
17. A Multi-criteria Approximation Algorithm for Influence Maximization with Probabilistic Guarantees.
    with M. Khan, G. Pandurangan, N. D. Pham, and A. Vullikanti
    Proc. SIAM Symposium on Algorithm Engineering and Experiments (ALENEX 20), pages 81-93. Salt Lake City, UT, U.S.A., January 2020.
    
    
18. Collaborative Learning with Limited Interaction: Tight Bounds for Distributed Exploration in Multi-Armed Bandits (preliminary full version, 37 pages) [conf. talk]
    with C. Tao and Y. Zhou
    Proc. IEEE Symposium on Foundations of Computer Science (FOCS 19), pages 126-146. Baltimore, MD, U.S.A., November 2019.
    
    • We conduct a systematic study of the best arm identification problem in the setting of collaborative learning with limited interaction.
    • We obtain almost tight round-speedup tradeoffs for both fixed-time and fixed-confidence settings, and show a complexity separation for the two variants.
    • We develop two new techniques for proving round lower bounds for multi-agent collaborative learning.

19. MinJoin: Efficient Edit Similarity Joins via Local Hash Minima
    with H. Zhang
    Proc. ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD 19), oral presentation, pages 1093-1103. Anchorage, AK, U.S.A., August 2019.
    
    
20. Distributed and Streaming Linear Programming in Low Dimensions
    with S. Assadi and N. Karpov
    Proc. ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 19), pages 236-253. Amsterdam, The Netherlands, June-July 2019.
    Invited to the special issue for PODS 2019 in ACM Transactions on Database Systems (TODS).
    
    
21. Tight Bounds for Collaborative PAC Learning via Multiplicative Weights
    with J. Chen and Y. Zhou
    Proc. Annual Conference on Neural Information Processing Systems (NeurIPS 18), pages 3602-3611. Montreal, Canada, December 2018.
    
    
22. A Practical Algorithm for Distributed Clustering and Outlier Detection
    with J. Chen and E. Sadeqi-Azer
    Proc. Annual Conference on Neural Information Processing Systems (NeurIPS 18), pages 2253-2262. Montreal, Canada, December 2018.
    
    
23. Smooth q-Gram, and Its Applications to Detection of Overlaps among Long, Error-Prone Sequencing Reads
    H. Zhang, Q. Zhang and H. Tang   (by contribution)
    Proc. ACM International Conference on Information and Knowledge Management (CIKM 18), pages 267-276. Turin, Italy, October 2018.
    Journal version (together with Y. Song) in Bioinformatics
    under the title "Overlap Detection on Long, Error-Prone Sequencing Reads via Smooth q-Gram". [Link]
    
    
24. Distinct Sampling on Streaming Data with Near-Duplicates
    with J. Chen
    Proc. ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 18), pages 369-382. Houston, TX, U.S.A., June 2018.
    
    
25. Distributed Statistical Estimation of Matrix Products with Applications [conf. talk]
    with D. P. Woodruff
    Proc. ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 18), pages 383-394. Houston, TX, U.S.A., June 2018.
    
    
26. Communication-Efficient Distributed Skyline Computation
    with H. Zhang
    Proc. ACM International Conference on Information and Knowledge Management (CIKM 17), pages 437-446. Singapore, November 2017.
    
    
27. A Concise Forwarding Information Base for Scalable and Fast Name Switching
    Y. Yu, D. Belazzougui, C. Qian and Q. Zhang   (by contribution)
    Proc. IEEE International Conference on Network Protocols (ICNP 17), to appear. Toronto, Canada, October 2017.
    Journal version in IEEE/ACM Transactions on Networking (TON)
    under the title "Memory-efficient and Ultra-fast Network Lookup and Forwarding using Othello Hashing", 26(3): 1151-1164 (2018). [Link].
    
    
28. EmbedJoin: Efficient Edit Similarity Joins via Embeddings
    with H. Zhang
    Proc. ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD 17), oral presentation, pages 585-594. Halifax, Nova Scotia, Canada, August 2017.
    
    
29. Adaptive Multiple-Arm Identification (preliminary full version, 30 pages)
    with J. Chen, X. Chen and Y. Zhou
    Proc. International Conference on Machine Learning (ICML 17), pages 722-730. Sydney, Australia, August 2017.
    
    
30. Distributed Partial Clustering (preliminary full version, 20 pages) [conf. talk]
    with S. Guha and Y. Li
    Proc. ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 17), pages 143-152. Washington D.C., U.S.A., July 2017.
    Best Paper Award
    Invited to special issue for SPAA 2017 papers in ACM Transactions on Parallel Computing (TOPC). [Link].
    • We give the first systematic study of communication/round-efficient distributed partial clustering, by providing almost tight bounds for partial k-center, k-median, and k-means in both deterministic and stochastic settings.
    • As a byproduct, we develop the first algorithms for the partial k-median and k-means objectives that run in subquadratic time.

31. Bias-Aware Sketches
    with J. Chen
    Proc. International Conference on Very Large Databases (VLDB 17), pages 961-972. Munich, Germany, August-September 2017.
    
    
32. Improved Algorithms for Distributed Entropy Monitoring
    with J. Chen
    Algorithmica (Algorithmica), volume 78, issue 3, pages 1041-1066, July 2017.
    
    
33. Submodular Maximization over Sliding Windows
    with J. Chen and H. L. Nguyen
    Manuscript, 2016.
    
    
34. Communication-Optimal Distributed Clustering
    with J. Chen, H. Sun and D. Woodruff
    Proc. Annual Conference on Neural Information Processing Systems (NIPS 16), pages 3720-3728. Barcelona, Spain, December 2016.
    
    
35. Edit Distance: Sketching, Streaming and Document Exchange (preliminary full version, 30 pages) [conf. talk]
    with D. Belazzougui
    Proc. IEEE Symposium on Foundations of Computer Science (FOCS 16), pages 51-60. New Brunswick, NJ, U.S.A., October 2016.
    
    • We achieve nearly optimal communication with almost linear time recovery for document exchange.
    • We obtain the first exact sketching and streaming algorithms for edit distance with sublinear size/space under small distance thresholds.
    • Our technique of aligning strings using multiple random walks may be of independent interest.

36. Streaming Algorithms for Robust Distinct Elements
    with D. Chen
    Proc. ACM SIGMOD International Conference on Management of Data (SIGMOD 16), pages 1433-1447. San Francisco, CA, U.S.A., June 2016.
    
    • We initiate the study of processing noisy datasets in the data steam model.

37. On Sketching Quadratic Forms (preliminary full version, 47 pages)
    with A. Andoni, J. Chen, R. Krauthgamer, B. Qin and D. P. Woodruff
    Proc. Innovations in Theoretical Computer Science (ITCS 16), pages 311-319. Cambridge, MA, U.S.A., January 2016.
    
    • We undertake a systematic study of sketching a quadratic form.
    • Our results provide the first separation between the sketch size needed for the "for all" and "for each" guarantees for Laplacian matrices.

38. Communication-Efficient Computation on Distributed Noisy Datasets [conf. talk]
    Q. Zhang
    Proc. ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 15), pages 313-322. Portland, Oregon, U.S.A., June 2015.
    
    • We give a first theoretical investigation to the general question: How can we process distributed noisy datasets communication-efficiently?.

39. The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication
    with D. Van Gucht, R. Williams and D. P. Woodruff
    Proc. ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 15), pages 199-212. Melbourne, VIC, Australia, May-June 2015.
    
    • We settle the communication complexity of a set of basic distributed set-join operations.
    • Our new algorithmic techniques also lead to an improved algorithm for computing transitive closure of a directed graph in terms of running time.

40. Communication Complexity of Approximate Matching in Distributed Graphs
    with Z. Huang, B. Radunovic and M. Vojnovic
    Proc. Symposium on Theoretical Aspects of Computer Science (STACS 15), pages 460-473. Munich, Germany, March 2015.
    
    
41. Robust Set Reconciliation
    with D. Chen, C. Konrad, K. Yi and W. Yu
    Proc. ACM SIGMOD International Conference on Management of Data (SIGMOD 14), pages 135-146. Snowbird, UT, U.S.A., June 2014.
    See an earlier version of this paper for the lower bound proofs.
    
    
42. An Optimal Lower Bound for Distinct Elements in the Message Passing Model
    with D. P. Woodruff
    Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA 14), pages 718-733. Portland, OR, U.S.A., January 2014.
    
    
43. When Distributed Computation is Communication Expensive (preliminary full version) [talk]
    with D. P. Woodruff
    Proc. International Symposium on Distributed Computing (DISC 13), pages 16-30. Jerusalem, Israel, October 2013.
    Invited to the special issue for DISC 2013 in Distributed Computing , volume 30, issue 5, pages 309-323, October 2017. [Link].
    
    
44. Subspace Embeddings and Lp Regression Using Exponential Random Variables (preliminary full version, 27 pages) [conf. talk]
    with D. P. Woodruff
    Proc. Conference on Learning Theory (COLT 13), pages 546-567. Princeton, NJ, U.S.A., June 2013.
    
    • We propose a unified algorithmic framework that improves the running time of Lp-regression for all p = [1, ∞)\2.

45. Parikh Matching in the Streaming Model
    with L. K. Lee and M. Lewenstein
    Proc. International Symposium on String Processing and Information Retrieval (SPIRE 12), pages 336-341. Cartagena de Indias, Colombia, October 2012.
    
    
46. Rademacher-Sketch: A Dimensionality-Reducing Embedding for Sum-Product Norms, with an Application to Earth-Mover Distance [talk]
    with E. Verbin
    Proc. International Colloquium on Automata, Languages and Programming (ICALP 12), pages 834-845. Warwick, U.K., July 2012.
    
    
47. Randomized Algorithms for Tracking Distributed Count, Frequencies, and Ranks
    with Z. Huang and K. Yi
    Proc. ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 12), pages 295-306. Scottsdale, Arizona, U.S.A., May 2012.
    Journal version in Algorithmica (Algorithmica). [Link].
    
    
48. Tight Bounds for Distributed Functional Monitoring (preliminary full version, 50 pages) [conf. talk]
    with D. P. Woodruff
    Proc. ACM Symposium on Theory of Computing (STOC 12), pages 941-960. New York, NY, U.S.A., May 2012.
    
    • We resolve several fundamental questions in the area of distributed functional monitoring (a.k.a. distributed streaming).
    • Surprisingly, the total communication required to keep monitoring a function is often similar to the corresponding one-shot computation!
    • A new technique called "composition" is proposed for randomized multiparty communication complexity.

49. Lower Bounds for Number-in-Hand Multiparty Communication Complexity, Made Easy (preliminary full version, 22 pages) [conf. talk]
    with J. M. Phillips, E. Verbin
    Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA 12), pages 486-501. Kyoto, Japan, January 2012.
    Journal version in SIAM Journal of Computing (SICOMP), volume 45, issue 1, pages 174-196, February 2016 [Link].
    • A new technique called "symmetrization" is proposed for randomized multiparty communication complexity.

50. Sorting, Searching and Simulation in the MapReduce Framework
    with M. T. Goodrich and N. Sitchinava
    Proc. International Symposium on Algorithms and Computation (ISAAC 11), pages 374-383. Yokohama, Japan, December 2011.
    Preliminary version in arXiv.
    
    
51. Edit Distance to Monotonicity in Sliding Windows
    with H. L. Chan, T. W. Lam, L. K. Lee, J. Pan and H. F. Ting
    Proc. International Symposium on Algorithms and Computation (ISAAC 11), pages 564-573. Yokohama, Japan, December 2011.
    
    
52. Clustering with Diversity [talk]
    with J. Li and K. Yi
    Proc. International Colloquium on Automata, Languages and Programming (ICALP 10), pages 188-200. Bordeaux, France, July 2010.
    
    
53. Cache-Oblivious Hashing
    with R. Pagh, Z. Wei and K. Yi
    Proc. ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 10), pages 297-304. Indianapolis, IN, U.S.A., June 2010.
    Journal version in Algorithmica (Algorithmica), volume 69, issue 4, pages 864-883, August 2014.
    
    
54. Optimal Sampling From Distributed Streams (preliminary full version, 25 pages) [talk]
    with G. Cormode, S. Muthukrishnan and K. Yi
    Proc. ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 10), pages 77-86. Indianapolis, IN, U.S.A., June 2010.
    Invited to Journal of the ACM (JACM), volume 59, issue 2, pages 10:1-10:25, April 2012 [Link].
    • In the distributed streaming model, random sampling is even easier than counting.

55. The Limits of Buffering: A Tight Lower Bound for Dynamic Membership in the External Memory Model (preliminary full version, 18 pages) [talk]
    with E. Verbin
    Proc. ACM Symposium on Theory of Computing (STOC 10), pages 447-456. Cambridge, MA, U.S.A., June 2010.
    Journal version in SIAM Journal of Computing (SICOMP), volume 42, issue 1, pages 212-229, January 2013 [Link].
    • We resolve several fundamental problems in the area of external memory data structures.
    • For many basic problems, buffering is impossible to achieve in the external memory model with sublogarithmic query time.
    • The external memory model is clearner than the RAM model in certain perspectives.

56. On the Cell Probe Complexity of Dynamic Membership [conf. talk]
    with K. Yi
    Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA 10), pages 123-133. Austin, TX, U.S.A., January 2010.
    
    
57. Dynamic External Hashing: The Limit of Buffering [conf. talk]
    with Z. Wei and K. Yi
    Proc. ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 09), pages 253-259. Calgary, Canada, August 2009.
    
    
58. Optimal Tracking of Distributed Heavy Hitters and Quantiles (preliminary full version) [conf. talk]
    with K. Yi
    Proc. ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 09), pages 167-174. Providence, RI, U.S.A., June 2009.
    Journal version in Algorithmica (Algorithmica), volume 65, issue 1, pages 206-223, January 2013 [Link].
    
    
59. Multi-Dimensional Online Tracking (preliminary full version, 18 pages) [conf. talk]
    with K. Yi
    Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA 09), pages 1098-1107. New York, NY, U.S.A., January 2009.
    Journal version in ACM Transactions on Algorithms (TALG), volume 8, issue 2, pages 12:1-12:16, April 2012 [Link].
    • A new and very natural class of online problems is studied.

60. Revenue Generation for Truthful Spectrum Auction in Dynamic Spectrum Access
    J. Jia, Q. Zhang, Q. Zhang and M. Liu   (by contribution)
    Proc. ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc 09), pages 3-12. New Orleans, LA, U.S.A., May 2009.
    
    
61. Finding Frequent Items in Probabilistic Data [conf. talk]
    Q. Zhang, F. Li and K. Yi   (by contribution)
    Proc. ACM SIGMOD International Conference on Management of Data (SIGMOD 08), pages 819-832. Vancouver, Canada, June 2008.