Back to results
US 8,527,497 B2Granted
Composite term index for graph data
AssigneeFacebook, Inc.
InventorsSanjeev Singh, Bret Steven Taylor, Paul Buchheit, James Norris, Tudor Bosman, Benjamin Darnell
Life of this patent
Estimating the term…
Abstract
An indexing system for graph data. In particular implementations, the indexing system provides for denormalization and replica index functionality to improve query performance.
Claims8
An apparatus comprising:
- an index stored in one or more memory devices, the index comprising:
- a plurality of index entries that each comprise a term and a document identifier, at least one of the index entries comprising:
- a document identifier corresponding to a data object of a plurality of data objects;
- and
- a composite term comprising two or more data-object attributes;
- and one or more index servers operative to:
- access a query comprising one or more attribute values;
- search the index against the attribute values to identify one or more data objects that match the query;
- and
- return one or more object identifiers corresponding to one or more identified data objects that match the query;
- and
- a term producer operative to:
- access a data object comprising a plurality of data-object attributes;
- parse the data object to create one or more index entries for the data object;
- and
- output a set of document-identifier term pairs, each pair comprising a type based on the corresponding object types of the data objects, wherein at least one of the terms is a composite term, the document-identifier-term pairs comprising:
- a connection type and source pair comprising:
- a document identifier of a source object;
- and
- a composite term identifying a connection type of an edge object and a document identifier of a destination object;
- a connection and source pair comprising:
- a document identifier of a source object;
- and
- a composite term identifying a connection and a document identifier of a destination object;
- a connection type and destination pair comprising:
- a document identifier of a destination object;
- and
- a composite term identifying a connection type of an edge object and a document identifier of a source object;
- or
- a connection and destination pair comprising:
- a document identifier of a destination object;
- and
- a composite term identifying a connection and a document identifier of a source object.
30 more elements
A method comprising:
- storing, by one or more memory devices, an index comprising:
- a plurality of index entries that each comprise a term and a document identifier, at least one of the index entries comprising:
- a document identifier corresponding to a data object of a plurality of data objects;
- and
- a composite term comprising two or more data-object attributes;
- and
- accessing, by one or more index servers, a query comprising one or more attribute values;
- searching, by the index servers, the index against the attribute values to identify one or more identified data objects that match the query;
- returning, by the index servers, one or more object identifiers corresponding to one or more identified data objects that match the query;
- accessing, by one or more term producers, a data object comprising a plurality of data-object attributes;
- parsing, by the term producers, the data object to create one or more index entries for the data object;
- and
- outputting, by the term producers, a set of document-identifier term pairs, each pair comprising a type based on the corresponding object types of the data objects, wherein at least one of the terms is a composite term, the document-identifier-term pairs comprising:
- a connection type and source pair comprising:
- a document identifier of a source object and a composite term identifying a connection type of an edge object and a document identifier of a destination object;
- a connection and source pair comprising:
- a document identifier of a source object;
- and
- a composite term identifying a connection and a document identifier of a destination object;
- a connection type and destination pair comprising:
- a document identifier of a destination object;
- and
- a composite term identifying a connection type of an edge object and a document identifier of a source object;
- or
- a connection and destination pair comprising:
- a document identifier of a destination object;
- and
- a composite term identifying a connection and a document identifier of a source object.
25 more elements
Dependencies are inferred from the claim text.