Method and apparatus for expandable biometric searching

• US 6,070,159 A
• Filed: 12/05/1997
• Issued: 05/30/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,099
• Time in Patent Office: 907 Days
• Field of Search: 707/3, 707/1, 707/4, 707/5, 707/6, 707/9, 707/10, 707/104, 707/101, 707/102, 707/103, 382/124-127, 382/115-116, 382/283, 235/380, 235/382
• US Class Current: 1/1
• CPC Class Codes: G06V 40/1365 Matching; Classification
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A method and apparatus for expandable biometric searching are provided. A method preferably includes forming a plurality of biometric records. Each of the plurality of biometric records preferably includes at least one biometric index and biometric data associated with the at least one biometric index. The method also includes forming a multi-dimensional virtual space having a data structure with the plurality of biometric records stored therein and generally defined by a configuration of a tree. Each of the nodal regions at each level of the tree preferably has a generally spherical shape. 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 records stored therein. The apparatus also includes a plurality of biometric searching engines. Each of the plurality of biometric searching engines includes data group managing means connected to said plurality of biometric data groups for managing the plurality of data groups. The data group managing means preferably includes multi-dimensional search space constructing means for constructing a multi-dimensional search space having a data structure with the plurality of biometric records stored therein and generally defined by a configuration of a tree. Each of the nodal regions at each level of the tree preferably has a generally spherical shape.

Claims

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

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

forming a multi-dimensional virtual space having the data structure with the plurality of biometric records stored therein and generally defined by a configuration of a tree, each nodal region at each level of the tree having a generally spherical shape;

assigning each of the plurality of biometric records to one of a plurality of biometric data groups;

assigning each of the plurality of biometric 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 space and to construct internal maps for each data group being controlled.

2. A method as defined in claim 1, further comprising inserting at least one additional biometric record into the data structure of the space responsive to following nodal regions of the tree along a data path having a maximum overlap of the at least one biometric record with each entry within a level of the nodal regions.

3. A method as defined in claim 2, wherein the inserting step includes splitting a nodal region to form a new node responsive to the nodal region being full.

4. A method as defined in claim 3, wherein the splitting step includes locating a selected nodal region of the tree and calculating the dimension of the multi-dimensional space having the maximum variance for all of the biometric records within the selected nodal region in all dimensions of the space.

5. A method as defined in claim 4, wherein the splitting step further includes calculating the mean of the plurality of biometric records within the selected nodal region and sorting the plurality of records in the selected nodal region in ascending order from the mean.

6. A method as defined in claim 5, wherein the splitting step further includes dividing the nodal region into two portions along the mean so as to form two new nodal regions, and wherein the inserting step further includes inserting the additional biometric record into only one of the two new nodal regions.

7. A method as defined in claim 6, wherein the step of inserting the additional biometric record into only one of the two new nodal regions includes calculating a minimum boundary region for each of the two divided portions and selecting the one of the divided portions having the greater distance from a parent nodal region of the nodal region being split.

8. A method as defined in claim 1, wherein the multi-dimensional space includes a balanced tree configuration defined by the multi-dimensional space having at least one root nodal region and a plurality of leaf nodal regions so that each of the plurality of leaf nodal regions are located on the same level of the tree of the multi-dimensional space.

9. A method as defined in claim 1, wherein the generally spherical shape includes boundaries being generally defined by a center point and a radius from the center point.

10. A method as defined in claim 9, wherein each generally spherical shape comprises a hyper-sphere.

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

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

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

14. A method as defined in claim 1, wherein the inserting step includes uniformly distributing the plurality of biometric indexes over the full range of biometric indexes in each of the plurality of data groups, and wherein each of the plurality of biometric data groups is uncorrelated to the biometric indexes.

15. 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.

16. A method of expandbly storing and searching biometric data, the method comprising the steps of:

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

forming a multi-dimensional virtual space having a data structure with the plurality of biometric records stored therein and generally defined by a configuration of a tree, each nodal regions at each level of the tree having a predetermined shape;

dynamically inserting at least one additional biometric record into the data structure of the space responsive to following the nodal regions of the tree along a data path having a maximum overlap of the at least one biometric record with each entry within a level of the nodal regions;

assigning each of the plurality of biometric records to one of a plurality of biometric data groups;

assigning each of the plurality of biometric 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 space and to construct internal maps for each data group being controlled.

17. A method as defined in claim 16, wherein the inserting step includes splitting a nodal region to form a new node responsive to the nodal region being full.

18. A method as defined in claim 17, wherein the splitting step includes locating a selected nodal region of the tree and calculating the dimension of the multi-dimensional space having the maximum variance for all of the biometric records within the selected nodal region in all dimensions of the space.

19. A method as defined in claim 18, wherein the splitting step further includes calculating the mean of the plurality of biometric records within the selected nodal region and sorting the plurality of records in the selected nodal region in ascending order from the mean.

