Appendix: A Lower Bound of Hash Codes ' Performance

All positives have ranks i placed on upper-right. We assume distances between query and any positive samples are different with each other. Figure 2: Mis-ranks marked on true positives and swaps that change ranks and mis-ranks. More generally, any swaps happen in a rank list would influence ranks and mis-ranks of involved positive samples. Eq. (3) is immediately obtained since B.1 Analysis on the Proposed Lower Bound B.1.1 Is the Introduced Lower Bound Tight?