Searching in multilevel clustered vector-based data

A multilevel clustered data set for multidimensional vectors is created by defining a plurality of clusters based on each of the signed dimensions of the vectors, each dimension functioning as an axis. Vectors are assigned to each cluster by measuring cosine similarity between a vector and each axis. Sub-clusters are defined as ranges of cosine similarity values within a cluster, and each vector is assigned into the appropriate range based on their cosine similarity value with the axis of the cluster. Searching for a matching vector to a new vector is efficiently achieved in near-constant time by measuring cosine similarity for the new vector with each axis to identify the closest cluster, reusing the cosine similarity of the new vector and axis to determine which sub-cluster corresponds to the appropriate range of values, and then comparing each vector within the sub-cluster until a match is found or ruled out.

BACKGROUND

The present invention relates generally to the field of multilevel data clustering, and more particularly to multilevel data clustering of vector-based data.

Scale-invariant feature transforms (SIFT) are a feature detection algorithm in the field of computer vision to detect and describe local features in images. SIFT keypoints of objects are initially extracted from a multitude of reference images and stored in a database. An object is recognized in a new input image by comparing each feature from the new image individually to this database and finding candidate matching features based on the Euclidean distance of their feature vectors.

Initially, a set of orientation histograms is created on four by four pixel neighborhoods with eight bins each. These histograms are computed from orientation and magnitude values of samples in a sixteen by sixteen area around the keypoint such that each histogram includes samples from a four by four subregion of the original neighborhood region. The magnitudes are further weighted by a gaussian function, with the gaussian function σ equal to one half of the width of the descriptor window. Then, the descriptor becomes a vector of all of the values of these histograms. As there are sixteen histograms (four times four) and each histogram has 8 bins, the vector has 128 elements. Then, this vector is normalized to unit length in order to enhance invariance to affine changes in illumination. In order to reduce the effects of non-linear illumination, a threshold of 0.2 is applied and the vector is again normalized.

Cosine similarity is a measure of similarity between two non-zero vectors of an inner product space which measures the cosine of the angle between them. The cosine of 0° is 1, and it is less than 1 for every angle in the interval (0,π] radians. It is therefore a judgment of orientation and not magnitude. Two vectors with the same orientation have a cosine similarity of 1, two vectors oriented at 90° relative to each other possess a similarity of 0, and two vectors diametrically opposed possess a similarity of −1, independent of their magnitudes.

SUMMARY

According to an aspect of the present invention, there is a method, computer program product and/or system that performs the following operations (not necessarily in the following order): (i) receiving a clustered images data set, with the clustered images data set including a plurality of top-level clusters, where a given top-level cluster is determined based on a signed axis and includes a plurality of sub-clusters, where a given sub-cluster is a range of values based, at least in part, on the signed axis of the given top-level cluster and includes one or more multidimensional vectors generated from historical images; (ii) receiving an input image data set; (iii) generating a multidimensional vector based on the input image data set; (iv) determining a top-level cluster closest to the generated multidimensional vector based, at least in part, on the signed axes of the plurality of top-level clusters; (v) determining a sub-cluster of the determined top-level cluster closest to the generated multidimensional vector based, at least in part, on the signed axis of the determined top-level cluster and the generated multidimensional vector; and (vi) determining a subset of one or more vectors of the determined sub-cluster as matches for the input image by comparing the generated multidimensional vector to one or more vectors of the determined sub-cluster.

DETAILED DESCRIPTION

Some embodiments of the present invention are directed to creating a multilevel clustered data set for multidimensional vectors by defining a plurality of clusters based on each of the signed dimensions of the vectors, each dimension functioning as an axis. Vectors are assigned to each cluster by measuring cosine similarity between a vector and each axis. Sub-clusters are defined as ranges of cosine similarity values within a cluster, and each vector is assigned into the appropriate range based on their cosine similarity value with the axis of the cluster. Searching for a matching vector to a new vector is efficiently achieved in near-constant time by measuring cosine similarity for the new vector with each axis to identify the closest cluster, reusing the cosine similarity of the new vector and axis to determine which sub-cluster corresponds to the appropriate range of values, and then comparing each vector within the sub-cluster until a match is found or ruled out.

