CS 632: Advanced DBMS

Suraj Shetiya

Spring 2026  

Grading Scheme

Anyone who does an exceptional course project that has the potential to be a publishable paper is eligible for a straight AA grade. Otherwise the grading breakup would be midsem 25, endsem 40, project 20 and assignments plus seminar presentation 15 (the breakup of these will depend on whether we have individual or joint seminars, which depends on the final enrollment).

Assignments

To be decided.

Project

The project is mandatorily an implementation oriented project. You may still need to do some literature survey to figure out your project though. Projects should be done in groups of 2. A basic project will take any of the papers we study in the course, or other related papers, and implement the algorithms in the paper, and do a very basic performance study. However, I would expect most projects to improve upon existing techniques. A more advanced project would take a problem specification for which no solution is publicly available, figure out how to solve it, and implement the solution.

Project List To be decided

Resources

Textbook (for background material only): Database System Concepts, 7th Ed. Avi Silberschatz, Hank Korth, and S. Sudarshan. McGraw Hill, 2020. (book home page)

List of papers

NOTE: The list of topics below is subject to change during the semester, especially those later in the semester

Vector Databases

• Yang, M., Li, W., & Wang, W. (2024). Quantization Meets Projection: A Happy Marriage for Approximate k-Nearest Neighbor Search. Proceedings of the VLDB Endowment.
• Chen, P.H., Chang, W., Yu, H., Dhillon, I.S., & Hsieh, C. (2022). FINGER: Fast Inference for Graph-based Approximate Nearest Neighbor Search. Proceedings of the ACM Web Conference 2023.
• Gionis, A., Indyk, P., & Motwani, R. (1999). Similarity Search in High Dimensions via Hashing. Very Large Data Bases Conference.
• Li, B., Yan, X., & Lu, S. (2025). Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search. Proceedings of the ACM on Management of Data, 4, 1 - 24.
• Subramanya, S.J., Devvrit, Kadekodi, R., Krishaswamy, R., & Simhadri, H.V. (2019). DiskANN : Fast Accurate Billion-point Nearest Neighbor Search on a Single Node.
• Durrant, R.J., Kabán, A., & Durrant, R.J. (2009). When Is ‘ Nearest Neighbor ’ Meaningful : A Converse Theorem and Implications.
• Lu, S., & Tao, Y. (2025). Proximity Graphs for Similarity Search: Fast Construction, Lower Bounds, and Euclidean Separation. Proceedings of the ACM on Management of Data, 3, 1 - 25.
• Hua, Z., Mo, Q., Yao, Z., Cui, L., Liu, X., Wang, G., Wei, Z., Liu, X., Tang, T., Liu, S., & Qu, L. (2025). Dynamically Detect and Fix Hardness for Efficient Approximate Nearest Neighbor Search. Proceedings of the ACM on Management of Data, 3, 1 - 28.
• Tellez, E.S., & Chávez, E. (2010). On locality sensitive hashing in metric spaces. Similarity Search and Applications.
• Chen, T., Fu, C., Ke, X., Gao, Y., Ni, Y., & Zeng, A. (2025). Stitching Inner Product and Euclidean Metrics for Topology-aware Maximum Inner Product Search. Proceedings of the 48th International ACM SIGIR Conference on Research and Development in Information Retrieval.
• Lu, S., Wang, R., & Tao, Y. (2025). Interactive Graph Search Made Simple. Proceedings of the ACM on Management of Data, 3, 1 - 25.
• Beyer, K.S., Goldstein, J., Ramakrishnan, R., & Shaft, U. (1999). When Is ''Nearest Neighbor'' Meaningful? International Conference on Database Theory.
• Berchtold, S., Keim, D.A., Kriegel, H., & Seidl, T. (2000). Indexing the Solution Space: A New Technique for Nearest Neighbor Search in High-Dimensional Space. IEEE Trans. Knowl. Data Eng., 12, 45-57.
• Subramanya, S.J., Devvrit, F., Simhadri, H.V., Krishnawamy, R., & Kadekodi, R. (2019). Rand-NSG: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node. Neural Information Processing Systems.

Potpourri

• Han, Z., He, Y., Kang, S., Xie, M., Cui, W., Ge, S., Zhang, H., Zhang, D., Chaudhuri, S., Mao, R., & Qin, J. (2026). Auto-Relate: A Unified Approach to Discovering Reliable Functional Relationships Leveraging Statistical Tests.
• Kossmann, J., Halfpap, S., Jankrift, M., & Schlosser, R. (2020). Magic mirror in my hand, which is the best in the land? Proceedings of the VLDB Endowment, 13, 2382 - 2395.
• Graefe, G. (1995). The Cascades Framework for Query Optimization. IEEE Data(base) Engineering Bulletin, 18, 19-29.
• Schlosser, R., Kossmann, J., & Boissier, M. (2019). Efficient Scalable Multi-attribute Index Selection Using Recursive Strategies. 2019 IEEE 35th International Conference on Data Engineering (ICDE), 1238-1249.
• Graefe, G., & McKenna, W.J. (1993). The Volcano optimizer generator: extensibility and efficient search. Proceedings of IEEE 9th International Conference on Data Engineering, 209-218.
• Chaudhuri, S., Das, G., & Narasayya, V.R. (2007). Optimized stratified sampling for approximate query processing. ACM Trans. Database Syst., 32, 9.
• Wang, X., Wu, W., Narasayya, V.R., & Chaudhuri, S. (2025). Esc: An Early-Stopping Checker for Budget-aware Index Tuning. Proc. VLDB Endow., 18, 1278-1290.
• Chaudhuri, S., Datar, M., & Narasayya, V.R. (2004). Index selection for databases: a hardness study and a principled heuristic solution. IEEE Transactions on Knowledge and Data Engineering, 16, 1313-1323.

Query Equivalence

• Klopfenstein, R., He, Y., Tremante, A., Wang, Y., Narodytska, N., & Wu, H. (2025). SpotIt: Evaluating Text-to-SQL Evaluation with Formal Verification. ArXiv, abs/2510.26840.
• Shah, S., Sudarshan, S., Kajbaje, S., Patidar, S., Gupta, B.P., & Vira, D. (2011). Generating test data for killing SQL mutants: A constraint-based approach. 2011 IEEE 27th International Conference on Data Engineering, 1175-1186.
• Somwase, S., Das, P., & Sudarshan, S. (2024). Data Generation for Testing Complex Queries. ArXiv, abs/2409.18821.
• He, Y., Zhao, P., Wang, X., & Wang, Y. (2024). VeriEQL: Bounded Equivalence Verification for Complex SQL Queries with Integrity Constraints. Proceedings of the ACM on Programming Languages, 8, 1071 - 1099.
• Mohamed, M., Reynolds, A., Tinelli, C., & Barrett, C.W. (2024). Verifying SQL Queries using Theories of Tables and Relations. ArXiv, abs/2405.03057.