Web price optimizer of multiple-item package orders for e-commerce on the internet and method of use

[0001] 1. Field of the Invention

[0002] This invention relates to electronic commerce, more specifically in the area of price or cost comparison and optimization of multiple-item package orders. In one embodiment, the invention relates to information processing and business methods for searching, optimized calculation, organization and display of information relating to items such as books via the Internet, to facilitate comparison browsing and shopping.

[0003] 2. Prior Art

[0004] At present, some public and private search engines on the Internet permit a user to search for the lowest price or cost for one individual item, such as a book. However, there is a need for users to search for the prices of multiple items in a single session and optimize all the prices for all such items considered as a package, so that comparisons by price or another variable can easily be made. For example, a college student may be asked to purchase 3 or 4 textbooks at once for an upcoming semester in college. The student probably will be on a limited budget. Therefore, the student will be interested in finding out how all of the books can be purchased at the lowest total price. So far, this has been difficult if not impossible on the Internet.

[0005] In view of this unfilled need, it is an object of the present invention to provide a method for searching for the lowest price or cost information for multiple-item package orders on the Internet; calculating one or more optimized prices for the items both individually and grouped by online store; organizing and displaying such information in a format useful for easy price comparison and browsing; and providing a method for easily purchasing the optimized items.

[0006] To achieve the aforementioned objects, there is provided a method of searching for, calculating, organizing and displaying an optimized rank of information for multiple items on the Internet, the method comprising the steps of:

• • [0007] establishing an Internet Web site, the site operating as a computer interface for a user who wishes to search for information on at least one item;
  • [0008] receiving a search request from the user who uses communications equipment and software to access the Web site to obtain information about one or more of the items;
  • [0009] executing a computer search on the Internet for all of the items designated in the search request;
  • [0010] receiving information about the items from other Web sites or Internet databases;
  • [0011] calculating an optimized rank of all of the items considered as a package; and
  • [0012] displaying the rank to the user.

[0013] In a preferred embodiment, the invention searches for the lowest price and second lowest price data for a plurality of items, designated by users, which items are being offered for sale by Internet Web sites; records the data in two matrices; and employs algorithms that implement certain set theory operations, including Cartesian product and set union to optimize the result for all items considered as a package.

[0024] In what follows, a preferred embodiment of the present invention will be described in detail with reference to the accompanying drawings.

[0025] To utilize the invention, a user seeking the best price or cost for a plurality of items (such as books) for sale on the Internet first uses his or her personal computer, modem (or other communications device) and Web browser software to connect to the Internet and log onto a Web site of the invention.

Initiation, User Input and Search Operations

[0026] FIG. 1 illustrates an example of a user input form that is displayed to the user after the user has logged on. In this case, the form is designed for searching book titles. The invention, however, is not limited to the purchase of books. It also finds application in any situation where any group of items need to be optimized by a particular numeric variable. The variable could be purchase price, rental price, quantity, etc. The items could be books, music CDs, DVDs, magazines, videotapes, software disks, or virtually any other item that can be individually identified by name or title and arranged into a package. Thus, the invention finds application in a wide variety of business-to-consumer (B2C) and business-to-business (B2B) transactions on the Internet.

[0027] Next, the user types in the book titles (or other item descriptions) desired on the form. In the illustration, the user has entered four titles. Then, the user clicks on the “search” button to start the search, or the “optimize” button to optimize the prices for all books (i.e., calculate the lowest prices available for all books considered as a package). Next, in one embodiment, the invention looks up the ISBN number (International Standard Book Number) for each title from a database located either at the invention's Web site or at another site on the Internet. Then, a cgi (Common Gate Interface) script is executed to open a number of parallel “threads” or communication channels to all bookstores on the Internet (in this case, 56) that are believed to offer at least one of the titles for sale. Then, a search routine is executed at all bookstores simultaneously (or quickly serially) to search for each title by ISBN number. When each bookstore's search engine returns the price, availability and other information for each title, this information is communicated back to the Web site of the invention, and algorithms for the optimization, organization and display of the information are executed (discussed below).

Optimized Result Table

