# Locality sensitive hashing for high-cardinality categorical data

I have output the terminal node IDs for an ensemble of extremely randomized trees and would like to calculate distances on the data set for clustering and KNN. My current distance metric is simple: sum(a != b)

That is, for every pair of records, I count the number of terminal nodes that aren't exactly the same. I would like to apply locality sensitive hashing to these output vectors but I am not sure how to proceed. Every example I have come across for LSH uses either sets, numeric data, or categorical data with only a few levels.

How can I apply LSH to high-cardinality categorical data where each feature might have 100 possible levels? One hot encoding seems infeasible to me. A 100 tree ensemble could have 10,000 one-hot vectors.