Please note: This master’s research paper presentation will be given online.
Tamal Adhikary, Master’s candidate
David R. Cheriton School of Computer Science
Supervisors: Professors Khuzaima Daudjee, Semih Salihoglu
Packed memory arrays (PMAs) keep the input data sorted to facilitate range queries. Gaps are distributed along with data to facilitate future updates. Existing studies on PMA use tree structures to support faster updates or keep the records consecutive in a single array for faster range query execution. However, tree structure provides poor scan performance with large updates and handling large arrays even using modern tools and techniques results in poor update performance for consecutively arranged PMAs.
We implement a tree-based PMA structure named JPMA where the leaves are memory segments. Segments are reused to avoid memory re-allocation in cycles of inserts and deletes. Jacobson Index has been used on the memory segments to avoid CPU branch mispredictions. Update and lookup operations can take advantage of Jacobson Index to avoid gaps in the PMA. However, the range scan still suffers as the data are not kept consecutively. Hence, a new design point is presented in this work, providing improved update and lookup performance while experiencing larger delays for scan queries. Performance evaluation of JPMA and comparison with other state-of-the-art works validate our design point.