Efficient Time-Restricted k NN Search in High-Dimensional Data Using Multi-Level Block Indexing, with Extensions to Multi-Attribute Filtering

How can we efficiently index extensive high-dimensional vector data increasing over time, enabling quick and accurate proximity searches within designated time windows? A time-restricted \( k \) -Nearest Neighbor (T \( k \) NN) query aims to identify the \( k \) -nearest vectors to a query vector within a specified time window. While high-dimensional and time-accumulating data are ubiquitous and managing such data efficiently is becoming increasingly significant, T \( k \) NN search within this context has not received much attention so far. In this article, we propose Multi-Level Block Indexing (MBI), a tailored indexing method for efficient approximate T \( k \) NN search. MBI employs an incremental hierarchical index structure that divides the data into multiple blocks based on timestamps. This structure ensures efficient query processing, irrespective of the length of the query time window, and facilitates the addition of new data over time. Furthermore, we extend T \( k \) NN beyond timestamps to the \( m \) -A \( k \) NN problem, incorporating \( m \) additional attributes—such as age, height, and weight in medical data or citation counts in academic papers—allowing queries to integrate multiple numerical constraints. Experimental results highlight MBI’s superiority over conventional methods, achieving query processing speeds up to 10.88 times faster and offering logarithmic scaling in data insertion time as the data volume grows. Additionally, in \( m \) -A \( k \) NN queries, MBI maintains stable indexing performance and achieves up to 1.99 times faster query performance, demonstrating its effectiveness in large-scale, multi-attribute \( k \) NN search.