Qin Zhang

Assistant Professor

Computer Science Department,
Indiana University Bloomington,
Lindley Hall, 428B, 150 S. Woodlawn Ave.,
Bloomington, IN 47405, USA

Email: qzhangcs@indiana.edu

Before joining IU, I spent a couple of great years at Theory Group, IBM Almaden Research Center,
      and Center for Massive Data Algorithmics, Aarhus University.
I obtained my PhD at Department of Computer Science and Engineering, HKUST.

[Home] [Publication] [Activities]

Papers

Note: In all papers, except mentioned otherwise, authors are ordered alphabetically.
  1. Distributed Statistical Estimation of Matrix Products with Applications
    with D. P. Woodruff
    Proc. ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 18), to appear. Houston, TX, U.S.A., June 2018.

  2. 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.

  3. 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.

  4. 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.

  5. 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.

  6. Distributed Partial Clustering (preliminary full version, 19 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)

  7. Bias-Aware Sketches
    with J. Chen
    Proc. International Conference on Very Large Databases (VLDB 17), pages 961-972. Munich, Germany, August-September 2017.

  8. Improved Algorithms for Distributed Entropy Monitoring
    with J. Chen
    Algorithmica (Algorithmica), volume 78, issue 3, pages 1041-1066, July 2017.

  9. Submodular Maximization over Sliding Windows
    with J. Chen and H. L. Nguyen
    Manuscript, 2016.

  10. 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.

  11. 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.

  12. 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.

  13. 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.

  14. 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.

  15. 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.

  16. 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.

  17. 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.

  18. 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.

  19. 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].

  20. 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.

  21. 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.

  22. 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.

  23. 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.

  24. 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.

  25. 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].

  26. 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.

  27. 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.

  28. 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.

  29. 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.

  30. 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].

  31. 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].

  32. 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.

  33. 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.

  34. 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].

  35. 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].

  36. 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.

  37. 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.