Apparatus and method for expandable biometric searching

• US 6,047,282 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: Wilson, Steven D., Momchev, Orlin, Virani, Amirali, Setlak, Dale R.
• Primary Examiner(s): Fetting, Anton W.
• Assistant Examiner(s): Shah, Sanjiv
• Application Number:
  US08/986,162
• Time in Patent Office: 851 Days
• Field of Search: 707/3, 707/4, 707/5, 707/6, 707/1, 707/7, 707/9, 707/10, 707/101, 707/104, 707/102, 382/124, 382/125-127, 382/116, 382/115, 235/380, 235/382
• US Class Current: 1/1
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content
• CPC Class Codes: G06F 18/24323 Tree-organised classifiers
• CPC Class Codes: G06V 40/10 Human or animal bodies, e.g. vehicle occupants or pedestrians; Body parts, e.g. hands
• 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 apparatus preferably includes a database having a plurality of biometric data groups. Each of the plurality of biometric data groups includes a plurality of biometric records stored therein, and each of the biometric records includes at least one biometric index and biometric data associated with the at least one biometric index. The apparatus also includes a plurality of biometric searching engines. Each of the plurality of biometric searching engines preferably include a data group manager connected to the plurality of biometric data groups for managing the plurality of data groups. The data group manager includes multi-dimensional search space constructing means for constructing a multi-dimensional search space and internal map constructing means for constructing internal maps for each data group being managed. A method of expandably storing and searching biometric data preferably includes assigning each of a plurality of data groups to a plurality of biometric searching engines for performing a search of biometric data from the plurality of biometric data groups so that each of the plurality of biometric data groups is assigned only one of the plurality of biometric searching engines and controlling the plurality of data groups so as to construct a multi-dimensional search space and to construct internal maps for each data group being controlled.

Claims

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

a database having a plurality of biometric data groups, each of the plurality of biometric data groups including a plurality of biometric records stored therein, each of the biometric records including at least one biometric index and biometric data associated with the at least one biometric index; and

a plurality of biometric searching engines, each of the plurality of biometric searching engines comprising data group managing means connected to said plurality of biometric data groups for managing the plurality of data groups, said data group managing means including multi-dimensional search space constructing means for constructing a multi-dimensional search space and internal map constructing means for constructing internal maps for each data group being managed.

2. An apparatus as defined in claim 1, wherein each of said plurality of searching engines further comprises selecting means for selecting from the multi-dimensional search space at least one biometric record and matching means responsive to said selecting means for matching a biometric from the at least one biometric record to a biometric being searched.

3. An apparatus as defined in claim 1, further comprising communications controlling means for controlling communications to and from the plurality of searching engines, transaction scheduling means responsive to said communications controlling means for scheduling priority of searching transactions by the plurality of searching engines, and searching means responsive to said transaction scheduling means for initiating search commands.

4. An apparatus as defined in claim 3, further comprising an application process controller in communication with each of the plurality of status controllers for controlling at least one selected application process.

5. An apparatus as defined in claim 4, further comprising logging means responsive to one of the plurality of status controllers for logging message data for selected applications.

6. An apparatus as defined in claim 1, further comprising a plurality of status controllers for controlling the status of the plurality of searching engines, each of the plurality of status controllers being connected to a different one of the plurality of searching engines.

7. An apparatus as defined in claim 1, wherein the multi-dimensional search space includes a balanced tree configuration defined by the search space having at least one root node and a plurality of leaf nodes so that each of the plurality of leaf nodes are located on the same level of the tree of the search space.

8. An apparatus as defined in claim 7, wherein the multi-dimensional search space further includes a data structure being defined by a plurality of spherical shapes.

9. An apparatus as defined in claim 8, wherein each of the plurality of spherical shapes comprises a hyper-sphere.

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

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

12. An apparatus as defined in claim 11, further comprising biometric record forming means for forming the plurality of biometric records, said biometric record forming means including index assigning means for assigning the at least one biometric index to biometric data independent of the biometric data.

13. An apparatus as defined in claim 12, further comprising biometric record assigning means for hashing additional biometric records to one of the plurality of data groups, and 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.

14. An apparatus as defined in claim 13, wherein the plurality of biometric indexes is generally uniformly distributed over the full range of biometric indexes and wherein each of the plurality of biometric data groups is uncorrelated to the biometric indexes.

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

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

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

