Index data structure for a peer-to-peer network

• US 7,664,742 B2
• Filed: 11/14/2006
• Issued: 02/16/2010
• Est. Priority Date: 11/14/2005
• Status: Active Grant

• Current Assignee: Primo M. Pettovello
• Original Assignee: Primo M. Pettovello
• Inventors: Pettovello, Primo M.
• Primary Examiner(s): Le; Uyen T.
• Application Number:
  US11/559,887
• Publication Number:
  US 20070112803A1
• Time in Patent Office: 1,190 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/134 Distributed indices
• CPC Class Codes: G06F 16/1837 Management specially adapted to peer-to-peer storage networks topology management mechanisms of peer-to-peer networks H04L67/1042
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

An index data structure has a plurality of index keys for uniquely identifying potential data object context nodes. Each index key is, in turn, associated with one or more potential context nodes. Moreover, the index key has a label that provides semantic content to a user. The index data structure further includes one or more routing tables associated with each index key that generally include a plurality of path references.

Claims

1. A computer implemented method of querying an index data structure for one or more data objects, the index data structure comprising:

a) a plurality of index keys for uniquely identifying potential data object context nodes, each index key being associated with a context node, at least one index key having a label that provides semantic content to a user; and

b) one or more routing tables associated with each index key, the one or more routing tables comprising at least 5 path references selected from a preceding peer-to-peer graph, a following peer-to-peer graph, an ancestor peer-to-peer graph, and descendent peer-to-peer graph, wherein the index data structure is stored on a digital storage medium, the method comprising the following steps that are implemented by a computer processor;

parsing a query into elementary steps;

executing the elementary steps on the index data structure; and

returning results of the query.

2. The method of claim 1 further comprising forwarding the query to one or more receiving nodes, the forwarding being initiated by a requesting node.

3. The method of claim 2 further comprising returning queries results from the one or more receiving nodes to the requesting node.

4. The method of claim 2 wherein the one or more receiving nodes are determined to be relevant based on the routing table.

5. The method of claim 2 wherein the one or more receiving nodes are determined to be relevant based on a semantic ordering.

6. The method of claim 2 wherein the query is in the XPath or XQuery language.

7. The method of claim 1 wherein the semantic content is a path to the node associated with the index key.

8. The method of claim 1 wherein a single node is associated with one or more semantic paths.

9. The method of claim 1 wherein the one or more routing tables comprises at least 10 path references.

10. The method of claim 1 wherein the one or more routing tables comprises:

at least 2 path references selected from the preceding peer-to-peer graph;

at least 2 path references selected from the following peer-to-peer graph;

at least 2 path references selected from the ancestor peer-to-peer graph; and

at least 2 path references selected from the descendent peer-to-peer graph.

11. The method of claim 1 wherein at least one data object is an object selected from the group consisting of a peer-to-peer network, an XML document, RDF files, music files, movie files, multimedia files, a collection of XML documents, a collection of distributed computers, a distributed service, a collection of distributed services, hierarchical file systems, tree data structures, XML file systems, relational database tables, multidimensional tables, computer graphics geometry space, polygon space, and combinations thereof.

12. The method of claim 1 wherein at least one data object is a peer-to-peer network.