Searching dynamically bundled goods with pairwise relations

ABSTRACT

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 offering 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 finds 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 offerings 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.

REFERENCES

• 1: Please visit travel package search demo page at http://pemdia.watson.ibm.com:8000/travel.html or http://129.34.24.23:8000/travel.html.
• 2: Martin Aigner, Combinatorial search, John Wiley & Sons, Inc., New York, NY, 1988
• 3: Yannis Bakos , Erik Brynjolfsson, Bundling Information Goods: Pricing, Profits, and Efficiency, Management Science, v.45 n.12, p.1613-1630, December 1999 [doi>10.1287/mnsc.45.12.1613]
• 4: G. D. Eppen, et al., "Bundling-new products, new markets, low risk," Sloan Management Review, pp. 7-14, 1991.
• 5: Ronald Fagin, Combining fuzzy information from multiple systems (extended abstract), Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.216-226, June 04-06, 1996, Montreal, Quebec, Canada [doi>10.1145/237661.237715]
• 6: Myron Flickner , Harpreet Sawhney , Wayne Niblack , Jonathan Ashley , Qian Huang , Byron Dom , Monika Gorkani , Jim Hafner , Denis Lee , Dragutin Petkovic , David Steele , Peter Yanker, Query by Image and Video Content: The QBIC System, Computer, v.28 n.9, p.23-32, September 1995 [doi>10.1109/2.410146]
• 7: E. A. Lee and D. G. Messerschmitt, "Digital communication," published by Kluwer Academic Publishers, 2nd Ed., 1994.
• 8: C. S. Li, J. R. Smith, L. D. Bergman, and V. Castelli, "Sequential processing for content-based retrieval of composite objects," SPIE Storage and Retrieval for Image and Video Database VI, pp. 2--13, 1998.
• 9: Apostol Natsev , Rajeev Rastogi , Kyuseok Shim, WALRUS: a similarity retrieval algorithm for image databases, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.395-406, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 10: Euripides G. M. Petrakis , Christos Faloutsos, Similarity Searching in Medical Image Databases, IEEE Transactions on Knowledge and Data Engineering, v.9 n.3, p.435-447, May 1997 [doi>10.1109/69.599932]
• 11: Martin L. Puterman, Dynamic Programming and Its Application, Academic Press, Inc., Orlando, FL, 1979

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Performance

Keywords:
bundle goods, commerce search, relationship graph