Paper Info
Title
Pacoks: Progressive Ant-Colony-Optimization-Based Keyword Search Over Relational Databases
Abstract
Keyword search over relational databases makes it easier to retrieve information from structural data. One solution is to first represent the relational data as a graph, and then find the minimum Steiner tree containing all the keywords by traversing the graph. However, the existing work involves substantial costs even for those based on heuristic algorithms, as the minimum Steiner tree problem is proved to be an NP-hard problem. In order to reduce the response time for a single search to a low level, a progressive ant-colony-optimization-based algorithm, called PACOKS, is proposed here, which achieves the best answer in a step-by-step manner, through the cooperation of large amounts of searches over time, instead of in an one-step manner by a single search. Through this way, the high costs for finding the best answer, are shared among large amounts of searches, so that low cost and fast response time for a single search is achieved. Extensive experimental results based on our prototype show that our method can achieve better performance than those state-of-the-art methods.
Year
DOI
Venue
2016
10.1007/978-3-319-39958-4_9
WEB-AGE INFORMATION MANAGEMENT, PT II
Field
DocType
Volume
Ant colony optimization algorithms,Data mining,Heuristic,Relational database,Steiner tree problem,Computer science,Keyword search,Response time,Compression ratio,Traverse
Conference
9659
ISSN
Citations 
PageRank 
0302-9743
0
0.34
References 
Authors
13
3
Name
Order
Citations
PageRank
林子雨112910.80
Qian Xue200.34
yongxuan lai311220.24