Layered solution for SLCA problem in xml information retrieval

doi:10.1360/jos180919

CORC > 北京大学 > 信息科学技术学院

	Layered solution for SLCA problem in xml information retrieval
	Kong, Ling-Bo ; Tang, Shi-Wei ; Yang, Dong-Qing ; Wang, Teng-Jiao ; Gao, Jun
刊名	ruan jian xue baojournal of software
	2007
DOI	10.1360/jos180919
英文摘要	SLCA (smallest lowest common ancestor) problem is a basic task of keyword search in XML information retrieval. It means to find all the nodes corresponding to the tightest subtrees in XML data, which involves the given keywords. Xu, et al., illustrate three algorithms-Indexed lookup eager (ILE), stack algorithm and scan eager (SE), and manifest that ILE has the best performance. Different from the complicated-B+-tree-based ILE algorithm, this paper proposes a layered solution for SLCA problem, named as LISA (layered intersection scan algorithm). It benefits from the distribution rule of SLCA nodes in XML tree, and calculates the SLCA nodes level by level (the deepest level runs first). That is, based on the retrieved Dewey codes corresponding to given keywords, the Dewey codes of SLCA nodes can be gotten by intersecting the prefix Dewey codes of each level. Compared with the ILE algorithm, LISA solutions need not sophisticated data structures, and have comparatively runtime performance. There are two instances following the LISA idea, called LISA I and LISA II respectively. They are distinguished from each other according to whether keeping Dewey codes in computation or transforming Dewey codes into integer sequences. Extensive experiments evaluate the performance of algorithms and prove the efficiency of LISA II.; EI; 0; 4; 919-932; 18
语种	英语
内容类型	期刊论文
源URL	[http://ir.pku.edu.cn/handle/20.500.11897/294214]
专题	信息科学技术学院
推荐引用方式 GB/T 7714	Kong, Ling-Bo,Tang, Shi-Wei,Yang, Dong-Qing,et al. Layered solution for SLCA problem in xml information retrieval[J]. ruan jian xue baojournal of software,2007.
APA	Kong, Ling-Bo,Tang, Shi-Wei,Yang, Dong-Qing,Wang, Teng-Jiao,&Gao, Jun.(2007).Layered solution for SLCA problem in xml information retrieval.ruan jian xue baojournal of software.
MLA	Kong, Ling-Bo,et al."Layered solution for SLCA problem in xml information retrieval".ruan jian xue baojournal of software (2007).