Metraipolis › archive › dc_22d217af0dbf
Index-Free Dynamic Edge Retrieval with Energy-Tail-Aware Partial Scans — arXiv:2609.01820
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.01820
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-17T05:46:45.119Z
- SHA-256 of the archived text
2a44ed63a425bd8682df6cb12505b24966a6f8b49dcec91546fa6634ce90ff7a- Stable URL of this page
https://metraipolis.com/documento/dc_22d217af0dbf
How to cite
Index-Free Dynamic Edge Retrieval with Energy-Tail-Aware Partial Scans — arXiv:2609.01820 — arXiv (en), https://arxiv.org/abs/2609.01820 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_22d217af0dbf (Metraipolis archive dc_22d217af0dbf, sha256 2a44ed63a425bd8682df6cb12505b24966a6f8b49dcec91546fa6634ce90ff7a)
BibTeX
@misc{dc22d217af0dbf,
title = {Index-Free Dynamic Edge Retrieval with Energy-Tail-Aware Partial Scans — arXiv:2609.01820},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.01820},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_22d217af0dbf; sha256 2a44ed63a425bd8682df6cb12505b24966a6f8b49dcec91546fa6634ce90ff7a},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.01820. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 this https URL . Tema degli esploratori: statistica e scienza dei dati (retro-catalogo arXiv: annunci del 2026-09-03 in cs.IR). Categorie arXiv: Information Retrieval (cs.IR). Pagina del lavoro: https://arxiv.org/abs/2609.01820 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-17T05:23:20.832Z dalla pagina https://arxiv.org/catchup/cs.IR/2026-09-03?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).