a plurality of biometric searching engines, the plurality of biometric searching engines comprising data groups for managing the plurality of data groups, said data group managing means including multi-dimensional search space constructing means for constructing a multi-dimensional search space and internal map constructing means for constructing internal maps for each data group being managed.

17. An apparatus as defined in claim 16, wherein each of said plurality of searching engines further comprises selecting means for selecting from the multi-dimensional search space at least one biometric record and matching means responsive to said selecting means for matching a biometric from the at least one biometric record to a biometric being searched.

18. An apparatus as defined in claim 16, further comprising communications controlling means for controlling communications to and from the plurality of searching engines, transaction scheduling means responsive to said communications controlling means for scheduling priority of searching transactions by the plurality of searching engines, and searching means responsive to said transaction scheduling means for initiating search commands.

19. An apparatus as defined in claim 16, further comprising a plurality of status controllers for controlling the status of the plurality of searching engines, each of the plurality of status controllers being connected to a different one of the plurality of searching engines.

20. An apparatus as defined in claim 19, further comprising an application process controller in communication with each of the plurality of status controllers for controlling at least one selected application process.

21. An apparatus as defined in claim 19, further comprising logging means responsive to one of the plurality of status controllers for logging message data for selected applications.

22. An apparatus as defined in claim 16, wherein the multi-dimensional search space includes a balanced tree configuration defined by the search space having at least one root node and a plurality of leaf nodes so that each of the plurality of leaf nodes are located on the same level of the tree of the search space.

23. An apparatus as defined in claim 16, wherein the multi-dimensional search space includes a data structure being defined by a plurality of spherical shapes.

24. An apparatus as defined in claim 23, wherein each of the plurality of spherical shapes comprises a hyper-sphere.

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

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

27. An apparatus as defined in claim 16, further comprising biometric record forming means for forming the plurality of biometric records, said biometric record forming means including index assigning means for assigning the at least one biometric index to biometric data independent of the biometric data.

28. An apparatus as defined in claim 16, further comprising biometric record assigning means for hashing additional biometric records to one of the plurality of data groups, and 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.

29. An apparatus as defined in claim 16, wherein the plurality of biometric indexes is generally uniformly distributed over the full range of biometric indexes and wherein each of the plurality of biometric data groups is uncorrelated to the biometric indexes.

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

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

at least one client computer having biometric recording means associated therewith for recording at least one biometric records, the at least one biometric record including at least one biometric index and biometric data associated with the at least one biometric index;

a data communications network connected to the client computer; and

at least one server computer connected to the data communications network, the server computer including a database having a plurality of biometric data groups, each of the plurality of biometric data groups including a plurality of biometric records stored therein, each of the biometric records including at least one biometric index and biometric data associated with the at least one biometric index, and a plurality of biometric searching engines, each of the plurality of biometric searching engines comprising data group managing means connected to said plurality of biometric data groups for managing the plurality of data groups, said data group managing means including multi-dimensional search space constructing means for constructing a multi-dimensional search space and internal map constructing means for constructing internal maps for each data group being managed.

32. An apparatus as defined in claim 31, wherein each of said plurality of searching engines further comprises selecting means for selecting from the multi-dimensional search space at least one biometric record and matching means responsive to said selecting means for matching a biometric from the at least one biometric record to a biometric being searched.

33. An apparatus as defined in claim 32, further comprising communications controlling means for controlling communications to and from the plurality of searching engines, transaction scheduling means responsive to said communications controlling means for scheduling priority of searching transactions by the plurality of searching engines, and searching means responsive to said transaction scheduling means for initiating search commands.

34. An apparatus as defined in claim 33, further comprising a plurality of status controllers for controlling the status of the plurality of searching engines, each of the plurality of status controllers being connected to a different one of the plurality of searching engines.

35. An apparatus as defined in claim 34, further comprising an application process controller in communication with each of the plurality of status controllers for controlling at least one selected application process.

36. An apparatus as defined in claim 35, further comprising logging means responsive to one of the plurality of status controllers for logging message data for selected applications.

