CAREER: A Locality-First Strategy for Developing Efficient Concurrent and Parallel Data Structures

Modern society runs on data: every time someone searches the web, interacts with a social network, or makes an online transaction, vast amounts of information must be stored, updated, and retrieved in fractions of a second. The explosion in data, the rise of artificial-intelligence (AI) systems that require real-time data access to make autonomous decisions, and the end of Moore's law, which means future performance gains must come from software rather than hardware, are pushing data-intensive applications to their computational limits. This project targets a fundamental bottleneck in these systems: the tension between inserting new data quickly and retrieving existing data quickly, which are essential functionalities for many modern data-intensive applications. The project will develop a software-optimization strategy that improves both simultaneously, producing faster and more scalable data-management systems with direct benefits to businesses, researchers, and everyday users. The project also addresses the growing need for performance engineers who can write fast, efficient software. This project develops a principled locality-first strategy for building efficient concurrent and batch-parallel dynamic data structures. These data structures underlie core software components driving modern databases and AI systems, on modern computing platforms including central processing units (CPUs) and graphics processing units (GPUs). The locality-first strategy prioritizes memory-hierarchy efficiency before introducing parallelism, based on the insight that memory access typically dominates performance, and that improving locality can enable, rather than constrain, effective parallelism. The project has two research thrusts. The first thrust develops cache-efficient node representations for popular concurrent data structures and integrates them into key-value stores, the backbone of modern databases and storage systems. The second thrust produces locality-optimized batch-parallel data structures and applies them to accelerate streaming graph-based approximate nearest-neighbor search, which powers recommendation systems, large language models, and web search. The educational activities integrate research outcomes into undergraduate and graduate courses, workshops, and performance-engineering contests, training the next generation of computer scientists to write fast, scalable code through principled methods. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria. NSF Award ID: 2543534 | Program: 01003031DB NSF RESEARCH & RELATED ACTIVIT,01002930DB NSF RESEARCH & RELATED ACTIVIT,01002627DB NSF RESEARCH & RELATED ACTIVIT | Principal Investigator: Helen Xu | Institution: Georgia Tech Research Corporation, ATLANTA, GA | Award Amount: $431,420 View on NSF Award Search: https://www.nsf.gov/awardsearch/show-award/?AWD_ID=2543534 View on Research.gov: https://www.research.gov/awardapi-service/v1/awards/2543534.html