Efficient sentence retrieval based on syntactic structure

This paper proposes an efficient method of sentence retrieval based on syntactic structure. Collins proposed Tree Kernel to calculate structural similarity. However, structual retrieval based on Tree Kernel is not practicable because the size of the index table by Tree Kernel becomes im-practical. We propose more efficient al-gorithms approximating Tree Kernel: Tree Overlapping and Subpath Set. These algo-rithms are more efficient than Tree Kernel because indexing is possible with practical computation resources. The results of the experiments comparing these three algo-rithms showed that structural retrieval with Tree Overlapping and Subpath Set were faster than that with Tree Kernel by 100 times and 1,000 times respectively.