I. The Hardware and Software Environment

A “storage device” is hereby defined to be any thing made or adapted to store computer code in a manner so that the computer code can be accessed by a computer processor. A storage device typically includes a storage medium, which is the material in, or on, which the data of the computer code is stored. A single “storage device” may have: (i) multiple discrete portions that are spaced apart, or distributed (for example, a set of six solid state storage devices respectively located in six laptop computers that collectively store a single computer program); and/or (ii) may use multiple storage media (for example, a set of computer code that is partially stored in as magnetic domains in a computer's non-volatile storage and partially stored in a set of semiconductor switches in the computer's volatile memory). The term “storage medium” should be construed to cover situations where multiple different types of storage media are used.

As shown inFIG. 1, networked computers system100is an embodiment of a hardware and software environment for use with various embodiments of the present invention. described in detail with reference to the Figures. Networked computers system100includes: clustering subsystem102(sometimes herein referred to, more simply, as subsystem102); client subsystems104and106; and communication network114. Clustering subsystem102includes: clustering computer200; communication unit202; processor set204; input/output (I/O) interface set206; memory208; persistent storage210; display212; external device(s)214; random access memory (RAM)230; cache232; and program300.

Subsystem102may be a laptop computer, tablet computer, netbook computer, personal computer (PC), a desktop computer, a personal digital assistant (PDA), a smart phone, or any other type of computer (see definition of “computer” in Definitions section, below). Program300is a collection of machine readable instructions and/or data that is used to create, manage and control certain software functions that will be discussed in detail, below, in the Example Embodiment subsection of this Detailed Description section.

Memory208and persistent storage210are computer-readable storage media. In general, memory208can include any suitable volatile or non-volatile computer-readable storage media. It is further noted that, now and/or in the near future: (i) external device(s)214may be able to supply, some or all, memory for subsystem102; and/or (ii) devices external to subsystem102may be able to provide memory for subsystem102. Both memory208and persistent storage210: (i) store data in a manner that is less transient than a signal in transit; and (ii) store data on a tangible medium (such as magnetic or optical domains). In this embodiment, memory208is volatile storage, while persistent storage210provides nonvolatile storage. The media used by persistent storage210may also be removable. For example, a removable hard drive may be used for persistent storage210. Other examples include optical and magnetic disks, thumb drives, and smart cards that are inserted into a drive for transfer onto another computer-readable storage medium that is also part of persistent storage210.

I/O interface set206allows for input and output of data with other devices that may be connected locally in data communication with server computer200. For example, I/O interface set206provides a connection to external device(s)214(alternatively referred to as external devices set214). External device set214will typically include devices such as a keyboard, keypad, a touch screen, and/or some other suitable input device. External device set214can also include portable computer-readable storage media such as, for example, thumb drives, portable optical or magnetic disks, and memory cards. Software and data used to practice embodiments of the present invention, for example, program300, can be stored on such portable computer-readable storage media. I/O interface set206also connects in data communication with display212. Display212is a display device that provides a mechanism to display data to a user and may be, for example, a computer monitor or a smart phone display screen.

In this embodiment, program300is stored in persistent storage210for access and/or execution by one or more computer processors of processor set204, usually through one or more memories of memory208. It will be understood by those of skill in the art that program300may be stored in a more highly distributed manner during its run time and/or when it is not running. Program300may include both machine readable and performable instructions and/or substantive data (that is, the type of data stored in a database). In this particular embodiment, persistent storage210includes a magnetic hard disk drive. To name some possible variations, persistent storage210may include a solid state hard drive, a semiconductor storage device, read-only memory (ROM), erasable programmable read-only memory (EPROM), flash memory, or any other computer-readable storage media that is capable of storing program instructions or digital information.