20. A method as defined in claim 19, wherein the splitting step further includes dividing the nodal region into two portions along the mean so as to form two new nodal regions, and wherein the inserting step further includes inserting the additional biometric record into only one of the two new nodal regions.

21. A method as defined in claim 20, wherein the step of inserting the additional biometric record into only one of the two new nodal regions includes calculating a minimum boundary region for each of the two divided portions and selecting the one of the divided portions having the greater distance from a parent nodal region of the nodal region being split.

22. A method as defined in claim 16, wherein the multi-dimensional space includes a balanced tree configuration defined by the multi-dimensional space having at least one root nodal region and a plurality of leaf nodal regions so that each of the plurality of leaf nodal regions are located on the same level of the tree of the multi-dimensional space.

23. A method as defined in claim 16, wherein the predetermined shape comprises a generally spherical shape having boundaries being generally defined by a center point and a radius from the center point.

24. A method as defined in claim 23, wherein each generally spherical shape comprises a hyper-sphere.

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

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

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

28. A method as defined in claim 16, wherein the inserting step includes uniformly distributing the plurality of biometric indexes over the full range of biometric indexes in each of the plurality of data groups, and wherein each of the plurality of biometric data groups is uncorrelated to the biometric indexes.

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

30. A method of expandbly storing and searching data, the method comprising the steps of:

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

forming a multi-dimensional virtual space having a data structure with the plurality of records stored therein and generally defined by a configuration of a tree;

inserting at least one additional record into the data structure of the space responsive to following the nodal regions of the tree along a data path having a maximum overlap of the at least one record with each entry within a level of the nodal regions;

assigning each of the plurality of records to one of a plurality of data groups;

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

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

31. A method as defined in claim 30, wherein the inserting step includes splitting a nodal region to form a new node responsive to the nodal region being full.

32. A method as defined in claim 31, wherein the splitting step includes locating a selected nodal region of the tree and calculating the dimension of the multi-dimensional space having the maximum variance for all of the records within the selected nodal region in all dimensions of the space.

33. A method as defined in claim 32, wherein the splitting step further includes calculating the mean of the plurality of records within the selected nodal region and sorting the plurality of records in the selected nodal region in ascending order from the mean.

34. A method as defined in claim 33, wherein the splitting step further includes dividing the nodal region into two portions along the mean so as to form two new nodal regions, and wherein the inserting step further includes inserting the additional record into only one of the two new nodal regions.

35. A method as defined in claim 34, wherein the step of inserting the additional record into only one of the two new nodal regions includes calculating a minimum boundary region for each of the two divided portions and selecting the one of the divided portions having the greater distance from a parent nodal region of the nodal region being split.

36. A method as defined in claim 35, wherein the multi-dimensional space includes a balanced tree configuration defined by the multi-dimensional space having at least one root nodal region and a plurality of leaf nodal regions so that each of the plurality of leaf nodal regions are located on the same level of the tree of the multi-dimensional space, and wherein each of the nodal regions at each level of the tree has a predetermined shape.

37. A method as defined in claim 36, wherein the predetermined shape comprises a generally spherical shape having boundaries being generally defined by a center point and a radius from the center point.

38. A method as defined in claim 37, wherein each generally spherical shape comprises a hyper-sphere.

39. A method as defined in claim 32, further comprising selecting from the multi-dimensional space at least one record and matching data from the at least one record to data being searched.

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

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

42. A method as defined in claim 41, wherein the inserting step includes uniformly distributing the plurality of indexes over the full range of indexes in each of the plurality of data groups, and wherein each of the plurality of data groups is uncorrelated to the indexes.

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

44. 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 having a data structure with the plurality of biometric records stored therein and generally defined by a configuration of a tree, each of the nodal regions at each level of the tree having a generally spherical shape.

45. An apparatus as defined in claim 44, 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.

46. An apparatus as defined in claim 45, 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.

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

48. An apparatus as defined in claim 47, wherein the generally spherical shape comprises a hyper-sphere.

49. An apparatus as defined in claim 44, 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.

50. An apparatus as defined in claim 49, 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.

51. An apparatus as defined in claim 50, 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.

52. An apparatus as defined in claim 51, 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.

53. 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.

54. An apparatus for expandable searching of data, the apparatus comprising:

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

a plurality of searching engines, each of the plurality of searching engines comprising data group managing means connected to said plurality of 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 having a data structure generally defined by a configuration of a tree; and

record assigning means for hashing at least one additional record into the data structure of the space responsive to following the nodal regions of the tree in a data path having a maximum overlap of the at least one additional record with each of the records within a level of the nodal regions.

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

56. An apparatus as defined in claim 55, 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.

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

58. An apparatus as defined in claim 57, wherein the generally spherical shape comprises a hyper-sphere.

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

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

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

62. An apparatus as defined in claim 61, 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.

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