  We propose a novel distance to calculate distance between high dimensional
vector pairs, utilizing vector quantization generated encodings. Vector
quantization based methods are successful in handling large scale high
dimensional data. These methods compress vectors into short encodings, and
allow efficient distance computation between an uncompressed vector and
compressed dataset without decompressing explicitly. However for large
datasets, these distance computing methods perform excessive computations. We
avoid excessive computations by storing the encodings on an Encoding
Tree(E-Tree), interestingly the memory consumption is also lowered. We also
propose Encoding Forest(E-Forest) to further lower the computation cost. E-Tree
and E-Forest is compatible with various existing quantization-based methods. We
show by experiments our methods speed-up distance computing for high
dimensional data drastically, and various existing algorithms can benefit from
our methods.
