Method and system for indexing and searching databases

• US 7,136,851 B2
• Filed: 05/14/2004
• Issued: 11/14/2006
• Est. Priority Date: 05/14/2004
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ma, Wei-Ying, Wen, Ji-Rong
• Primary Examiner(s): Bruce, David
• Assistant Examiner(s): Sanders, Aaron J.
• Application Number:
  US10/846,776
• Publication Number:
  US 20050256865A1
• Time in Patent Office: 914 Days
• Field of Search: 707/2, 707/3, 707/5, 707/4
• US Class Current: 707/770
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9532 Query formulation
• CPC Class Codes: G06F 16/9538 Presentation of query results
• CPC Class Codes: Y10S 707/962 Entity-attribute-value
• 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

Abstract

A search system generates an index for databases by generatively sampling the databases and uses that index to identify and formulate queries for searching the databases. The generated index is referred to as a domain-attribute index and contains a domain-level index and site-level indexes. A site-level index for a database maps site attributes to distinct attribute values within the database. The domain-level index for a domain maps attribute values to database and site attribute pairs that contain those attribute values. To generate a site-level index for a database within a certain domain, the search system starts out with an initial set of the sample data for that domain. The search system generates sampling queries based on the sample data and submits the sampling queries to a database. The search system updates the site-level index based on the sampling results and uses the results to generate more sampling queries.

Claims

1. A method in a computer system for searching web databases, the method comprising:

providing of mapping of attribute and attribute value pairs to web databases that contain the attribute and attribute value pairs, the mapping being generated by sampling the web databases;

receiving an unstructured query having terms;

identifying, from the unstructured query, terms that are attribute terms that correspond to an attribute of a web database;

identifying, from the unstructured query, terms that are attribute value terms that correspond to an attribute value of a web database;

for each pair of identified attribute terms and identified attribute value terms,

formulating a query with an attribute corresponding to the identified attribute term set to the identified attribute value term; and

when the mapping indicates that a web database has an attribute and an attribute value pair that corresponds to the pair of the identified attribute term and the identified attribute value term used to formulate the query, submitting the formulated query to the web database.

2. The method of claim 1 wherein the mapping is a domain-attribute index.

3. The method of claim 2 wherein the domain-attribute index provides, for a plurality of attribute values, each contained within at least one attribute of one entry of one web database, a mapping from the attribute value to a web database and attribute of that web database that contains that attribute value in that attribute of an entry of that web database.

4. The method of claim 2 wherein the domain-attribute index provides, for each web database and for each attribute within that web database, a mapping to distinct attribute values that are contained within that attribute of an entry within that database.

5. The method of claim 2 wherein the domain-attribute index includes a domain-level index and a site-level index.

6. A method in a computer system for searching web databases, the method comprising:

receiving pairs of attributes and attribute values;

formulating a query for each received pair;

identifying web databases to submit the formulated queries using a domain-attribute index, the domain-attribute index providing, for a plurality of attribute values, each contained within at least one attribute of one entry of one web database, a mapping from the attribute value to a web database and attribute of that web database that contains that attribute value in that attribute of an entry of that web database, the mapping being generated by sampling the web databases by submitting queries to the web databases with various combinations of attribute and attribute value pairs; and

submitting the formulated queries to the identified web databases.

7. The method of claim 6 wherein the domain-attribute index includes a domain-level index and a site-level index.

8. A method in a computer system for sampling databases within a domain, the method comprising:

providing sets of attribute values for attributes of the domain (See e.g. col. 1, lines 58–

59, ‘

means for storing a value based index of selected attributes’

); and

for each of a plurality of databases to sample,

for each of a plurality of attribute and an-attribute value pairs selected from the provided sets,

submitting a query to the database that queries the selected attribute of the pair with the attribute value of the pair, wherein the submitted query generates a result; and

generating a mapping between the attributes of the database and attribute values when the result indicates that the database contains the attribute and the attribute value pair of the submitted query.

9. The method of claim 8 including updating the sets of attribute values for attributes of the domain based on the result so that an attribute value from an updated set can be used when a query is next submitted.

10. The method of claim 8 wherein the generated mapping is a domain-attribute index.

11. The method of claim 10 wherein the generated mapping is a site-level index.

12. The method of claim 10 wherein the generated mapping is a domain-level index.

13. The method of claim 8 wherein an attribute is selected that has the smallest number of distinct attribute values.

14. The method of claim 8 wherein an attribute value is selected that has the largest number of occurrences among attribute values that have not yet been selected.

15. The method of claim 8 including providing a correspondence table that maps a domain attribute to database-specific attributes for the databases.

16. The method of claim 15 wherein the submitting of a query includes using the correspondence table to determine for a domain attribute a database-specific attribute for the database to which the query is to be submitted.

17. The method of claim 15 including generating a mapping for each database that maps database-specific attributes of the database to attribute values contained in the database.

18. A computer system for generating a mapping between attribute values and databases having attributes with the attribute values, the databases being in a domain, comprising:

a component that provides attributes and attribute values for the domain;

a component that, for each of a plurality of pairs of provided attributes and provided attribute values, submits to each database a query for querying the attribute of the pair for the attribute value of the pair and that receives a result of each submitted query; and

a component that generates from the received results a mapping that indicates which databases contain which attribute values for which attributes.

19. The computer system of claim 18 wherein the component that generates the mapping maps each attribute value to the databases and attributes of the databases that contain the attribute value.

20. The computer system of claim 18 wherein the component that generates the mapping maps each attribute of a database to the attribute values of that attribute contained within the database.

21. The computer system of claim 18 including a component that receives a query, identifies an attribute and attribute value of the received query, identifies from the mapping databases that contain the identified attribute with the identified attribute value, and submits queries for the identified attribute with identified attribute value to the identified databases.

22. The computer system of claim 18 including a component that adds new attributes and attribute values to the provided attributes and provided attribute values based on the results so that a new attribute and a new attribute value can be used when a query is next submitted.

23. The computer system of claim 18 wherein the plurality of pairs of provided attributes and provided attribute values are selected randomly.

24. The computer system of claim 18 wherein a provided attribute is selected that has the smallest number of distinct provided attribute values.

25. The computer system of claim 18 wherein a provided attribute value is selected that has the largest number of occurrences among provided attribute values that have not yet been selected.

26. The computer system of claim 18 including a correspondence table that maps a domain attribute to database-specific attributes for the databases.

27. The computer system of claim 26 wherein the component that submits a query uses the correspondence table to determine for a domain attribute a database-specific attribute for the database to which the query is to be submitted.