skip to main content
10.1145/2124295.2124340acmconferencesArticle/Chapter ViewAbstractPublication PageswsdmConference Proceedingsconference-collections
research-article

Language models for keyword search over data graphs

Published: 08 February 2012 Publication History

Abstract

In keyword search over data graphs, an answer is a non-redundant subtree that includes the given keywords. This paper focuses on improving the effectiveness of that type of search. A novel approach that combines language models with structural relevance is described. The proposed approach consists of three steps. First, language models are used to assign dynamic, query-dependent weights to the graph. Those weights complement static weights that are pre-assigned to the graph. Second, an existing algorithm returns candidate answers based on their weights. Third, the candidate answers are re-ranked by creating a language model for each one. The effectiveness of the proposed approach is verified on a benchmark of three datasets: IMDB, Wikipedia and Mondial. The proposed approach outperforms all existing systems on the three datasets, which is a testament to its robustness. It is also shown that the effectiveness can be further improved by augmenting keyword queries with very basic knowledge about the structure.

References

[1]
H. Achiezra, K. Golenberg, B. Kimelfeld, and Y. Sagiv. Exploratory keyword search on data graphs. In SIGMOD, 2010.
[2]
S. Agrawal, S. Chaudhuri, and G. Das. Dbxplorer: A system for keyword-based search over relational databases. In ICDE, 2002.
[3]
G. Bhalotia, A. Hulgeri, C. Nakhe, and S. Chakrabarti. Keyword searching and browsing in databases using banks. In ICDE, pages 431--440, 2002.
[4]
J. Coffman and A. C. Weaver. A framework for evaluating database keyword search strategies. In CIKM, 2010.
[5]
J. Coffman and A. C. Weaver. Structured data retrieval using cover density ranking. In KEYS, pages 115--126, 2010.
[6]
E. Demidova, X. Zhou, and W. Nejdl. Iqp: Incremental query construction, a probabilistic approach. In ICDE, 2010.
[7]
B. Ding, J. X. Yu, S. Wang, L. Qin, X. Zhang, and X. Lin. Finding top-k min-cost connected trees in databases. In ICDE, pages 836--845, 2007.
[8]
S. Elbassuoni1, M. Ramanath, R. Schenkel, M. Sydow, and G. Weikum1. Language-model-based ranking for queries on rdf-graphs. In CIKM, 2009.
[9]
K. Golenberg, B. Kimelfeld, and Y. Sagiv. Keyword proximity search in complex data graphs. In SIGMOD, 2008.
[10]
H. He, H. Wang, J. Yang, and P. S. Yu. Blinks: Ranked keyword searches on graphs. In SIGMOD, 2007.
[11]
V. Hristidis, L. Gravano, and Y. Papakonstantinou. Efficient ir-style keyword search over relational databases. In VLDB, pages 850--861, 2003.
[12]
V. Hristidis and Y. Papakonstantinou. Discover: Keyword search in relational databases. In VLDB, 2002.
[13]
V. Kacholia, S. Pandit, S. Chakrabarti, S. Sudarshan, and R. Desai. Bidirectional expansion for keyword search on graph databases. In VLDB, pages 505--516, 2005.
[14]
E. Kandogan, R. Krishnamurthy, S. Raghavan, S. Vaithyanathan, and H. Zhu. Avatar semantic search: a database approach to information retrieval. In SIGMOD, 2006.
[15]
F. Liu, C. Yu, W. Meng, and A. Chowdhury. Effective keyword search in relational databases. In SIGMOD, pages 563--574, 2006.
[16]
Y. Luo, X. Lin, W. Wang, and X. Zhou. SPARK: top-k keyword query in relational databases. In SIGMOD, pages 115--126, 2007.
[17]
Y. Mass, M. Ramanath, Y. Sagiv, and G. Weikum. Iq: The case for iterative querying for knowledge. In CIDR, 2011.
[18]
J. Pound, I. F. Ilyas, and G. Weddell. Expressive and flexible access to web-extracted data: A keyword-based structured query languag. In SIGMOD, 2010.
[19]
C. Zhai and J. Lafferty. A study of smoothing methods for language models applied to information retrieval. ACM Trans. Inf. Syst., 22(2):179--214, 2004.

Cited By

View all
  • (2020)Efficient keyword search over graph-structured data based on minimal covered r-cliquesFrontiers of Information Technology & Electronic Engineering10.1631/FITEE.180013321:3(448-464)Online publication date: 1-Apr-2020
  • (2020)An Attribute-Specific Ranking Method Based on Language Models for Keyword Search over GraphsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2018.287986332:1(12-25)Online publication date: 1-Jan-2020
  • (2014)Knowledge Management for Keyword Search over Data GraphsProceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management10.1145/2661829.2661846(2051-2053)Online publication date: 3-Nov-2014
  • Show More Cited By

Index Terms

  1. Language models for keyword search over data graphs

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    WSDM '12: Proceedings of the fifth ACM international conference on Web search and data mining
    February 2012
    792 pages
    ISBN:9781450307475
    DOI:10.1145/2124295
    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: 08 February 2012

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. data graphs
    2. language models
    3. ranking
    4. semantic weights

    Qualifiers

    • Research-article

    Conference

    Acceptance Rates

    Overall Acceptance Rate 498 of 2,863 submissions, 17%

    Upcoming Conference

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)6
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 20 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2020)Efficient keyword search over graph-structured data based on minimal covered r-cliquesFrontiers of Information Technology & Electronic Engineering10.1631/FITEE.180013321:3(448-464)Online publication date: 1-Apr-2020
    • (2020)An Attribute-Specific Ranking Method Based on Language Models for Keyword Search over GraphsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2018.287986332:1(12-25)Online publication date: 1-Jan-2020
    • (2014)Knowledge Management for Keyword Search over Data GraphsProceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management10.1145/2661829.2661846(2051-2053)Online publication date: 3-Nov-2014
    • (2014)An Empirical Performance Evaluation of Relational Keyword Search TechniquesIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2012.22826:1(30-42)Online publication date: 1-Jan-2014
    • (2014)Keyword Search on Graphs Based on Content and StructureProceedings of the 9th International Conference on Wireless Algorithms, Systems, and Applications - Volume 849110.1007/978-3-319-07782-6_68(760-772)Online publication date: 23-Jun-2014
    • (2013)A personal perspective on keyword search over data graphsProceedings of the 16th International Conference on Database Theory10.1145/2448496.2448500(21-32)Online publication date: 18-Mar-2013
    • (2013)Search on Graphs: Theory Meets EngineeringWeb Technologies and Applications10.1007/978-3-642-37401-2_3(3-6)Online publication date: 2013

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media