NDLI: Efficient query processing for XML keyword queries based on the IDList index

Content Provider	Springer Nature Link
Author	Zhou, Junfeng Bao, Zhifeng Wang, Wei Zhao, Jinjia Meng, Xiaofeng
Copyright Year	2013
Abstract	Keyword search over XML data has attracted a lot of research efforts in the last decade, where one of the fundamental research problems is how to efficiently answer a given keyword query w.r.t. a certain query semantics. We found that the key factor resulting in the inefficiency for existing methods is that they all heavily suffer from the common-ancestor-repetition problem. In this paper, we propose a novel form of inverted list, namely the IDList; the IDList for keyword $$k$$ consists of ordered nodes that directly or indirectly contain $$k$$ . We then show that finding keyword query results based on the smallest lowest common ancestor and exclusive lowest common ancestor semantics can be reduced to ordered set intersection problem, which has been heavily optimized due to its application in areas such as information retrieval and database systems. We propose several algorithms that exploit set intersection in different directions and with or without using additional indexes. We further propose several algorithms that are based on hash search to simplify the operation of finding common nodes from all involved IDLists. We have conducted an extensive set of experiments using many state-of-the-art algorithms and several large-scale datasets. The results demonstrate that our proposed methods outperform existing methods by up to two orders of magnitude in many cases.
Starting Page	25
Ending Page	50
Page Count	26
File Format	PDF
ISSN	10668888
Journal	The VLDB Journal
Volume Number	23
Issue Number	1
e-ISSN	0949877X
Language	English
Publisher	Springer Berlin Heidelberg
Publisher Date	2013-05-01
Publisher Place	Berlin, Heidelberg
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	XML Keyword Query Processing LCA SLCA ELCA Database Management
Content Type	Text
Resource Type	Article
Subject	Information Systems Hardware and Architecture

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

ELCA evaluation for keyword search on probabilistic XML data

Reasoning with patterns to effectively answer XML keyword queries

Efficient subtree results computation for XML keyword queries

Quasi-SLCA Based Keyword Query Processing over Probabilistic XML Data

Coding-based Join Algorithms for Structural Queries on Graph-Structured XML Document

Top-k answers for XML keyword queries

Improved selectivity estimator for XML queries based on structural synopsis

Sampling-based estimators for subset-based queries

Attribute grammars for scalable query processing on XML streams

Efficient query processing for XML keyword queries based on the IDList index

Similar Documents

ELCA evaluation for keyword search on probabilistic XML data

Reasoning with patterns to effectively answer XML keyword queries

Efficient subtree results computation for XML keyword queries

Quasi-SLCA Based Keyword Query Processing over Probabilistic XML Data

Coding-based Join Algorithms for Structural Queries on Graph-Structured XML Document

Top-k answers for XML keyword queries

Improved selectivity estimator for XML queries based on structural synopsis

Sampling-based estimators for subset-based queries

Attribute grammars for scalable query processing on XML streams

Efficient query processing for XML keyword queries based on the IDList index