Searching Dynamically Bundled Goods with Pairwise Relations

Economics research has long recognized that bundling enables savings in production and transaction costs, promotes complementary among the bundle components and sorts consumers according to their valuations. Sellers employ market analysis and intelligence to extract the most surplus. In the age of electronic commerce with low product information access cost, buyers can take advantage of the benefits of bundling by performing dynamic composition of goods from multiple companies oering heterogeneous products and services. These goods, with the proper mix of sources and quantity, may offer additional discounts and benefits, which would not have risen should purchase decisions were made independently. A prominent example is packaged travel, which often involves air, hotel and car rentals. An optimal travel package search not only takes advantage of the lowest available prices of air, hotel and car rental individually but also exploits various discounts through business partnerships between service providers. Today's database infrastructure to support the search of dynamically bundled goods, however, is insufficient. The complex search operations involving cross join of many product categories with hundreds or thousands of offerings can be formulated as SQL queries. But executing these queries in a traditional database is inefficient. This paper proposes an I/O conscious, dynamic programming based algorithm for bundle search. The proposed algorithm nds the top-K combinations of goods abstracted by a linear relationship graph. Experimental results indicate that the proposed algorithm achieves more than two orders of magnitude speedup over cross join, and it is more than an order-of-magnitude faster than the simple dynamic programming solution. The performance gap further widens as the number of product categories and the number of oerings within each category increase. This paper characterizes the computational and I/O complexity of the proposed algorithm and suggests extensions to search bundles with more complex relationships.