Semantic querying a peer-to-peer network

• US 7,039,634 B2
• Filed: 03/12/2003
• Issued: 05/02/2006
• Est. Priority Date: 03/12/2003
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Xu, Zhichen, Mahalingam, Mallik, Tang, Chunqiang
• Primary Examiner(s): Mofiz, Apu
• Assistant Examiner(s): Hicks, Michael J
• Application Number:
  US10/385,454
• Publication Number:
  US 20040181511A1
• Time in Patent Office: 1,147 Days
• Field of Search: 707/100, 707/102, 707/3, 707/4, 707/5, 700/3, 700/4, 709/239, 709/243, 709/245, 370/389
• US Class Current: 1/1
• CPC Class Codes: G06F 16/1834 implemented based on peer-to-peer networks, e.g. gnutella p2p communication protocols H04L67/104
• CPC Class Codes: G06F 16/3347 using vector based model
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1065 Discovery involving distributed pre-established resource-based relationships among peers, e.g. based on distributed hash tables [DHT] pre-configuration of logical or physical connections H04L67/1053
• 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

In a method of semantic querying in a peer-to-peer network, an item of information is mapped into a semantic vector based on the latent semantic indexing algorithm or any IR algorithms that can derive a vector representation. The semantic vector is associated with an address index as a key pair. The key pair is stored in an overlay network formed from the peer-to-peer network such that the stored key pair is proximally located to at least one other key pair having a similar semantic vector.

Claims

1. A method for semantic querying of a peer-to-peer network, said method comprising:

mapping an item of information into a semantic vector based on a latent semantic indexing algorithm;

associating said semantic vector with an address index as a key pair; and

storing said key pair in an overlay network formed from said peer-to-peer network such that the stored key pair is proximally located to at least one other key pair having a similar semantic vector.

2. The method according to claim 1, further comprising:

forming a plurality of indices; and

associating each index of said plurality with a respective peer of said peer-to-peer network, each index formed by storing key pairs at said respective peer.

3. The method according to claim 2, further comprising:

receiving a query for requested information; and

converting said query to a semantic query vector based on said latent semantic indexing algorithm.

4. The method according to claim 3, further comprising:

routing said semantic query vector to a selected node based on a location of where said semantic query vector falls within said overlay network.

5. The method according to claim 4, further comprising:

flooding said semantic query vector to a plurality of peers of said peer-to-peer network, said plurality of peers within a radius of said selected node.

6. The method according to claim 5, further comprising:

retrieving preselected sets of information, each candidate set of information filtered by each respective peer of said plurality of peers; and

forwarding said preselected sets of information to an initiator of said query.

7. The method according to claim 6, further comprising:

receiving said preselected sets of information; and

applying said latent semantic indexing algorithm to said preselected sets of information to form a candidate set of information.

8. The method according to 1, further comprising:

converting said semantic vector to a parameter vector based on a transformation.

9. The method according to claim 8, further comprising:

parsing at least one of said parameter vector and said semantic vector into a plurality of subvectors.

10. The method according to claim 9, further comprising:

creating a plurality of planes in said overlay network, wherein each plane is associated with a respective subvector and associated address index.

11. The method according to claim 10, further comprising:

receiving a query; and

converting said query into a query parameter vector.

12. The method according to claim 11, further comprising:

routing said query-parameter vector to a selected node based on a location of where said query-parameter vector falls within said overlay network.

13. The method according to claim 11, further comprising:

parsing said query-parameter vector into a plurality of query subvectors; and

routing said plurality of query subvectors among said plurality of planes.

14. The method of claim 1, further comprising:

parsing at least one of the semantic vector or a parameter vector generated from the semantic vector into a plurality of subvectors; and

creating a plurality of planes in the overlay network from the plurality of subvectors.

15. The method of claim 14, wherein parsing at least one of the semantic vector or a parameter vector generated from the semantic vector into a plurality of subvectors comprises:

applying clustering algorithms to semantic vectors or parameter vectors in the overlay network to identify related vectors;

identifying elements from the related vectors that are similar; and

generating the plurality of subvectors from the similar elements.

16. The method of claim 14, wherein parsing at least one of the semantic vector or a parameter vector generated from the semantic vector into a plurality of subvectors comprises:

identifying continuous elements in the semantic vector or parameter vector that are associated with concepts in the item of information; and

generating the plurality of subvectors from the continuous elements.

17. The method of claim 14, further comprising searching the plurality of planes in response to receiving a query.

18. The method of claim 1, further comprising substantially evenly distributing key pairs in the overlay network by using parameter vectors generated from semantic vectors to determine locations for storing the key pairs in the overlay network.

19. The method of claim 1, further comprising:

identifying a new node joining the overlay network;

determining a parameter vector for an item of information associated with the new node; and

assigning the new node to a zone where the parameter vector falls in the overlay network.

20. An apparatus for semantic querying in a peer-to-peer network, said apparatus comprising:

means for creating a plurality of indices, each index of said plurality of indices comprising a plurality of key pairs, each key pair comprising a respective semantic vector and an associated address index; and

means for associating a selected index of said plurality to a selected peer based on a location of where said respective semantic vectors of said key pairs of said selected index falls within an overlay network.

21. The apparatus according to claim 20, further comprising:

means for receiving a query; and

means for converting said query into a semantic query vector.

22. The apparatus according to claim 21, further comprising:

means for routing said semantic query vector to a selected node based on a location of where said semantic query vector falls within said overlay network, wherein said location is owned by said selected node.

23. The apparatus according to claim 22, further comprising:

means for routing said semantic query vector to a plurality of peers of said peer-to-peer network based on said plurality of peers being within a radius of said selected node.

24. A system for querying a peer-to-peer network, said system comprising:

a plurality of peers;

an overlay network implemented by said plurality of peers, wherein said overlay network is configured to be divided into zones, each zone owned by a respective peer of said plurality of peers;

a plurality of indices, each index of said plurality of indices based on at least one key pair comprising of a respective parameter vector and associated address index, wherein said parameter vector is based on a transformation of a respective semantic vector; and

a query module stored an executed by each peer of said plurality of peers, wherein said query module is configured to convert a query into a query parameter vector and receive requested information from a respective index stored a selected peer that owns the respective zone where said query parameter vector falls within said overlay network.

25. The system according to claim 24, wherein said query module is further configured to receive said query parameter vector and to parse said query parameter vector into a plurality of query subvectors.

26. The system according to claim 25, wherein said overlay network comprises a plurality of planes, each plane associated with a respective subvector and wherein said query module is further configured to route said query parameter vector to a plurality of peers within a radius and to route said plurality of query subvectors among said plurality of planes.

27. The system according to claim 26, wherein said query module is further configured to collect a set of information based on said query parameter vector and said plurality of query subvectors and provide said set of information.

28. The system according to claim 24, further comprising an index module configured to instantiate and maintain said plurality of indices.

29. The system according to claim 28, further comprising an indices module configured to store said plurality of indices and adapted to interface with said index module.

30. The system according to claim 24, further comprising a routing module configured to route said query parameter vector through said overlay network.

31. The system according to claim 30, wherein said routing module is further configured to select a zone for a new node to join said overlay document based on selecting a document stored on said new node, converting said document into a respective parameter vector and locating a host node of where said respective parameter vector falls within said overlay network.