# US 2010/0076947 A1 · Performing large scale structured search allowing partial schema changes without system downtime

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2010/0076947 A1
- Document ID: US20100076947A1
- Status: Published application
- Kind: A1
- Application number: 12/205,107
- Filed: 2008-09-05
- Published: 2010-03-25
- Earliest claimed: 2008-09-05
- Assignees: Yahoo! Inc.
- Inventors: Kaushal Kurapat; Robert Marshall; Kenneth Yung; Hongbin Qi; Mike Guangyu Cao; Alan Wada; Ryan Edmund Sue; Xuejun Wang
- Web page: https://patentgrep.com/patent/US20100076947A1

## CPC

- G06F 16/951: Indexing; Web crawling techniques
- G06F 16/2228: {Indexing structures}
- G06F 16/9538: Presentation of query results
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A method and apparatus is provided for hosting within a search engine, large-scale heterogeneous repositories of searchable and navigable content. Customers of the hosting platform are customers wanting to outsource the management of their searchable content. Content domain experts from each customer independently define a taxonomy of categories and attributes for their structured content that form a hierarchical set of nodes (a directed graph) that are mapped to a common physical search engine infrastructure. The mapping algorithm that maps unique attributes across potentially very different subject domains onto the same physical infrastructure is introduced. Once the physical structure is created, the search engine can use it for searching or navigating just within one customer's domain or users can search across multiple customer domains. When a customer makes changes to the logical structure, each individual change is categorized as compatible and incompatible, and executed in different time frames based on the amount of disruption it will require to the operational system.

## Claims

### Claim 1

A system comprising:
a set of indexes built on a set of physical attributes;
a first mapping between a first set of logical attributes and the set of physical attributes, wherein the first set of logical attributes are associated with searchable items that belong to a first repository;
a second mapping between a second set of logical attributes and the set of physical attributes, wherein the second set of logical attributes are associated with searchable items that belong to a second repository;
wherein a first logical attribute of the first set of logical attributes is mapped to a first physical attribute;
wherein a second logical attribute of the second set of logical attributes is mapped to said first physical attribute;
wherein said first logical attribute is semantically different from said second logical attribute;
wherein said set of indexes includes a first index built on said first physical attribute;
wherein said first index includes index entries for values of said first logical attribute and entries for values of said second logical attribute; and
a search engine that uses said set of indexes to find searchable items from said first repository for queries issued against said first repository, and to find searchable items from said second repository for queries issued against said second repository.

### Claim 2 (depends on 1)

The system of claim 1 wherein:
a third logical attribute of the first set of logical attributes is mapped to a second physical attribute;
a fourth logical attribute of the second set of logical attributes is mapped to a third physical attribute, that is different from said second physical attribute;
wherein said third logical attribute is semantically identical to said fourth logical attribute.

### Claim 3 (depends on 1)

The system of claim 1 wherein:
a third logical attribute of the first set of logical attributes is mapped to a second physical attribute;
a fourth logical attribute of the second set of logical attributes is mapped to said second physical attribute;
wherein said third logical attribute is semantically different to said fourth logical attribute.

### Claim 4 (depends on 1)

The system of claim 1 wherein:
a third logical attribute of the first set of logical attributes is mapped to a second physical attribute;
a fourth logical attribute of the first set of logical attributes is mapped to said second physical attribute;
wherein said first logical attribute is semantically different from said second logical attribute and the first logical attribute and the second logical attributes belong to different nodes in the hierarchy.

### Claim 5 (depends on 1)

The system of claim 1 wherein:
a third logical attribute of the first set of logical attributes is mapped to a second physical attribute;
a fourth logical attribute of the first set of logical attributes is mapped to a third physical attribute; and
wherein said first logical attribute is semantically identical to said second logical attribute.

### Claim 6 (depends on 1)

The system of claim 1 wherein the number of logical attributes in the first set of logical attributes is greater that the number of physical attributes in the set of physical attributes.

### Claim 7 (depends on 1)

The system of claim 1 wherein:
the first repository and the second repository belong to a set of repositories of searchable items having logical attributes mapped to the physical attributes; and
the number of attributes in a union of semantically different logical attributes associated with each repository in the set of repositories exceeds the number of physical attributes.

### Claim 8 (depends on 1)

The system of claim 1 further comprising data representing a plurality of nodes organized in a hierarchical structure;
wherein the hierarchical structure includes a plurality of sub-graphs;
wherein each sub-graph represents a distinct repository; and
wherein searchable item records of each sub-graph correspond to searchable items that belong to the repository represented by the sub-graph.

### Claim 9 (depends on 8)

The system of claim 8 wherein a set of logical attributes of a first node includes:
a first set of logical attributes assigned to the first node; and
a second set of logical attributes comprising of a union of logical attributes assigned to all nodes from which said first node descends in the hierarchical structure.

### Claim 10 (depends on 8)

The system of claim 8 wherein nodes of the hierarchical structure represent categories that are specific to the repository represented by the hierarchical structure.

### Claim 11

A method for searching across a plurality of repositories comprising the steps of:
storing data that defines a plurality of nodes organized in a hierarchical structure;
wherein the hierarchical structure includes a plurality of sub-graphs;
wherein each sub-graph of said plurality of sub-graphs represents a distinct repository;
receiving a request to perform a search based on a query, the request including identification information that identifies a node, and an attribute value for a particular logical attribute of said node;
reading mapping information to identify a physical attribute to which the particular logical attribute is mapped; and
using an index associated with the physical attributes to find searchable items that (a) have said attribute values for said particular logical attributes; and (b) are located, within the hierarchical structure, at or below said node.

### Claim 12 (depends on 11)