[0028] FIG. 2 is an example of a table of optimized search results that are returned by the invention after the user's search from FIG. 1. As can be seen, information about the books or other items is organized by bookstore, book title, number of copies requested, unit price posted at the best on-line stores which carry each particular title, availability information, shipping and handling charge, tax, total price, and hyperlink to the Web site of the bookstores where the lowest priced books may be purchased. Also shown is a grouping of titles into the lowest priced packages that are available from particular bookstores. In this example, after the approximation and optimization algorithms have been executed, the invention has determined that one bookstore, namely Barnes and Noble, offers the lowest price for the package consisting of the titles “War and Peace” and “The Twin Cities,” whereas another bookstore, namely Amazon, offers the lowest price for the package consisting of the titles “Moby Dick” and “TCP/IP.” (Two titles are shown temporarily out of stock, but this is not considered a problem because the titles may return to in-stock status in a short time.)

[0029] For other searches, it is possible that the lowest package price for all titles or other items could be available from a single bookstore, or a different bookstore may be identified for each of the titles separately in order to yield the lowest total price. A store or merchant (e.g., bookstore) index is also established with merchant identifiers.

Matrix Establishment and Pre-Computation

[0030] FIG. 3 is a flowchart showing some initial steps carried out in one embodiment of the invention, including pre-computation algorithms using matrices. To start, the user logs onto the Web site of the invention at step 100. At decision step 130, the user is asked if he or she wishes to “go shopping” for one or more books. If the answer is “yes, the user requests a search using the form of FIG. 1. Searching may be done by title, author's last name, first name, keyword or ISBN number. After the search results are returned and displayed, the user may compare price and other information from a list of all bookstores that carry the book. In decision step 150, the user is asked whether he or she wants to add the book to the “shopping cart” for an actual purchase. If “no,” then the user is returned to step 130 in the event another search is desired.

[0031] As soon as the first book is added to the shopping cart, the method of the invention executes a “pre-computation” algorithm at steps 160 and 170 (FIG. 3). The algorithm starting at step 160 is as follows:

• • [0032] (1) Establish matrix 1.
  • [0033] (2) Save the current item descriptions (book titles, etc.) into matrix 1.
  • [0034] (3) Save the best store's offering (lowest price and identifier) into matrix 1.
  • [0035] (4) Save the second best store's offering into matrix 1.

[0036] Therefore, for N items (such as titles of books), an N×2 matrix is recorded. For two items (such as books), an example of matrix 1 would be: $\hspace{1em}\left[\begin{array}{cc}\mathrm{S1a}& \mathrm{S1b}\\ \mathrm{S2a}& \mathrm{S2b}\end{array}\right]$
where

• [0037] S1a=Store with best price for item 1
• [0038] S1b=Store with 2^nd best price for item 1
• [0039] S2a=Store with best price for item 2
• [0040] S2b=Store with 2^nd best price for item 2.

[0041] The algorithm continues at step 170, where all merchant prices (not necessarily the best prices) for all items are recorded. The steps are:

• • [0042] (1) Establish matrix 2.
  • [0043] (2) Save the current item descriptions (book titles, etc.) into matrix 2.
  • [0044] (3) Save the prices offered by all stores that carry all items into matrix 2.

[0045] In a preferred embodiment, the present invention searches a total of 56 online bookstores on the Internet. Not all of these, however, will carry every title. For best results, the invention records an entry for only those bookstores that carry all titles requested by the user. As used herein, a bookstore is said to “carry” or “offer” a book if it is in the bookstore's official catalog, even if the book is temporarily out of stock. A purpose for recording all such prices in matrix 2 is to handle a situation where the lowest total price for all books considered as a package happens to be where all books are carried by one store. This is discussed in more detail below.

[0046] Therefore, for N items (such as titles of books), given M online stores that carry all N items, an N X M matrix is recorded. For two books and four stores, each of which carry both books, an example of matrix 2 would be: $\hspace{1em}\left[\begin{array}{cccc}\mathrm{Item}1\text{/}\mathrm{Store}1& \mathrm{Item}1\text{/}\mathrm{Store}2& \mathrm{Item}1\text{/}\mathrm{Store}3& \mathrm{Item}1\text{/}\mathrm{Store}4\\ \mathrm{Item}2\text{/}\mathrm{Store}1& \mathrm{Item}2\text{/}\mathrm{Store}2& \mathrm{Item}2\text{/}\mathrm{Store}3& \mathrm{Item}2\text{/}\mathrm{Store}4\end{array}\right]$

