Error tolerance approach for similarity search problems

A recently introduced error tolerance (ET) approach is an exercise of designing and testing systems cost-effectively by exploiting the advantages of a controlled relaxation of system level output quality precision requirement. The basic theme of ET approach is to allow erroneous output leading to imperceptible degree of system level quality degradation in order to simplify and optimize the circuit size and complexity, power consumption, costs as well as chip manufacturing yield rate. With a primary focus on similarity search problem within the scope of this ET concept, this thesis presents several methodologies to deal with the problems of system complexity and high vulnerability to hardware defects and fabrication process variability and consequently a lower yield rate.;First part of this thesis studies similarity search problem and presents a novel methodology, called quantization based nearest-neighbor-preserving metric approximation algorithm(QNNM), which leads to significant complexity reduction in search metric computation. Proposed algorithm exploits four observations: homogeneity of viewpoint property, concentration of extreme value distribution, NN-preserving not distance-preserving criterion, fixed query info during search process. Based on these, QNNM approximates original/benchmark metric by applying query-dependent non-uniform quantization directly on the dataset, which is designed to minimize the average NNS error, while achieving significantly lower complexity, e.g., typically 1-bit quantizer. We show how the optimal query adaptive quantizers minimizing NNS error can be designed "off-line" without prior knowledge of the query information to avoid the on-line overhead complexity and present an efficient and specifically tailored off-line optimization algorithm to find such optimal quantizer.;Three distinguishing characteristics of QNNM are statistical modeling of dataset, employing quantization within a metric, and query-adaptive metric, all of which allow QNNM to improve performance complexity trade-off significantly and provide robust result especially when the problem involves non-predefined or largely varying data set or metric function due to its intrinsic flexibility from query to query change.;Second part of the thesis, we present a complete analysis of the effect of interconnect faults in NNS metric computation circuit. We provided a model to capture the effect of any fault (or combination of multiple faults) on the matching metric. We then describe how these errors in metric computation lead to errors in the matching process. Our motivation was twofold. First, we used this analysis to predict the behavior of NNS algorithms and MMC architectures in the presence of faults. Second, this analysis is a required step towards developing efficient ET based acceptability decision strategies and can be used to simplify fault space, separate acceptable/unacceptable faults, and consequently simplify testing. Based on this model, we investigated the error tolerance behavior of NNS process in the presence of multiple hardware faults from both algorithmic and hardware architecture point of views by defining the characteristics of the search algorithm and hardware architecture that lead to increased error tolerance.;With ME application, our simulation showed that search algorithms satisfying error tolerant characteristics we defined perform up to 2.5dB higher than other search methods in the presence of fault, and they also exhibit significant complexity reduction (more than 99%) without having to compromise with the performance. Our simulation also showed that if error tolerant hardware architecture is used, the expected error due to a fault can be reduced by more than 95% and more than 99.2% of fault locations within matching metric computation circuits result in less than 0.01dB performance degradation. (Abstract shortened by UMI.)...