ENTS - a fast and adaptive indexing system for codebooks

We describe Ents, a new tree structured indexing system for vector quantization. This new indexing system is generic, adaptive and can be used as a software component in any vector quantization system. The cost of this higher speed (compared to tabular indexing) is a negligible degradation of the distortion error. Nevertheless, a parameter allows the user to tradeoff speed for a lower distortion error. A distinctive and attractive feature of Ents is that it can follow a non-stationary input vector distribution by performing local repairs to its indexing tree. Experimental results show that Ents is very fast; it outperforms other tree indexing systems like TSVQ and K-trees.