Optimal algorithms for crawling a hidden database in the web
Publication in refereed journal


摘要A hidden database refers to a dataset that an organization makes accessible on the web by allowing users to issue queries through a search interface. In other words, data acquisition from such a source is not by following static hyper-links. Instead, data are obtained by querying the interface, and reading the result page dynamically generated. This, with other facts such as the interface may answer a query only partially, has prevented hidden databases from being crawled effectively by existing search engines. This paper remedies the problem by giving algorithms to extract all the tuples from a hidden database. Our algorithms are provably efficient, namely, they accomplish the task by performing only a small number of queries, even in the worst case. We also establish theoretical results indicating that these algorithms are asymptotically optimal - i.e., it is impossible to improve their efficiency by more than a constant factor. The derivation of our upper and lower bound results reveals significant insight into the characteristics of the underlying problem. Extensive experiments confirm the proposed techniques work very well on all the real datasets examined. © 2012 VLDB Endowment.
著者Sheng C., Zhang N., Tao Y., Jin X.
期刊名稱Proceedings of the VLDB Endowment
詳細描述organized by VLDB endowment,
頁次1112 - 1123

上次更新時間 2020-14-10 於 02:12