TY - GEN
T1 - pq-Hash
T2 - 1st International Workshop on Graph Database, IWGD 2010, 1st International Workshop on Advanced Techniques on XML Data Management, XMLDM 2010, 2nd International Workshop on WCMT 2010, Held in Conj. with WAIM 2010
AU - Li, Fei
AU - Wang, Hongzhi
AU - Hao, Liang
AU - Li, Jianzhong
AU - Gao, Hong
PY - 2010
Y1 - 2010
N2 - Approximate matching between large tree sets is broadly used in many applications such as data integration and XML de-duplication. However, most existing methods suffer for low efficiency, thus do not scale to large tree sets. pq-gram is a widely-used method with high quality of matches. In this paper, we propose pq-hash as an improvement to pq-gram. As the base of pq-hash, a randomized data structure, pq-array, is developed. With pq-array, large trees are represented as small fixed sized arrays. Sort-merge and hash join technique is applied based on these pq-arrays to avoid nested-loop join. From theoretical analysis and experimental results, retaining high join quality, pq-hash gains much higher efficiency than pq-gram.
AB - Approximate matching between large tree sets is broadly used in many applications such as data integration and XML de-duplication. However, most existing methods suffer for low efficiency, thus do not scale to large tree sets. pq-gram is a widely-used method with high quality of matches. In this paper, we propose pq-hash as an improvement to pq-gram. As the base of pq-hash, a randomized data structure, pq-array, is developed. With pq-array, large trees are represented as small fixed sized arrays. Sort-merge and hash join technique is applied based on these pq-arrays to avoid nested-loop join. From theoretical analysis and experimental results, retaining high join quality, pq-hash gains much higher efficiency than pq-gram.
UR - https://www.scopus.com/pages/publications/78649914571
U2 - 10.1007/978-3-642-16720-1_13
DO - 10.1007/978-3-642-16720-1_13
M3 - 会议稿件
AN - SCOPUS:78649914571
SN - 3642167195
SN - 9783642167195
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 125
EP - 134
BT - Web-Age Information Management - WAIM 2010 International Workshops
Y2 - 15 July 2010 through 17 July 2010
ER -