Simple and efficient Hash sketching for tree-structured data

Tree sketching seeks to sketch each tree-structured data instance as a low-dimensional vector, with similarity between tree pairs accurately preserved. Unfortunately, a multitude of current methods, especially the well-known Neural Network (NN) framework, face serious computational challenge due to massive parameter learning, which renders them unworkable on devices with limited computational capacity. In this paper, we present a simple and efficient tree sketching model named TreeHash, which achieves an excellent trade-off between accuracy and efficiency. To be more precise, the proposed TreeHash model fast extracts a subtree with the designated depth for each node based on the directed sparse matrix indexing operation formatted by compressed sparse row. This leads to the time required to extract a single subtree being linear in the number of edges within that subtree. Furthermore, it swiftly sketches multisets composed of the extracted subtrees via Locality-Sensitive Hashing (LSH), which does not need learning and introduces just a theoretically small error. The extensive experimental results indicate that the TreeHash method not only competes effectively with the state-of-the-art methods but also remarkably reduces runtime.