Search method using coded keys

• US 20050091443A1
• Filed: 10/23/2003
• Published: 04/28/2005
• Est. Priority Date: 10/23/2003
• Status: Active Grant

• Current Assignee: Hywire Limited
• Original Assignee: Hywire Limited
• Inventors: Shezaf, Nira, Hershkovich, Moshe
• Granted Patent: US 7,499,912 B2
• Time in Patent Office: Days
• US Class Current: 711/100
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A computer-implemented method of searching an ordered database using transformed key entries including the steps of: (a) providing a system having: (i) a memory for storing a plurality of key entries, and (ii) processing logic for transforming said key entries into coded entries, and for searching the coded entries; (b) performing a pre-determined transformation of each key entry so as to obtain a plurality of coded entries, and (c) performing a deterministic search in at least one data structure within the memory to obtain a match between an input key and a key entry.

Claims

1. A computer-implemented method of searching an ordered database using transformed key entries, the method comprising the steps of:

(a) providing a system including;

(i) a memory for storing a plurality of key entries, and

(ii) processing logic for;

(A) transforming said key entries into coded entries, and

(B) searching said coded entries;

(b) performing a pre-determined transformation of each key entry of said plurality of key entries so as to obtain a plurality of coded entries, and

(c) performing a deterministic search in at least one data structure within said memory to obtain a match between an input key and a key entry of said key entries.

2. The method of claim 1, wherein said search is deterministic with respect to specific key data.

3. The method of claim 2, wherein said specific key data includes said input key.

4. The method of claim 2, wherein said specific key data includes said key entries.

5. The method of claim 2, wherein said specific key data includes said coded entries in said data structure.

6. The method of claim 1, wherein said search is deterministic with respect to a required amount of auxiliary data.

7. The method of claim 1, wherein said search is a pre-determined search.

8. The method of claim 1, wherein each coded entry of said coded entries includes information relating to at least one different key entry of said key entries.

9. The method of claim 8, wherein said at least one different key entry is a single key entry.

10. The method of claim 8, wherein said information includes positional information.

11. The method of claim 8, wherein said information includes information resulting from at least one varying bit.

12. The method of claim 11, wherein said at least one varying bit includes a most significant bit.

13. The method of claim 1, wherein said transformation is a deterministic transformation.

14. The method of claim 1, wherein said performing of said deterministic search includes:

(i) processing said coded keys to determine a required set of auxiliary data, said set being required to proceed with said search, and

(ii) using said required set of auxiliary data for an additional processing of said coded keys so as to determine a result of said search.

15. The method of claim 14, wherein said auxiliary data includes a portion of a key entry, and wherein said portion is then compared to said input key.

16. The method of claim 1, wherein said search is an exact search, and wherein said performing of said deterministic search includes:

(i) processing said coded keys to determine a required set of auxiliary data, said set being required to proceed with said search, and

(ii) comparing said set with said input key to determine a result of said search.

17. The method of claim 2, wherein a certain match exists between said input key and a key entry of said plurality of key entries, and wherein said deterministic search is performed solely by processing of said coded keys.

18. The method of claim 1, further comprising the step of:

(d) storing said plurality of key entries in a particular order.

19. The method of claim 18, wherein said particular order is a monotonic order.

20. The method of claim 1, wherein said transformation is a unidirectional transformation.

21. A computer-implemented method of searching an ordered database using transformed key entries, the method comprising the steps of:

(a) providing a system including;

(i) a memory for storing a plurality of key entries, and

(ii) processing logic for;

(A) transforming said key entries into coded entries, and

(B) searching said coded entries;

(b) performing a transformation of each key entry of said plurality of key entries so as to obtain a plurality of coded entries;

(c) arranging said coded entries in a search-tree structure having at least one node, such that each of said at least one node includes a plurality of said coded entries, and

(d) performing a deterministic search within said at least one node of said search-tree structure so as to obtain a match between an input key and a key entry of said key entries.

22. The method of claim 21, wherein each coded entry of said coded entries includes information relating to at least one different key entry.

23. The method of claim 21, wherein a first coded entry of said coded entries includes positional information relating to a first different key entry, and wherein a second coded entry of said coded entries includes positional information relating to a second different key entry.

24. The method of claim 21, wherein each coded entry of said coded entries includes positional information relating to a different respective key entry.

25. The method of claim 21, wherein said transformation is a deterministic transformation.

26. The method of claim 21, wherein said transformation is a pre-determined transformation.

27. The method of claim 21, wherein said search within said at least one node is deterministic with respect to a required amount of auxiliary data.

28. The method of claim 27, wherein said auxiliary data includes at least a portion of a key entry of said key entries.

29. The method of claim 28, wherein a size of said auxiliary data equals less than half of a size of said key entries.

30. The method of claim 27, wherein said auxiliary data is a portion of a single key entry.

31. The method of claim 21, wherein said information for a particular coded entry of said compacted coded key entries includes information resulting from at least one varying bit.

32. The method of claim 31, wherein said at least one varying bit includes a most significant bit.

33. The method of claim 21, wherein said search is deterministic with respect to specific key data.

34. The method of claim 33, wherein said specific key data includes said input key.

35. The method of claim 33, wherein said specific key data includes said key entries.

36. The method of claim 33, wherein said specific key data includes said coded entries in said data structure.

37. The method of claim 21, wherein said search is deterministic with respect to a required amount of auxiliary data.

38. The method of claim 21, wherein said search is a pre-determined search.

39. A computer-implemented method of searching an ordered database using transformed key entries, the method comprising the steps of:

(a) providing a system including;

(i) a memory for storing a plurality of key entries, and

(ii) processing logic for;

(A) transforming said key entries into coded entries, and (B) searching said coded entries;

(b) performing a pre-determined transformation of each key entry of said plurality of key entries so as to obtain a plurality of coded entries;

(c) arranging said coded entries in a search-tree structure having at least one node, such that each of said at least one node includes a plurality of said coded entries, and

(d) performing a pipelined search within said search-tree structure so as to obtain a plurality of matches, each of said matches representing a match between a particular, respective input key and a particular key entry of said key entries.