BLC-RFANN : B+ tree with Lazy Caching for RFANN

Lampropoulos, Panagiotis; Λαμπρόπουλος, Παναγιώτης

Master Thesis

Author

Lampropoulos, Panagiotis

Λαμπρόπουλος, Παναγιώτης

Date

2026-03

Abstract

The following thesis examines a new algorithm for performing Range Filtered Approximate Nearest Neighbor (or RFANN for short) queries named BLC-RFANN (B+ tree with Lazy Caching for RFANN). Existing RFANN methods tend to work with static datasets (i.e. datasets whose data remain the same throughout time) and moreover lack any type of caching mechanisms to improve query execution speed. BLC-RFANN’s two basic components (the B+ tree and the caching system) try to address these two limitations. Given a set of data points (each data point consisting of a vector and a numeric value) and an input vector, RFANN searches try to find the (approximate) nearest data points to the input vector and whose numeric value is in a specified, continuous range. It is an issue that has attracted an increasing amount of interest in both academia and industry for its wide range of applications. The method which we discuss is based on the B+ tree, an (existing) variation of the B-tree where data is only stored in the leaf level (instead of being stored on every node of the tree), and an intricate caching mechanism which we introduce in this study in order to reduce query response time. Our goal in this study is to compare our method’s performance with other, state-of-the-art algorithms used for RFANN queries in various metrics, such as index build time (the amount of time needed in order for an index to be created), the memory footprint of an index (how much memory space does an index use), the amount of queries processed per second and recall (the number of true positives compared to the real positives), which is the most commonly used metric for measuring the validity of RFANN metrics. Our experiments show that BLC-RFANN requires less time and (generally speaking) less space to build its index compared to its competitors, while also achieving a very high level of recall (up to 100% with specific configuration), at a cost of reduced throughput. However, features such as our caching mechanism manage to improve the number of queries processed per second, and in specific scenarios (e.g., where selectivity is low or scenarios where the datasets are very large compared to the available resources) BLC-RFANN manages to deliver a comparable throughput as other modern RFANN algorithms.

Postgraduate Studies Programme

Πληροφοριακά Συστήματα και Υπηρεσίες

Department

Σχολή Τεχνολογιών Πληροφορικής και Επικοινωνιών. Τμήμα Ψηφιακών Συστημάτων

Number of pages

Language

English

URI

https://dione.lib.unipi.gr/xmlui/handle/unipi/19064

Collections

Τμήμα Ψηφιακών Συστημάτων

Show full item record

Except where otherwise noted, this item's license is described as
Αναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 3.0 Ελλάδα