37. An apparatus as defined in claim 36, wherein the multi-dimensional search space includes a balanced tree configuration defined by the search space having at least one root node and a plurality of leaf nodes so that each of the plurality of leaf nodes are located on the same level of the tree of the search space.

38. An apparatus as defined in claim 37, wherein the multi-dimensional search space further includes a data structure being defined by a plurality of spherical shapes.

39. An apparatus as defined in claim 38, wherein each of the plurality of spherical shapes comprises a hyper-sphere.

40. An apparatus as defined in claim 39, further comprising an additional biometric searching engine and means for reassigning biometric data groups 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, further comprising biometric record forming means for forming the plurality of biometric records, said biometric record forming means including index assigning means for 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, and 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.

44. An apparatus as defined in claim 43, wherein the plurality of biometric indexes is generally uniformly distributed over the full range of biometric indexes and wherein each of the plurality of biometric data groups is uncorrelated to the biometric indexes.

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

46. 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;

assigning each of the plurality of 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 only one of the plurality of biometric searching engines; and

controlling the plurality of data groups so as to construct a multi-dimensional search space and to construct internal maps for each data group being controlled.

47. A method as defined in claim 46, further comprising selecting from the multi-dimensional search space at least one biometric record and matching a biometric from the at least one biometric record to a biometric being searched.

48. A method as defined in claim 46, further comprising controlling communications to and from the multi-dimensional search space so as to search therefrom, scheduling priority of searching transactions from the multi-dimensional search space, and searching the multi-dimensional search space.

49. A method as defined in claim 48, further comprising controlling the status of the searching transactions from the multi-dimensional search space.

50. A method as defined in claim 49, further comprising controlling at least one selected application process responsive to the search transaction status and logging message data for selected applications.

51. A method as defined in claim 46, wherein the multi-dimensional search space includes a balanced tree configuration defined by the search space having at least one root node and a plurality of leaf nodes so that each of the plurality of leaf nodes are located on the same level of the tree of the search space.

52. A method as defined in claim 51, wherein the multi-dimensional search space further includes a data structure being defined by a plurality of spherical shapes.

53. A method as defined in claim 52, wherein each of the plurality of spherical shapes comprises a hyper-sphere.

54. A method as defined in claim 46, further comprising the step of searching each of the plurality of data groups in parallel for preselected biometric data.

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

56. A method as defined in claim 46, further comprising the step of hashing an additional biometric record to one of the plurality of separate database addresses.

57. A method as defined in claim 46, 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.

58. A method as defined in claim 46, wherein the providing step includes uniformly distributing the plurality of biometric indexes over the predetermined full range of biometric indexes in each of the plurality of data groups.

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

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

61. A method as defined in claim 60, further comprising searching for biometric data which matches at least one preselected biometric characteristic.

62. A method for expandably storing and searching biometric data, the method comprising the step of:

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

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

controlling the plurality of data groups so as to construct the multi-dimensional search space and to construct internal maps for each data group being controlled.

63. A method as defined in claim 62, further comprising selecting from the multi-dimensional search space at least one biometric record and matching a biometric from the at least one biometric record to a biometric being searched.

64. A method as defined in claim 63, further comprising controlling communications to and from the multi-dimensional search space so as to search therefrom, scheduling priority of searching transactions from the multi-dimensional search space, and searching the multi-dimensional search space.

65. A method as defined in claim 64, further comprising controlling the status of the searching transactions from the multi-dimensional search space.

66. A method as defined in claim 65, further comprising controlling at least one selected application process responsive to the search transaction status and logging message data for selected applications.

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

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

69. A method as defined in claim 68, further comprising searching for biometric data which matches at least one preselected biometric characteristic.

70. A method as defined in claim 62, wherein the multi-dimensional search space includes a balanced tree configuration defined by the search space having at least one root node and a plurality of leaf nodes so that each of the plurality of leaf nodes are located on the same level of the tree of the search space.

71. A method as defined in claim 70, wherein the multi-dimensional search space further includes a data structure being defined by a plurality of spherical shapes.

72. A method as defined in claim 71, wherein each of the plurality of spherical shapes comprises a hyper-sphere.

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

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

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

76. A method as defined in claim 75, 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.

77. A method as defined in claim 76, wherein the providing step includes uniformly distributing the plurality of biometric indexes over the predetermined full range of biometric indexes in each of the plurality of data groups.