1) A method comprising:
a) receiving, into a provided memory readable and writable by a provided CPU, one or more sets of digital data which can be presented in one-dimension, each set comprising
i) data values organized in sequential addresses or at set intervals of addresses,
ii) the number of data values per data point,
iii) a specified starting address,
iv) a specified number of data points, called the length;
b) the computation of a numerical similarity signature, referred to as the equivalence signature as the volume of the presentation space, and
c) the computation of a similarity distance between any two sets of digital data as the absolute value of the difference of their equivalence signatures.
2) The method of claim 1, comprising a means for arranging the data values into planes with specified starting addresses and lengths of each presentation dimension for each plane wherein the ith plane consists of the set of the ith data values at each point.
3) The method of claim 1, wherein computing an equivalence signature of a section of digital data further comprises normalizing the data values of each plane by any of a plurality of methods including linearly mapping the data of each plane individually to fixed maximum and minimum values using slope-offset formulae and the like.
4) The method of claim 1, wherein, for text, binaries, audio data and other digital data that may be presented in one-dimension, computing an equivalence signature as the length of the presentation space of the normalized digital data, further comprises looping over each x-position, from the first x-position to the second to last x-position, and for each position,
a) looping over each plane,
b) computing the difference of the data value at said position in the plane and the data value at said position shifted by one in the x-direction in the plane and squaring the result,
c) add the result from the previous step to the result from the previous roll of this inner most loop if this is not the first roll of the said inner most loop,
d) upon completion of the loop over the planes, compute the square root of the result from the last roll of the inner most loop to form the result for the current roll of the loop over the x-position, with the value for the current roll of the loop over the x-position set to zero in the initial roll of said loop over the x-position,
e) upon completion of said loop over the x-position assigning the value from the loop over the x-position as the value of the equivalence signature.
5) A method comprising:
a) receiving, into a provided memory readable and writable by a provided CPU, one or more sets of digital data which can be presented in one-dimension, each set comprising
i) data values organized in sequential addresses or at set intervals of addresses,
ii) the number of data values per data point,
iii) a specified starting address,
iv) a specified number of data points, called the length,
b) the computation of a numerical similarity signature, referred to as the equivalence signature as the volume of the presentation space,
c) the computation of a similarity distance between any two sets of digital data as the absolute value of the difference of their equivalence signatures,
d) the persistence of said equivalence signature for said input sets digital data by means of a database for storing a record for each of the sections of said input set of digital data, if said record is not already present in the database and the database is configured to store said records; and
e) a means for querying the database for sections of the sets of digital data that are candidates for similarity with said one or more target sections of the said input set of digital data.
6) The method of claim 5, comprising a means for creating and writing a record, in said database, for each section in each set of the said input sets of digital data, comprising,
a) a key,
i) the most significant half of whose value, is the equivalence signature of said section in the set of digital data, and
ii) the least significant half of whose value is the sequential count, starting at zero, of sections of digital data with said equivalence signature and whose equivalence signatures were previously written to the database,
b) one or more fields including a field storing the value referencing the medium wherein said set of digital data is stored, and
c) one or more fields including secondary feature data, for said planes or set of digital data, and
d) other fields containing meta data about said set of digital data.
7) The method of claim 5, wherein a storage identifier comprises the location of a file containing a set of digital data along with the starting position of said data set in the file and the length of the data comprising said set.
8) The method of claim 5, further comprising a means for writing a record including assigning the key, the most significant half of whose value is the equivalence signature for a section in the set of digital data.
9) The method of claim 5, further comprising a means for reading a plurality of records and for each of the records extracting the equivalence signature of a set of digital data as the most significant half of the key of the record and extracting the fields, containing secondary features as well as the meta data, including the storage identifier, from the record.
10) The method of claim 5, further comprising a means for retrieving, from said database, a plurality of records for which the most significant half of the values of the keys of the records are equal to a specified equivalence signature of a said target sections.
11) The method of claim 5, further comprising a means for retrieving from said database a plurality of records with the most significant half of the values of the keys being within a range of equivalence signatures.
12) The method of claim 5, further comprising the selection of a target section of said input set and the computation of a lower and upper bound on the values of the equivalence signature such that any section of sets of digital data with equivalence signatures that are less than the lower bound or greater than the upper bound will not be similar to the target section and all other sections of sets of digital data recorded in the database will be candidates for sections of sets of digital data that are similar to the target section, with
a) the lower bound given by the equivalence signature of the target section minus the absolute value of an equivalence signature delta for the target section, and
b) the upper bound given by the equivalence signature of the target section plus the absolute value of an equivalence signature delta for the target section.
13) The method of claim 12, further comprising a means of extracting, from said database, a plurality of records with keys such that the most significant half of each key is equal to or greater than said lower bound and equal to or less than said upper bound.
14) The method of claim 12, wherein said equivalence signature delta is computed as the equivalence signature of said target section of a set of digital data minus a second equivalence signature for said target section with data values resealed and shifted by set constants for each plane specifying the maximum scaling and shifting of the data values at each data point in a plane in order for the plane so altered to still be considered similar to the corresponding unaltered plane.
15) The method of claim 14, further comprising a means for specifying the maximum scaling and shifting of the data values at each data point in a plane in order for the section so altered to still be considered similar to the corresponding unaltered section.
16) The method of claim 14, wherein, for text, binaries, audio data and other digital data that may be presented in one-dimension, the computation of said second equivalence signature as the length of the presentation space of said section, with said resealing and shifting of the data values, and consisting of a means to normalize the digital data, further comprises looping over each x-position, from the first x-position to the second to last x-position, and for each position,
a) looping over each plane,
b) computing the difference of the data value at said position in the plane and the data value at said position shifted by one in the x-direction in the plane and squaring the result,
c) add the result from the previous step to the result from the previous roll of this inner most loop if this is not the first roll of the said inner most loop,
d) upon completion of the loop over the planes, compute the square root of the result from the last roll of the inner most loop to form the result for the current roll of the loop over the x-position, with the value for the current roll of the loop over the x-position set to zero in the initial roll of said loop over the x-position,
e) upon completion of said loop over the x-position assigning the value from the loop over the x-position as the value of the equivalence signature.
17) The method of claim 5, further comprising a means to return to a user of the method,
a) the difference between the value of an equivalence signature of said target section and the most significant halves of the keys returned by said database; and
b) the meta data from each field in the records identified by said keys.
18) The method of claim 5, further comprising calculation of and sorting of a list of differences, between the equivalence signature of said target pair of and the values of the most significant halves of the keys of the records of the candidates for similar digital data, from smallest to largest values of said differences along with a means for returning to the user of the method, the meta data from the records ordered by the sorted differences.
19) A method comprising:
a) receiving, into a provided memory readable and writable by a provided CPU, one or more sets of digital data which can be presented in one-dimension, each set comprising
i) data values organized in sequential addresses or at set intervals of addresses,
ii) the number of data values per data point,
iii) a specified starting address,
iv) a specified number of data points, called the length;
b) the computation of a numerical similarity signature, referred to as the equivalence signature as the volume of the presentation space,
c) the computation of a similarity distance between any two sets of digital data as the absolute value of the difference of their equivalence signatures,
d) the persistence of said equivalence signature for said input sets digital data by means of a database for storing a record for each of the sections of said input set of digital data, if said record is not already present in the database and the database is configured to store said records,
e) a means for querying the database for sections of the sets of digital data that are candidates for similarity with said one or more target sections of the said input set of digital data; and
f) a means to compare a set of secondary features provided with a target section of a set of digital data against the secondary features for similar sections of digital data whose records are in said database.
20) The method of claim 19, further comprising the comparison, of said set of secondary features provided with said target section, against the secondary features for said similar sections of sets of digital data found by querying the database and returning the list produced by the comparison of the secondary features as the final list of sections of sets of digital data that are similar to said target section.
The claims below are in addition to those above.
All refrences to claim(s) which appear below refer to the numbering after this setence.
1. A method comprising:
receiving broadcast packets transmitted from a transmitting node and determining if all of the broadcast packets have been received using a Latest Neighbor’s Broadcast Count Number (NBC) stored in a neighbor table within a buffer of a pertinent node and a Broadcast Count Number (BC) contained in the broadcast packets received from the transmitting node;
comparing the Broadcast Count Number (BC) of the received broadcast packet with a buffer size of the pertinent node if all of the broadcast packets transmitted from the transmitting node have been received; and
generating a hello packet for flushing a buffer of the transmitting node and transmitting the hello packet to the transmitting node, flushing the buffer of the pertinent node, and updating the neighbor table of the flushed buffer of the pertinent node in accordance with the broadcast packet if the Broadcast Count Number (BC) of the received broadcast packet exceeds the buffer size of the pertinent node.
2. The method according to in claim 1, wherein the neighbor table comprises ID information of a broadcast packet transmitting node, Latest Neighbor’s Broadcast Count Number (NBC) information, buffer size information of a buffer storing the received broadcast packets and bit map information regarding a list of packets from among the received broadcast packets that have not been received due to a packet error or missing packet.
3. The method according to claim 1, wherein the transmitting node comprises a relay node to relay the broadcast packets transmitted via a sender node which generates and transmits the broadcast packets toward a receiving node.
4. The method according to claim 1, wherein each broadcast packet comprises an IP header field, a relayer node list information field including list information of neighboring relayer nodes, a broadcast count information field of broadcast packets transmitted from an associated node and a broadcast data field.
5. The method according to claim 1, further comprising updating received broadcast packet information in the neighbor table if the Broadcast Count Number (BC) of the received broadcast packet does not exceed the buffer size of the pertinent node.
6. The method according to claim 1, further comprising periodically generating a hello packet containing broadcast packet receipt confirmation information and transmitting the hello packet to the transmitting node according to a predetermined time period or a predetermined packet number upon receipt of the broadcast packet from the transmitting node.
7. The method according to claim 1, wherein the hello packet comprises a packet type information field, a reply information (NACK, ACK) field regarding receipt of the broadcast packet, a flag information field including a reserved field, an ID information field of a neighboring transmitting node, a Broadcast Count Number (BC) information field, a bit map information field (NACK MAP) of missing packets identified by a failure to receive a broadcast packet receipt, a neighbor information field containing ID information of the sender node and neighboring relayer nodes and NACK information as to reply information in response to the failure to receive the broadcast packet receipt, a broadcast retransmission information field containing ID information of a corresponding node from which a broadcast packet has not been received, and a node and ID information or source (SRC) address of the corresponding node.
8. The method according to claim 1, further comprising:
determining if the Broadcast Count Number BC contained in the received broadcast packets is larger than a Broadcast Count Number (NBC+1) following the Latest Neighbor’s Broadcast Count Number (NBC) if all of the broadcast packet have not been received;
updating a missing packet list in the neighbor table of the receiver node and transmitting a hello packet for retransmission of a missing packet if the Broadcast Count Number transmitted up to the present from the transmitting node is larger than the Broadcast Count Number received up to the present; and
determining if the receiver node has received all of the packets and a corresponding broadcast packet has been received at the request of another node for retransmission of a missing packet and discarding the received broadcast packet if the Broadcast Count Number transmitted up to the present from the transmitting node is not larger than the Broadcast Count Number received up to the present.
9. The method according to claim 6, wherein generating and transmitting a hello packet to the transmitting node comprises:
sequentially retrieving broadcast data bit map information regarding respective nodes which transmitted the broadcast packets stored in the neighbor table to determine if there is a missing packet; and
generating a hello packet for requesting the missing packet using a bit map in the neighbor table and transmitting the hello packet to a corresponding node which transmitted the missing packet if it has been determined that there is a missing packet.
10. The method according to claim 9, wherein, upon receiving the hello packet, the transmitting node:
determines if the hello packet has been received from a new node which is not listed in a neighbor table within a buffer of the transmitting node;
determines if the received hello packet is a triggering hello packet for flushing a full buffer if the hello packet has been received from a node listed in the neighbor table of the transmitting node;
examines bit map information in the received hello packet to determine if there is a missing packet if the received hello packet is not the triggering hello packet but is a hello packet for periodically informing receipt of a broadcast packet; and
transmits a broadcast packet corresponding to the missing packet to the node which transmitted the hello packet and updating the neighbor table of the transmitting node if there is a missing packet.
11. The method according to claim 10, wherein, if the received hello packet is determined to be a triggering hello packet, the transmitting node:
determines if triggering hello packets have been received from all of the neighboring nodes for the purpose of buffer flushing;
flushes the buffer if the triggering hello packets have been received from all of the neighboring nodes and sets a timer to count a set time if the triggering hello packets have not been received from all of the neighboring nodes; and
compares the counted time with the set time and flushes the buffer even though the triggering hello packets have not been received from all of the neighboring nodes if the counted time exceeds the set time.
12. A method comprising:
providing at least one sender node and a relayer node to relay broadcast packets from the sender node to a receiver node;
the receiver node determining if all of the broadcast packets transmitted from the sender or relayer node have been received based upon a Latest Neighbor’s Broadcast Count Number (NBC) stored in a neighbor table within a buffer of the receiver node and a Broadcast Count Number (BC) contained in the broadcast packets received from the sender or relayer node upon receiving the broadcast packets from the sender or relayer node;
the receiver node comparing the received broadcast packets with the buffer size of the Broadcast Count Number (BC) if all of the broadcast packets from the sender or relayer node have been received; and
generating a hello packet for flushing a buffer in the sender or relayer node and transmitting the hello packet to any of the sender and relayer nodes which transmitted the broadcast packets, flushing the buffer of the receiver node, and updating the neighbor table of the flushed neighbor table of the receiver node using the received broadcast packets if the Broadcast Count Number (BC) of the received broadcast packets exceeds the buffer size of the receiver node.
13. The method according to claim 12, wherein the neighbor table within the buffer of the receiver node comprises ID information of the relayer node which relayed the broadcast packets, latest NBC information received from the node which transmitted the broadcast packets, buffer size information of the buffer storing the received broadcast packets and bit map information regarding a list of packets from among the received broadcast packets which have not been received due to a packet error or missing packet.
14. The method according to claim 12, wherein each of the broadcast packets comprises an IP header field, a relayer node list information field containing list information of neighboring relayer nodes of the receiver node, a broadcast count information field for the broadcast packets transmitted from a corresponding node, and a broadcast data field.
15. The method according to claim 12, further comprising the receiver node periodically generating and transmitting a hello packet containing broadcast packet receipt confirmation information to the relayer node or to the sender node via the relayer node according to a predetermined time interval or a predetermined packet number upon receiving the broadcast packet from the relayer node.
16. The method according to claim 15, wherein the hello packet transmitted to the relayer node or to the sender node via the relayer node from the receiver node comprises: a packet type information field, a reply information (NACK, ACK) field regarding receipt of the broadcast packet, a flag information field including a reserved field, an ID information field of a neighboring transmitting node, a broadcast count (BC) information field, a bit map information field (NACK MAP) of missing packets identified by a failure to receive a broadcast packet receipt, a neighbor information field containing ID information of the sender node and neighboring relayer nodes and NACK information as reply information in response to the failure to receive the broadcast packet receipt and a broadcast retransmission information field containing ID information of a corresponding one of the relayer and sender nodes from which a broadcast packet has not been received and a node and ID information or source (SRC) address of the corresponding node.
17. The method according to claim 12, further comprising:
determining if the Broadcast Count Number (BC) contained in the received broadcast packet is larger than a Broadcast Count Number NBC+1 following the Latest Neighbor’s Broadcast Count Number (NBC) if it has been determined that all of the transmitted broadcast packets have not been received from the relayer node;
updating a missing packet list in the neighbor table of the receiver node and transmitting a hello packet for retransmission of a missing packet if the Broadcast Count Number transmitted up to the present from the relayer node is larger than the Broadcast Count Number received up to the present; and
determining if the receiver node has received all of the packets and a corresponding broadcast packet has been received at the request of another node for retransmission of a missing packet and discarding the received broadcast packet if the Broadcast Count Number transmitted up to the present from the relayer node is not larger than the Broadcast Count Number received up to the present.
18. The method according to claim 12, wherein generating and transmitting a hello packet to the relayer node or to the sender node via the relayer node comprises:
sequentially retrieving broadcast data bit map information regarding the sender and relayer nodes which have transmitted broadcast packets stored in the neighbor table within the buffer of the receiver node to determine if there is a missing packet; and
generating a hello packet for requesting the missing packet using bit map information in the neighbor table and transmitting the hello packet to the relayer node or to the sender node via the relayer node that transmitted the missing broadcast packet if it has been determined that there is a missing packet.
19. The method according to claim 18, wherein upon receiving the hello packet, the relayer or sender node:
determines if the hello packet has been received from a new receiver node which is not listed in a neighbor table within a buffer of the relayer or sender node;
determines if the received hello packet is a triggering hello packet for flushing a full buffer if the hello packet has been received from a node listed in the neighbor table of the relayer or sender node;
examines bit map information in the received hello packet to determine if there is a missing packet if the received hello packet is not the triggering hello packet but is a hello packet for periodically informing receipt of broadcast packets; and
transmits a broadcast packet corresponding to the missing packet to the receiver node which transmitted the hello packet and updates the neighbor table of the relayer or sender node if there is a missing packet.
20. The method according to claim 19, wherein, if the received hello packet is determined to be a triggering hello packet, the relayer or sender node:
determines if the triggering hello packets have been received from all of the neighboring nodes for flushing the buffer;
flushes the buffer if the triggering hello packets have been received from all of the neighboring nodes, and sets a timer to count a set time if the triggering hello packets have not been received from all of the neighboring nodes; and
compares the counted time with the set time and flushes the buffer even though the triggering hello packets have not been received from all of the neighboring nodes if the counted time exceeds the set time.
21. A method comprising:
providing at least one sender node and a relayer node to relay broadcast packets from the sender node to a receiver node;
transmitting a hello packet processed by the relayer or sender node upon receipt of the broadcast packets:
determining if the hello packet has been received from a new receiver node which is not listed in a neighbor table within a buffer of the relayer or sender node;
determining if the received hello packet is a triggering hello packet for flushing a full buffer if the hello packet has been received from a node listed in the neighbor table of the relayer or sender node;
examining bit map information in the received hello packet to determine if there is a missing packet if the received hello packet is not the triggering hello packet but is a hello packet for periodically acknowledging receipt of the broadcast packets; and
transmitting a broadcast packet corresponding to the missing packet to the receiver node which transmitted the hello packet and updating the neighbor table of the relayer or sender node if there is a missing packet.
22. The method according to claim 21, wherein if the received hello packet is determined to be a triggering hello packet, the relayer or sender node:
determines if the triggering hello packets have been received from all of neighboring nodes for flushing the buffer;
flushes the buffer if the triggering hello packets have been received from all of the neighboring nodes and sets a timer to count a set time if the triggering hello packets have not been received from all of the neighboring nodes; and
compares the counted time with the set time and flushes the buffer even though the triggering hello packets have not been received from all of the neighboring nodes if the counted time exceeds the set time.
23. The method according to claim 21, wherein the hello packet transmitted from the receiver node comprises: a packet type information field, a reply information (NACK, ACK) field regarding receipt of the broadcast packet, a flag information field including a reserved field, an ID information field of a neighboring transmitting node, a broadcast count (BC) information field, a bit map information field (NACK MAP) of missing packets in response to a failure to receive a broadcast packet receipt, a neighbor information field containing ID information of the sender node and neighboring relayer nodes and NACK information as reply information in response to the failure to receive the broadcast packet receipt and a broadcast retransmission information field containing ID information of a corresponding one of the relayer and sender nodes from which a broadcast packet has not been received and a node and ID information or source (SRC) address of the corresponding node.