XML Keyword Query Processing on Disk based Index using Top Down Approach

Nikita R. Alai, A. S. Vaidya


From the past many years there has been much scope in efficiently replying to the Extended Markup Language (XML) keyword queries. Limitations of the existing system can be listed as the common-ancestor-repetition (CAR) and visitinguseless-nodes (VUN) issues. In order to solve the CAR problem, we hereby introduce a generic top-down strategy to answer a given keyword query. The meaning of this top-down method is that we will be visiting all the common ancestor (CA) nodes in approaches like depth-wise, left-to-right and by introducing generic approach it can be concluded that our implementation is not related to query semantics. So as to solve the issue of VUN, we implement to make use of child nodes, instead of descendant. We would be showing that for the purpose of faster document retrieval, the usage of tree is better than usage of array.Algorithms like LList based, Hash search based are performed for improved performance. We are using disk based index approach to reduce memory load.The advantage of the tree data structure over traditional array data structure is the searching process is more efficient and time saving.

Full Text:



Junfeng Zhou, Wei Wang, Ziyang Chen and Jeffrey Xu Yu, “Top-Down

XML Keyword Query Processing”,in IEEE Transactions on Knowledge

and Data Engineening,Volume:28,Issue: 5, May 1 2016,pp. 1340-1353.

L. Kircher, M. Grossniklaus, C. Grun, and M. H. Scholl, “Efficient

structural bulk updates on the pre/dist/size XML encoding”, in Proc. IEEE

st Int. Conf. Data Eng., 2015, pp. 447-458.

M. K. Agarwal and K. Ramamritham, “Enabling generic keyword search

over raw XML data”, in Proc. 31st Int. Conf. Data Eng., 2015, pp. 1496-

J. Li, C. Liu, and J. X. Yu, “Context-based diversification for keyword

queries over XML data”,in IEEE Transactions on Knowledge and Data

Engineering, vol. 27, no. 3, Mar. 2015, pp. 660-672.

Yu-Rong Cheng, Ye Yuan, Jia-Yu Li, Lei Chen and Guo-Ren Wang,

“Keyword Query over Error-Tolerant Knowledge Bases”,in Journal of

Computer Science and Technology, DOI. 10.1007/s11390-016-1658-y,

July 2016, pp. 702-719.

Da Yan, James Cheng, Fan Yang, Yi Lu, John C. S. Lui, Qizhen Zhang

and Wilfred Ng, “A General Purpose Query Centric Framework for

Querying Big Graphs”, in Proceedings of the VLDB Endowment, Vol. 9,

No. 7, 2016, pp. 564-575.

Jing Wang, Nikos Ntarmos and Peter Triantafillou, “Indexing Query

Graphs to Speedup Graph Query Processing”, in Proc. 19th International

Conference on Extending Database Technology (EDBT), March 15-18,

, ISBN 978-3-89318-070-7.

Ajay B. Gadicha, A. S. Alvi, Vijay B. Gadicha and S. M. Zaki,

“Top-Down Approach Process Built on Conceptual Design to Physical

Design Using LIS, GCS Schema”, in International Journal of Engineering

Sciences & Emerging Technologies, Volume 3, Issue 1, August 2012, pp.


Jeremy Barbay, Alejandro Lopez-Ortiz and Tyler Lu, “Faster Adaptive Set

Intersections for Text Searching”, in Proceeding WEA’06 Proceedings of

the 5th international conference on Experimental Algorithms, May 24-27,

, pp. 146-157.

Yi Chen, Wei Wang and Ziyang Liu, “Keyword-based search and

exploration on databases”, in 2011 IEEE 27th International Conference

on Data Engineering, DOI. 10.1109/ICDE.2011.5767958, 16 May 2011,

pp. 1380-1383.

Dimitris Tsirogiannis, Sudipto Guha and Nick Koudas, “Improving the

Performance of List Intersection”, in Journal Proceedings of the VLDB

Endowment, Volume 2, Issue 1, August 2009,pp. 838-849.

Vishwakarma Singh, Bo Zong, and Ambuj K. Singh, “Nearest Keyword

Set Search in Multi-Dimensional Datasets”, in IEEE Transactions On

Knowledge And Data Engineering, Vol. 28, No. 3, March 2016, pp. 741-

Evandrino G. Barros, Fernando G. D. C. Ferreira and Alberto H. F.

Laender, “Parallelizing Multiple Keyword Queries over XML Streams”,

in Data Engineering Workshops (ICDEW), 2016 IEEE 32nd International

Conference, June 2016, pp. 1-4.

A John, M Sugumaran, and RS Rajesh, “Indexing And Query Processing

Techniques In Spatio-Temporal Data”, in Ictact Journal On Soft Computing,

Volume 06, Issue 03, April 2016, pp. 1198-1217.

Guimei Liu, Andre Suchitra, and Limsoon Wong, “A performance

study of three disk-based structures for indexing and querying frequent

itemsets”, in Proceedings of the VLDB Endowment, Vol. 6, No. 7, May

, pp. 505-516.

Nikita R. Alai and A.S. Vaidya, “A Survey: Top-Down Xml Keyword

Query Processing”, in Global Journal of Advanced Engineering Technologies

(GJAET), Volume 5, Issue 4- 2016, ISSN (Online): 2277-6370

& ISSN (Print):2394-0921, pp. 426-430.

B. Q. Truong, S. S. Bhowmick, C. E. Dyreson and A. Sun, “MESSIAH:

Missing element-conscious SLCA nodes search in XML data”, in Proc.

SIGMOD, 2013, pp. 37-48.

C. E. Dyreson, S. S. Bhowmick and R. Grapp, “Querying virtual

hierarchies using virtual prefix-based numbers”, in Proc. ACM SIGMOD

International Conference Manage. Data, 2014, pp. 791-802.

Khanh Nguyen and Jinli Cao, “Exploit Keyword Query Semantics

and Structure of Data for Effective XML Keyword Search”, in Proc.

st Australasian Database Conference, Brisbane, Australia, Volume 104,

January 2010, pp. 133-140.

J. Lu, T. W. Ling, C. Y. Chan and T. Chen, “From region encoding to

extended dewey: On efficient processing of XML twig pattern matching”,

in Proc. 31st Int. Conf. Very Large Data Base, 2005, pp. 193-204.


  • There are currently no refbacks.


Copyright © IJETT, International Journal on Emerging Trends in Technology