[0047] The pre-computation algorithm discussed above is repeated each time a user adds an item to the shopping cart, as shown by the sequence in FIG. 3 that cycles around the following path: step 170, decision 130, step 140, decision 150 and step 160. Each time the cycle is repeated to add another item, an additional row is added to matrix 1 and an additional row is added to matrix 2. Of course, if the user later changes his or her mind and decides to remove an item from the cart, then one row is deleted from each matrix respectively. Matrices 1 and 2 are each recorded in separate files.

Set Theory Background

[0048] The approximation and optimization algorithms of the present invention will now be discussed. For better understanding of these algorithms, it is useful to provide a brief background of set theory mathematics. A set is a collection of items called elements of the set. The elements are determined by one or more rules and are usually ordered. There are two types of notation for representing sets, namely roster notation and set-builder notation. Roster notation is a complete or implied listing of all the elements of the set. An example is: A={a, b, c, d}, which may also be called a “4-tuple.” Set-builder notation is used when the roster method is cumbersome or impossible. An example is: {x|x is a real number}. Below is a list of some commonly used symbols:

• [0049] X=Cartesian product
• [0050] ∪=set union
• [0051] c=element of
• [0052] |=such that.

[0053] In set theory and matrix operations, the Cartesian product and union operators are well-known. The “Cartesian product” X is defined as a set that is constructed from two or more given sets and comprises all pairs or other “n-tuples” of elements such that one element of the tuple is from the first set, the next element is from the second set, and so on. In mathematical notation, for a group of n sets A₁, A₂, . . . A_n, this can be expressed as: A₁X A₂X . . . A_n, and the resulting set consists of all n-tuples (m₁, . . . m_n) with m_iεA_i for i=1, 2, . . . n. The “set Union” ∪ is defined as a set that is constructed from two or more given sets and comprises all pairs or other n-tuples of elements such that each element is a number at least one of the other sets. In mathematical notation, for two sets, this can be expressed as: {x|xεA or xεB}, namely the set of x such that x is an element of set A or x is an element of set B.

Approximation and Optimization Algorithms

[0054] Turning now to FIG. 4, this figure, together with FIGS. 5-9, illustrate the approximation and optimization algorithms of the present invention. In a preferred embodiment, five situations will be considered in turn, starting with one item selected by the user and then going up to five items. Each time one item is added, the complexity of the optimization calculations increases because, of course, the number of possible combinations increases with each additional item. In fact, the number of combinations doubles with each additional item added.

[0055] To manage the varying complexity that is presented in “real world” searching by users, each situation (from N=1 to N>=5, where N is the number of titles in the shopping cart) is handled by a different sub-algorithm of the invention.

[0056] In a preferred embodiment, after the user has finished shopping at decision step 130 (FIG. 3), the user clicks on the “optimize” button on the Web site of the invention (see FIG. 1). The invention then proceeds to FIG. 4 to start the approximation algorithm. A series of four decision steps 200, 210, 220 and 230 redirects the process flow to a different sub-algorithm depending upon the number of titles N in the shopping cart. If N=1, then the flow is directed to sub-algorithm 1 of FIG. 5. If N=2, then the flow is directed to sub-algorithm 2 of FIG. 6. If N=3, then the flow is directed to sub-algorithm 3 of FIG. 7. If N=4, then the flow is directed to sub-algorithm 4 of FIG. 8. Finally, if N>=5, then the flow is directed to sub-algorithm 5 of FIG. 9.

Sub-algorithm 1

[0057] Sub-algorithm 1 is illustrated in FIG. 5. Here, only one item has been selected by the user. Thus, only one possibility need be considered—select the store with the lowest price for that title. That store has already been located in the search (see FIG. 3). Thus, to achieve optimization, the invention chooses “S1a”, meaning “store with the best price for title 1.” This result is then displayed to the user at the invention's Web site. A simplified version of the table of FIG. 2 (having only one row) would be employed to display the result.

Sub-algorithm 2

