{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T15:15:00Z","timestamp":1759331700563,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":50,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,9]],"date-time":"2021-06-09T00:00:00Z","timestamp":1623196800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Research Foundation Singapore under its Strategic Capability Research Centres Funding Initiative"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,9]]},"DOI":"10.1145\/3448016.3457240","type":"proceedings-article","created":{"date-parts":[[2021,6,18]],"date-time":"2021-06-18T17:22:39Z","timestamp":1624036959000},"page":"777-789","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Point-to-Hyperplane Nearest Neighbor Search Beyond the Unit Hypersphere"],"prefix":"10.1145","author":[{"given":"Qiang","family":"Huang","sequence":"first","affiliation":[{"name":"National University of Singapore, Singapore, Singapore"}]},{"given":"Yifan","family":"Lei","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore, Singapore"}]},{"given":"Anthony K. H.","family":"Tung","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore, Singapore"}]}],"member":"320","published-online":{"date-parts":[[2021,6,18]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"crossref","unstructured":"Alexandr Andoni and Piotr Indyk. 2006. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. In FOCS . 459--468.  Alexandr Andoni and Piotr Indyk. 2006. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. In FOCS . 459--468.","DOI":"10.1109\/FOCS.2006.49"},{"key":"e_1_3_2_2_2_1","unstructured":"Alexandr Andoni Piotr Indyk Thijs Laarhoven Ilya Razenshteyn and Ludwig Schmidt. 2015. Practical and optimal LSH for angular distance. In NeurIPS. 1225--1233.  Alexandr Andoni Piotr Indyk Thijs Laarhoven Ilya Razenshteyn and Ludwig Schmidt. 2015. Practical and optimal LSH for angular distance. In NeurIPS. 1225--1233."},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"crossref","unstructured":"Alexandr Andoni and Ilya Razenshteyn. 2015. Optimal data-dependent hashing for approximate near neighbors. In STOC. 793--801.  Alexandr Andoni and Ilya Razenshteyn. 2015. Optimal data-dependent hashing for approximate near neighbors. In STOC. 793--801.","DOI":"10.1145\/2746539.2746553"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"crossref","unstructured":"Martin Aum\u00fcller Tobias Christiani Rasmus Pagh and Francesco Silvestri. 2018. Distance-sensitive hashing. In PODS. 89--104.  Martin Aum\u00fcller Tobias Christiani Rasmus Pagh and Francesco Silvestri. 2018. Distance-sensitive hashing. In PODS. 89--104.","DOI":"10.1145\/3196959.3196976"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"crossref","unstructured":"Yoram Bachrach Yehuda Finkelstein Ran Gilad-Bachrach Liran Katzir Noam Koenigstein Nir Nice and Ulrich Paquet. 2014. Speeding up the xbox recommender system using a euclidean transformation for inner-product spaces. In RecSys. 257--264.  Yoram Bachrach Yehuda Finkelstein Ran Gilad-Bachrach Liran Katzir Noam Koenigstein Nir Nice and Ulrich Paquet. 2014. Speeding up the xbox recommender system using a euclidean transformation for inner-product spaces. In RecSys. 257--264.","DOI":"10.1145\/2645710.2645741"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"crossref","unstructured":"Jon Louis Bentley. 1990. K-d trees for semidynamic point sets. In SoCG. 187--197.  Jon Louis Bentley. 1990. K-d trees for semidynamic point sets. In SoCG. 187--197.","DOI":"10.1145\/98524.98564"},{"volume-title":"\u201cnearest neighbor","author":"Beyer Kevin","key":"e_1_3_2_2_7_1","unstructured":"Kevin Beyer , Jonathan Goldstein , Raghu Ramakrishnan , and Uri Shaft . 1999. When is \u201cnearest neighbor \u201d meaningful?. In ICDT. 217--235. Kevin Beyer, Jonathan Goldstein, Raghu Ramakrishnan, and Uri Shaft. 1999. When is \u201cnearest neighbor\u201d meaningful?. In ICDT. 217--235."},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"crossref","unstructured":"Moses S Charikar. 2002. Similarity estimation techniques from rounding algorithms. In STOC. 380--388.  Moses S Charikar. 2002. Similarity estimation techniques from rounding algorithms. In STOC. 380--388.","DOI":"10.1145\/509907.509965"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2017.12.010"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-46759-7_17"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"crossref","unstructured":"Mayur Datar Nicole Immorlica Piotr Indyk and Vahab S Mirrokni. 2004. Locality-sensitive hashing scheme based on p-stable distributions. In SoCG . 253--262.  Mayur Datar Nicole Immorlica Piotr Indyk and Vahab S Mirrokni. 2004. Locality-sensitive hashing scheme based on p-stable distributions. In SoCG . 253--262.","DOI":"10.1145\/997817.997857"},{"key":"e_1_3_2_2_12_1","unstructured":"Junhao Gan Jianlin Feng Qiong Fang and Wilfred Ng. 2012. Locality-sensitive hashing scheme based on dynamic collision counting. In SIGMOD . 541--552.  Junhao Gan Jianlin Feng Qiong Fang and Wilfred Ng. 2012. Locality-sensitive hashing scheme based on dynamic collision counting. In SIGMOD . 541--552."},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a014"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2752156"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0472-7"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850469.2850470"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"crossref","unstructured":"Qiang Huang Guihong Ma Jianlin Feng Qiong Fang and Anthony KH Tung. 2018. Accurate and Fast Asymmetric Locality-Sensitive Hashing Scheme for Maximum Inner Product Search. In KDD. 1561--1570.  Qiang Huang Guihong Ma Jianlin Feng Qiong Fang and Anthony KH Tung. 2018. Accurate and Fast Asymmetric Locality-Sensitive Hashing Scheme for Maximum Inner Product Search. In KDD. 1561--1570.","DOI":"10.1145\/3219819.3219971"},{"key":"e_1_3_2_2_18_1","unstructured":"Piotr Indyk. 2003. Better algorithms for high-dimensional proximity problems via asymmetric embeddings. In SODA . 539--545.  Piotr Indyk. 2003. Better algorithms for high-dimensional proximity problems via asymmetric embeddings. In SODA . 539--545."},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"crossref","unstructured":"Piotr Indyk and Rajeev Motwani. 1998. Approximate nearest neighbors: towards removing the curse of dimensionality. In STOC . 604--613.  Piotr Indyk and Rajeev Motwani. 1998. Approximate nearest neighbors: towards removing the curse of dimensionality. In STOC . 604--613.","DOI":"10.1145\/276698.276876"},{"key":"e_1_3_2_2_20_1","unstructured":"Prateek Jain Sudheendra Vijayanarasimhan and Kristen Grauman. 2010. Hashing hyperplane queries to near points with applications to large-scale active learning. In NeurIPS. 928--936.  Prateek Jain Sudheendra Vijayanarasimhan and Kristen Grauman. 2010. Hashing hyperplane queries to near points with applications to large-scale active learning. In NeurIPS. 928--936."},{"key":"e_1_3_2_2_21_1","unstructured":"Yifan Lei Qiang Huang Mohan Kankanhalli and Anthony Tung. 2019. Sublinear Time Nearest Neighbor Search over Generalized Weighted Space. In ICML . 3773--3781.  Yifan Lei Qiang Huang Mohan Kankanhalli and Anthony Tung. 2019. Sublinear Time Nearest Neighbor Search over Generalized Weighted Space. In ICML . 3773--3781."},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"crossref","unstructured":"Yifan Lei Qiang Huang Mohan Kankanhalli and Anthony KH Tung. 2020. Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring. In SIGMOD . 2589--2599.  Yifan Lei Qiang Huang Mohan Kankanhalli and Anthony KH Tung. 2020. Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring. In SIGMOD . 2589--2599.","DOI":"10.1145\/3318464.3389778"},{"volume-title":"I\/O Efficient c-Approximate Nearest Neighbor Search in High-Dimensional Space","author":"Liu Wanqi","key":"e_1_3_2_2_23_1","unstructured":"Wanqi Liu , Hanchen Wang , Ying Zhang , Wei Wang , and Lu Qin . 2019. I-LSH : I\/O Efficient c-Approximate Nearest Neighbor Search in High-Dimensional Space . In IEEE ICDE . 1670--1673. Wanqi Liu, Hanchen Wang, Ying Zhang, Wei Wang, and Lu Qin. 2019. I-LSH: I\/O Efficient c-Approximate Nearest Neighbor Search in High-Dimensional Space. In IEEE ICDE . 1670--1673."},{"key":"e_1_3_2_2_24_1","unstructured":"Wei Liu Jun Wang Yadong Mu Sanjiv Kumar and Shih-Fu Chang. 2012. Compact hyperplane hashing with bilinear functions. In ICML. 467--474.  Wei Liu Jun Wang Yadong Mu Sanjiv Kumar and Shih-Fu Chang. 2012. Compact hyperplane hashing with bilinear functions. In ICML. 467--474."},{"key":"e_1_3_2_2_25_1","unstructured":"Xianglong Liu Xinjie Fan Cheng Deng Zhujin Li Hao Su and Dacheng Tao. 2016. Multilinear hyperplane hashing. In CVPR. 5119--5127.  Xianglong Liu Xinjie Fan Cheng Deng Zhujin Li Hao Su and Dacheng Tao. 2016. Multilinear hyperplane hashing. In CVPR. 5119--5127."},{"volume-title":"R2LSH: A Nearest Neighbor Search Scheme Based on Two-dimensional Projected Spaces","author":"Lu Kejing","key":"e_1_3_2_2_26_1","unstructured":"Kejing Lu and Mineichi Kudo . 2020. R2LSH: A Nearest Neighbor Search Scheme Based on Two-dimensional Projected Spaces . In IEEE ICDE . 1045--1056. Kejing Lu and Mineichi Kudo. 2020. R2LSH: A Nearest Neighbor Search Scheme Based on Two-dimensional Projected Spaces. In IEEE ICDE . 1045--1056."},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/3397230.3397240"},{"key":"e_1_3_2_2_28_1","unstructured":"Behnam Neyshabur and Nathan Srebro. 2015. On Symmetric and Asymmetric LSHs for Inner Product Search. In ICML. 1926--1934.  Behnam Neyshabur and Nathan Srebro. 2015. On Symmetric and Asymmetric LSHs for Inner Product Search. In ICML. 1926--1934."},{"volume-title":"Five balltree construction algorithms","author":"Omohundro Stephen M","key":"e_1_3_2_2_29_1","unstructured":"Stephen M Omohundro . 1989. Five balltree construction algorithms . International Computer Science Institute Berkeley . Stephen M Omohundro. 1989. Five balltree construction algorithms .International Computer Science Institute Berkeley."},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-25087-8_1"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2016.07.006"},{"key":"e_1_3_2_2_32_1","unstructured":"Parikshit Ram and Alexander G Gray. 2012. Maximum inner-product search using cone trees. In KDD. 931--939.  Parikshit Ram and Alexander G Gray. 2012. Maximum inner-product search using cone trees. In KDD. 931--939."},{"key":"e_1_3_2_2_33_1","volume-title":"Can Xu, Jian Yang, and Nuno Nvasconcelos.","author":"Saberian Mohammad","year":"2016","unstructured":"Mohammad Saberian , Jose Costa Pereira , Can Xu, Jian Yang, and Nuno Nvasconcelos. 2016 . Large margin discriminant dimensionality reduction in prediction space. In NeurIPS . 1488--1496. Mohammad Saberian, Jose Costa Pereira, Can Xu, Jian Yang, and Nuno Nvasconcelos. 2016. Large margin discriminant dimensionality reduction in prediction space. In NeurIPS . 1488--1496."},{"key":"e_1_3_2_2_34_1","unstructured":"Greg Schohn and David Cohn. 2000. Less is More: Active Learning with Support Vector Machines. In ICML. 839--846.  Greg Schohn and David Cohn. 2000. Less is More: Active Learning with Support Vector Machines. In ICML. 839--846."},{"key":"e_1_3_2_2_35_1","unstructured":"Anshumali Shrivastava and Ping Li. 2014. Asymmetric LSH (ALSH) for sublinear time Maximum Inner Product Search (MIPS). In NeurIPS . 2321--2329.  Anshumali Shrivastava and Ping Li. 2014. Asymmetric LSH (ALSH) for sublinear time Maximum Inner Product Search (MIPS). In NeurIPS . 2321--2329."},{"key":"e_1_3_2_2_36_1","unstructured":"Anshumali Shrivastava and Ping Li. 2015. Improved asymmetric locality sensitive hashing (ALSH) for Maximum Inner Product Search (MIPS). In UAI. 812--821.  Anshumali Shrivastava and Ping Li. 2015. Improved asymmetric locality sensitive hashing (ALSH) for Maximum Inner Product Search (MIPS). In UAI. 812--821."},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735461.2735462"},{"key":"e_1_3_2_2_38_1","doi-asserted-by":"crossref","unstructured":"Yufei Tao Ke Yi Cheng Sheng and Panos Kalnis. 2009. Quality and efficiency in high dimensional nearest neighbor search. In SIGMOD . 563--576.  Yufei Tao Ke Yi Cheng Sheng and Panos Kalnis. 2009. Quality and efficiency in high dimensional nearest neighbor search. In SIGMOD . 563--576.","DOI":"10.1145\/1559845.1559905"},{"key":"e_1_3_2_2_39_1","volume-title":"JMLR","volume":"2","author":"Tong Simon","year":"2001","unstructured":"Simon Tong and Daphne Koller . 2001 . Support vector machine active learning with applications to text classification . JMLR , Vol. 2 , Nov (2001), 45--66. Simon Tong and Daphne Koller. 2001. Support vector machine active learning with applications to text classification. JMLR , Vol. 2, Nov (2001), 45--66."},{"key":"e_1_3_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2008.128"},{"key":"e_1_3_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11263-014-0721-9"},{"key":"e_1_3_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2013.121"},{"key":"e_1_3_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/3424573.3424580"},{"key":"e_1_3_2_2_44_1","first-page":"194","article-title":"A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces","volume":"98","author":"Weber Roger","year":"1998","unstructured":"Roger Weber , Hans-J\u00f6rg Schek , and Stephen Blott . 1998 . A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces . In VLDB , Vol. 98. 194 -- 205 . Roger Weber, Hans-J\u00f6rg Schek, and Stephen Blott. 1998. A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces. In VLDB, Vol. 98. 194--205.","journal-title":"VLDB"},{"key":"e_1_3_2_2_45_1","unstructured":"Chang Xu Dacheng Tao Chao Xu and Yong Rui. 2014. Large-margin weakly supervised dimensionality reduction. In ICML. 865--873.  Chang Xu Dacheng Tao Chao Xu and Yong Rui. 2014. Large-margin weakly supervised dimensionality reduction. In ICML. 865--873."},{"key":"e_1_3_2_2_46_1","unstructured":"Xiao Yan Jinfeng Li Xinyan Dai Hongzhi Chen and James Cheng. 2018. Norm-Ranging LSH for Maximum Inner Product Search. In NeurIPS. 2956--2965.  Xiao Yan Jinfeng Li Xinyan Dai Hongzhi Chen and James Cheng. 2018. Norm-Ranging LSH for Maximum Inner Product Search. In NeurIPS. 2956--2965."},{"key":"e_1_3_2_2_47_1","unstructured":"Teng Zhang and Zhi-Hua Zhou. 2018. Optimal margin distribution clustering. In AAAI. 4474--4481.  Teng Zhang and Zhi-Hua Zhou. 2018. Optimal margin distribution clustering. In AAAI. 4474--4481."},{"key":"e_1_3_2_2_48_1","doi-asserted-by":"crossref","unstructured":"Bin Zhao Fei Wang and Changshui Zhang. 2008. Efficient maximum margin clustering via cutting plane algorithm. In SDM . 751--762.  Bin Zhao Fei Wang and Changshui Zhang. 2008. Efficient maximum margin clustering via cutting plane algorithm. In SDM . 751--762.","DOI":"10.1137\/1.9781611972788.68"},{"key":"e_1_3_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.14778\/3377369.3377374"},{"key":"e_1_3_2_2_50_1","volume-title":"Anthony KH Tung, and Sai Wu","author":"Zheng Yuxin","year":"2016","unstructured":"Yuxin Zheng , Qi Guo , Anthony KH Tung, and Sai Wu . 2016 . Lazylsh : Approximate nearest neighbor search for multiple distance functions with a single index. In SIGMOD. 2023--2037. Yuxin Zheng, Qi Guo, Anthony KH Tung, and Sai Wu. 2016. Lazylsh: Approximate nearest neighbor search for multiple distance functions with a single index. In SIGMOD. 2023--2037."}],"event":{"name":"SIGMOD\/PODS '21: International Conference on Management of Data","sponsor":["SIGMOD ACM Special Interest Group on Management of Data"],"location":"Virtual Event China","acronym":"SIGMOD\/PODS '21"},"container-title":["Proceedings of the 2021 International Conference on Management of Data"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3448016.3457240","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3448016.3457240","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:28:06Z","timestamp":1750195686000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3448016.3457240"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,9]]},"references-count":50,"alternative-id":["10.1145\/3448016.3457240","10.1145\/3448016"],"URL":"https:\/\/doi.org\/10.1145\/3448016.3457240","relation":{},"subject":[],"published":{"date-parts":[[2021,6,9]]},"assertion":[{"value":"2021-06-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}