Method and apparatus for expandable biometric searching

• US 6,047,281 A
• Filed: 12/05/1997
• Issued: 04/04/2000
• Est. Priority Date: 12/05/1997
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: AuthenTec Incorporated (Apple Inc.)
• Inventors: Setlak, Dale R., Wilson, Steven D., Momchev, Orlin, Virani, Amirali
• Primary Examiner(s): Fetting, Anton W.
• Assistant Examiner(s): Shah, Sanjiv
• Application Number:
  US08/986,058
• Time in Patent Office: 851 Days
• Field of Search: 707/104, 707/101, 707/102, 707/1, 707/3, 707/4, 707/5, 707/6, 707/7, 707/9, 707/10, 382/124-127, 382/116, 382/115, 382/283, 235/380, 235/382
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2264 Multidimensional index structures
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A method and apparatus for expandable biometric searching are provided. The method preferably includes forming a plurality of biometric records. Each of the biometric records includes at least one biometric index and biometric data associated with the at least one biometric index. The method also includes assigning each of the plurality of biometric records to a plurality of biometric data groups so that each of the plurality of biometric data groups includes a full range of biometric indexes and about the same number of biometric records. Each of the plurality of biometric data groups is preferably uncorrelated to the biometric indexes. The method further preferably includes assigning each of the plurality of biometric data groups to a plurality of biometric searching engines so that each of the plurality of biometric data groups is assigned to only one of the plurality of biometric searching engines. An apparatus for expandable biometric searching preferably includes a plurality of biometric data groups each of which includes a plurality of biometric records having at least one biometric index and biometric data and a full range of biometric indexes. Each of the plurality of biometric data groups is preferably uncorrelated to the biometric indexes. An apparatus also preferably includes a plurality of biometric searching engines. Each of the plurality of data groups is connected to only one of the plurality of biometric searching engines.

Claims

1. A method of expandably storing and searching biometric data, the method comprising the steps of:

providing a plurality of biometric data groups, each of the plurality of biometric data groups having a plurality of biometric records stored therein, each of the plurality of biometric records including at least one biometric index and biometric data associated with the at least one biometric index, each of the plurality of biometric data groups having about the same full range of biometric indexes and having about the same number of biometric records stored therein; and

assigning each of the plurality of separate data groups to a plurality of biometric searching engines for performing a search of biometric data from the plurality of separate biometric data groups so that each of the plurality of biometric data groups is assigned to only one of the plurality of biometric searching engines.

2. A method as defined in claim 1, further comprising the steps of adding an additional biometric searching engine and reassigning biometric records from each of the plurality of separate biometric data groups to the additional biometric searching engine for performing a search of biometric data therefrom.

3. A method as defined in claim 1, further comprising the step of selectively searching the plurality of data groups in parallel for preselected biometric data.

4. A method as defined in claim 1, further comprising the step of assigning the at least one biometric index to biometric data independent of the biometric data.

5. A method as defined in claim 1, further comprising the step of hashing an additional biometric record to one of the plurality of separate data groups.

6. A method as defined in claim 1, wherein each of the biometric records further includes a plurality of indexes, each of the plurality of indexes being independent of the other ones of the plurality of indexes.

7. A method as defined in claim 1, wherein the plurality of biometric indexes is generally uniformly distributed over the full range of biometric indexes.

8. A method as defined in claim 1, wherein the biometric data comprises features of fingerprint data, and wherein the biometric indexes each comprise a numeric value.

9. A method as defined in claim 8, wherein each of the plurality of separate biometric data groups is uncorrelated to the biometric indexes.

10. A method as defined in claim 1, further comprising searching for biometric data which matches at least one preselected biometric characteristic using at least one of the plurality of biometric searching engines.

11. A method of expandably storing and searching biometric data, the method comprising the steps of:

assigning a plurality of biometric indexes to a plurality of biometric data groups so that each of the plurality of biometric data groups includes a full range of biometric indexes and about the same number of biometric records, each of the plurality of biometric data groups being uncorrelated to the biometric indexes; and

assigning each of the plurality of biometric data groups to a plurality of biometric searching engines so that each of the plurality of biometric data groups is assigned to only one of the plurality of biometric searching engines.

12. A method as defined in claim 11, further comprising the steps of adding an additional biometric searching engine and reassigning biometric records from each of the plurality of biometric data groups to the additional biometric searching engine for performing a search of biometric data therefrom.

13. A method as defined in claim 11, further comprising the step of selectively searching the plurality of data groups in parallel for preselected biometric data.

14. A method as defined in claim 11, further comprising the step of assigning the plurality of indexes to biometric data independent of the biometric data.

15. A method as defined in claim 11, further comprising the step of hashing additional biometric indexes to one of the plurality of separate data groups.

16. A method as defined in claim 11, wherein each of the plurality of indexes are independent of the other ones of the plurality of indexes.

17. A method as defined in claim 11, wherein the plurality of biometric indexes is generally uniformly distributed over the full range of biometric indexes.

18. A method as defined in claim 11, wherein the biometric data comprises features of fingerprint data, and wherein the biometric indexes each comprise a numeric value.

19. A method as defined in claim 11, further comprising searching for biometric data which matches at least one preselected biometric characteristic using at least one of the plurality of biometric searching engines.

