Efficient subtree results computation for XML keyword queries

Abstract

In this paper, we focus on efficient construction of restricted subtree (RSubtree) results for XML keyword queries on a multicore system. We firstly show that the performance bottlenecks for existing methods lie in 1) computing the set of relevant keyword nodes(RKNs) for each subtree root node, 2) constructing the corresponding RSubtree, and 3) parallel execution. We then propose a two-step generic top-down subtree construction algorithm, which computes SLCA/ELCA nodes in the first step, and parallelly gets RKNs and generates RSubtree results in the second step, where generic means that 1) our method can be used to compute different kinds of subtree results, 2) our method is independent of the query semantics; top-down means that our method constructs each RSubtree by visiting nodes of the subtree constructed based on an RKN set level-by-level from left to right, such that to avoid visiting as many useless nodes as possible. The experimental results show that our method is much more efficient than existing ones according to various metrics.

Keywords

XML / SLCA/ELCA / RSubtree / RKNs / parallel

References

[1] Zhou R, Liu C F, Li J X. Fast ELCA computation for keyword queries on XML data. In: Proceedings of the 13th International Conference on Extending Database Technology. 2010, 549-560

[2] Xu Y, Papakonstantinou Y. Efficient keyword search for smallest LCAs in XML databases. In: Proceedings of the ACM SIGMOD International Conference on Management of Data. 2005, 537-538

[3] Chen L J, Papakonstantinou Y. Supporting top-K keyword search in XML databases. In: Proceedings of the 26th International Conference on Data Engineering. 2010, 689-700

[4] Guo L, Shao F, Botev C, Shanmugasundaram J. XRANK: ranked keyword search over XML Documents. In: Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data. 2003, 16-27

[5] Li Y Y, Yu C, Jagadish H V. Schema-free XQuery. In: Proceedings of the 13th International Conference on Very Large Data Bases. 2004, 72-83

[6] Kong L B, Gilleron R, Lemay A. Retrieving meaningful relaxed tightest fragments for XML keyword search. In: Proceedings of the 12th International Conference on Extending Database Technology. 2009, 815-826

[7] Liu Z Y, Chen Y. Reasoning and identifying relevant matches for XML keyword search. The Proceedings of the VLOB Endowment, 2008, 1(1): 921-932

[8] Xu Y, Papakonstantinou Y. Efficient LCA based keyword search in XML data. In: Proceedings of the 11th International Conference on Extending Database Technology. 2008, 535-546

[9] Tatarinov I, Viglas S, Beyer K S, Shanmugasundaram J, Shekita E J, Zhang C. Storing and querying ordered XML using a relational database system. In: Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data. 2002, 204-215

[10] Hristidis V, Koudas N, Papakonstantinou Y, Srivastava D. Keyword proximity search in XML Trees. IEEE Transactions on Knowledge and Date Engineering, 2006, 18(4): 525-539

[11] Zhou J F, Bao Z F, Chen Z Y, Ling T W. Fast result enumeration for keyword queries on XML data. In: Proceedings of the 17th International Conference on Database Systems for Advanced Applications. 2012, 95-109

[12] Zhou J F, Bao Z F, Wang W, Ling T W, Chen Z Y, Lin X D, Guo J F. Fast SLCA and ELCA computation for XML keyword queries based on set intersection. In: Proceedings of the IEEE 28th International Conference on Data Engineering. 2012, 905-916

[13] Zhou J F, Bao Z F, Chen Z Y, Lan G X, Lin X D, Ling T W. Top-down SLCA computation based on list partition. In: Proceedings of the 17th International Conference on Database Systems for Advanced Applications. 2012, 172-184

[14] Pandis I, Johnson R, Hardavellas N, Ailamaki A. Data-oriented transaction execution. The Proceedings of the VLOB Endowment, 2010, 3(1): 928-939

[15] Tsirogiannis D, Guha S, Koudas N. Improving the performance of list intersection. The Proceedings of the VLOB Endowment, 2009, 2(1): 838-849

[16] Bordawekar R, Lim L, Kementsietsidis A, K B. Statistics-based parallelization of XPath queries in shared memory systems. In: Proceedings of the 13th International Conference on Extending Database Technology. 2010, 159-170

[17] Qin L, Yu J X, Chang L J. Ten thousand SQLs: parallel keyword queries computing. The Proceedings of the VLOB Endowment, 2010, 3(1): 58-69

[18] Zhou J F, Zhao J J, Wang B, Zhao X M, Chen Z Y. Efficient Msubtree results computation for XML keyword queries. In: Proceedings of the 14th International Conference on Web-Age Information Management. 2013, 472-477

[19] Sun C, Chan C Y, Goenka A K. Multiway SLCA-based keyword search in XML data. In: Proceedings of the 16th International Conference on World Wide Web. 2007, 1043-1052

[20] Wang W Y, Wang X L, Zhou A Y. Hash-search: an efficient SLCAbased keyword search algorithm on XML documents. In: Proceedings of the 14th International Conference on Database Systems for Advanced Applications. 2009, 496-510

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg