Before revision:  We give a simple data structure that generalizes and outperforms previous algorithms such as MinHash [J. Discrete Algorithms 1998], SimHash [STOC 2002], Spherical LSF [SODA  2017] and Chosen Path [STOC 2017] ; and we show matching lower bounds using hypercontractive inequalities for a wide range of parameters and space/time trade-offs. This answers the main open question in Christiani and Pagh STOC 2017 on unifying the landscape of Locality Sensitive (non-data-dependent) set similarity search in both time and space;
After revision:  We give a simple data structure that generalizes and outperforms previous algorithms such as MinHash [J. Discrete Algorithms 1998], SimHash [STOC 2002], Spherical LSF [SODA 2017] and Chosen Path [STOC 2017] STOC 2017 on unifying the landscape of Locality Sensitive (non-data-dependent) set similarity search in both time and space;