{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T22:38:41Z","timestamp":1778279921042,"version":"3.51.4"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2015,12]]},"abstract":"<jats:p>Nearest Neighbor (NN) search in high dimension is an important feature in many applications (e.g., image retrieval, multimedia databases). Product Quantization (PQ) is a widely used solution which offers high performance, i.e., low response time while preserving a high accuracy. PQ represents high-dimensional vectors (e.g., image descriptors) by compact codes. Hence, very large databases can be stored in memory, allowing NN queries without resorting to slow I\/O operations. PQ computes distances to neighbors using cache-resident lookup tables, thus its performance remains limited by (i) the many cache accesses that the algorithm requires, and (ii) its inability to leverage SIMD instructions available on modern CPUs.<\/jats:p>\n          <jats:p>In this paper, we advocate that cache locality is not sufficient for efficiency. To address these limitations, we design a novel algorithm, PQ Fast Scan, that transforms the cache-resident lookup tables into small tables, sized to fit SIMD registers. This transformation allows (i) in-register lookups in place of cache accesses and (ii) an efficient SIMD implementation. PQ Fast Scan has the exact same accuracy as PQ, while having 4 to 6 times lower response time (e.g., for 25 million vectors, scan time is reduced from 74ms to 13ms).<\/jats:p>","DOI":"10.14778\/2856318.2856324","type":"journal-article","created":{"date-parts":[[2016,2,1]],"date-time":"2016-02-01T14:10:31Z","timestamp":1454335831000},"page":"288-299","source":"Crossref","is-referenced-by-count":55,"title":["Cache locality is not enough"],"prefix":"10.14778","volume":"9","author":[{"given":"Fabien","family":"Andr\u00e9","sequence":"first","affiliation":[{"name":"Technicolor"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anne-Marie","family":"Kermarrec","sequence":"additional","affiliation":[{"name":"Inria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nicolas","family":"Le Scouarnec","sequence":"additional","affiliation":[{"name":"Technicolor"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,12]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Intel\u00ae 64 and IA-32 Architectures Optimization Reference Manual April 2012.  Intel\u00ae 64 and IA-32 Architectures Optimization Reference Manual April 2012."},{"key":"e_1_2_1_2_1","volume-title":"June","year":"2015"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142548"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/2354409.2355036"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732219.2732227"},{"key":"e_1_2_1_6_1","first-page":"225","volume-title":"CIDR","author":"Boncz P.","year":"2005"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/1454159.1454171"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/997817.997857"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213898"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2013.240"},{"key":"e_1_2_1_11_1","first-page":"518","volume-title":"VLDB","author":"Gionis A.","year":"1999"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/SOAC.1991.143840"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2568058.2568068"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2010.57"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2014.298"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687553.1687564"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCSCT.2008.141"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-007-0064-z"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732939.2732947"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1982.1056489"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2013.388"},{"key":"e_1_2_1_22_1","first-page":"298","volume-title":"FAST","author":"Plank J. S.","year":"2013"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/163090.163096"},{"key":"e_1_2_1_24_1","volume-title":"Same-size k-means variation","author":"Schubert E.","year":"2012"},{"key":"e_1_2_1_25_1","first-page":"553","volume-title":"VLDB","author":"Stonebraker M.","year":"2005"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735461.2735462"},{"key":"e_1_2_1_27_1","first-page":"861","volume-title":"ICASSP","author":"Tavenard R.","year":"2011"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV.2013.424"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2856318.2856324","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:22:57Z","timestamp":1672222977000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2856318.2856324"}},"subtitle":["high-performance nearest neighbor search with product quantization fast scan"],"short-title":[],"issued":{"date-parts":[[2015,12]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,12]]}},"alternative-id":["10.14778\/2856318.2856324"],"URL":"https:\/\/doi.org\/10.14778\/2856318.2856324","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2015,12]]}}}