Keyword search on structured and semi-structured data
Published 29 June 2009
Yi Chen, Wei Wang, Ziyang Liu, Xuemin Lin
Citations174
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
An overview of the state-of-the-art techniques for supporting keyword search on structured and semi-structured data, including query result definition, ranking functions, result generation and top-k query processing, snippet generation, result clustering, query cleaning, performance optimization, and search quality evaluation are given.
Abstract
Empowering users to access databases using simple keywords can relieve the users from the steep learning curve of mastering a structured query language and understanding complex and possibly fast evolving data schemas. In this tutorial, we give an overview of the state-of-the-art techniques for supporting keyword search on structured and semi-structured data, including query result definition, ranking functions, result generation and top-k query processing, snippet generation, result clustering, query cleaning, performance optimization, and search quality evaluation. Various data models will be discussed, including relational data, XML data, graph-structured data, data streams, and workflows. We also discuss applications that are built upon keyword search, such as keyword based database selection, query generation, and analytical processing. Finally we identify the challenges and opportunities of future research to advance the feld.
Keywords
Computer Science
Keyword searching and browsing in databases using BANKS
872 Citations2003Gaurav Bhalotia, Arvind Hulgeri +3 more
BANKS is described, a system which enables keyword-based search on relational databases, together with data and schema browsing, and presents an efficient heuristic algorithm for finding and ranking query results.
Elsevier eBooksDiscover
787 Citations2002Vagelis Hristidis, Yannis Papakonstantinou
It is proved that DISCOVER finds without redundancy all relevant candidate networks, whose size can be data bound, by exploiting the structure of the schema and the selection of the optimal execution plan (way to reuse common subexpressions) is NP-complete.
XRANK
773 Citations2003Guo Lin, Feng Shao +2 more
The XRANK system is presented, designed to handle the novel features of XML keyword search, which naturally generalizes a hyperlink based HTML search engine such as Google and can be used to query a mix of HTML and XML documents.
DBXplorer: a system for keyword-based search over relational databases
731 Citations2003Sanjay Agrawal, Surajit Chaudhuri +1 more
DBXplorer, a system that enables keyword-based searches in relational databases using a commercial relational database and Web server and allows users to interact via a browser front-end is discussed.
BLINKS
543 Citations2007Hao He, Haixun Wang +2 more
Elsevier eBooksEfficient IR-Style Keyword Search over Relational Databases
536 Citations2003Vagelis Hristidis, Yannis Papakonstantinou +1 more
This paper adapts IR-style document-relevance ranking strategies to the problem of processing free-form keyword queries over RDBMSs, and develops query-processing strategies that build on a crucial characteristic of IR- style keyword search: only the few most relevant matches are generally of interest.
Elsevier eBooksXSEarch
518 Citations2003Sara Cohen, Jonathan Mamou +2 more
These experiments indicate that XSEarch is efficient, scalable and ranks quality results highly.
Keyword Search on Spatial Databases
485 Citations2008Ian De Felipe, Vagelis Hristidis +1 more
This work presents an efficient method to answer top-k spatial keyword queries using an indexing structure called IR2-Tree (Information Retrieval R-Tree) which combines an R- Tree with superimposed text signatures.
Bidirectional expansion for keyword search on graph databases
480 Citations2005Varun Kacholia, Shashank Pandit +4 more
This paper proposes a new search algorithm, Bidirectional Search, which improves on Backward Expanding search by allowing forward search from potential roots towards leaves, and devise a novel search frontier prioritization technique based on spreading activation.
Efficient keyword search for smallest LCAs in XML databases
466 Citations2005Yu Xu, Yannis Papakonstantinou
The core contribution, the Indexed Lookup Eager algorithm, exploits key properties of smallest trees in order to outperform prior algorithms by orders of magnitude when the query contains keywords with significantly different frequencies.
Effective keyword search in relational databases
356 Citations2006Fang Liu, Clement Yu +2 more
This paper proposes a novel IR ranking strategy for effective keyword search and is the first that conducts comprehensive experiments on search effectiveness using a real world database and a set of keyword queries collected by a major search company.
Elsevier eBooksSchema-Free XQuery
356 Citations2004Yunyao Li, Cong Yu +1 more
This work introduces the notion of Meaningful Lowest Common Ancestor Structure (MLCAS) for finding related nodes within an XML document and adds new functionality to XQuery to enable users to take full advantage of XQuery in querying XML data precisely and efficiently without requiring (perfect) knowledge of the document structure.
Principles of dataspace systems
346 Citations2006Alon Halevy, Michael J. Franklin +1 more
This paper lays out specific technical challenges to realizing DSSPs, the DSSP's ability to introspect on its content, and the use of human attention to enhance the semantic relationships in a dataspace.
Finding Top-k Min-Cost Connected Trees in Databases
320 Citations2007Bolin Ding, Jeffrey Xu Yu +4 more
This paper proposes a novel parameterized solution, with l as a parameter, to find the optimal GST-1, in time complexity O(3ln + 2l ((l + logn)n + m), where n and m are the numbers of nodes and edges in graph G, which can handle graphs with a large number of nodes.
Spark
313 Citations2007Yi Luo, Xuemin Lin +2 more
A new ranking formula is proposed by adapting existing IR techniques based on a natural notion of virtual document based on a natural notion of virtual document that is simple yet effective, and agrees with human perceptions.
Proceedings - International Conference on Data EngineeringKeyword Search in Spatial Databases: Towards Searching by Document
279 Citations2009Dongxiang Zhang, Yeow Meng Chee +3 more
This work addresses a novel spatial keyword query called the m-closest keywords (mCK) query, which aims to find the spatially closest tuples which match m user-specified keywords, and introduces a new index called the bR*-tree, which is an extension of the R-tree.
Proceedings - International Conference on Data EngineeringTop-k Exploration of Query Candidates for Efficient Keyword Search on Graph-Shaped (RDF) Data
274 Citations2009Thanh Tran, Haofen Wang +2 more
A novel keyword search paradigm for graph-structured data, focusing in particular on the RDF data model, which first compute queries from the keywords, allowing the user to choose the appropriate query, and finally, process the query using the underlying database engine.
Keyword proximity search on XML graphs
270 Citations2004Vagelis Hristidis, Yannis Papakonstantinou +1 more
This work proposes and experimentally evaluates algorithms to minimize the number of queries sent to the database to output the top-K results and provides theoretical and experimental points for the selection of the appropriate set of precomputed path relations.
Identifying meaningful return information for XML keyword search
267 Citations2007Ziyang Liu, Yi Chen
This work presents an XML keyword search engine, XSeek, to infer the semantics of the search and identify return nodes effectively and demonstrates the effectiveness of this engine.
Making database systems usable
246 Citations2007H. V. Jagadish, Adriane Chapman +5 more
A presentation data model is introduced and direct data manipulation with a schema later approach is recommended and the importance of provenance and of consistency across presentation models is stressed.
Proximity Search in Databases
195 Citations1998Roy Goldman, Narayanan Shivakumar +2 more
This paper implements a prototype search engine that uses a model based on textual proximity of keywords within each document to enable keyword searches over databases, and has found it very effective for quickly finding relevant information.
Keyword Search in Relational Databases: A Survey.
181 Citations2010Jeffrey Xu Yu, Lu Qin +1 more
This work surveys the developments on finding structural information among tuples in an RDB using an l-keyword query, Q, which is a set of keywords of size l, denoted as Q = {k1, k2, · · · , kl}.
Multiway SLCA-based keyword search in XML data
173 Citations2007Chong Sun, Chee-Yong Chan +1 more
This paper first analyzes properties of the LCA computation and proposes improved algorithms to solve the traditional keyword search problem (with only AND semantics), and extends this approach to handle general keyword search involving combinations of AND and OR boolean operators.
Proceedings - International Conference on Data EngineeringEffective XML Keyword Search with Relevance Oriented Ranking
167 Citations2009Zhifeng Bao, Tok Wang Ling +2 more
This paper designs novel formulae to identify the search for nodes and search via nodes of a query, and presents a novel XML TF*IDF ranking strategy to rank the individual matches of all possible search intentions.
Keyword proximity search in complex data graphs
163 Citations2008Konstantin Golenberg, Benny Kimelfeld +1 more
This paper presents an engine that generates all the answers with provable guarantees for keyword search over data graphs and presents a novel approach for implementing rankers destined for eliminating redundancy.
Finding and approximating top-k answers in keyword proximity search
163 Citations2006Benny Kimelfeld, Yehoshua Sagiv
This paper gives the first efficient algorithms, under data complexity, for enumerating all the answers in ranked order and for computing the top-k answers.
Proceedings of the VLDB EndowmentReasoning and identifying relevant matches for XML keyword search
140 Citations2008Ziyang Liu, Yi Cher
This work investigates an axiomatic framework that includes two intuitive and non-trivial properties that an XML keyword search technique should ideally satisfy: monotonicity and consistency, with respect to data and query and proposes a novel semantics for identifying relevant matches that satisfies both properties.
Efficient LCA based keyword search in XML data
119 Citations2008Yu Xu, Yannis Papakonstantinou
The results show that the Indexed Stack algorithm outperforms in terms of both CPU and I/O costs other algorithms by orders of magnitude when the query contains at least one low frequency keyword along with high frequency keywords.
Proceedings of the VLDB EndowmentKeyword search on external memory data graphs
115 Citations2008Bhavana Dalvi, Meghana Kshirsagar +1 more
This paper proposes a graph representation technique that combines a condensed version of the graph (the "supernode graph") which is always memory resident, along with whatever parts of the detailed graph are in a cache, to form a multi-granular graph representation.
Retrieving and organizing web pages by “information unit”
106 Citations2001Wen‐Syan Li, K. Selçuk Candan +2 more
This paper introduces and describes the use of the concept of information unit, which can be viewed as a logical Web document consisting of multiple physical pages as one atomic retrieval unit, and presents an algorithm to eAEciently retrieve information units.
Efficient Keyword Search Across Heterogeneous Relational Databases
103 Citations2007Mayssam Sayyadian, Hieu LeKhac +2 more
Kite combines schema matching and structure discovery techniques to find approximate foreign-key joins across heterogeneous databases and exploits the joins - discovered automatically across the databases - to enable fast and effective querying over the distributed data.
SQAK
99 Citations2008Sandeep Tata, Guy M. Lohman
SQAK provides a novel and exciting way to trade-off some of the expressive power of SQL in exchange for the ability to express a large class of aggregate queries using simple keywords.
Query biased snippet generation in XML search
98 Citations2008Yu Huang, Ziyang Liu +1 more
This paper identifies that a good XML result snippet should be a self-contained meaningful information unit of a small size that effectively summarizes this query result and differentiates it from others, according to which users can quickly assess the relevance of the query result.
Data clouds
87 Citations2009Georgia Koutrika, Zahra Mohammadi Zadeh +1 more
This paper proposes coupling the flexibility of keyword searches over structured data with the summarization and navigation capabilities of tag clouds to help users access a database and presents a system that offers a unified search and browse interface to a course database.
Proceedings of the VLDB EndowmentLearning to create data-integrating queries
83 Citations2008Partha Talukdar, Marie Jacob +5 more
A system with which a non-expert user can author new query templates and Web forms, to be reused by anyone with related information needs, and which learns to assign costs to sources and associations according to the user's specific information need, as a result changing the ranking of the queries used to generate results.
Towards keyword-driven analytical processing
78 Citations2007Ping Wu, Yannis Sismanis +1 more
This paper introduces "Keyword-Driven Analytical Processing" (KDAP), which combines intuitive keyword-based search with the power of aggregation in OLAP without having to spend considerable effort in organizing the data in terms that the business analyst understands, and presents the complete solution framework.
Effective keyword-based selection of relational databases
74 Citations2007Bei Yu, Guoliang Li +2 more
This paper studies the database selection problem for relational data sources, and proposes a method that effectively summarizes the relationships between keywords in a relational database based on its structure, and develops effective ranking methods based on the keyword relationship summaries.
XSeek: a semantic XML search engine using keywords
61 Citations2007Ziyang Liu, Jeffrey P. Walker +1 more
XSeek is presented, a keyword search engine that enables users to easily access XML data without the need of learning XPath or XQuery and studying possibly complex data schemas.
Précis: The Essence of a Query Answer
60 Citations2006Georgia Koutrika, Alkis Simitsis +1 more
A framework and system architecture for supporting free-form précis queries in the context of a relational database system is developed and algorithms that implement the required functionality are described.
DB&IR
57 Citations2007Gerhard Weikum
Database systems (DB) and information retrieval (IR) are two separate fields of computer science by historical accident, but only recently important killer applications are emerging with really strong desire for an integrated DB&IR platform.
Indexing Relational Database Content Offline for Efficient Keyword-Based Search
56 Citations2006Qi Su, Jennifer Widom
An architecture that supports highly efficient keyword-based search over relational databases is proposed that creates virtual documents from joining relational tuples and uses the DB2 Net Search Extender for indexing and keyword-search processing.
Proceedings of the VLDB EndowmentKeyword query cleaning
51 Citations2008Ken Q. Pu, Xiaohui Yu
This paper defines a quality metric of a keyword query, and proposes a number of algorithms for cleaning keyword queries optimally, and demonstrates that the basic optimal query cleaning problem can be solved using a dynamic programming algorithm.
Retrieving meaningful relaxed tightest fragments for XML keyword search
50 Citations2009Lingbo Kong, Rémi Gilleron +1 more
The ValidRTF algorithm not only overcomes those two problems in MaxMatch, but also satisfies the axiomatic properties deduced in [1] that an XKS technique should satisfy.
A graph method for keyword-based selection of the top-K databases
50 Citations2008Quang Hieu Vu, Beng Chin Ooi +2 more
G-KS, a novel method for selecting the top-K candidates based on their potential to contain results for a given query, is proposed, which outperforms the current state-of-the-art technique on all aspects, including precision, recall, efficiency, space overhead and flexibility of accommodating different semantics.
SPARK: A Keyword Search Engine on Relational Databases
48 Citations2008Yi Luo, Wei Wang +1 more
Relational database is the most widely adopted and mature technology for information storage and increasing amount of text data is now stored in relational databases, accompanied by increasing demands of retrieving relevant information by free-style keyword search.
Proceedings - International Conference on Data EngineeringWISE: A Workflow Information Search Engine
43 Citations2009Qihong Shao, Peng Sun +1 more
This demonstration presents an effective workflow search engine, WISE, which returns informative and concise search results, defined as the minimal views of the most specific workflow hierarchies containing matching keywords.
Proceedings - International Conference on Data EngineeringProgressive Keyword Search in Relational Databases
43 Citations2009Guoliang Li, Xiaofang Zhou +2 more
A new concept called Compact Steiner Tree (CSTree) is proposed, which can be used to approximate the Steiner tree problem for answering top-k keyword queries efficiently and achieves high search efficiency and result quality comparing to existing state-of-the-art approaches.
The VLDB JournalEfficient keyword search over virtual XML views
36 Citations2009Feng Shao, Guo Lin +5 more
A system architecture and algorithm is presented that can efficiently evaluate keyword search queries over virtual (unmaterialized) XML views and exploits indices present on the base data and thereby avoids materializing large parts of the view that are not relevant to the query results.
Finding frequent co-occurring terms in relational keyword search
35 Citations2009Yufei Tao, Jeffrey Xu Yu
This paper proposes a relevant problem called frequent co-occurring term (FCT) retrieval, and provides a faster algorithm that extracts the correct results without evaluating any KS query at all.
Answering aggregate keyword queries on relational databases using minimal group-bys
27 Citations2009Bin Zhou, Jian Pei
This paper motivates a novel problem of aggregate keyword search: finding minimal group-bys covering a set of query keywords well, which is useful in many applications and develops two interesting approaches to tackle the problem.
DaNaLIX
27 Citations2007Yunyao Li, Ishan Chaudhuri +3 more
This demonstration shows how a generic system like DaNaLIX can take advantage of domain knowledge to improve its usability and query translation accuracy and presents how domain knowledge can be obtained through user interactions in an automatic fashion.
Answering Keyword Queries on XML Using Materialized Views
23 Citations2008Ziyang Liu, Yi Chen
This paper investigates the problem and presents techniques for answering keyword queries using a minimal number of materialized views, and demonstrates the efficiency of the proposed techniques.
Proceedings - International Conference on Data EngineeringReachability Indexes for Relational Keyword Search
22 Citations2009Alexander Markowetz, Yin Yang +1 more
A comprehensive framework for reachability indexing that eliminates fruitless operations in relational keyword search and describes a range of indexes that capture various types of join reachability.
Very Large Data BasesNUITS: a novel user interface for efficient keyword search over databases
22 Citations2006Shan Wang, Zhaohui Peng +5 more
A prototype system, called NUITS, is presented, for efficiently processing keyword queries on top of a relational database, which allows users to issue simple keyword queries as well as advanced keyword queries with conditions.
Very Large Data BasesXML full-text search: challenges and opportunities
22 Citations2005Sihem Amer-Yahia, Jayavel Shanmugasundaram
An ever growing number of XML repositories are being made available for search, and a growing interest in adopting IR techniques in DBs and vice versa is demonstrated.
Proceedings of the VLDB EndowmenteXtract
17 Citations2008Yu Huang, Ziyang Liu +1 more
This work presents eXtract, a system that efficiently generates self-contained result snippets within a given size bound which effectively summarize the query results and differentiate them from one another, according to which users can quickly assess the relevance of thequery results.
Proceedings of the VLDB EndowmentAn effective and versatile keyword search engine on heterogenous data sources
11 Citations2008Guoliang Li, Jianhua Feng +2 more
EASE models unstructured, semi-structured and structured data as graphs, summarizes the graphs, and constructs graph indices instead of using traditional inverted indices for effective keyword search.