Skip navigation

Classification-Aware Hidden-Web Text Database Selection

Authors: Ipeirotis, Panagiotis G.
Gravano, Luis
Issue Date: 6-Mar-2006
Publisher: Stern School of Business, New York University
Series/Report no.: CeDER-06-04
Abstract: Many valuable text databases on the web have non-crawlable contents that are ``hidden'' behind search interfaces. Metasearchers are helpful tools for searching over multiple such ``hidden-web'' text databases at once through a unified query interface. An important step in the metasearching process is database selection, or determining which databases are the most relevant for a given user query. The state-of-the-art database selection techniques rely on statistical summaries of the database contents, generally including the database vocabulary and the associated word frequencies. Unfortunately, hidden-web text databases typically do not export such summaries, so previous research has developed algorithms for constructing approximate content summaries from document samples extracted from the databases via querying. We present a novel ``focused probing'' sampling algorithm that detects the topics covered in a database and adaptively extracts documents that are representative of the topic coverage of the database. Our algorithm is the first that constructs content summaries that include the frequencies of the words in the database. Unfortunately, Zipf's law practically guarantees that, for any relatively large database, content summaries built from moderately sized document samples will fail to cover many low-frequency words; in turn, incomplete content summaries might negatively affect the database selection process, especially for short queries with infrequent words. To enhance the sparse document samples and improve the database selection decisions, we exploit the fact that topically similar databases tend to have similar vocabularies, so samples extracted from databases with a similar topical focus can complement each other. We have developed two database selection algorithms that exploit this observation. The first algorithm proceeds hierarchically and selects the best category for a query, and then sends the query to the appropriate databases in the chosen category. The second algorithm uses ``shrinkage,'' a statistical technique for improving parameter estimation in the face of sparse data, to enhance the database content summaries with category-specific words. We describe how to modify existing database selection algorithms to adaptively decide --at run-time-- whether shrinkage is beneficial for a query. A thorough evaluation over a variety of databases, including 315 real web databases as well as TREC data, suggests that the proposed sampling methods generate high-quality content summaries and the database selection algorithms produce significantly more relevant database selection decisions and overall search results than existing algorithms.
Appears in Collections:CeDER Working Papers
IOMS: Information Systems Working Papers

Files in This Item:
File Description SizeFormat 
CeDER-06-04.pdf992.94 kBAdobe PDFView/Open

Items in FDA are protected by copyright, with all rights reserved, unless otherwise indicated.