Method and apparatus for representing data available in a peer-to-peer network using bloom-filters
First Claim
1. A processor-implemented method for searching for a data object in a plurality of nodes forming a peer-to-peer network, the method comprising:
- forming Bloom-Filters at the nodes as a function of data available via the nodes;
communicating the Bloom-filters between peer-to-peer coupled nodes of the peer-to-peer network that have formed connections using incentive-based criteria to control whether one node connects to another node;
forming a search expression for locating the data object;
selecting nodes to propagate the search expression as a function of the Bloom-filters and the incentive-based criteria;
propagating the search expression to the selected nodes; and
outputting a result of the search expression from nodes that satisfy the search expression.
2 Assignments
0 Petitions
Accused Products
Abstract
A method and apparatus is disclosed for representing data available in a peer-to-peer network of processing nodes. In one arrangement, respective Bloom-Filters may be formed at the nodes as a function of data available via the nodes. The Bloom-filters may be communicated between peer-to-peer coupled nodes of the peer-to-peer network that have formed connections using incentive-based criteria to control whether one node connects to another node. A search expression may be formed for locating a data object, and nodes selected as a function of the Bloom-filters and the incentive-based criteria. The search expression may be propagated to the selected nodes, and the result of the search expression output from nodes that satisfy the search expression.
126 Citations
25 Claims
-
1. A processor-implemented method for searching for a data object in a plurality of nodes forming a peer-to-peer network, the method comprising:
-
forming Bloom-Filters at the nodes as a function of data available via the nodes;
communicating the Bloom-filters between peer-to-peer coupled nodes of the peer-to-peer network that have formed connections using incentive-based criteria to control whether one node connects to another node;
forming a search expression for locating the data object;
selecting nodes to propagate the search expression as a function of the Bloom-filters and the incentive-based criteria;
propagating the search expression to the selected nodes; and
outputting a result of the search expression from nodes that satisfy the search expression. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A system comprising:
a plurality of data processors coupled via a peer-to-peer network arrangement, each data processor including;
a network interface arranged to provide one or more respective connections with one or more associated data processor of the peer-to-peer network arrangement, the connections formed using an incentive-based criteria;
a memory for storing one or more respective remote Bloom filters representing data accessible via the associated connections; and
a processing unit arranged to;
form a query Bloom-filter based on a data query;
select a subset of the connections as a function of the query Bloom-filter and the respective remote Bloom-filters associated with the connections; and
send the data query to the subset of the connections. - View Dependent Claims (9, 10, 11, 12, 13, 14, 15, 20)
-
16. A computer-readable medium having instructions stored thereon which are executable on a processor for performing steps comprising:
-
forming one or more respective peer-to-peer connections with one or more network peers of the processor using an incentive-based criteria;
receiving respective remote Bloom-filters representing data accessible via associated peer-to-peer connections;
forming a query Bloom-filter based on a data query;
selecting a subset of the peer-to-peer connections as a function of the query Bloom-filter and the respective remote Bloom filters associated with the peer-to-peer connections; and
sending the data query to the subset of the connections. - View Dependent Claims (17, 18, 19)
-
-
21. A method for updating a Bloom-filter array having a plurality of bits that indicate data accessible via a peer-to-peer network, comprising:
-
associating respective counters with the bits of the Bloom-filter array;
receiving a Bloom-filter update having a plurality of bits associated with the bits of the Bloom-filter array that indicate a change in the data accessible via the peer-to-peer network;
changing the respective counters based on the associated bits of the Bloom-filter update;
setting the bits of the Bloom-filter array to zero where the respective counters associated with the bits are zero; and
setting the bits of the Bloom-filter array to one where the respective counters associated with the bits are greater than zero. - View Dependent Claims (22, 23)
-
-
24. A data processing arrangement, comprising means for storing data objects;
-
means for forming respective peer-to-peer data connections with one or more network peers using an incentive-based criteria;
means for storing remote Bloom-filters associated with respective peer-to-peer data connections, the Bloom-filters indicating data accessible via the respective peer-to-peer data connections;
means for forming a query for locating one or more data objects of the network peers; and
means for sending the query to a subset of the peer-to-peer data connections as a function of the query and the Bloom filters associated with the respective peer-to-peer data connections. - View Dependent Claims (25)
-
Specification