关键词: 可扩展标记语言（XML）, 关键字查询, 列存储

Abstract: Considering that existing methods suffer from redundant computation when processing XML keyword queries based on SLCA (smallest lowest common ancestor) semantics, this paper proposes a new inverted list based on column storage, namely CList, to avoid the problem of repeatedly storing the same value in inverted lists. Based on CList, the paper proposes an efficient algorithm, i.e., TDCOL (top-down SLCA computation based on column storage), which processes all node IDs in CList in a top-down way to accelerate the overall performance. For a given keyword query Q={k1, k2, ..., km} and each of its common ancestor node, TDCOL processes it just once to get all qualified results, thus can reduce the time complexity to [O(m×|LID1|×lb|Skmaxch(v)|),] where [|LID1|] is the number of distinct IDs in the shortest inverted list of Q, while [Skmaxch(v)] is the child set of v, which has the largest number of child nodes among all processed nodes that contain some keywords of Q. The experimental results demonstrate the performance benefits of the proposed method in adding keyword search on XML data.

Key words: extensible markup language (XML), keyword search, column storage