As shown inFIG. 1, networked computers system100is an environment in which an example method according to the present invention can be performed. As shown inFIG. 2, flowchart250shows an example method according to the present invention. As shown inFIG. 3, program300performs or control performance of at least some of the method operations of flowchart250. This method and associated software will now be discussed, over the course of the following paragraphs, with extensive reference to the blocks ofFIGS. 1, 2 and 3.

Processing begins at operation S255, where input image data store module (“mod”)302receives a new input image. In this simplified embodiment, the input image is a biometric facial image corresponding to an authorization request using a biometric facial image process, with the request directed towards accessing client104ofFIG. 1, which is a smartphone device. This image is stored in input image data store mod302for subsequent use by modules of program300. In alternative embodiments, the input image may comprise different types of information, such as fingerprints, retinal scans, or other types of image data.

Processing proceeds to operation S260, where vector generation mod304generates a multi-dimensional vector of unit length based on the input image in input image data store mod302. In this simplified embodiment, mod304generates the new multi-dimensional vector through known SIFT techniques. The result of these techniques generates a vector of unit length (1) and 128 dimensions that describes the features of the input image in mod302, which will be further referred to as “new input vector.” Alternatively, entire dimensions of the input vector can be eliminated through comparison of non-distinguishing features against a set of reference vectors. If all vectors possess some dimensions that are identical (and thus, serve no purpose in distinguishing one vector from another), then those non-distinguishing features can be removed to streamline future comparisons and computing efficiency.

Processing proceeds to operation S265, where top-level cluster determination mod306determines which top-level cluster is closest to the generated vector. In this simplified embodiment, clustered reference images data store mod303includes a clustered images data set, received from client106, which is structured to include 256 ‘top-level’ bins or clusters with a plurality of vectors within each top-level cluster. These top-level bins are based on the 128 dimensions of vectors generated SIFT techniques applied to historical input images, accounting for positive and negative signs of each dimension, which are henceforth referred to as “signed vectors.” These signed vectors function as axes (or signed axes) for cluster definition. Retrieving the cosine similarity measurement between a given input vector and each axis yields a measurement of how closely aligned the given input vector is to each axis, enabling mod306to determine which axis is the most closely aligned with a given input vector. In this simplified embodiment, a historical set of biometric facial images have been used to generate a historical set of input vectors which mod306has measured cosine similarity for against the 256 axes that define the 256 top-level clusters. Then, using the cosine similarity previously measured, the historical set of input vectors are each assigned to one of the 256 top-level bins. Each bin may feature more than one input vector assigned to it. In this simplified embodiment, each top-level cluster has 100 historical input vectors assigned to it, for a total of 256,000 input vectors in the clustered images data set.

To determine which top-level cluster is closest to the new input vector based on the image stored in mod302, a cosine similarity measurement is taken against each of the 256 axes of the clustered images data set, where the measurement closest or equal to a value of 1 indicates the closest axis. In this simplified embodiment, a cosine similarity measurement between the new input vector and the first axis, a positive signed axis of the first dimension of a vector of 128 dimensions, results in the closest value out of the remaining 255 axes, with a value of 0.963333. If a cosine similarity measurement for a given vector is identical for two or more bins, then the bin with fewer assigned vectors receives the given vector. If both bins have the same number of vectors, then whichever bin represents the lower numbered dimension, when considering the dimensions of a vector sequentially, receives the given vector. Alternatively, other amounts of clusters may be implemented corresponding to the number of dimensions of corresponding input vectors (for example, 200 bins/clusters for vectors with 100 dimensions).

