Overview
ELPIS is a graph-based similarity search algorithm for scalable data science, published in Proceedings of the VLDB Endowment 16.6 (2023): 1548-1559.
Index Building
- Builds index 3x-8x faster than competitors
- Uses 40% less memory than competing methods
- Achieves high recall of 0.99
- Up to 2x faster than state-of-the-art methods
- Answers 1-NN queries up to one order of magnitude faster
- 3x faster than graph-based method EFANNA
- Returns same answer as serial scan and QALSH but over three orders of magnitude faster
Technical Approach
DC Strategy with II and ND
- Adopted Divide-and-Conquer (DC) strategy
- Leverages both Iterative Improvement (II) and Neighbor Diversification (ND)
- Maintains graphs separately and searches them in parallel
Graph Construction
ELPIS uses the same search algorithm as other state-of-the-art graph-based methods (HNSW, NSG, etc.) but differs in:
- How it constructs the graph
- How it selects seed points
- Parallel graph maintenance and search
Research Impact (2025-2026)
ELPIS is cited among state-of-the-art graph-based vector search methods in recent comprehensive evaluations:
- "Graph-Based Vector Search: An Experimental Evaluation of the State-of-the-Art" (February 2025)
- Included in comparisons with HNSW, NSG, HCNNG, and other leading algorithms
Authors
Azizi, Ilias, Karima Echihabi, and Themis Palpanas (2023)
Use Cases
- Scalable data science applications
- Large-scale similarity search
- High-dimensional nearest neighbor search
- Applications requiring fast index building
- Memory-constrained environments
Comparison with Competitors
ELPIS offers an excellent balance:
- Faster index building than most competitors
- Lower memory usage
- Competitive or superior query performance
- High recall guarantees