[0058] Sub-algorithm 2 is illustrated in FIG. 6. Here, two items have been selected by the user. In a preferred embodiment, the combinations considered are those from matrices 1 and 2. Although more combinations could be considered, such as every price offered by every bookstore on the Internet for each item, this is not necessary. Near perfect optimization is achieved if only the best and second best individual stores for each item are considered, plus the best (lowest-price) store carrying both items. Thus, when N=2, the 2×2 combinations from matrix 1 plus the elements of matrix 2 are considered. The 2×2 combinations are:
{(S1a, S2a), (S1a, S2b), (S1b, S2a), (S1b, S2b)}
where

• [0059] S1a=Store with best price for item 1
• [0060] S1b=Store with 2^nd best price for item 1
• [0061] S2a=Store with best price for item 2
• [0062] S2b=Store with 2^nd best price for item 2.

[0063] Using this as a starting point, the approximation algorithm of the present invention for the optimization of 2 items is then calculated using the following formula:
Select the best from: {S1a, S1b} X {S2a, S2b} ∪{(1, 1), (2, 2), (3, 3), . . . (M, M)}
where

• [0064] X=Cartesian product
• [0065] ∪=set union
• [0066] (1, 1)=First store found that carries both items
• [0067] (2, 2)=Second store found that carries both items
• [0068] (3, 3)=Third store found that carries both items
• [0069] (M, M)=Last store found that carries both items.
  Sub-algorithm 3

[0070] Sub-algorithm 3 is illustrated in FIG. 7. Here, three items have been selected by the user. In a preferred embodiment, the combinations considered are those from matrices 1 and 2. As with the case with two items, although more combinations could be considered, such as every price offered by every bookstore on the Internet for all three books, this is not necessary. Near perfect optimization is achieved if only the best and second best individual stores for each item are considered, plus the best (lowest price) store carrying all three items. Thus, when N=3, the 2×2×2 combinations from matrix 1 plus the elements of matrix 2 are considered. The 2×2×2 combinations are:
{(S1a, S2a), (S1a, S2b), (S1b, S2a), (S1b, S2b)} X {S3a, S3b}
where

• [0071] S1a=Store with best price for item 1
• [0072] S1b=Store with 2^nd best price for item 1
• [0073] S2a=Store with best price for item 2
• [0074] S2b=Store with 2^nd best price for item 2
• [0075] S3a=Store with best price for title 3
• [0076] S3b=Store with 2^nd best price for item 3
• [0077] X=Cartesian product.

[0078] Using this as a starting point, the approximation algorithm of the present invention for the optimization of 3 items is then calculated using the following formula:
Select best from: {S1a, S1b} X {S2a, S2b} X {S3a), S3b} ∪{(1, 1, 1), (2, 2, 2), (3, 3, 3), . . . , (M, M, M)}
where

• [0079] X=Cartesian product
• [0080] ∪=set union
• [0081] (1, 1, 1)=First store found that carries all 3 items
• [0082] (2, 2, 2)=Second store found that carries all 3 items, etc.
• [0083] (M, M)=Last store found that carries all 3 items.
  Sub-algorithm 4

[0084] Sub-algorithm 4 is illustrated in FIG. 8. Here, four items have been selected by the user. In the preferred embodiment, the combinations considered are those from matrices 1 and 2. As with the case with two and three items, although more combinations could be considered, such as every price offered by every bookstore on the Internet for all four books, this is not necessary. Near perfect optimization is achieved if only the best and second best individual stores for each item are considered, plus the best (lowest price) store carrying all four items. Thus, when N=4, the 2×2×2×2combinations from matrix 1 plus the elements of matrix 2 are considered. The 2×2×2×2 combinations are:
{(S1a, S2a), (S1a, S2b), (S1b, S2a), (S1b, S2b)} X {S3a, S3b} X {S4a, S4b}
where

• [0085] S1a Store with best price for item 1
• [0086] S2=Store with 2 best price for item 1
• [0087] S2a=Store with best price for item 2
• [0088] S2b=Store with 2^nd best price for item 2
• [0089] S3a=Store with best price for title 3
• [0090] S3b=Store with 2^nd best price for item 3
• [0091] S4a=Store with best price for title 4
• [0092] S4b=Store with 2^nd best price for title 4
• [0093] X=Cartesian product.