20. A method of expandably storing and searching biometric data, the method comprising the steps of:

forming a plurality of biometric records, each of the biometric records including at least one biometric index and biometric data associated with the at least one biometric index;

assigning each of the plurality of biometric records to a plurality of biometric data groups so that each of the plurality of biometric data groups includes a full range of biometric indexes and about the same number of biometric records, each of the plurality of biometric data groups being uncorrelated to the biometric indexes; and

assigning each of the plurality of biometric data groups to a plurality of biometric searching engines so that each of the plurality of biometric data groups is assigned to only one of the plurality of biometric searching engines.

21. A method as defined in claim 20, further comprising the steps of adding an additional biometric searching engine and reassigning biometric records from each of the plurality of biometric data groups to the additional biometric searching engine for performing a search of biometric data therefrom.

22. A method as defined in claim 21, further comprising the step of selectively searching the plurality of data groups in parallel for preselected biometric data.

23. A method as defined in claim 22, further comprising the step of arbitrarily assigning the at least one biometric index to biometric data independent of the biometric data.

24. A method as defined in claim 23, further comprising the step of hashing an additional biometric record to one of the plurality of data groups.

25. A method as defined in claim 23, wherein each of the biometric records further includes a plurality of indexes, each of the plurality of indexes being independent of the other ones of the plurality of indexes.

26. A method as defined in claim 25, wherein the plurality of biometric indexes is generally uniformly distributed over the full range of biometric indexes.

27. A method as defined in claim 26, wherein the biometric data comprises features of fingerprint data, and wherein the biometric indexes each comprise a numeric value.

28. A method as defined in claim 27, wherein each of the plurality of biometric data groups is uncorrelated to the biometric indexes.

29. A method as defined in claim 28, further comprising searching for biometric data which matches at least one preselected biometric characteristic using at least one of the plurality of biometric searching engines.

30. An apparatus for expandable biometric searching, the apparatus comprising:

biometric record forming means for forming a plurality of biometric records, each of the biometric records including at least one biometric index and biometric data associated with the at least one biometric index;

a plurality of biometric data groups for storing the plurality of biometric records, each of the plurality of biometric data groups including a full range of biometric indexes and about the same number of biometric records, each of the plurality of biometric data groups being uncorrelated to the biometric indexes; and

a plurality of biometric searching engines, each of the plurality of biometric data groups being connected to only one of the plurality of biometric searching engines.

31. An apparatus as defined in claim 30, further comprising an additional biometric searching engine and means for reassigning biometric records from each of the plurality of biometric data groups to the additional biometric searching engine for performing a search of biometric data therefrom.

32. An apparatus as defined in claim 31, further comprising parallel searching means for selectively searching the plurality of data groups in parallel for preselected biometric data.

33. An apparatus as defined in claim 32, wherein said biometric record forming means includes index assigning means for arbitrarily assigning the at least one biometric index to biometric data independent of the biometric data.

34. An apparatus as defined in claim 33, further comprising biometric record assigning means for hashing additional biometric records to one of the plurality of data groups.

35. An apparatus as defined in claim 33, wherein each of the biometric records further includes a plurality of indexes, each of the plurality of indexes being independent of the other ones of the plurality of indexes.

36. An apparatus as defined in claim 35, wherein the plurality of biometric indexes is generally uniformly distributed over the full range of biometric indexes.

37. An apparatus as defined in claim 36, wherein the biometric data comprises features of fingerprint data, and wherein the biometric indexes each comprise a numeric value.

38. An apparatus as defined in claim 37, wherein each of the plurality of biometric data groups is uncorrelated to the biometric indexes.

39. An apparatus for expandable biometric searching, the apparatus comprising:

a plurality of biometric data groups, each of the plurality of biometric data groups including a plurality of biometric records having at least one biometric index and biometric data and a full range of biometric indexes, each of the plurality of biometric data groups being uncorrelated to the biometric indexes; and

a plurality of biometric searching engines, each of the plurality of biometric data groups being connected to only one of the plurality of biometric searching engines.

40. An apparatus as defined in claim 39, further comprising an additional biometric searching engine and means for reassigning biometric records from each of the plurality of biometric data groups to the additional biometric searching engine for performing a search of biometric data therefrom.

41. An apparatus as defined in claim 40, further comprising parallel searching means for selectively searching the plurality of data groups in parallel for preselected biometric data.

42. An apparatus as defined in claim 41, wherein said biometric record forming means includes index assigning means for arbitrarily assigning the at least one biometric index to biometric data independent of the biometric data.

43. An apparatus as defined in claim 42, further comprising biometric record assigning means for hashing additional biometric records to one of the plurality of data groups.

44. An apparatus as defined in claim 42, wherein each of the biometric records further includes a plurality of indexes, each of the plurality of indexes being independent of the other ones of the plurality of indexes.

45. An apparatus as defined in claim 44, wherein the plurality of biometric indexes is generally uniformly distributed over the full range of biometric indexes.

46. An apparatus as defined in claim 45, wherein the biometric data comprises features of fingerprint data, and wherein the biometric indexes each comprise a numeric value.

47. An apparatus as defined in claim 46, wherein each of the plurality of biometric data groups is uncorrelated to the biometric indexes.