Method and apparatus for creating and utilizing information signatures

• US 8,150,835 B2
• Filed: 09/23/2009
• Issued: 04/03/2012
• Est. Priority Date: 09/23/2009
• Status: Active Grant

• Current Assignee: Piece Future Pte., Ltd.
• Original Assignee: Nokia Corporation
• Inventors: Boldyrev, Sergey, Oliver, Ian Justin, Honkola, Jukka, Lappeteläinen, Antti Tuomas, Balandin, Sergey
• Primary Examiner(s): Alam, Shahid
• Assistant Examiner(s): LODHI, ANDALIB FT
• Application Number:
  US12/565,435
• Publication Number:
  US 20110072003A1
• Time in Patent Office: 923 Days
• Field of Search: 707/693, 707/705, 707/713, 707/718, 707/769
• US Class Current: 707/713
• CPC Class Codes: G06F 16/2452 Query translation
• CPC Class Codes: G06F 16/24534 Query rewriting; Transformation
• CPC Class Codes: G06F 16/901 Indexing; Data structures therefor; Storage structures for retrieval from the web G06F16/951
• CPC Class Codes: G06F 17/10 Complex mathematical operations function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544

Abstract

An approach is provided for efficiently searching information in an information space utilizing information signatures. A signature application receives queries over information sources. The signature application, for each of the queries, generates a polynomial by defining the each query against the information sources as input parameters in polynomial form. The signature application provides irreducible polynomials over a finite field of a degree of orthogonality by factoring polynomials generated from the queries. The signature application adjusts the degree of orthogonality of the irreducible polynomials to provide adjusted irreducible polynomials, each of which is a signature and corresponds to a signature fragment, such that the signature fragments have overlapping portions. The signature application causes at least in part storage of the signatures or the signature fragments in a signature domain over an information space.

Claims

1. A method comprising:

receiving queries over information sources;

for each of the queries, generating a polynomial by defining each query against the information sources as input parameters in polynomial form;

providing irreducible polynomials over a finite field of a degree of orthogonality by factoring polynomials generated from the queries;

adjusting the degree of orthogonality of the irreducible polynomials to provide adjusted irreducible polynomials, each of which is a signature and corresponds to a signature fragment, such that the signature fragments have overlapping portions; and

causing at least in part storage of the signatures or the signature fragments in a signature domain over an information space.

2. The method of claim 1, further comprising:

for each of the queries, searching for signature fragments corresponding to each query; and

responding to each query with the searched signature fragments.

3. The method of claim 2, further comprising:

selectively combining signatures into supersignatures by multiplying irreducible polynomials corresponding to the signatures, the supersignatures corresponding to supersignature fragments;

causing at least in part storage of the supersignature fragments in the signature domain;

for each of the queries, searching for a supersignature fragment correspond to each query; and

responding to each query with the searched signature fragments, the supersignature fragments, or a combination thereof.

4. The method of claim 3, further comprising:

comparing a difference between a target information fragment and a signature or supersignature fragment by comparing polynomials corresponding to the fragments or by comparing values of the corresponding polynomials.

5. The method of claim 3, further comprising:

receiving a request to reconstruct the queries; and

reconstructing the queries from the signature fragments, the supersignature fragments, or a combination thereof.

6. The method of claim 1, wherein the signature fragment constitutes a finest lossless component in an information representation format or structure that has one or more overlapping portions with one or more other signature fragments.

7. The method of claim 1, further comprising:

adjusting sizes of the overlapping portions and the signature fragments by adjusting the degree of orthogonality of the irreducible polynomials.

8. An apparatus comprising:

at least one processor; and

at least one memory including computer program code,

the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus to perform at least the following,

receive queries over information sources;

for each of the queries, generate a polynomial by defining each query against the information sources as input parameters in polynomial form;

provide irreducible polynomials over a finite field of a degree of orthogonality by factoring polynomials generated from the queries;

adjust the degree of orthogonality of the irreducible polynomials to provide adjusted irreducible polynomials, each of which is a signature and corresponds to a signature fragment, such that the signature fragments have overlapping portions; and

cause at least in part storage of the signatures or the signature fragments in a signature domain over an information space.

9. An apparatus of claim 8, wherein the apparatus is further caused to:

for each of the queries, search for signature fragments corresponding to each query; and

respond to each query with the searched signature fragments.

10. An apparatus of claim 9, wherein the apparatus is further caused to:

selectively combine signatures into supersignatures by multiplying irreducible polynomials corresponding to the signatures, the supersignatures corresponding to supersignature fragments;

cause at least in part storage of the supersignature fragments in the signature domain;

for each of the queries, searching for a supersignature fragment correspond to each query; and

respond to each query with the searched signature fragments, the supersignature fragments, or a combination thereof.

11. An apparatus of claim 10, wherein the apparatus is further caused to:

compare a difference between a target information fragment and a signature or supersignature fragment by comparing polynomials corresponding to the fragments or by comparing values of the corresponding polynomials.

12. An apparatus of claim 10, wherein the apparatus is further caused to:

receive a request to reconstruct the queries; and

reconstruct the queries from the signature fragments, the supersignature fragments, or a combination thereof.

13. An apparatus of claim 8, wherein the signature fragment constitutes a finest lossless component in an information representation format or structure that has one or more overlapping portions with one or more other signature fragments.

14. An apparatus of claim 8, wherein the apparatus is further caused to:

adjust sizes of the overlapping portions and the signature fragments by adjusting the degree of orthogonality of the irreducible polynomials.

15. A computer-readable storage medium carrying one or more sequences of one or more instructions which, when executed by one or more processors, cause an apparatus to perform at least the following steps:

receiving queries over information sources;

for each of the queries, generating a polynomial by defining each query against the information sources as input parameters in polynomial form;

providing irreducible polynomials over a finite field of a degree of orthogonality by factoring polynomials generated from the queries;

adjusting the degree of orthogonality of the irreducible polynomials to provide adjusted irreducible polynomials, each of which is a signature and corresponds to a signature fragment, such that the signature fragments have overlapping portions; and

causing at least in part storage of the signatures or the signature fragments in a signature domain over an information space.

16. A computer-readable storage medium of claim 15, wherein the apparatus is caused further to perform:

for each of the queries, searching for signature fragments corresponding to each query; and

responding to each query with the searched signature fragments.

17. A computer-readable storage medium of claim 16, wherein the apparatus is caused further to perform:

selectively combining signatures into supersignatures by multiplying irreducible polynomials corresponding to the signatures, the supersignatures corresponding to supersignature fragments;

causing at least in part storage of the supersignature fragments in the signature domain;

for each of the queries, searching for a supersignature fragment corresponding to each query; and

responding to each query with the searched signature fragments, the supersignature fragments, or a combination thereof.

18. A computer-readable storage medium of claim 17, wherein the apparatus is caused further to perform:

comparing a difference between a target information fragment and a signature or supersignature fragment by comparing polynomials corresponding to the fragments or by comparing values of the corresponding polynomials.

19. A computer-readable storage medium of claim 17, wherein the apparatus is caused further to perform:

receiving a request to reconstruct the queries; and

reconstructing the queries from the signature fragments, the supersignature fragments, or a combination thereof.

20. A computer-readable storage medium of claim 15, wherein the signature fragment constitutes a finest lossless component in an information representation format or structure that has one or more overlapping portions with one or more other signature fragments.