{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,10]],"date-time":"2025-05-10T23:01:00Z","timestamp":1746918060143},"reference-count":60,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2015,11]]},"abstract":"<jats:p>\n            Approximate\n            <jats:italic>k<\/jats:italic>\n            NN (\n            <jats:italic>k<\/jats:italic>\n            -nearest neighbor) techniques using binary hash functions are among the most commonly used approaches for overcoming the prohibitive cost of performing exact\n            <jats:italic>k<\/jats:italic>\n            NN queries. However, the success of these techniques largely depends on their hash functions' ability to distinguish\n            <jats:italic>k<\/jats:italic>\n            NN items; that is, the\n            <jats:italic>k<\/jats:italic>\n            NN items retrieved based on data items'\n            <jats:italic>hashcodes<\/jats:italic>\n            , should include as many\n            <jats:italic>true k<\/jats:italic>\n            NN items as possible. A widely-adopted principle for this process is to ensure that similar items are assigned to the same hashcode so that the items with the hashcodes similar to a query's hashcode are likely to be true neighbors.\n          <\/jats:p>\n          <jats:p>\n            In this work, we abandon this heavily-utilized principle and pursue the opposite direction for generating more effective hash functions for\n            <jats:italic>k<\/jats:italic>\n            NN tasks. That is, we aim to\n            <jats:italic>increase<\/jats:italic>\n            the distance between similar items in the hashcode space, instead of reducing it. Our contribution begins by providing theoretical analysis on why this revolutionary and seemingly counter-intuitive approach leads to a more accurate identification of\n            <jats:italic>k<\/jats:italic>\n            NN items. Our analysis is followed by a proposal for a hashing algorithm that embeds this novel principle. Our empirical studies confirm that a hashing algorithm based on this counter-intuitive idea significantly improves the efficiency and accuracy of state-of-the-art techniques.\n          <\/jats:p>","DOI":"10.14778\/2850583.2850589","type":"journal-article","created":{"date-parts":[[2016,2,1]],"date-time":"2016-02-01T14:10:31Z","timestamp":1454335831000},"page":"144-155","source":"Crossref","is-referenced-by-count":23,"title":["Neighbor-sensitive hashing"],"prefix":"10.14778","volume":"9","author":[{"given":"Yongjoo","family":"Park","sequence":"first","affiliation":[{"name":"University of Michigan, Ann Arbor, MI"}]},{"given":"Michael","family":"Cafarella","sequence":"additional","affiliation":[{"name":"University of Michigan, Ann Arbor, MI"}]},{"given":"Barzan","family":"Mozafari","sequence":"additional","affiliation":[{"name":"University of Michigan, Ann Arbor, MI"}]}],"member":"320","published-online":{"date-parts":[[2015,11]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Presto: Distributed SQL query engine for big data. https:\/\/prestodb.io\/docs\/current\/release\/release-0.61.html.  Presto: Distributed SQL query engine for big data. https:\/\/prestodb.io\/docs\/current\/release\/release-0.61.html."},{"key":"e_1_2_1_2_1","unstructured":"SnappyData. http:\/\/www.snappydata.io\/.  SnappyData. http:\/\/www.snappydata.io\/."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2593667"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465351.2465355"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.49"},{"key":"e_1_2_1_6_1","volume-title":"SODA","author":"Arthur D.","year":"2007"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1353343.1353376"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242524.1242525"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497441"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2008.4587598"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509965"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2005.46"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/997817.997857"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687675"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213898"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2588565"},{"key":"e_1_2_1_17_1","volume-title":"VLDB","author":"Gionis A.","year":"1999"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2011.5995432"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/971697.602266"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2011.5995518"},{"key":"e_1_2_1_21_1","volume-title":"CVPR","author":"Heo J.-P.","year":"2012"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2014.272"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1071610.1071612"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2010.57"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICASSP.2011.5946540"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV.2013.39"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2011.5995709"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020607"},{"key":"e_1_2_1_29_1","volume-title":"NIPS","author":"Kedem D.","year":"2012"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPR.2004.545"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-85820-3_5"},{"key":"e_1_2_1_32_1","volume-title":"NIPS","author":"Kulis B.","year":"2009"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2011.219"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1126004.1126005"},{"key":"e_1_2_1_35_1","author":"Lin K.-I.","year":"1994","journal-title":"The tv-tree: An index structure for high-dimensional data. The VLDB Journal"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2013.64"},{"key":"e_1_2_1_37_1","volume-title":"CVPR","author":"Liu W.","year":"2012"},{"key":"e_1_2_1_38_1","volume-title":"ICML","author":"Liu W.","year":"2011"},{"key":"e_1_2_1_39_1","volume-title":"VLDB","author":"Lv Q.","year":"2007"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2009.27"},{"key":"e_1_2_1_41_1","volume-title":"A handbook for building an approximate query engine","author":"Mozafari B.","year":"2015"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/2354409.2354813"},{"key":"e_1_2_1_43_1","volume-title":"Online aggregation for large mapreduce jobs. PVLDB, 4","author":"Pansare N.","year":"2011"},{"key":"e_1_2_1_44_1","unstructured":"Y. Park. Supplementary material for neighbor-sensitive hashing. http:\/\/www-personal.umich.edu\/~pyongjoo\/vldb2016sup.pdf.  Y. Park. Supplementary material for neighbor-sensitive hashing. http:\/\/www-personal.umich.edu\/~pyongjoo\/vldb2016sup.pdf."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ijar.2008.11.006"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICASSP.2010.5495403"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.14778\/2140436.2140440"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.5555\/1768197.1768208"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.5555\/946247.946721"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.895972"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735461.2735462"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556574"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559905"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2008.128"},{"key":"e_1_2_1_55_1","volume-title":"VLDB","author":"Weber R.","year":"1998"},{"key":"e_1_2_1_56_1","volume-title":"NIPS","author":"Weiss Y.","year":"2009"},{"key":"e_1_2_1_57_1","volume-title":"ICCV","author":"Xu H.","year":"2011"},{"key":"e_1_2_1_58_1","volume-title":"VLDB","author":"Yu C.","year":"2001"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2588579"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2006.301"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2850583.2850589","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:17:49Z","timestamp":1672222669000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2850583.2850589"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,11]]},"references-count":60,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,11]]}},"alternative-id":["10.14778\/2850583.2850589"],"URL":"https:\/\/doi.org\/10.14778\/2850583.2850589","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2015,11]]}}}