research-article

Effective, design-independent XML keyword search

Authors:

Arash Termehchy,

Marainne WinslettAuthors Info & Claims

CIKM '09: Proceedings of the 18th ACM conference on Information and knowledge management

Pages 107 - 116

https://doi.org/10.1145/1645953.1645970

Published: 02 November 2009 Publication History

Abstract

Keyword search techniques that take advantage of XML structure make it very easy for ordinary users to query XML databases, but current approaches to processing these queries rely on intuitively appealing heuristics that are ultimately ad hoc. These approaches often retrieve irrelevant answers, overlook relevant answers, and cannot rank answers appropriately. To address these problems for data-centric XML, we propose coherency ranking (CR), a domain- and database design-independent ranking method for XML keyword queries that is based on an extension of the concept of mutual information. With CR, the results of a keyword query are invariant under schema reorganization. We analyze how previous approaches to XML keyword search approximate CR, and present efficient algorithms to perform CR. Our empirical evaluation with 65 user-supplied queries over two real-world XML data sets shows that CR has better precision and recall and provides better ranking than all previous approaches.

References

[1]

Z. Bao et al. E ffective XML Keyword Search with Relevance Oriented Ranking. In ICDE 2009.

Digital Library

[2]

G. Bhalotoa et al. Keyword Searching and Browsing in databases using BANKS. In ICDE 2002.

Digital Library

[3]

S. Chakrabarti, K. Puniyani, and S. Das. Optimizing Scoring Functions and Indexes for Proximity Search in Type-annotated Corpora. In WWW 2007.

Digital Library

[4]

S. Cohen et al. XSearch: A Semantic Search Engine for XML. In VLDB 2003.

Digital Library

[5]

T. Cover and J. Thomas. Elements of Information Theory. Wiley, 1983.

Digital Library

[6]

L. Guo et al. XRANK: Ranked Keyword Search over XML Documents. In SIGMOD 2003.

Digital Library

[7]

V. Hristidis et al. Keyword Proximity Search in XML Trees. TKDE, 18(5):525--536, 2006.

Digital Library

[8]

Y. Ke, J. Cheng, and W. Ng. Mining Quantitative Correlated Patterns Using an Information-Theoretic Approach. In SIGKDD 2006.

Digital Library

[9]

M. Kendall and J. D. Gibbons. Rank Correlation Methods. 1990.

[10]

G. Li et al. Ef fective Keyword Search for Valuable LCAs over XML Documents. In CIKM 2007.

Digital Library

[11]

Y. Li, C. Yu, and H. V. Jagadish. Schema-Free XQuery. In VLDB 2004.

Digital Library

[12]

Z. Liu and Y. Chen. Reasoning and Identifying Relevant Matches for XML Keyword Search. In VLDB 2008.

Digital Library

[13]

C. Manning, P. Raghavan, and H. Schutze. An Introduction to Information Retrieval. 2008.

Digital Library

[14]

A. Termehchy and M. Winslett. E ffective Ranking of XML Keyword Search Results (Extended Version). Technical Report UIUCDCS-R-2009-3043, 2009.

[15]

S. Watanabe. Information Theoretical Analysis of Multivariate Correlation. IBM Journal of Research and Development, 4(1):66.

Digital Library

[16]

J. Wen, J. Nie, and H. Zhang. Clustering User Queries of a Search Engine. In WWW 2001.

Digital Library

[17]

I. Witten and E. Frank. Data Mining: Practical Machine Learning Tools and Techniques. 2005.

Digital Library

[18]

Y. Xu and Y. Papakonstantinou. Efficient Keyword Search for Smallest LCAs in XML Databases. In SIGMOD 2005.

Digital Library

[19]

X. Yin, J. Han, and J. Yang. Searching for Related Objects in Relational Databases. In SSDBM 2005.

Digital Library

[20]

M. Zaki. Efficiently Mining Frequent Trees in a Forest. TKDE, 17(8):1021--1035, 2005.

Digital Library

Cited By