Processing proceeds to operation S270, where sub-cluster determination mod308determines the sub-cluster closest to the generated vector. In this simplified embodiment, the cosine similarity is again used to determine which sub-cluster the new input vector belongs to. First, after the 256 top-level bins are previously created for the clustered images data set, a plurality of sub-clusters are created within each top-level bin, with each sub-cluster including a range of angles (or cosine similarity values) between the axis and each historical input vector assigned to the top-level bin of the axis. The number of sub-clusters is predefined (in the simplified example embodiment, 10 sub-clusters exist, with each sub-cluster including 10 historical input vectors). In this simplified example embodiment, the ten sub-clusters of the first dimension are delineated by the following range of angles: (i) sub-cluster1includes cosine similarity values from 0.950000 to 0.954999; (ii) sub-cluster2includes cosine similarity values from 0.955000 to 0.959999; (iii) sub-cluster3includes cosine similarity values from 0.960000 to 0.964999; (iv) sub-cluster4includes cosine similarity values from 0.965000 to 0.969999; (v) sub-cluster5includes cosine similarity values from 0.970000 to 0.974999; (vi) sub-cluster6includes cosine similarity values from 0.975000 to 0.979999; (vii) sub-cluster7includes cosine similarity values from 0.980000 to 0.984999; (viii) sub-cluster8includes cosine similarity values from 0.985000 to 0.989999; (ix) sub-cluster9includes cosine similarity values from 0.990000 to 0.994999; and (x) sub-cluster10includes cosine similarity values from 0.995000 to 1.0 With these ranges of cosine similarity values, each sub-cluster has 10 historical input vectors assigned to them, each having a different cosine similarity value that falls within the range for their assigned sub-cluster. In this simplified example embodiment, the new input vector, which had a cosine similarity measurement of 0.963333, is closest to the third sub-cluster.

Alternatively, the number of sub-clusters can be adjusted on the fly to accommodate a uniform quantity of vectors within each sub-cluster. Alternatively, the predetermined number of clusters can be different than the example of the simplified embodiment. As a further alternative, the number of sub-clusters can be based upon the number of top-level (for example, the number of sub-clusters is equal to a fraction or multiple of the number of top-level clusters). As yet a further alternative, the number of sub-clusters can be dynamically determined based on a predetermined limit value and the number of vectors within a given top-level cluster. For example, if the predetermined limit value of sub-clusters is 5, but there are only four vectors assigned to a given top-level cluster, then the sub-clusters may be collapsed into four or fewer sub-clusters, to reap efficiency benefits against checking against an empty sub-cluster.

Processing proceeds to operation S275, where vector-to-vector comparison mod310compares the generated vector to each vector within the determined sub-cluster until one or more matches within a threshold are identified. In this simplified embodiment, with 10 historical input vectors in each sub-cluster, and the third sub-cluster of the first top-level cluster having previously been determined as the closest sub-cluster of the new input vector, mod310compares the new input vector against each of the ten historical input vectors of the determined sub-cluster, until one or more matches are found within a predetermined threshold value. In this simplified embodiment, the threshold value is 0.000010. When referring to a threshold at this step, the threshold indicates a tolerance range between a cosine similarity of historical input vector with the axis of the top-level cluster and the cosine similarity of the new input vector with the axis of the top-level cluster. If the difference between the aforementioned cosine similarities is less than or equal to the threshold value, then the new input vector is considered a match for the historical input vector. Alternatively, a threshold value of 0 is used, indicating that only precisely equal vectors are considered matching. In this simplified embodiment, one of the ten historical input vectors of the determined sub-cluster has a cosine similarity measurement of 0.963330, which is different than the cosine similarity of the new input vector by a value of 0.000003 and is considered a match by mod310. Comparisons against the cosine similarity measurements of the other nine historical input vectors yielded differences greater than 0.000010 and are not considered matches. In alternative embodiments, more than one historical input vector may match with the new input vector.

Processing proceeds to operation S280, where authorization mod312authorizes the requested access corresponding to the received input image. In this simplified embodiment, if a match with a historical input vector is found for the new input vector, which was generated from the received input image stored in mod302, then authorization is provided to the accompanying request. As the new input vector matched with one of the historical input vectors, found through the novel clustering technique described above, authorization is provided. Alternative operations are possible, described below, using the novel clustering technique described in the present embodiments. In this simplified embodiment, authorization is reported to client104as displayed in message402of screenshot400ofFIG. 4. In alternative embodiments, other types of notifications may be presented, as known in the art, or no notification beyond the provision of access requested by the authorization request may be provided.