The method of claim 11 wherein said index includes index entries for values associated with one or more logical attributes, other than said particular logical attribute, that are mapped to said physical attribute.

### Claim 13 (depends on 12)

The method of claim 12 wherein the one or more logical attributes includes a logical attribute that is semantically different than said particular logical attribute.

### Claim 14 (depends on 11)

The method of claim 11 further comprising presenting a guided navigation interface, based on said hierarchical structure, to allow users to navigate to find searchable items that belong to at least one of said plurality of repositories.

### Claim 15 (depends on 14)

The method of claim 14 further comprising:
receiving user input at said guided navigation interface, that navigates to a display associated with a particular node in said hierarchical structure; and
displaying, on said display, an indication of logical attributes of said particular node;
wherein the logical attributes of said particular node include logical attributes assigned to said node, and logical attributes assigned to any node from which said particular node descends in said hierarchical structure.

### Claim 16 (depends on 14)

The method of claim 14 further comprising:
receiving user input at said guided navigation interface, that navigates to a display associated with a particular node in said hierarchical structure; and
displaying, on said display, an indication of searchable categories;
wherein the searchable categories are determined based on nodes, within the hierarchical structure, that are children of said particular node.

### Claim 17

A method for responding to a change made to a hierarchy of categories into which searchable items of a repository have been organized, the method comprising the steps:
storing a hierarchy of nodes that correspond to said hierarchy of categories;
receiving a request to make a first change to said hierarchy of nodes;
determining whether said first change is an incompatible or compatible change, wherein an incompatible change requires modification to how searchable items from said repository are indexed by a search engine, and a compatible change does not require modification to how searchable items from said repository are indexed by the search engine; and
in response to detecting that said first change is compatible, propagating the change to the search engine repository while the search engine continues to respond to search requests.

### Claim 18 (depends on 17)

The method of claim 17 further comprising the step of:
in response to detecting that said first change is incompatible, performing the steps comprising:
creating an offline copy of the repository, wherein the offline copy of the repository does not respond to end user search requests;
applying the first change to the offline copy of the repository;
re-indexing content based on the new structure of the offline copy of the repository; and
switching the offline copy of the repository to become an online repository, wherein the online repository responds to end user search requests, and responses to end user search requests reflect the first change.

### Claim 19 (depends on 18)

The method of claim 18, wherein before applying the first change to the offline copy of the repository, the first change is added to a list of pending incompatible changes.

### Claim 20 (depends on 17)

The method of claim 17 wherein:
the change causes a second node to descend from a first node; and
the step of determining whether said first change is incompatible or compatible comprises:
(a) the first node has a first instance of a particular logical attribute;
(b) a second instance of the particular logical attribute is assigned to (i) the second node, (ii) an ancestor of the second node, or (iii) a descendent of the second node; and
(c) the first and second instances of the particular logical attribute are mapped to different physical attributes indexed by the search engine; and
if (a), (b) and (c) are true, then determining that said first change is incompatible.

### Claim 21 (depends on 17)

The method of claim 17 wherein
the change causes a second node to descend from a first node; and
the step of determining whether said first change is incompatible or compatible, includes:
determining whether causing the second node to descend from the first node results in the second node, or a descendent thereof, having two or more semantically different logical attributes that map to a same physical attribute indexed by said search engine; and
if causing the second node to descend from the first node results in the second node, or a descendent thereof, having two or more semantically different logical attributes that map to the same physical attribute indexed by said search engine, then determining that said first change is incompatible.

### Claim 22 (depends on 17)

The method of claim 17 wherein
in response to receiving a plurality of changes to the hierarchy of nodes,
identifying a first set of changes that are compatible and making said first set of changes while the search engine continues to perform searches;
identifying a second set of changes that are incompatible;
adding said second set of changes to a list of pending incompatible changes;
creating an offline copy of the repository, wherein the offline copy of the repository does not respond to end user search requests;
applying all changes in the list of pending incompatible changes to the offline copy of the repository;
re-indexing content based on the new structure of the offline copy of the repository; and
switching the offline copy of the repository to become an online repository, wherein the online repository responds to end user search requests, and responses to end user search requests reflect the first change.

### Claim 23

A method for mapping logical attributes to physical attributes in a hierarchical structure of nodes comprising the steps of:
assigning to a first node a first logical attribute;
assigning to a second node a second logical attribute; and
in response to determining that a third node descends from both the first node and the second node, and that the first logical attribute matches the second logical attribute, mapping both the first logical attribute and the second logical attribute to a same physical attribute.

### Claim 24 (depends on 23)

The method of claim 23 further comprising:
identifying a set of nodes in a subgraph of the hierarchy, wherein the subgraph represents a single repository, wherein each node in the set of nodes is assigned a common first logical attribute; and
for each node in the set of nodes, mapping said common first logical attribute to a particular physical attribute, unless for a particular node, the particular physical attribute has previously been mapped to a second logical attribute where the first logical attribute is different from the second logical attribute.

### Claim 25 (depends on 11)

A computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 11.

### Claim 26 (depends on 12)

A computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 12.

### Claim 27 (depends on 13)

A computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 13.

### Claim 28 (depends on 14)

A computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 14.

### Claim 29 (depends on 15)

A computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 15.

### Claim 30 (depends on 16)

A computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 16.

### Claim 31 (depends on 17)

A computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 17.

### Claim 32 (depends on 18)

A computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 18.

### Claim 33 (depends on 19)

A computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 19.

### Claim 34 (depends on 20)

A computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 20.

### Claim 35 (depends on 21)

A computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 21.

### Claim 36 (depends on 22)

A computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 22.

### Claim 37 (depends on 23)

A computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 23.

### Claim 38 (depends on 24)

A computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 24.
