.png){kind=icon}
.png){kind=icon}
Return
Simple and efficient Hash sketching for tree-structured data
.png){kind=icon}
PRE
AI
DOI：10.1016/j.eswa.2024.125973.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 wellknown 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.
Keywords:
Tree-structured data
Tree sketching
Locality-sensitive hashing
Subtree extraction
Journal
IF:
7.5
Papers:
2.9W
Citations:
10.2W