Some embodiments of the present invention recognize the following facts, potential problems and/or potential areas for improvement with respect to the current state of the art: (i) typical enterprise level application or real-life applications deal with large amounts of data; (ii) applications dealing with biometric data matching bear no exception to this; (iii) in biometric data matching, large amounts of image data is typically required; (iv) since the biometric data is generally represented by high dimensional vectors/matrices, the problem is further magnified; (v) clustering or indexing of the data is frequently required to perform queries on the data or to perform some other computations on the data within usable time-frames; (vi) in the existing literature, there are some techniques available for clustering the data but each of them suffers either from instability or poor performance; (vii) there is a need for an effective clustering technique which can do the clustering of the data in such a manner that the fetched results of the queries should contain at least all the candidate results of the query and the time taken is in the order of “less than linear”; (viii) in the current disclosure, we solve these two major problems: (a) clustering high dimensional data with large number of identities effectively in a stable manner, and (b) fetching the queried data in a constant time, thereby improving the performance significantly; (ix) in any biometric matching system, we have a large amount of data which really consists of large number of individual identities; (x) as far as create, read, update and delete (CRUD) operations are concerned, one very important and much needed task is to cluster the data in such a manner that queries on the data are done in the best way i.e. in a least amount of time; (x) another important aspect is the accuracy of the queried results; (xi) the result set should contain at least all the suspected potential duplicates; and (xii) having large number of identities and high dimensional data, the existing clustering methods do not perform well; (xiii) further, they tend to be unstable which reduces the accuracy of the results; (xiv) most of the existing clustering techniques are unstable in nature because of the iterative process they follow to stabilize their clusters; (xv) query time in case of many existing clustering methods grows very rapidly as the data grows in size and it is somewhat proportional to that size; and (xvi) existing methods need to perform re-clustering once the data has grown by 40% or so in size.

Some embodiments of the present invention may include one, or more, of the following operations, features, characteristics and/or advantages: (i) one solution to the above recognized problems includes limiting the number of clusters to be created even after a large number of identities present using a binning approach, and retrieving the results in “less than linear time” while maintaining the accuracy of the result set; (ii) one of the many types of biometric data is facial image data; (iii) the context of facial image data will be used to discuss several embodiments; (iv) the techniques used herein can be extended to other kinds of biometric features as well with minor or no modifications; (v) raw facial image data is generally converted to multidimensional vectors in Euclidean space; (vi) every multidimensional vector is converted to a vector of length1such that the vectors are restricted to lie on the surface of a multidimensional hypersphere of radius1; (vii) using some modules, we can convert a raw image data to a vector of 128 dimensions and, by dividing every component of the vector by its length, it can be reduced to a vector of length1; (viii) therefore, one problem reduces to efficiently clustering the very large number of unit vectors of 128 dimension; (ix) if no clustering techniques are performed on the data, the naïve method (where the naïve method means the raw search, or checking for all the images one-by-one for the match) for searching the data will be linear in time which will become a severe problem while dealing with the large amount of data; (x) some proposed techniques in this disclosure work in constant time and therefore does not hamper the performance in the same ratio as the growth of the data; (xi) to solve the problem of large number of identities or clusters, this application proposes a methodology based on multilevel clustering; (xii) the approach used in this disclosure is a totally new and better performing approach to multi-level clustering of biometric data; and (xii) for the sake of explanation, two-level clustering is described in detail in the current disclosure.

Some embodiments of the present invention may include one, or more, of the following operations, features, characteristics and/or advantages: (i) in multilevel clustering, data is clustered at multiple levels based on some similarity measure used at each level; (ii) the similarity measure can be different at different levels based on the nature of the data; (iii) as per a first level of clustering, a subset of the entire data which is representative of the whole population is indexed/clustered and, in turn, each data point is assigned to one of the clusters; (iv) as per a second level of clustering, each data point inside a cluster is further indexed and thereby, every data point in that cluster gets associated to one of the sub-clusters of the cluster under consideration; (v) the process can be further continued to multiple levels of clustering as per present demands; (vi) all of the data points are vectors of length1, and lie on the surface of a 128 dimensional hypersphere; and (vii) the similarity measure in Euclidean space is the distance between two vectors which can also be captured with the cosine similarity between the vectors which is calculated as EQ1, below.

