Merging Hierarchies Using Object Placement

Objects are often organized in a hierarchy to help in managing or browsing them. For example, products in a store can be divided by type (electronics, clothes, books, ...) and then by brand (Sony, Epson, Dockers, ...). Web pages at a site can also be placed in a hierarchy. For instance, a French tourist site may have categories cities, history, hotels, tours; within the cities category we have pages divided by city, and then by events, maps, restaurants. In this paper we study the problem of hierarchy integration, in particular, how to combine two related hierarchies into one, more comprehensive one. The need to integrate arises in many situations where the objects come from different systems. In our product hierarchy examplFrench tourism sitese above, we may want to provide a comparison shopping service that offers products from two stores; in our tourism example, we may want to build a meta- web-site that combines the resources of two or more French tourism sites. To simplify the problem, we study how to merge one hierarchy into a second known base hierarchy, by copying references to objects into the base hierarchy, and perhaps by adding some categories into the base hierarchy.