{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T00:28:46Z","timestamp":1777854526850,"version":"3.51.4"},"reference-count":35,"publisher":"SAGE Publications","issue":"4","license":[{"start":{"date-parts":[[2016,5,1]],"date-time":"2016-05-01T00:00:00Z","timestamp":1462060800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Journal of Information Science"],"published-print":{"date-parts":[[2017,8]]},"abstract":"<jats:p>Finding k-nearest neighbours ( k-NN) is one of the most important primitives of many applications such as search engines and recommendation systems. However, its computational cost is extremely high when searching for k-NN points in a huge collection of high-dimensional points. Locality-sensitive hashing (LSH) has been introduced for an efficient k-NN approximation, but none of the existing LSH approaches clearly outperforms others. We propose a novel LSH approach, Signature Selection LSH (S2LSH), which finds approximate k-NN points very efficiently in various datasets. It first constructs a large pool of highly diversified signature regions with various sizes. Given a query point, it dynamically generates a query-specific signature region by merging highly effective signature regions selected from the signature pool. We also suggest S2LSH-M, a variant of S2LSH, which processes multiple queries more efficiently by using query-specific features and optimization techniques. Extensive experiments show the performance superiority of our approaches in diverse settings.<\/jats:p>","DOI":"10.1177\/0165551516644176","type":"journal-article","created":{"date-parts":[[2016,5,11]],"date-time":"2016-05-11T00:04:30Z","timestamp":1462925070000},"page":"440-457","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":0,"title":["Query-specific signature selection for efficient\n                    <i>k<\/i>\n                    -nearest neighbour approximation"],"prefix":"10.1177","volume":"43","author":[{"given":"Youngki","family":"Park","sequence":"first","affiliation":[{"name":"School of Computer Science and Engineering, Seoul National University, Korea"}]},{"given":"Heasoo","family":"Hwang","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, University of Seoul, Korea"}]},{"given":"Sang-goo","family":"Lee","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, Seoul National University, Korea"}]}],"member":"179","published-online":{"date-parts":[[2016,5,1]]},"reference":[{"key":"bibr1-0165551516644176","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276876"},{"key":"bibr2-0165551516644176","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213898"},{"key":"bibr3-0165551516644176","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559905"},{"key":"bibr4-0165551516644176","doi-asserted-by":"publisher","DOI":"10.1145\/997817.997857"},{"key":"bibr5-0165551516644176","first-page":"518","volume-title":"Proceedings of the international conference on very large data bases","author":"Gionis A","year":"1999"},{"key":"bibr6-0165551516644176","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509965"},{"key":"bibr7-0165551516644176","first-page":"21","volume-title":"Proceedings of the compression and complexity of sequences","author":"Broader AZ","year":"1997"},{"key":"bibr8-0165551516644176","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2015.2408363"},{"key":"bibr9-0165551516644176","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963487"},{"key":"bibr10-0165551516644176","first-page":"1989","volume":"10","author":"Chen J","year":"2009","journal-title":"Journal of Machine Learning Research"},{"key":"bibr11-0165551516644176","doi-asserted-by":"publisher","DOI":"10.1177\/0165551515594728"},{"key":"bibr12-0165551516644176","doi-asserted-by":"publisher","DOI":"10.1145\/1864708.1864770"},{"key":"bibr13-0165551516644176","doi-asserted-by":"publisher","DOI":"10.1016\/j.ijinfomgt.2009.09.006"},{"key":"bibr14-0165551516644176","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2006.227"},{"key":"bibr15-0165551516644176","doi-asserted-by":"publisher","DOI":"10.1016\/j.knosys.2013.03.012"},{"key":"bibr16-0165551516644176","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2012.6247790"},{"key":"bibr17-0165551516644176","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2014.2361055"},{"key":"bibr18-0165551516644176","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40991-2_42"},{"key":"bibr19-0165551516644176","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipm.2012.07.008"},{"key":"bibr20-0165551516644176","doi-asserted-by":"publisher","DOI":"10.1177\/0165551512437517"},{"key":"bibr21-0165551516644176","doi-asserted-by":"publisher","DOI":"10.1177\/0165551512451667"},{"key":"bibr22-0165551516644176","doi-asserted-by":"publisher","DOI":"10.1177\/0165551515591724"},{"key":"bibr23-0165551516644176","doi-asserted-by":"publisher","DOI":"10.1177\/0165551507082592"},{"key":"bibr24-0165551516644176","doi-asserted-by":"publisher","DOI":"10.1145\/347090.347123"},{"key":"bibr25-0165551516644176","first-page":"1753","volume":"1","author":"Weiss Y","year":"2009","journal-title":"Advances in Neural Information Processing Systems"},{"key":"bibr26-0165551516644176","first-page":"1","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Liu W","year":"2011"},{"key":"bibr27-0165551516644176","doi-asserted-by":"publisher","DOI":"10.1145\/1031171.1031213"},{"key":"bibr28-0165551516644176","volume-title":"Computer Vision","author":"Shapiro L","year":"2001"},{"key":"bibr29-0165551516644176","doi-asserted-by":"publisher","DOI":"10.1017\/S1355771800003071"},{"key":"bibr30-0165551516644176","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV.1999.790410"},{"key":"bibr31-0165551516644176","first-page":"156","volume-title":"Proceedings of the symposium on geometry processing","author":"Kazhdan M","year":"2003"},{"key":"bibr32-0165551516644176","doi-asserted-by":"publisher","DOI":"10.1109\/5.726791"},{"key":"bibr33-0165551516644176","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2010.57"},{"key":"bibr34-0165551516644176","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2015.01.001"},{"key":"bibr35-0165551516644176","doi-asserted-by":"publisher","DOI":"10.1145\/2806416.2806632"}],"container-title":["Journal of Information Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0165551516644176","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/0165551516644176","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0165551516644176","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T23:09:26Z","timestamp":1777504166000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/0165551516644176"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,5,1]]},"references-count":35,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,8]]}},"alternative-id":["10.1177\/0165551516644176"],"URL":"https:\/\/doi.org\/10.1177\/0165551516644176","relation":{},"ISSN":["0165-5515","1741-6485"],"issn-type":[{"value":"0165-5515","type":"print"},{"value":"1741-6485","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,5,1]]}}}