Some embodiments of the present invention may include one, or more, of the following operations, features, characteristics and/or advantages: (i) the proposed binning technique takes each axis as a bin; (ii) then separate the data points according to their closeness to the axis; (iii) consider each axis with their sign as a bin, so there will be 256 bins in a 128 dimensional space; (iv) for each given data point, it is possible to find which axis (or bin) is the closest by measuring the cosine similarity between the vector corresponding to the data point and all the axes; (v) then assign each data point to one of the bins based on the measure of closeness; (vi) by using this technique, the data points in one bin are the ones which are closer to each other in the space; (vii) with a fixed number of bins and that number of bins covers the space uniformly, this technique does not require creating more clusters or bins as the data increases in number; and (viii) since the number of bins/clusters are determined based on the dimension of the data (e.g. 128 in the present case), some of the described techniques can generally work for any dimensional of data by configuring the number of clusters accordingly.

Some embodiments of the present invention may include one, or more, of the following operations, features, characteristics and/or advantages: (i) once the data points are clustered in bins based on their closeness with the axes at the first level, the data points are clustered further within each bin in such a way that their retrieval becomes faster; (ii) for the second-level clustering, again use the information of cosine similarity of vectors with the axis or bin under which they are placed at the first level; (iii) inside of a bin, a fixed number of sub-bins are created based on the angles that data points make with respect to the axis to which they were assigned earlier at the first level (where the fixed number of sub-bins may be fixed by a user at design time based on the anticipated data size); (iv) a bin at this level is a range of angles of data points to the assigned axis of the bin; (v) any data which makes an angle with the assigned axis where the angle lies within the range of angles of that bin will be assigned to that bin at the second level; (vi) again, the data points which are very close to each other will fall into one bin; (vii) proceeding in the same way, cluster the data points in different bins on the basis of their cosine similarity measure and this process can be extended to multiple levels; and (viii) using the cosine similarity as the similarity measure ensures that similar data points are clubbed together in the bins at both levels.

Screenshot500A ofFIG. 5Ashows a first level clustering according to a second embodiment of the present invention and includes: (i) cluster1502A; (ii) cluster2504A; (iii) cluster3506A; (iv) cluster4508A; (v) positive Y axis510A; (vi) negative Y axis512A; (vii) positive X axis514A; (viii) negative X axis516A; (ix) boundary518A; (x) boundary520A; (xi) boundary522A; and (xii) boundary524A. Cluster1502A includes all datapoints with vectors closest to axis510A and is bounded by boundaries524A and518A. Cluster2504A includes all datapoints with vectors closest to axis514A and is bounded by boundaries518A and520A. Cluster3506A includes all datapoints with vectors closest to axis512A and is bounded520A and522A. Cluster4508A includes all datapoints with vectors closest to axis516A and is bounded by boundaries522A and524A. A vector's closeness to an axis is determined by comparing cosine similarity between each axis and the vector. Four axes (two dimensions with two signs each) are presented for simplicity of explanation in a two-dimensional space such as a sheet of paper. Typical embodiments put into practice would employ many more axes, such as in the field of biometric facial data, where vectors typically have 128 dimensions, which would yield 256 axes (and therefore 256 bins) once positive and negative signs are accounted for.

Screenshot500B ofFIG. 5Bshows a second level clustering of data points within cluster2504A ofFIG. 5Aaccording to the second embodiment of the present invention and includes: (i) cluster2504A; (ii) boundary518A; (iii) boundary520A; (iv) sub-bins530B,532B,534B,536B, and538B; and (v) sub-bin boundaries540B,542B,544B and546B. In this second embodiment, each sub-bin represents a range of angles of cosine similarities between vectors of data points in cluster2504A and axis514A, shown inFIG. 5A.

