{
  "id": "1704.06556",
  "version": "v1",
  "published": "2017-04-21T14:22:16.000Z",
  "updated": "2017-04-21T14:22:16.000Z",
  "title": "PQTable: Non-exhaustive Fast Search for Product-quantized Codes using Hash Tables",
  "authors": [
    "Yusuke Matsui",
    "Toshihiko Yamasaki",
    "Kiyoharu Aizawa"
  ],
  "categories": [
    "cs.CV"
  ],
  "abstract": "In this paper, we propose a product quantization table (PQTable); a fast search method for product-quantized codes via hash-tables. An identifier of each database vector is associated with the slot of a hash table by using its PQ-code as a key. For querying, an input vector is PQ-encoded and hashed, and the items associated with that code are then retrieved. The proposed PQTable produces the same results as a linear PQ scan, and is 10^2 to 10^5 times faster. Although state-of-the-art performance can be achieved by previous inverted-indexing-based approaches, such methods require manually-designed parameter setting and significant training; our PQTable is free of these limitations, and therefore offers a practical and effective solution for real-world problems. Specifically, when the vectors are highly compressed, our PQTable achieves one of the fastest search performances on a single CPU to date with significantly efficient memory usage (0.059 ms per query over 10^9 data points with just 5.5 GB memory consumption). Finally, we show that our proposed PQTable can naturally handle the codes of an optimized product quantization (OPQTable).",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-04-21T14:22:16.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "non-exhaustive fast search",
      "product-quantized codes",
      "hash table",
      "product quantization",
      "fastest search performances"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}