Hierarchical directory mapping for category-constrained meta-search

Hierarchical category directories, in which categories are recursively partitioned into sub-categories, have been provided by many information sources, such as news, online stores and shopping websites. Such information sources categorize instances in their databases, and support category-constrained search in which one usually navigates along the category directory to select a category, and then submits a query to find objects in the selected category whose descriptions match the query. As more and more online sources are available, it is challenging to build a meta-search system which provides a unified directory and a meta-search capability to search and access all sources from different websites in one query submission. One of the fundamental problems in building such a meta-search system is category mapping which maps the selected category in the unified directory to categories provided by the information sources. In this paper, we develop an efficient algorithm for category mapping between hierarchical directories. Our algorithm is based on the following two techniques: consistency refinement and hierarchical substitution, which are developed with extensive use of hierarchical structures. Experiment shows that our approach substantially improves previous approaches, and can be used to implement automatic category mapping for meta-search systems which support category-constrained search.