Finding Top-k Min-Cost Connected Trees in Databases
- 1 April 2007
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10636382,p. 836-845
Abstract
It is widely realized that the integration of database and information retrieval techniques will provide users with a wide range of high quality services. In this paper, we study processing an l-keyword query, p 1 , p 1 , ..., p l , against a relational database which can be modeled as a weighted graph, G(V, E). Here V is a set of nodes (tuples) and E is a set of edges representing foreign key references between tuples. Let V i ⊆ V be a set of nodes that contain the keyword p i . We study finding top-k minimum cost connected trees that contain at least one node in every subset V i , and denote our problem as GST-k When k = 1, it is known as a minimum cost group Steiner tree problem which is NP-complete. We observe that the number of keywords, l, is small, and propose a novel parameterized solution, with l as a parameter, to find the optimal GST-1, in time complexity O(3 l n + 2 l ((l + logn)n + m)), where n and m are the numbers of nodes and edges in graph G. Our solution can handle graphs with a large number of nodes. Our GST-1 solution can be easily extended to support GST-k, which outperforms the existing GST-k solutions over both weighted undirected/directed graphs. We conducted extensive experimental studies, and report our finding.Keywords
This publication has 13 references indexed in Scilit:
- Report on the DB/IR panel at SIGMOD 2005ACM SIGMOD Record, 2005
- DBXplorer: a system for keyword-based search over relational databases2003
- Efficient IR-Style Keyword Search over Relational Databases2003
- Query relaxation by structure and semantics for retrieval of logical Web documentsIEEE Transactions on Knowledge and Data Engineering, 2002
- A Polylogarithmic Approximation Algorithm for the Group Steiner Tree ProblemJournal of Algorithms, 2000
- An improved approximation scheme for the Group Steiner ProblemNetworks, 2000
- Parameterized Complexity1999
- A threshold of ln n for approximating set coverJournal of the ACM, 1998
- The anatomy of a large-scale hypertextual Web search engineComputer Networks and ISDN Systems, 1998
- The steiner problem in graphsNetworks, 1971