Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces ETAR, an index-free method for dynamic maximum inner-product search (MIPS) that balances high recall and efficient query performance while allowing for simple updates. By retaining only the most significant query coordinates and using a compact representation for lower-magnitude tail coordinates, ETAR achieves an impressive average of 99.2% Recall@10 across multiple datasets while being over four times faster than traditional full-vector scanning. Notably, ETAR maintains 100% Recall@10 under various streaming workloads without the need for index rebuilds, making it a practical solution for dynamic edge retrieval tasks.
ETAR achieves 99.2% recall while being over four times faster than traditional methods, revolutionizing dynamic edge retrieval efficiency.
Dynamic maximum inner-product search (MIPS) returns the $K$ stored vectors with the largest dot products with a query while allowing the dataset to change through insertions, replacements, and deletions. For edge retrieval, the challenge is to achieve high recall and fast queries without making updates expensive. Full-vector scanning keeps updates simple but compares each query with every stored vector, while indexed methods reduce query cost at the expense of maintaining additional structures during updates. We propose ETAR, an index-free method that reduces query work while preserving simple updates. ETAR keeps the query coordinates with the largest squared values until they cover most of its total squared magnitude and treats the rest as a low-magnitude tail. It estimates similarity from the retained coordinates using a compact lower-precision representation, corrects for skipped coordinates, and reranks a fixed number of candidates using full-precision vectors. Across five runs on nine static datasets, ETAR averages 99.2% Recall@10, the fraction of exact top-10 results recovered, while running over 4$\times$ faster than exact scanning at a representative setting. This speedup also extends to an ARM-based mobile device, where ETAR is up to 6.9$\times$ faster across four synthetic distributions. Under five streaming workloads, it maintains 100% Recall@10 at every measured point without index rebuilds. Overall, ETAR offers a practical middle ground for dynamic MIPS by reducing query cost while retaining simple, index-free updates. Code is available at https://github.com/arasyi/etar-mips.