Amini LKeyvanpour M(2019)A Crowdsourcing-based Approach for Efficient XML Keyword Search2019 5th International Conference on Web Research (ICWR)10.1109/ICWR.2019.8765281(16-21)Online publication date: Apr-2019
https://doi.org/10.1109/ICWR.2019.8765281
Truong BS Bhowmick SDyreson CSun ARoss KSrivastava DPapadias D(2013)MESSIAHProceedings of the 2013 ACM SIGMOD International Conference on Management of Data10.1145/2463676.2463699(37-48)Online publication date: 22-Jun-2013
https://dl.acm.org/doi/10.1145/2463676.2463699
Termehchy AWinslett M(2011)Using structural information in XML keyword search effectivelyACM Transactions on Database Systems (TODS)10.1145/1929934.192993836:1(1-39)Online publication date: 18-Mar-2011
https://dl.acm.org/doi/10.1145/1929934.1929938
Show More Cited By

Index Terms

Effective, design-independent XML keyword search
1. Information systems
  1. Data management systems
    1. Database management system engines
      1. Database query processing
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Database theory
      1. Database query processing and optimization (theory)

Recommendations

Using structural information in XML keyword search effectively

The popularity of XML has exacerbated the need for an easy-to-use, high precision query interface for XML data. When traditional document-oriented keyword search techniques do not suffice, natural language interfaces and keyword search techniques that ...
Towards an Effective XML Keyword Search

Inspired by the great success of information retrieval (IR) style keyword search on the web, keyword search on XML has emerged recently. The difference between text database and XML database results in three new challenges: 1) Identify the user search ...
Return specification inference and result clustering for keyword search on XML

Keyword search enables Web users to easily access XML data without the need to learn a structured query language and to study possibly complex data schemas. Existing work has addressed the problem of selecting qualified data nodes that match keywords ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

CIKM '09: Proceedings of the 18th ACM conference on Information and knowledge management

November 2009

2162 pages

ISBN:9781605585123

DOI:10.1145/1645953

General Chairs:
David Cheung
University of Hong Kong, Hong Kong
,
Il-Yeol Song
Drexel University, USA
,
Program Chairs:
Wesley Chu
UCLA, USA
,
Xiaohua Hu
Drexel University, USA
,
Jimmy Lin
University of Maryland, USA

Copyright © 2009 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 November 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

CIKM '09

Sponsor:

CIKM '09: Conference on Information and Knowledge Management

November 2 - 6, 2009

Hong Kong, China

Acceptance Rates

Overall Acceptance Rate 1,861 of 8,427 submissions, 22%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
320
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Amini LKeyvanpour M(2019)A Crowdsourcing-based Approach for Efficient XML Keyword Search2019 5th International Conference on Web Research (ICWR)10.1109/ICWR.2019.8765281(16-21)Online publication date: Apr-2019
https://doi.org/10.1109/ICWR.2019.8765281
Truong BS Bhowmick SDyreson CSun ARoss KSrivastava DPapadias D(2013)MESSIAHProceedings of the 2013 ACM SIGMOD International Conference on Management of Data10.1145/2463676.2463699(37-48)Online publication date: 22-Jun-2013
https://dl.acm.org/doi/10.1145/2463676.2463699
Termehchy AWinslett M(2011)Using structural information in XML keyword search effectivelyACM Transactions on Database Systems (TODS)10.1145/1929934.192993836:1(1-39)Online publication date: 18-Mar-2011
https://dl.acm.org/doi/10.1145/1929934.1929938
Termehchy AWinslett MChodpathumwan Y(2011)How schema independent are schema free query interfaces?Proceedings of the 2011 IEEE 27th International Conference on Data Engineering10.1109/ICDE.2011.5767880(649-660)Online publication date: 11-Apr-2011
https://dl.acm.org/doi/10.1109/ICDE.2011.5767880
Termehchy AWinslett M(2010)EXTRUCTProceedings of the VLDB Endowment10.14778/1920841.19210473:1-2(1593-1596)Online publication date: 1-Sep-2010
https://dl.acm.org/doi/10.14778/1920841.1921047
Li JLiu CZhou RWang W(2010)Suggestion of promising result types for XML keyword searchProceedings of the 13th International Conference on Extending Database Technology10.1145/1739041.1739108(561-572)Online publication date: 22-Mar-2010
https://dl.acm.org/doi/10.1145/1739041.1739108
Termehchy AWinslett M(2010)Keyword search for data-centric XML collections with long text fieldsProceedings of the 13th International Conference on Extending Database Technology10.1145/1739041.1739106(537-548)Online publication date: 22-Mar-2010
https://dl.acm.org/doi/10.1145/1739041.1739106

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents