LAF: a new XML encoding and indexing strategy for keyword-based XML   search

doi:10.1002/cpe.2906

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

	LAF: a new XML encoding and indexing strategy for keyword-based XML search
	Deng, Zhi-Hong ; Xiang, Yong-Qing ; Gao, Ning
刊名	concurrency and computation practice experience
	2013
关键词	XML keyword search LAF two-layer index ABS SLCA DOCUMENTS
DOI	10.1002/cpe.2906
英文摘要	As a large number of corpuses are represented, stored and published in XML format, how to find useful information from XML databases has become an increasingly important issue. Keyword search enables web users to easily access XML data without the need to learn a structured query language or to study complex data schemas. Most existing indexing strategies for XML keyword search are based upon Dewey encoding. In this paper, we proposed a new encoding method called Level Order and Father (LAF) for XML documents. With LAF encoding, we devised a new index structure, called two-layer LAF inverted index, which can greatly decrease the space complexity compared with Dewey encoding-based inverted index. Furthermore, with two-layer LAF inverted index, we proposed a new keyword query algorithm called Algorithm based on Binary Search (ABS) that can quickly find all Smallest Lowest Common Ancestor. We experimentally evaluate two-layer LAF inverted index and ABS algorithm on four real XML data sets selected from Wikipedia. The experimental results prove the advantages of our index method and querying algorithm. The space consumed by two-layer LAF index is less than half of that consumed by Dewey inverted index. Moreover, ABS is about one to two orders of magnitude faster than the classic Stack algorithm. Concurrency and Computation: Practice and Experience, 2012.(c) 2012 Wiley Periodicals, Inc.; Computer Science, Software Engineering; Computer Science, Theory & Methods; SCI(E); EI; 0; ARTICLE; 11; 1604-1621; 25
语种	英语
内容类型	期刊论文
源URL	[http://ir.pku.edu.cn/handle/20.500.11897/152273]
专题	信息科学技术学院
推荐引用方式 GB/T 7714	Deng, Zhi-Hong,Xiang, Yong-Qing,Gao, Ning. LAF: a new XML encoding and indexing strategy for keyword-based XML search[J]. concurrency and computation practice experience,2013.
APA	Deng, Zhi-Hong,Xiang, Yong-Qing,&Gao, Ning.(2013).LAF: a new XML encoding and indexing strategy for keyword-based XML search.concurrency and computation practice experience.
MLA	Deng, Zhi-Hong,et al."LAF: a new XML encoding and indexing strategy for keyword-based XML search".concurrency and computation practice experience (2013).