[0094] Using this as a starting point, the approximation algorithm of the present invention for the optimization of 4 items is then calculated using the following formula:
Select best from: {S1a, S1b} X {S2a, S2b} X {S3a, S3b} X {S4a, S4b} ∪ {1, 1, 1, 1,), (2, 2, 2, 2), (3, 3, 3, 3), . . . , (M, M, M, M)
where

• [0095] X=Cartesian product
• [0096] ∪=set union
• [0097] (1, 1, 1, 1)=First store found that carries all 4 items
• [0098] (2, 2, 2, 2)=Second store found that carries all 4 items, etc.
• [0099] (M, M, M, M)=Last store found that carries all 4 items.
  Sub-algorithm 5

[0100] Sub-algorithm 5 is illustrated in FIG. 9. This is the most generalized case, where five or more items (“n” items) have been selected by the user. In the preferred embodiment, the combinations considered are those from matrices 1 and 2. As with the case with sub-algorithms 2-4, although more combinations could be considered, such as every price offered by every bookstore on the Internet for all n books, this is not necessary. Near perfect optimization is achieved if only the best and second best individual stores for each item are considered, plus the best (lowest price) store carrying all n items. Thus, when n=4, the 2×2×2×2combinations from matrix 1 plus the elements of matrix 2 are considered. For large numbers of n, it is only necessary to consider 2×2×2×2 combinations for the first 4 items. The combinations for n>=5 are:
{(S1a, S2a), (S1a, S2b), (S1b, S2a), (S1b, S2b)} X {S3a, S3b} X {S4a, S4b} X {S5a, S5b} X {S6a, S6b} X . . . X {Sna, Snb}
where

• [0101] S1a=Store with best price for item 1
• [0102] S1b=Store with 2^nd best price for item 1
• [0103] S2a=Store with best price for item 2
• [0104] S2b=Store with 2^nd best price for item 2, etc.
• [0105] Sna=Store with best price for item n
• [0106] Snb=Store with 2^nd best price for title n
• [0107] X=Cartesian product.

[0108] Using this as a starting point, the approximation algorithm of the present invention for the optimization of n items is then calculated using the following formula:

[0109] Let n be number of items in shopping cart.
Select best from {S1a, S1b} X {S2a, S2b} X {S3a, S3b} X {S4a, S4b} X {S5a, S5b} X . . . X {Sna, Snb} ∪ {(1, 1, 1, 1, . . . , 1), (2, 2, 2, 2, . . . , 2), (3, 3, 3, 3, . . . 3), . . . , (M, M, M, M, . . . , M)}
where

• [0110] X=Cartesian product
• [0111] ∪=set union
• [0112] (1, 1, 1, 1, . . . , 1)=First store found that carries all n items
• [0113] (2, 2, 2, 2, . . . , 2)=Second store found that carries all n items, etc.
• [0114] (M, M, M, M, . . . , M)=Last store found that carries all n items.

[0115] The present invention provides a new software method and business method for searching for, optimizing and organizing information (such as price or cost data) for a plurality of items via the Internet.

[0116] Some advantages of the present invention include:

[0117] 1. User utility through pre-computation. The best two stores and prices for any book title or other item are recorded in a matrix file. Another matrix file is recorded for the prices of all stores that carry all items.

[0118] 2. Direct file access to obtain the price, cost or other data. The principle of “pre-computation” is hundreds of times faster than digging out the data individually or manually from the separate Web sites or stores or merchants. All data is quickly optimized upon a user pressing the “optimize” button on the Web site of the invention.

[0119] 2. Low complexity of the algorithms used. The number of combinations is bounded by 2×2×2×2=16. For example, In addition to the cheapest bookstore among all bookstores and other sites searched, the invention provides a list of all titles of books or other items.

[0120] 3. Close to optimal results. It is rarely likely that, in an optimal solution, a book or other item is chosen from an online store except from the best (lowest price) two stores corresponding to that item. Also, it is rarely likely that the user will want to purchase more than four items at once.

[0121] While the invention has been described herein with reference to certain preferred embodiments, these embodiments have been presented by way of example only, and not to limit the scope of the invention.