Method for creating an information closure model

• US 6,539,378 B2
• Filed: 11/30/2001
• Issued: 03/25/2003
• Est. Priority Date: 11/21/1997
• Status: Expired due to Term

• Current Assignee: A9.com Incorporated (Amazon.com, Inc.)
• Original Assignee: Amazon.com, Inc.
• Inventors: Gupta, Ashish, Norvig, Peter, Rajaraman, Anand
• Primary Examiner(s): Homere, Jean R.
• Assistant Examiner(s): Wassum, Luke S
• Application Number:
  US10/000,235
• Publication Number:
  US 20020062222A1
• Time in Patent Office: 480 Days
• Field of Search: 707/1-5, 707/10, 707/100-101, 707/102
• US Class Current: 1/1
• CPC Class Codes: G06F 16/86 Mapping to a database
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

According to the invention, a method is provided for forming an information closure of a plurality of rows in a listing stack built by a wrapper program for accessing semistructured information. This method includes removing a first row from the listing stack and computing a cross product of the fields in the first row. A step of adding this cross product to a list of accepted rows can also be part of the method. For each remaining row in the listing stack, the method includes a step of computing a selective cross product according to a plurality of steps. In one step, a result is initialized to empty. Then, for each row in the list of accepted rows, a step of determining for a first new row from the accepted row, extended with the non-empty fields of the remaining row is performed. The method can also include a step of determining a second new row from the remaining row, extended with the non-empty fields in the accepted row. Thereupon, a step of adding the two new rows to the result can be performed. Repeating the determining steps and the adding step for all rows in the list of accepted rows, and removing from the result any identical rows can provide an information closure.

Claims

1. A method of forming an information closure of a plurality of information units, dividable into a first unit and a plurality of remaining units, each unit having at least one of a plurality of fields, for accessing semistructured information, comprising the steps:

computing a cross product of the fields in a first unit;

adding said cross product to a list of accepted units;

for each remaining unit r in said plurality of remaining units, computing a selective cross product from said remaining unit r and said list of accepted units; and

removing from the list of accepted units at least one of a plurality of units having identical fields,

wherein said information units are derived from a source of semistructured information, and

wherein said computing a selective cross product step further comprises the steps;

initializing a result to empty;

for each accepted unit r″

in said list of accepted units, determining a unit r′

containing accepted unit r″ and

at least one of a plurality of non-empty fields in remaining unit r;

determining a new unit n′

containing remaining unit r and at least one of a plurality of non-empty fields in accepted unit r″

;

adding r′ and

n′

to result; and

repeating the two determining steps and adding step above for all accepted units r″

in said list of accepted units.

2. The method of claim 1 wherein said units comprise rows in a listing stack.

3. The method of claim 1 wherein said information units contain information about shopping items.

4. The method of claim 1 wherein said information units contain information about job listings.

5. The method of claim 1 wherein said information units contain information about real estate listings.

6. The method of claim 1 wherein said source of semistructured information comprises a plurality of web pages.

7. A method of forming an information closure of a plurality of rows, having at least one of a plurality fields, in a listing stack of a wrapper program for accessing semistructured information, comprising the steps:

removing a first row from said listing stack, leaving a plurality of remaining rows in said listing stack;

computing a cross product of the fields in the first row from said listing stack;

adding said cross product of said fields in said first row to a list of accepted rows;

for each remaining row r in said plurality of remaining rows in said listing stack, computing a selective cross product from said remaining row r and said list of accepted rows, comprising the steps;

initializing a result to empty;

for each accepted row r″

in said list of accepted rows,

determining a row r′

containing accepted row r″ and

at least one of a plurality non-empty fields in remaining row r;

determining a new row n′

containing remaining row r and at least one of a plurality non-empty fields in accepted row r″

;

adding rows r′ and

n′

to result;

repeating the two determining steps and adding step above for all accepted rows r″

in said list of accepted rows;

repeating the computing a selective cross product step above for all remaining rows r in said listing stack;

removing from the list of accepted rows at least one of a plurality rows having identical fields; and

providing the result as the information closure,

wherein said rows are derived from a source of semistructured information.

8. The method of claim 7 wherein said rows contain information about shopping items.

9. The method of claim 7 wherein said rows contain information about job listings.

10. The method of claim 7 wherein said rows contain information about real estate listings.

11. The method of claim 7 wherein said source of semistructured information comprises a plurality of web pages.

12. The method of claim 7 wherein a default field value is copied into a row only if there is no other row having a value for the field, given the current state of the row.

13. A system for computing an information closure of a plurality of information units, dividable into a first unit and a plurality of remaining units, each unit having at least one of a plurality of fields, for accessing semistructured information, comprising:

a computer readable medium for containing said plurality of information; and

a processor means operatively disposed to;

compute a cross product of the fields in a first unit;

add said cross product to a list of accepted units;

for each remaining unit r in said plurality of remaining units, compute a selective cross product from said remaining unit r and said list of accepted units; and

remove from the list of accepted units at least one of a plurality of units having identical fields;

wherein said processor means is further operatively disposed to perform the computing of the selective cross product, which further comprises;

initializing a result to empty;

for each accepted unit r″

in said list of accepted units, determining a unit r′

containing accepted unit r″ and

at least one of a plurality of non-empty fields in remaining unit r;

determining a new unit n′

containing remaining unit r and at least one of a plurality of non-empty fields in accepted unit r″

;

adding r′ and

n′

to result; and

repeating the two determining operations and adding operation for all accepted units r″

in said list of accepted units.

14. The system of claim 13 wherein said units comprise rows in a listing stack.

15. The system of claim 13 wherein said information units contain information about shopping items.

16. The system of claim 13 wherein said information units contain information about job listings.

17. The system of claim 13 wherein said information units contain information about real estate listings.

18. The system of claim 13 wherein said source of semistructured information comprises a plurality of web pages.

19. A computer programming product for computing an information closure of a plurality of information units, dividable into a first unit and a plurality of remaining units, each unit having at least one of a plurality of fields, for accessing semistructured information, comprising:

code for computing a cross product of the fields in a first unit;

code for adding said cross product to a list of accepted units;

code for computing a selective cross product from said remaining unit r and said list of accepted units for each remaining unit r in said plurality of remaining units;

code for removing from the list of accepted units at least one of a plurality of units having identical fields; and

a computer readable medium for containing said codes,

wherein said code for computing a selective cross product further comprises;

code for initializing a result to empty;

code for determining a unit r′

containing accepted unit r″ and

at least one of a plurality of non-empty fields in remaining unit r, for each accepted unit r″

in said list of accepted units;

code for determining a new unit n′

containing remaining unit r and at least one of a plurality of non-empty fields in accepted unit r″

;

code for adding r′ and

n′

to result; and

code for repeatedly invoking the two codes for determining and code for adding above for all accepted units r″

in said list of accepted units.

20. The computer program product of claim 19 wherein said units comprise rows in a listing stack.

21. The computer program product of claim 19 wherein said information units contain information about shopping items.

22. The computer program product of claim 19 wherein said information units contain information about job listings.

23. The computer program product of claim 19 wherein said information units contain information about real estate listings.

24. The computer program product of claim 19 wherein said source of semistructured information comprises a plurality of web pages.