Some embodiments of the present invention may include one, or more, of the following operations, features, characteristics and/or advantages: (i) a facial biometric data image is represented as a vector of 128 dimensions; (ii) not all the elements of that vector are significant when it comes to comparison of two images/image vectors; (iii) the contribution of different elements of the vectors to an overall comparison score is not the same; (iv) check the variance of different elements over a sample of image vectors data; (v) elements with significantly less variance as compared to other elements are considered as insignificant; (vi) insignificant elements are removed from the image vectors, reducing the dimensions of the vectors and accelerating the comparison of two images/image vectors; (vii) some of the proposed clustering techniques exploit the vector similarity measure to find the relevant cluster and does not depend on any iterative process, enhancing stability over existing techniques; (viii) a fixed number of clusters using cosine similarity to detect the clusters results in a time complexity order of almost-constant; (ix) this approach does not require re-clustering because it is non-iterative in nature; (x) multilevel clustering of biometric data based on cosine similarity with the axes of hyperspace which is a non-iterative process and stable; (xi) the achieved complexity of search T(xn) is almost constant; (xii) a non-iterative, stable and faster multilevel clustering; (xiii) a multilevel clustering approach for biometric data based on cosine similarity measure which is non-iterative, stable and faster; and (xiv) a novel approach for multilevel clustering of biometric data using cosine similarity and other angle measures.

Some embodiments of the present invention may include one, or more, of the following operations, features, characteristics and/or advantages: (i) a bulk add operation, where a large number of image datapoints are processed and added to a database; (ii) process the image data in batches and generate their 128-dimensional embeddings; (iii) after embeddings are generated, select one embedding at a time, find the closest bin-center to assign selected embedding, and assign the selected embedding to that bin; (iv) for the second level, a sub-cluster inside this bin is found with the same closeness measure and the selected embedding is assigned to that sub-cluster; (v) in this way, all the images are processed in bulk; (vi) an add operation happens in a similar way as the bulk add but it is intended only for one image datapoint; (vii) first, generate the embedding from the incoming image datapoint; (viii) then, check with all the bin centers to find the closest one for this embedding; (ix) then, assign the embedding to the closest bin; (x) within the assigned bin, using the same similarity measure we assign the sub-cluster to this image; (xi) an update operation includes updating the image datapoint corresponding to an existing record in the system; (xii) the update process is similar to add in terms of finding clusters at multiple levels but there is a slight difference; (xiii) when updating, there are two possibilities: (a) after an update, the embedding based on the image does not fall in the same clusters/bins as before, or (a) the embedding falls in the same cluster as before; (xiv) in (a) case, updating the bin count is necessary as well as bin center information at various levels; (xv) in (b) case, only the center information is updated but not the count; (xvi) a search operation is for finding similar records for a given image datapoint input; (xvii) it starts with generating the embedding for the incoming image datapoint input; (xviii) then, finding the bin and the sub-cluster underneath at the lowest level that is closest to the generated embedding; (xix) then, every image embedding in that sub-cluster is compared against the input embedding and the ones having the comparison score beyond a system-defined threshold are returned in output as similar images to the input image datapoint.

Some embodiments of the present invention may include one, or more, of the following operations, features, characteristics and/or advantages: (i) a novel way of multilevel clustering the high dimensional data based on binning approach using cosine similarity; (ii) a clustering method which is stable because of being non-iterative in nature; (iii) a method having time-complexity of order almost-constant; (iv) a method which doesn't require re-clustering of the data even if the data keeps growing in number; (v) these methods combined result in an approach that yields 100 times better performance than the raw search on an example scale of 500,000 images; (vi) a reduction in the dimension of the vectors with the help of statistical analysis of different elements of the vectors.

Computer: any device with significant data processing and/or machine readable instruction reading capabilities including, but not limited to: desktop computers, mainframe computers, laptop computers, field-programmable gate array (FPGA) based devices, smart phones, personal digital assistants (PDAs), body-mounted or inserted computers, embedded device style computers, and application-specific integrated circuit (ASIC) based devices.