Computational workload in biometric identification systems: an overview <s> Introduction <s> The nearestor near-neighbor query problems arise in a large variety of database applications, usually in the context of similarity searching. Of late, there has been increasing interest in building search/index structures for performing similarity search over high-dimensional data, e.g., image databases, document collections, time-series databases, and genome databases. Unfortunately, all known techniques for solving this problem fall prey to the \curse of dimensionality." That is, the data structures scale poorly with data dimensionality; in fact, if the number of dimensions exceeds 10 to 20, searching in k-d trees and related structures involves the inspection of a large fraction of the database, thereby doing no better than brute-force linear search. It has been suggested that since the selection of features and the choice of a distance metric in typical applications is rather heuristic, determining an approximate nearest neighbor should su ce for most practical purposes. In this paper, we examine a novel scheme for approximate similarity search based on hashing. The basic idea is to hash the points Supported by NAVY N00014-96-1-1221 grant and NSF Grant IIS-9811904. Supported by Stanford Graduate Fellowship and NSF NYI Award CCR-9357849. Supported by ARO MURI Grant DAAH04-96-1-0007, NSF Grant IIS-9811904, and NSF Young Investigator Award CCR9357849, with matching funds from IBM, Mitsubishi, Schlumberger Foundation, Shell Foundation, and Xerox Corporation. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment. Proceedings of the 25th VLDB Conference, Edinburgh, Scotland, 1999. from the database so as to ensure that the probability of collision is much higher for objects that are close to each other than for those that are far apart. We provide experimental evidence that our method gives signi cant improvement in running time over other methods for searching in highdimensional spaces based on hierarchical tree decomposition. Experimental results also indicate that our scheme scales well even for a relatively large number of dimensions (more than 50). <s> BIB001 </s> Computational workload in biometric identification systems: an overview <s> Introduction <s> This report investigates the “decision landscapes” that characterize several forms of biometric decision making. The issues discussed include: (i) Estimating the degrees-of-freedom associated with different biometrics, as a way of measuring the randomness and complexity (and therefore the uniqueness) of their templates. (ii) The consequences of combining more than one biometric test to arrive at a decision. (iii) The requirements for performing identification by large-scale exhaustive database search, as opposed to mere verification by comparison against a single template. (iv) Scenarios for Biometric Key Cryptography (the use of biometrics for encryption of messages). These issues are considered here in abstract form, but where appropriate, the particular example of iris recognition is used as an illustration. A unifying theme of all four sets of issues is the role of combinatorial complexity, and its measurement, in determining the potential decisiveness of biometric decision making. <s> BIB002 </s> Computational workload in biometric identification systems: an overview <s> Introduction <s> The problem of searching the elements of a set that are close to a given query element under some similarity criterion has a vast number of applications in many branches of computer science, from pattern recognition to textual and multimedia information retrieval. We are interested in the rather general case where the similarity criterion defines a metric space, instead of the more restricted case of a vector space. Many solutions have been proposed in different areas, in many cases without cross-knowledge. Because of this, the same ideas have been reconceived several times, and very different presentations have been given for the same approaches. We present some basic results that explain the intrinsic difficulty of the search problem. This includes a quantitative definition of the elusive concept of "intrinsic dimensionality." We also present a unified view of all the known proposals to organize metric spaces, so as to be able to understand them under a common framework. Most approaches turn out to be variations on a few different concepts. We organize those works in a taxonomy that allows us to devise new algorithms from combinations of concepts not noticed before because of the lack of communication between different communities. We present experiments validating our results and comparing the existing approaches. We finish with recommendations for practitioners and open questions for future development. <s> BIB003 </s> Computational workload in biometric identification systems: an overview <s> Introduction <s> Similarity search is a very important operation in multimedia databases and other database applications involving complex objects, and involves finding objects in a data set S similar to a query object q, based on some similarity measure. In this article, we focus on methods for similarity search that make the general assumption that similarity is represented with a distance metric d. Existing methods for handling similarity search in this setting typically fall into one of two classes. The first directly indexes the objects based on distances (distance-based indexing), while the second is based on mapping to a vector space (mapping-based approach). The main part of this article is dedicated to a survey of distance-based indexing methods, but we also briefly outline how search occurs in mapping-based methods. We also present a general framework for performing search based on distances, and present algorithms for common types of queries that operate on an arbitrary "search hierarchy." These algorithms can be applied on each of the methods presented, provided a suitable search hierarchy is defined. <s> BIB004 </s> Computational workload in biometric identification systems: an overview <s> Introduction <s> A major new professional reference work on fingerprint security systems and technology from leading international researchers in the field. Handbook provides authoritative and comprehensive coverage of all major topics, concepts, and methods for fingerprint security systems. This unique reference work is an absolutely essential resource for all biometric security professionals, researchers, and systems administrators. <s> BIB005 </s> Computational workload in biometric identification systems: an overview <s> Introduction <s> The proliferation of information housed in computerized domains makes it vital to find tools to search these resources efficiently and effectively. Ordinary retrieval techniques are inadequate because sorting is simply impossible. Consequently, proximity searching has become a fundamental computation task in a variety of application areas. Similarity Search focuses on the state of the art in developing index structures for searching the metric space. Part I of the text describes major theoretical principles, and provides an extensive survey of specific techniques for a large range of applications. Part II concentrates on approaches particularly designed for searching in large collections of data. After describing the most popular centralized disk-based metric indexes, approximation techniques are presented as a way to significantly speed up search time at the cost of some imprecision in query results. Finally, the scalable and distributed metric structures are discussed. <s> BIB006 </s> Computational workload in biometric identification systems: an overview <s> Introduction <s> Biometrics is a rapidly evolving field with applications ranging from accessing ones computer to gaining entry into a country. The deployment of large-scale biometric systems in both commercial and government applications has increased public awareness of this technology. Recent years have seen significant growth in biometric research resulting in the development of innovative sensors, new algorithms, enhanced test methodologies and novel applications. This book addresses this void by inviting some of the prominent researchers in Biometrics to contribute chapters describing the fundamentals as well as the latest innovations in their respective areas of expertise. <s> BIB007 </s> Computational workload in biometric identification systems: an overview <s> Introduction <s> This highly anticipated new edition provides a comprehensive account of face recognition research and technology, spanning the full range of topics needed for designing operational face recognition systems. After a thorough introductory chapter, each of the following chapters focus on a specific topic, reviewing background information, up-to-date techniques, and recent results, as well as offering challenges and future directions. Features: fully updated, revised and expanded, covering the entire spectrum of concepts, methods, and algorithms for automated face detection and recognition systems; provides comprehensive coverage of face detection, tracking, alignment, feature extraction, and recognition technologies, and issues in evaluation, systems, security, and applications; contains numerous step-by-step algorithms; describes a broad range of applications; presents contributions from an international selection of experts; integrates numerous supporting graphs, tables, charts, and performance data. <s> BIB008 </s> Computational workload in biometric identification systems: an overview <s> Introduction <s> Similarity search (nearest neighbor search) is a problem of pursuing the data items whose distances to a query item are the smallest from a large database. Various methods have been developed to address this problem, and recently a lot of efforts have been devoted to approximate search. In this paper, we present a survey on one of the main solutions, hashing, which has been widely studied since the pioneering work locality sensitive hashing. We divide the hashing algorithms two main categories: locality sensitive hashing, which designs hash functions without exploring the data distribution and learning to hash, which learns hash functions according the data distribution, and review them from various aspects, including hash function design and distance measure and search scheme in the hash coding space. <s> BIB009 </s> Computational workload in biometric identification systems: an overview <s> Introduction <s> ABSTRACT Nowadays, the need to techniques, approaches, and algorithms to search on data is increased due to improvements in computer science and increasing amount of information. This ever increasing information volume has led to time and computation complexity. Recently, different methods to solve such problems are proposed. Among the others, nearest neighbor search is one of the best techniques to this end which is focused by many researchers. Different techniques are used for nearest neighbor search. In addition to put an end to some complexities, variety of these techniques has made them suitable for different applications such as pattern recognition, searching in multimedia data, information retrieval, databases, data mining, and computational geometry to name but a few. In this paper, by opening a new view to this problem, a comprehensive evaluation on structures, techniques and different algorithms in this field is done and a new categorization of techniques in NNS is presented. This categorization is consists of seven groups: Weighted, Reductional, Additive, Reverse, Continuous, Principal Axis and Other techniques which are studied, evaluated and compared in this paper. Complexity of used structures, techniques and their algorithms are discussed, as well. <s> BIB010 </s> Computational workload in biometric identification systems: an overview <s> Introduction <s> This encyclopedia provides a comprehensive reference to topics in biometrics including concepts, modalities, algorithms, devices, systems, security, performance testing, applications and standardization. With an AZ format and over 1400 entries, it provides easy access to relevant information on all aspects of biometrics for those seeking entry into this broad field.Entries are written by experts in biometrics and related fields. Each entry includes a definition, key words, list of synonyms, list of related entries, illustration(s), applications and a bibliography. Most entries include useful literature references providing the reader with a portal to more detailed information.Comprehensive and tutorial, the Encyclopedia of Biometrics, 2nd Edition is a practical resource for experts in the field and professionals interested in aspects of biometrics. <s> BIB011 </s> Computational workload in biometric identification systems: an overview <s> Introduction <s> This article reviews index structures for fast similarity search for objects represented by binary vectors (with components equal to 0 or 1). Structures for both exact and approximate search by Hamming distance and other similarity measures are considered. Mainly, index structures are presented that are based on hash tables and similarity-preserving hashing and also on tree structures, neighborhood graphs, and distributed neural autoassociative memory. Ideas of well-known algorithms and algorithms proposed in recent years are stated. <s> BIB012 </s> Computational workload in biometric identification systems: an overview <s> Introduction <s> Indexing/retrieving sets of iris biometric signatures has been a topic of increasing popularity, mostly due to the deployment of iris recognition systems in nationwide scale scenarios. In these conditions, for each identification attempt, there might exist hundreds of millions of enrolled identities and is unrealistic to match the probe against all gallery elements in a reasonable amount of time. Hence, the idea of indexing/retrieval is - upon receiving one sample - to find in a quick way a subset of elements in the database that most probably contains the identity of interest, i.e., the one corresponding to the probe. Most of the state-of-the-art strategies to index iris biometric signatures were devised to decision environments with a clear separation between genuine and impostor matching scores. However, if iris recognition systems work in low quality data, the resulting decision environments are poorly separable, with a significant overlap between the distributions of both matching scores. This chapter summarizes the state-of-the-art in terms of iris biometric indexing/retrieval and focuses in an indexing/retrieval method for such low quality data and operates at the code level, i.e., after the signature encoding process. Gallery codes are decomposed at multiple scales, and using the most reliable components of each scale, their position in a n-ary tree is determined. During retrieval, the probe is decomposed similarly, and the distances to multi-scale centroids are used to penalize paths in the tree. At the end, only a subset of branches is traversed up to the last level. <s> BIB013 </s> Computational workload in biometric identification systems: an overview <s> Introduction <s> This survey article considers index structures for fast similarity search for objects represented by real-valued vectors. Structures for both exact and faster but approximate similarity search are considered. Index structures based on partitioning into regions (including hierarchical ones) and on proximity graphs are mainly presented. The acceleration of similarity search using the transformation of initial data is also discussed. The ideas of concrete algorithms including recently proposed ones are outlined. The approaches to the acceleration of similarity search in index structures of the considered types and also on the basis of similarity-preserving hashing are discussed and compared. <s> BIB014 </s> Computational workload in biometric identification systems: an overview <s> Introduction <s> Nowadays, several biometric databases already contain millions of entries of individuals. With an increasing number of enrolled individuals, the response time of queries grows and can become critical. Fingerprint indexing offers a set of techniques to reduce the workload of entries, which have to be compared thoroughly. This work surveys research on such techniques. It focuses on the features of fingerprints, which are used as input. This survey also provides an assessment of the quality of the body of research in this field. Deficiencies herein are identified, e.g. ::: there is a lack of common datasets and metrics used for testing. <s> BIB015 </s> Computational workload in biometric identification systems: an overview <s> Introduction <s> This open access handbook provides the first comprehensive overview of biometrics exploiting the shape of human blood vessels for biometric recognition, i.e. vascular biometrics, including finger vein recognition, hand/palm vein recognition, retina recognition, and sclera recognition. After an introductory chapter summarizing the state of the art in and availability of commercial systems and open datasets/open source software, individual chapters focus on specific aspects of one of the biometric modalities, including questions of usability, security, and privacy. The book features contributions from both academia and major industrial manufacturers. <s> BIB016
The interest in biometric technologies has been steadily growing in recent years, as evidenced by various market value studies    and numbers of scientific publications in the area. Many states have utilised biometric technologies for purposes such as forensic investigations and law enforcement, border crossing entry-exit tracking, national citizen inventory (ID systems), and voter registration. By far the largest biometric deployment to date is the Indian Aadhaar national ID system, which, at the time of this writing, accommodates 1.3 billion enrolled subjects -almost the entire Indian population. Table 1 gives an overview of this and several other examples of operational and planned large-scale biometric systems. The table is non-exhaustive; instead, it seeks to highlight the diversity of the used biometric characteristics, the system purposes, and the geographical locations of some of the largest biometric systems around the world. In figure 1 , example images of biometric characteristics most commonly used in large-scale biometric identification systems are shown. Biometric systems can operate in a broad variety of ways. Two such ways (as defined in the ISO/IEC international standards   ) are: Biometric verification Referring to the "process of confirming a biometric claim through biometric comparison". Biometric identification Referring to the "process of searching against a biometric enrolment database to find and return the biometric reference identifier(s) attributable to a single individual". Two main scenarios can be distinguished in this case: closed-set identification, for which all potential users are enrolled in the system, and open-set identification, for which some potential users are not enrolled in the system. Naturally, the second case (i.e. open-set identification, as well as the duplicate-enrolment check) is the most interesting and challenging from the practical point of view for the aforementioned real-world applications. Unfortunately, in the worst case, an exhaustive search (i.e. comparing a probe against all the enrolled subjects) is required in order to reach a decision. This naïve approach quickly runs into two non-trivial problems: Computational costs As the number of enrolled subjects increases, the system response times become gradually slower, thus requiring optimisations and/or investment into larger hardware architectures. False positives costs The probability of at least one false positive (P N ) occurring in a identification scenario is: P N = 1 − (1 − P 1 ) N , where N is the number of enrolled subjects and P 1 the false positive probability of a one-to-one template comparison. This relationship is very demanding -even for systems which perform extremely well in verification mode (i.e. have low P 1 ), the value of P N very quickly becomes unacceptably high, as the number of enrolled subjects N increases (see BIB002 ). Note, that this equation ignores other system errors, e.g. the failure-toacquire rate and assumes that at a given threshold all subjects have the same false-match-rate, which likely is not the case. Nonetheless, it is a useful approximation for illustrating this challenge of biometric identification systems. In a recent interview  , Daugman, the pioneer of iris recognition (see  ), has stated that performing accurate and efficient biometric identification (i.e. not by an exhaustive search) is one of the important, unsolved issues in the biometrics field in general. Substantial research effort has been devoted to development of workload reduction methods, which seek to alleviate the aforementioned issues (especially the computational cost, since the biometric performance can also be improved through other means, such as increasing data quality and information fusion). Since the overall computational costs in a biometric identification scenario are dominated by Operational Aadhaar   India Fingerprint and iris (operational), face (potential future use) 1.3 billion National ID EURODAC   EU Fingerprint 7 million Border-control IDENT/US-VISIT  USA Fingerprint (operational), face and iris (pilots ongoing) 200 million Entry-exit CODIS  USA DNA 17.5 million Law enforcement CENI  DR Congo Fingerprint 46 million Voter registration Planned HART   USA Fingerprint, Face, Iris (expected) up to 500 million Entry-exit EES   EU Fingerprint, Face (expected) up to 200 million Entry-exit performing the biometric comparisons, most approaches are aimed at that step in the system pipeline. Specialised data representations and search algorithms are utilised to reduce the computational effort required for a single template comparison, and/or to reduce the overall number of required template comparisons. However, biometric data exhibits certain properties, which present challenges or outright invalidate many traditional approaches aimed at retrieval speed improvement: Ordering Biometric data has no inherent logical ordering (as opposed to, for example, text data, which can be indexed e.g. alphabetically). Within-subject variability The samples acquired from the same subject (even within short time intervals) are almost never exactly identical (i.e. they are fuzzy). Some variations are nearly inevitable due to numerous noise sources in the acquisition process (e.g. distance and angle from the sensor, environmental conditions, occlusions etc.). Dimensionality The biometric feature vectors are typically highdimensional; many search and indexing methods perform poorly in such spaces BIB001 . Consequently, computational workload reduction methods tailored specifically to the particular properties of biometric data have been developed in recent years. Such methods will be surveyed in the following sections. For a general overview of search structures and algorithms used for fast similarity searches across various disciplines, the reader is referred to e.g. BIB003 BIB004 BIB006 BIB009 BIB010 BIB012  BIB014 . The reader is expected to possess certain background knowledge on biometric recognition systems in general and the typical algorithms used in their signal processing pipelines. For quick primers, the reader is referred to the encyclopedia of biometrics BIB011 , as well as the renowned handbook series: BIB007 for biometrics in general and BIB005 BIB008  BIB016 specifically for fingerprint, face, iris, and vascular characteristics, respectively. While previously there have been surveys on biometric workload reduction methods (e.g. BIB013 for iris and BIB015 for fingerprint), they tend to concentrate on particular methods and/or biometric characteristics, rather than the overall spectrum of available research. Although the emphasis of this article is on the academic research, a discussion from the industry perspective and the interplay between academia and industry are included. The main contributions of this article are thus as follows: Taxonomy which conceptually categorises the computational workload reduction methods in biometric identification. Comprehensive survey of the methods reported in the scientific literature. It is organised by the relevant concepts, rather than by biometric characteristics. Instead of concentrating on one biometric characteristic only, the (arguably) most popular ones (in terms of actual use in industry and scientific research interest) are surveyed.