[go: up one dir, main page]

WO2013129580A1 - Dispositif de recherche de voisin approximativement le plus proche, procédé de recherche de voisin approximativement le plus proche, et programme - Google Patents

Dispositif de recherche de voisin approximativement le plus proche, procédé de recherche de voisin approximativement le plus proche, et programme Download PDF

Info

Publication number
WO2013129580A1
WO2013129580A1 PCT/JP2013/055440 JP2013055440W WO2013129580A1 WO 2013129580 A1 WO2013129580 A1 WO 2013129580A1 JP 2013055440 W JP2013055440 W JP 2013055440W WO 2013129580 A1 WO2013129580 A1 WO 2013129580A1
Authority
WO
WIPO (PCT)
Prior art keywords
query
point
distance
search
hash
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/JP2013/055440
Other languages
English (en)
Japanese (ja)
Inventor
雅一 岩村
智一 佐藤
浩一 黄瀬
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Osaka Metropolitan University
Original Assignee
Osaka Prefecture University PUC
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Osaka Prefecture University PUC filed Critical Osaka Prefecture University PUC
Publication of WO2013129580A1 publication Critical patent/WO2013129580A1/fr
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/50—Information retrieval; Database structures therefor; File system structures therefor of still image data
    • G06F16/58—Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
    • G06F16/583—Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually using metadata automatically derived from the content

Definitions

  • the present invention relates to an approximate nearest neighbor search apparatus, an approximate nearest neighbor search method, and a program thereof, and more specifically, an approximate nearest neighbor search apparatus, an approximate nearest neighbor search method, and an approximate nearest neighbor using fast distance estimation by hashing with a codebook. It relates to a search program.
  • Nearest neighbor search is a method of searching data (points) that are most similar to a query, that is, the data having the shortest distance (nearest point) from data (points) expressed by vectors.
  • Nearest neighbor search is a basic and effective technique for processing large-scale data, and because it is basic, it has a wide range of applicability to excellent methods. Even those that the inventors are involved in can be applied to object recognition (for example, see Non-Patent Document 1), document image search (for example, Non-Patent Document 2), character recognition (for example, Non-Patent Document 3) and Face recognition (for example, refer nonpatent literature 4) can be mentioned. Both have been shown to operate very fast on relatively large amounts of data.
  • the above-mentioned technique can be said to be an image recognition technique in a broad sense, but the application field of nearest neighbor search is not limited to that, but extends to statistical classification, code logic, data compression, recommendation system, spell checker, and the like. Considering practical applications, the nearest neighbor search requires high speed. If the speed increases, it will be possible to process a larger amount of data in the same time than before, and it will be possible to use it for applications that have been given up in the past due to processing time constraints.
  • the approximate nearest neighbor search is a technique that can significantly reduce the processing time by introducing an approximation to the nearest neighbor search and allowing a search error. Since a search error occurs, there is no guarantee that the true nearest neighbor will be found, but it is used for applications that only need to have a certain degree of search accuracy. Improvement in search accuracy and speeding up are conflicting requirements, and it is generally not easy to satisfy both at the same time.
  • Kise "Memory-based recognition of camera-captured characters," Proceedings of the 9th IAPR International Works on Document Analysis Systems (DAS2010), pp.89-96, June 2010. Keisuke Maekawa, Yuzuko Utsumi, Masakazu Iwamura, Koichi Kise, “Realization of Matching in 1 Million Face Image Database in 34 ms -Large-scale Fast Face Image Search Using Approximate Nearest Neighbor Search-”, IEICE Technology Research report, vol.111, no.353, pp.95-100, Dec. 2011. S. Arya, DM Mount, NS photographer, R.
  • the approximate nearest neighbor search indexing is performed by dividing the data space into a number of regions in advance.
  • the present invention particularly relates to a technique using a hash.
  • the data space is basically linearly divided along a plurality of axes, and data is registered in a hash table for each divided area (bin). Then, a high-speed search is realized by extracting from the hash table the points that have entered the query area or its neighboring areas, and obtaining the nearest neighbors from the extracted points.
  • a bin product area (bucket) is a unit of division.
  • the approximate nearest neighbor search is composed of two steps.
  • a bin or bucket having a high probability of including the nearest point is specified.
  • a point belonging to this point is called a nearest neighbor candidate.
  • the point having the smallest distance from the query is calculated.
  • the “approximate” element is included only in the first step. Therefore, this processing affects the search accuracy and processing time of the approximate nearest neighbor search.
  • the processing time required for the distance calculation is greatly reduced by limiting the distance calculation target to the nearest neighbor candidate.
  • this is a double-edged sword, and although the speed can be increased by reducing the number of nearest neighbor candidates, the search accuracy decreases. This is because the true nearest neighbor point leaks from the nearest neighbor candidate and the probability of failure in nearest neighbor search increases. Therefore, what is required in the first-stage processing is that the true nearest neighbor point is not leaked while the number of nearest neighbor candidates is reduced. Moreover, it is necessary to select the nearest neighbor candidate at high speed.
  • the policy taken by the inventors to satisfy these requirements is to use the same distance measure used in the second stage when selecting the nearest neighbor candidates. Thereby, even if the number of nearest neighbor candidates is reduced, the probability that a true nearest neighbor point is included in the nearest neighbors is difficult to decrease. However, such processing usually requires a large calculation cost.
  • an approximate nearest neighbor search method capable of executing the above-described processing at high speed is desired.
  • the present invention has been made in view of the above circumstances, and provides a new approximate nearest neighbor search method that combines high search accuracy and high speed by appropriately narrowing down the nearest neighbor candidates. Is.
  • a hash index for each point is calculated by applying a hash function for calculating the index of the multidimensional hash table, and a plurality of points are calculated by bins of the multidimensional hash table.
  • a hash index is calculated by applying a hash function to each point, and multiple points divided into a plurality of regions by an orthonormal basis are obtained.
  • a database storage unit in which each point is registered in a multidimensional hash table by projecting each point to an area corresponding to the index in the dimensional space, and when the query is input, the hash function is applied to the query.
  • a search range in which a position of the query in the space is determined, an estimated value of a distance between the query and each area in the space is determined, and one or more areas are determined as search areas based on the estimated value
  • a determination unit and a nearest point determination unit that calculates a distance between each point in the search area and the query, and calculates a point closest to the query as a nearest neighbor point of the query.
  • Search range determining unit the position of the representative point representing the area determined with reference to the index of a region in which each point belongs and provides the approximate nearest neighbor searching and wherein the
  • the present invention applies a hash function for calculating an index of a multidimensional hash table when a plurality of points represented by vector data are input, and calculates a hash index for each point.
  • Each point is stored in the multidimensional hash table by calculating and projecting each point to an area corresponding to the hash index in the multidimensional space divided into a plurality of areas by bins of the multidimensional hash table Accessing the database storage, and when a query is input, applying the hash function to the query to determine the position of the query in the space, and determining the distance between the query and each region in the space
  • a search range determination process for determining an estimated value and determining at least one area to be searched based on the estimated value.
  • the search range determining step refers to an index of each area to obtain a position of a representative point representing the area, and estimates the difference between the position of the query and the position of each representative point Provided is an approximate nearest neighbor search method characterized by a value.
  • the present invention calculates a hash index for each point by applying a hash function for calculating an index of a multidimensional hash table when a plurality of points represented by vector data are input.
  • Access the database storage unit that stores each point in the multidimensional hash table by projecting each point to the area corresponding to the hash index in the multidimensional space divided into multiple areas by the bin of the multidimensional hash table
  • the hash function is applied to the query to determine the position of the query in the space, and an estimate of the distance between the query and each region in the space is determined.
  • Processing as a search range determination unit for determining at least one region to be searched based on the estimated value, and the search The distance between each point in the power region and the query is calculated, and the computer is caused to execute processing as a nearest neighbor point determination unit that calculates the closest point to the query as the nearest neighbor point of the query.
  • a representative point of the region is obtained with reference to the index of the region, the estimated value is determined based on a distance between the query and each representative point, and the region to be searched cannot be applied by applying a branch and bound method.
  • Provided is an approximate nearest neighbor search program characterized in that a region to be searched is determined by excluding a region.
  • the program product is provided. The inventions from the above three viewpoints are all related to the description of “first improvement: hash-based point-to-bucket distance estimation” in the embodiments described later.
  • the search range determining unit refers to the index of each region to obtain a representative point of that region, and determines the estimated value based on the distance between the query and each representative point. Therefore, without calculating the distance between the query and each region, the estimated value is determined using the index, the region to be searched (search region) is determined based on the estimated value, and the nearest neighbor determining unit determines the distance.
  • the points to be calculated can be narrowed down.
  • the method of the present invention that estimates the point-to-bucket distance can improve the accuracy of distance estimation with the same data structure.
  • the branch and bound method is applied to exclude regions that cannot be search regions, so that the search regions can be determined in a short time.
  • individual data registered in the database and data of a query (search question) used for searching the database are expressed as at least one point.
  • Each point has an attribute indicating the characteristics of the data or query, and the attribute is expressed by vector data.
  • Hashing is a well-known method for retrieving data at high speed on a memory.
  • the hash function receives a vector data and outputs a scalar value.
  • the scalar value is a discrete value used to refer to a hash table that is a kind of data table, and is called a hash value, a hash index, or simply an index. It can be said that the hash function divides the output space by the discrete values that the index can take.
  • a hash function can also be said to project vector data (points) as an input into an output multidimensional space.
  • each vector data is projected into a multidimensional space.
  • ⁇ hash functions are used to project vector data onto a vector space of ⁇ dimension ( ⁇ is an integer of 2 or more), for example.
  • ⁇ is an integer of 2 or more
  • Each point is composed of ⁇ bases by applying ⁇ hash functions, is divided into a plurality of bins along each base, and any bin is specified by the index of each hash function Projected into space. Since the registration of each point in each bin is represented using a hash table, there are ⁇ hash tables ( ⁇ dimensions). However, a single hash function may be used by combining several dimensions. In this case, there are fewer than ⁇ hash tables.
  • the approximate nearest neighbor search method according to the present invention can be applied to object recognition, document image search, character recognition, face recognition, statistical classification, code logic, data compression, recommendation system, spell checker, and the like.
  • the 2nd graph which shows the relationship between the precision in the optimal parameter, and processing time compared with the conventional method.
  • it is explanatory drawing which shows the example of the division
  • it is explanatory drawing which shows a mode that a search radius is changed according to the density of a query periphery.
  • It is a graph which shows the accuracy of distance estimation by BDH and k-means BDH of the present invention in comparison with SH of the conventional method with the horizontal axis as the code length and the vertical axis as the correlation coefficient.
  • BDH it is a graph which shows the average rank of the nearest point in the distance on a hash when code length is changed compared with SH of a conventional method.
  • this invention is a graph which shows the relationship between the search precision of k-means
  • it is a graph which shows the relationship between the parameter c regarding the number of nearest neighbor candidates, and processing time.
  • it is a figure which shows two algorithms which identify the bucket within the search radius R at high speed.
  • each point is registered in each of M sets of multidimensional hash tables corresponding to each hash function group using M sets (M is a natural number of 2 or more) of hash functions.
  • the function group may be a combination of a plurality of hash functions. In this way, for example, when ⁇ hash functions ( ⁇ > M) are divided into one hash function group without being divided, if the number of bins in each hash table is s, it corresponds to s bins. Since it is necessary to prepare ⁇ sets of data storage areas, the order of the hash table size is O (s ⁇ ).
  • O (s ⁇ / M ) is a notation method of an approximate calculation amount necessary for solving the problem, and the calculation amount when s is determined is the order of s to the ⁇ power, that is, as ⁇ + bs ( ⁇ ⁇ 1). + ... + ls 2 + ms + n or less.
  • a, b,..., L, m, and n are constants. This aspect is related to the description of “second improvement: hash table division” in an embodiment described later.
  • the M sets of hash tables may be defined so that the number of dimensions of each hash is substantially equal.
  • the basis selection method at this time may be determined so that the sum of the variances of the basis is substantially equal.
  • the sum of the variances of the data in the respective base directions and the basis of each set of hash tables divided so that the sum of the variances is as equal as possible. Determine the assignment.
  • the distance in the base direction having a large variance tends to be large, and the distance in the base direction having a small dispersion tends to be small. Therefore, summing the sum of the variances of the hash tables has the effect of aligning the distances calculated for each hash table.
  • the search radius R used for selection of the distance calculation target or censoring of the distance calculation (processing for replacing the distance with a constant value when the distance calculation target point does not exist in the search range) as in the embodiment of the present specification. If the tables are shared, it is considered that each hash table divided into M sets contributes to the determination of the nearest neighbor candidates by equalizing the sum of the variance of each hash table. It is not necessary to set a parameter instead of R, and the calculation can be performed easily. This aspect is related to the description of “second improvement: hash table division” in an embodiment described later.
  • the multi-dimensional hash table is a combination of hash tables corresponding to each dimension.
  • Each hash table divides a base corresponding to each dimension into bins, and each bin has a uniform width.
  • the position error between the point that will be registered in each bin and the representative point that represents each bin is obtained for each bin, and the width of each bin is adjusted so that the sum of these errors becomes smaller May be.
  • the processing time of distance calculation with each point in the search area varies depending on the number of data registered in the bucket of the search area. This variation can be suppressed.
  • This aspect relates to the description of “third improvement: division of data space suitable for distance estimation” in an embodiment described later.
  • each hash table calculates the representative point for each cluster by clustering each point into predetermined n clusters, and represents the average distance from each point belonging to each cluster to the representative point of that cluster.
  • the width of each bin may be determined so that the variance is smaller than a predetermined threshold. In this way, by determining the width of each bin so that the variance of each point in the bin is equal to or less than the threshold, the number of points registered in each bin can be leveled within an appropriate range.
  • This aspect relates to the description of “third improvement: division of data space suitable for distance estimation” in an embodiment described later.
  • the search range determination unit may determine a probability density function from the distribution of vector data in each base direction, and determine the estimated value using the probability density function for weighting the distance. In this way, appropriate leveling is possible even for complex distributions by using the probability density function.
  • This aspect relates to the description of “fourth improvement: distance estimation based on probability density function” in an embodiment described later.
  • the search range determination unit may set a region having a representative point within a range of a search radius R determined in advance centering on a query as the search region. In this way, the search area can be determined by setting the search radius R in advance.
  • This aspect is related to the description of “fifth improvement: expansion of search radius considering data density around query” in an embodiment described later.
  • the search range determination unit searches a region having a representative point within the range of the search radius R around the query as the search region, and searches until the number of points included in the search region reaches a predetermined number
  • the radius R may be gradually increased.
  • the number of points included in the search area that is, the number of candidates for the nearest neighbor point
  • the processing time required for calculating the distance to each point in the search area can be made substantially constant. This aspect is related to the description of “fifth improvement: expansion of search radius considering data density around query” in an embodiment described later.
  • the database storage unit projects each point in a ⁇ -dimensional space in which the basis is determined by principal component analysis
  • the search range determination unit is configured to determine the distance between the query and each representative point in each base direction.
  • Each distance component is calculated as the estimated value, and in the course of calculating each distance component, a constraint condition is that the sum of the distance components is within a determined search radius R, and a large eigenvalue is calculated in the principal component analysis.
  • the search area may be determined by pruning an area that cannot be the search area by applying a branch and bound method that determines whether the representative point of each area is within the radius R in the order of the bases.
  • the search area can be determined in a short time.
  • This aspect is related to the description of “first improvement: point-to-bucket distance estimation based on hash” in an embodiment described later.
  • the database storage unit calculates ⁇ indexes by applying ⁇ ( ⁇ is an integer of 2 or more) hash functions to each point, and is composed of ⁇ bases. It is generated by projecting each point into a ⁇ -dimensional space that is divided into bins and each bin is specified by each index, and the registration of each point in each bin is represented using a hash table. May be. This aspect is related to the description of “first improvement: point-to-bucket distance estimation based on hash” in an embodiment described later.
  • the database storage unit projects each point in a ⁇ -dimensional space, and the multi-dimensional hash table selects M sets of subspaces spanned by P orthogonal bases among ⁇ orthogonal bases spanning the ⁇ -dimensional space.
  • the subspace is divided into subspaces using the k-means method, and the subspace having a larger variance in each region is set to have a larger number of divisions.
  • the estimated value may be determined so that an estimation error of a square distance between a point existing in each region and a query is minimized in each base direction according to a probability density function obtained from the distribution of vector data in the direction of .
  • This aspect relates to the description of “sixth improvement” in the embodiment described later.
  • Preferred embodiments of the present invention include combinations of any of the plurality of embodiments shown here.
  • FIG. 20 is a block diagram showing an image recognition apparatus as an application example of the approximate nearest neighbor search apparatus of the present invention.
  • the approximate nearest neighbor search according to the present invention is realized by the computer processing image data using hardware resources such as a storage device on the image recognition apparatus shown in FIG.
  • the hardware of the image recognition apparatus includes, for example, a CPU, a storage device such as a hard disk device storing a program indicating a processing procedure executed by the CPU, a RAM that provides a work area to the CPU, and an input / output that inputs and outputs data. It consists of a circuit. More specifically, the image recognition apparatus may be realized by a personal computer having the above configuration. Or it may be comprised from the microcomputer which is integrated in an apparatus and has the said structure.
  • the feature point extraction unit 11 is a block that extracts a feature vector from a pattern of an object included in input image data using a known method.
  • a feature vector represents a local feature of an image, and a plurality of feature vectors each representing a plurality of local features are extracted from one image.
  • the CPU When registering image data in the image database 15, the CPU attaches an image ID for identifying the image and stores it in the image database 15, and further associates a feature vector extracted from the image with the image ID in a hash table.
  • Register at 15h Specifically, the hash function is applied to classify each feature vector into one of a plurality of bins and register the bins in the bins. That is, an index is calculated by applying a hash function to each feature vector, and an image database 15 in which each feature vector is registered in a bin or bucket corresponding to the index is created.
  • the hash function used at the time of registration is the same as the hash function used by the search range determination unit 13 for calculating the index.
  • the image recognition apparatus selects the image closest to the query image from among the images stored in the image database 15. Is output as a recognition result.
  • the search for the closest image is realized by comparing feature vectors and searching for the nearest vector for each feature vector of the query. An approximate nearest neighbor search is applied to this nearest neighbor vector search.
  • the CPU as the feature point extraction unit 11 extracts a feature vector from the query.
  • the extracted feature vector is called a query vector
  • the feature vector registered in the hash table 15h is called a reference vector.
  • the CPU obtains an index by applying the hash function described above to each query vector. Then, the CPU refers to the bin of the hash table 15h specified by the obtained index, and sets the reference vector registered in the bin as the nearest candidate for the query vector.
  • the process of applying a hash function to a query vector to refer to a bin and using the reference vector registered in the bin as the nearest neighbor candidate corresponds to the first stage process of the approximate nearest neighbor search.
  • the hash function is determined in advance in consideration of balance so that the number of reference vectors registered in each bin is reduced while the reference vector includes a reference vector having a high probability of being the nearest bin.
  • the CPU sets the image ID associated with the reference vector as a recognition result candidate.
  • the CPU determines the nearest neighbor vector among the reference vectors as the nearest neighbor point determination unit 17. Specifically, the CPU performs distance calculation between the query vector and the reference vector registered in the reference destination bin. Then, the reference vector closest to the query vector is determined as the nearest neighbor vector.
  • the image ID associated with the reference vector is set as a recognition result candidate.
  • the nearest neighbor determination unit 17 corresponds to a configuration that embodies the second step of the approximate nearest neighbor search.
  • the CPU obtains the nearest reference vector for each of a plurality of query vectors extracted from the query, and uses the image ID associated with the reference vector as a recognition result candidate.
  • the voting unit 19 the CPU performs voting on image IDs that are candidates for recognition results for each query vector.
  • a voting table 21 is provided for storing the number of votes for each image ID (image 1 to image n) at the time of voting.
  • a search range determination unit 13 that applies a hash function to a query vector
  • a hash table 15 h that systematizes and stores feature vectors
  • a nearest neighbor point determination unit that determines a nearest neighbor vector among reference vectors registered in the same bin.
  • Reference numeral 17 denotes a configuration related to the approximate nearest neighbor search, which can be said to be an element constituting the nearest neighbor search device. Since the image recognition apparatus in FIG. 20 outputs an image as a recognition result, for example, the nearest neighbor determination unit 17 outputs an image ID associated with the nearest neighbor vector.
  • the component as an approximate nearest neighbor search device determines and outputs the nearest feature vector from the feature vectors registered in the hash table for the input feature vector.
  • a component that stores an image ID associated with a feature vector and a component that outputs an image ID associated with a nearest neighbor vector are not included.
  • the image recognition apparatus in FIG. 20 is an application example of nearest neighbor search, and data handled by the nearest neighbor search apparatus is not limited to feature vectors.
  • ANN Approximate Nearest Neighbor
  • ANN is based on binary trees. In constructing a tree, the data space is divided into two equal parts, and division is repeated until one point enters the leaf. When a query is given, the tree is traced, and the distance registered with the data registered in the reached leaf is calculated. If the distance is r, the search area is the area where the closest part of each divided area falls within the radius r / (1 + ⁇ ) from the query.
  • FLANN> Fast Library for Approximate Nearest Neighbors is a library that provides an approximate nearest neighbor search method suitable for a given database and its parameter tuning. This library includes an exhaustive search in addition to randamized kd-tree (for example, see Non-Patent Document 12) and hierarchical k-means (for example, see Non-Patent Document 13), which have high performance among the proposed methods. Is adopted.
  • Randamized kd-tree is a technique for selecting re-neighbor candidates from multiple trees.
  • a tree structure is formed by dividing a space into two parts while sequentially changing elements of data of interest.
  • the processing time required for the tree traversal and a lot of useless distance calculations are performed. Therefore, the principal component analysis is performed in the randamized kd-tree, and the kd-tree is constructed by focusing on only the upper D-dimensional base that contributes to the distance calculation.
  • Hierarchical k-means as its name suggests, points belonging to each node at each node are clustered by k-means, and the space is divided into clusters at each hierarchy.
  • LSH> Locality Sensitive Hashing is one of the most representative techniques among approximate nearest neighbor search techniques using a hash.
  • LSH that can be used in the vector space (refer to, for example, Non-Patent Document 8) related to the present invention will be described.
  • LSH uses a plurality of hash functions to select points that are considered to be in the vicinity of the query, and performs distance calculation only for those points.
  • the data space is divided into a plurality of randomly generated bases at equal intervals, thereby dividing the space into regions called buckets for indexing.
  • FIG. 21 is an explanatory diagram of LSH, which is one method of conventional approximate nearest neighbor search.
  • FIG. 21A shows a state in which the data space is equally divided by the bins of the hash table along the directions of two bases a 1 and a 2 that are randomly generated.
  • Each region divided along the axis a 1 is a bin indexed by the hash function h j1 related to the base a 1
  • each region divided along the axis a 2 is a hash function h j2 related to the base a 2 Is a bin indexed by.
  • Each axis shows the index value.
  • a cell-like region where these two types of bins intersect, that is, a product region where bins of each dimension of the two-dimensional hash table intersect is a bucket.
  • the numerical value of each bucket has shown the value of the index of hash function hj1 and hj2 .
  • FIG. 21B shows the state of the search area obtained by three projections.
  • LSH of Non-Patent Document 8 a hash function group as shown in the following equation is used.
  • x is an arbitrary point
  • a i is a vector in which the value of each dimension element is independently selected from a Gaussian distribution
  • W is a hash width
  • b i is uniformly selected from the interval [0, W]. It is a real number.
  • a hash function that is sensitive to locality is a hash function that has a high probability of taking the same hash value (index) at points close to each other and a low probability of taking the same hash value at points far away from each other.
  • a hash function group H j is created by combining k hash functions h ji .
  • the bucket is obtained by applying the hash function group H j to the query.
  • This bucket is a target area for distance calculation related to one function group H j .
  • L (L sets) of such hash function groups H j are created, and an area obtained by combining the L areas is finally set as a target area for distance calculation with the query.
  • SH An outline of typical spectral hashing (SH) among techniques using a binary code hash function will be described.
  • SH is a technique that is said to provide good performance among those using a hash.
  • SH selects several principal components of the data space from the top and performs projection onto the Hamming space. Then, a candidate having a distance (Hamming distance) in the projected Hamming space that is equal to or smaller than a threshold is set as the nearest neighbor candidate. That is, paying attention only to the upper principal component basis, each sample is converted into a binary code, and the nearest neighbor candidate is selected according to the Hamming distance from the query.
  • the SH encoding assumes a uniform distribution of the data space, divides the space so that the divided area is divided as close to a rectangular parallelepiped as possible, and gives a binary code to each bucket.
  • FIG. 22 is an explanatory diagram of SH, which is a conventional approximate nearest neighbor search method, and shows a state in which the data space is projected onto a two-dimensional Hamming space composed of two principal component bases pv 1 and pv 2 .
  • SH which is a conventional approximate nearest neighbor search method
  • Each axis has an index indicated by a binary code.
  • the sign of each bucket is a combination of the indices of the axes pv 1 and pv 2 .
  • the query belongs to the bucket denoted by reference numeral 111.
  • the gray area represents a search area for a query when the upper limit of the Hamming distance is 1.
  • buckets of reference numerals 110, 101, and 011 that differ from reference numeral 111 by only one reference code are search areas. Since SH projects the data space onto the principal component basis, it can be said that the original distance is easily maintained after the projection, but since the distance in the projected space is represented by the Hamming distance, an error from the Euclidean distance occurs. For example, there is a problem that the region 011 far from the bucket 111 onto which the query is projected in FIG.
  • the nearest neighbor candidate is extracted from the approximate hypersphere region centered on the query by obtaining the distance between the bucket to which the query belongs and the bucket to which each point belongs.
  • FIG. 23 is an explanatory diagram showing a procedure for determining the distance of each bucket in the method of Sato et al., which is a conventional method of approximate nearest neighbor search.
  • the numerical values attached to the vertical axis and the horizontal axis are indexes.
  • Each cell-shaped section is a bucket as a bin product area.
  • the sequence of numbers 11 to 33 assigned to each bucket is a combination of bin indexes that make up the bucket. This sequence of numbers can be considered as a position vector indicating the position of the bucket in the data space.
  • a distance D between the buckets is defined from the index sequence, that is, the position vector of the bucket.
  • the search for the nearest point may be performed by referring to the data included in the bucket in order from the bucket having the smallest bucket distance. In this way, a search for a hypersphere region centered on the query can be realized. Only points with a small approximate distance from the query can be targeted for distance calculation.
  • FIG. 23 shows an example when the index of the bin is ⁇ 2, 2> when the hash function is applied to the query.
  • the distance between the points registered in the bucket with the same index as the query is calculated.
  • a bucket with a bucket distance of 1 is searched.
  • the buckets are indexes ⁇ 1, 2>, ⁇ 2, 1>, ⁇ 2, 3>, ⁇ 3, 2>. These buckets are searched in order. If it is determined that a sufficient number of buckets have been searched, the search is terminated. On the other hand, if it is determined that the number of buckets is still insufficient, the search range is expanded to farther buckets.
  • the buckets are the indexes ⁇ 1,1>, ⁇ 3,1>, ⁇ 3,3>, ⁇ 1,3>.
  • the accuracy of the approximate distance decreases when the dimension of the projection space is smaller than the dimension of the data space.
  • the hash size increases exponentially with respect to the hash dimension number ⁇ , an enormous hash size is required to maintain accuracy for high-dimensional data. It is difficult to increase the dimension number ⁇ of the hash for high-dimensional data, and as a result, it is not possible to obtain a sufficient approximate distance accuracy for high-dimensional data.
  • the hash size becomes too large, it is necessary to refer to many buckets in order to maintain the accuracy of nearest neighbor search, and it takes a lot of time to extract the nearest neighbor candidate. ⁇ 6.
  • G. At this time, the expected value (estimated distance) of the distance from the query to the point belonging to each area is the distance to the centroid of the area.
  • IVFADC nearest neighbor selection IVFADC uses simple vector quantization for coarse quantization (eg H. Jegou, M. Douze, and C. Schmid, "Product quantization for nearest neighbor search," IEEE Trans. TPAMI, vol. .33, no.1, pp.117-128, 2011).
  • coarse quantization eg H. Jegou, M. Douze, and C. Schmid, "Product quantization for nearest neighbor search," IEEE Trans. TPAMI, vol. .33, no.1, pp.117-128, 2011.
  • G the calculation cost for selecting the nearest neighbor candidate
  • O O
  • IMI nearest neighbor candidate selection Therefore, IMI has been proposed as an improved method of IVFADV (for example, A. Babenko and V. Lempitsky, "The inverted multi-index," Proc. IEEE Conference on Computer Vision and Pattern Recognition ( CVPR), pp. 3069-3076, 2012).
  • product quantization is performed by dividing the vector x into two partial vectors U 1 (x) and U 2 (x).
  • the set of partial centroids obtained is C 1 , C 2 , and the number of elements
  • is g.
  • estimated square distance F ij to the point belonging to the query q and c ij (Q) is the distance from the query to the i-th element of the m-th partial centroid Is expressed by the following equation. Therefore, the problem of selecting centroids in order of proximity to the query is the two partial distance lists This results in a problem of searching for a combination of i and j where the sum F ij is small. In IMI, this problem is solved by using a combinatorial search method called Multi-Sequence algorithm.
  • the algorithm Each time the algorithm generates the combination of subscripts with the shortest distance at a given time, it adds subscript candidates as subscript pairs that may generate the next smallest combination of distances. Repeat the process of selecting the next combination. Then, the search is terminated when the obtained number of nearest neighbor candidates reaches point L.
  • the space division number G is equal, the product quantization is less accurate than the vector quantization.
  • the Multi-Sequence algorithm can be applied and the calculation cost is reduced. Since the nearest neighbor candidates can be obtained, the search speed can be increased.
  • the inverted multi-index it is reported that a solution can be obtained at a higher speed than that of IVFADC. The conventional representative nearest neighbor search method has been described above.
  • the distance from the query can be estimated based on the index.
  • the distance in the space after projection cannot sufficiently hold the distance in the original space, and the estimated distance cannot sufficiently hold the magnitude relationship of the true distance. In that case, in order to increase the accuracy of the search, it is necessary to secure many nearest neighbor candidates, and a solution cannot be obtained at high speed.
  • the inventors pay attention to the method of Sato et al.
  • the approximate distance well reflects the magnitude relationship of the true distance
  • This makes it possible to estimate the distance with higher accuracy and higher speed than the conventional method, and as a result, the overall speed of the approximate nearest neighbor search can be increased.
  • the present invention provides a distance estimation method and an adaptive search range determination method. Special attention.
  • Bucket Distance Hashing an approximate nearest neighbor search method to which the first point-to-bucket distance estimation and the second hash table partitioning are applied is referred to as Bucket Distance Hashing or BDH.
  • BDH space division suitable for distance estimation
  • k-means BDH a method in which k-means BDH is combined with distance estimation based on a probability density function, which is the fourth improvement point, is called k-means BDH P.
  • k-meansmeanBDH PC a technique in which the adaptive search range which is the fifth improvement point is combined with k-meansmeanBDH P.
  • the first improved method mainly relates to improvement in accuracy of distance estimation. Sato et al. Estimated the distance between buckets to which the query and data belong, that is, the bucket-to-bucket distance. Here, a method for improving the accuracy of distance estimation with the same data structure by estimating the distance from the exact query position to the bucket to which each data belongs, that is, the distance of the point-to-bucket, is proposed.
  • This technique uses the same equation (5) as the technique of Sato et al.
  • the representative point is determined by calculating the expected value of the coordinate of p 1 and the coordinate of the point belonging to the same bucket as p 2 .
  • the representative point is determined so that the coordinate of the representative point becomes an expected value of the coordinates of the point belonging to the bucket. That is, the representative point is the center of gravity of the bucket.
  • the Euclidean distance between the two points of the coordinates of p 1 and the coordinates of the representative point of the bucket to which p 2 belongs is calculated, and this is used as the approximate distance.
  • the expected value of the Euclidean square distance in the base i direction is as follows. From the assumption that each base is independent, the expected value of the Euclidean square distance in v-dimensional space is as follows.
  • the distance between the buckets B (p 2 ) to which the points p 1 and p 2 belong, that is, the point-to-bucket distance is expressed as follows.
  • (h i (p 2 ) +1/2) represents the coordinates in the ⁇ i direction of the center of gravity of the bucket B (p 2 ), and the distance in Expression (7) is the distance between the query and the center of gravity of the bucket. be equivalent to. Since the position of the query is specified, distance estimation with higher accuracy than Expression (6) is realized.
  • the error variance of the estimated distance is 1 / W 2 compared to the method of Sato et al. That estimates the bucket-to-bucket distance.
  • the distance of the expression (7) is multiplied by W, and is rewritten as the following expression.
  • BD i (p 1 , B (p 2 )) represents the distance in the base direction of the i-th dimension between the point p 1 and the center of gravity of the bucket B (p 2 ).
  • FIG. 2 is an explanatory diagram showing an example of distance estimation according to this embodiment. It is a figure corresponding to FIG. 1 which shows the distance estimation in the method of the conventional Sato et al.
  • the star in FIG. 2 represents a query. If the distance between the bucket centers is 1, the left and right direction query is 0.6 from the center of the left bucket and 0.4 from the center of the right bucket, and the vertical direction is 0.7 from the center of the upper bucket. Located at 0.3 from the center of the lower bucket.
  • the number on the axis (2.56, 0.36, etc.) represents the weight of the bucket distance in the horizontal direction and the vertical direction, and the number in the bucket (3.05, 0.85, etc.) represents the weight of the distance between the estimated query and each bucket.
  • the weight is the Euclidean square distance.
  • FIG. 3 is an explanatory view showing a different example of distance estimation according to this embodiment.
  • the dimension number ⁇ 2 of the hash function.
  • This is an example of a search space and query different from those in FIG.
  • a circle centered on the query in FIG. 3 represents the size of the search radius, a bucket whose bucket center is within the circle is a search area, and the search area is shown in gray.
  • a bucket within a search radius R given as a parameter is referred to. Since the search range is within the circle centered on the query instead of the center of the bucket containing the query (a hypersphere when the dimension ⁇ of the hash is expanded to an arbitrary natural number), Sato performs the bucket-to-bucket distance estimation.
  • Distance estimation can be performed with higher accuracy than those methods.
  • the process of selecting a bucket within the search radius R is more complicated than the method of Sato et al.
  • the reason is that the estimated distance is limited to an integer in the method of Sato et al., But is a real number in BDH, so it takes a long time to handle the estimated distance strictly.
  • the present invention proposes an algorithm for quickly identifying buckets within the search radius R.
  • FIG. 18 shows two algorithms based on the branch and bound method for quickly identifying buckets within the search radius R in this embodiment. “Algorithm 1” and “Algorithm 2”.
  • ⁇ coordinate values are required to obtain the distance from the query to the representative point of a bucket.
  • H (x) ⁇ h 1 (x), h 2 (x)... H ⁇ (x) ⁇ .
  • the distance to the bucket can be found by adding ⁇ times.
  • the ⁇ bases are selected by principal component analysis and are arranged in descending order of the eigenvalues. Therefore, the data has a large variance in the upper base direction (the subscript number is young). Therefore, the most efficient method for searching for buckets within the radius R is to evaluate in the order of subscript numbers as described below.
  • Algorithm 2 takes two arguments. I indicating the dimension of the hash value to be determined, and the distance D for the (i ⁇ 1) th dimension already determined. In the 1st to 7th lines, if the last base (the stage at which the ⁇ -th hash value is determined) has not been reached (1st line), k i (the number of divisions of the i-th base, that is, the bucket in the i-th base direction) Try the hash value (index) of the number of bins that make up (second line).
  • BD ij is a one-dimensional distance (distance component in the i-th base direction) in the i-th base when the hash value j (j-th bin) is selected
  • D + BD ij + mD i is i hash values. Is the distance to the nearest bucket at a determined stage, and only when it is smaller than the search radius R, recursively calls itself and proceeds to the next base (lines 3-5). Lines 9 to 13 are executed only when the last ⁇ th base is reached. If there is a bucket within the search radius, the hash is subtracted.
  • Hash table partitioning> The technique of Sato et al. Has a problem that high-speed data cannot be searched at high speed. This is a problem caused by the relationship between the number of dimensions of the hash and the number of buckets included in the hash table (hereinafter referred to as hash size).
  • hash size the number of dimensions of the hash and the number of buckets included in the hash table.
  • the hash dimension number ⁇ In order to maintain the accuracy of the estimated distance, it is necessary to increase the hash dimension number ⁇ in accordance with the data dimension number. However, if the dimension number ⁇ of the hash is increased, the hash size becomes enormous and falls into a situation where it cannot fit in the memory.
  • the estimated distance of the high-dimensional hash is obtained by dividing the high-dimensional hash table and integrating the estimated distances obtained from the low-dimensional hash table. Suggest a method.
  • the estimated distance from query q to any point p Can be expressed as This is equal to the estimated distance determined by the ⁇ -dimensional hash.
  • the advantage of dividing the hash table is that the hash size can be drastically reduced even when a hash of the same number of dimensions is expressed as compared to the case of using one hash table.
  • FIG. 4 is a graph showing the relationship between accuracy and processing time when the dimension number ⁇ of the multidimensional hash of the conventional Sato et al. Method is changed.
  • the data used here is 64 dimensions or 128 dimensions
  • FIG. 4A shows the case of 64 dimensions
  • FIG. 4B shows the case of 128 dimensions.
  • Artificial data and queries based on a normal distribution of 10 million points are both 2000 points generated under the same conditions.
  • the computer used was an Opteron (tm) 6174 (2.2 GHz) CPU, 256 [GB] memory, and the experiment was performed on a single core.
  • tm 6174 (2.2 GHz) CPU, 256 [GB] memory
  • Data is extracted from artificial data following normal distribution of 64, 128, and 256 dimensions (dispersion is uniformly selected from 100 to 400 for each base) and each frame image of the video distributed by Instance Search task of TRECVID2010 SIFT features (128 dimensions, for SIFT, DG Lowe, "Distinctive image features from scale-invariant keypoints," International journal of computer vision, vol.60, no.2, pp.91-110, 2004 .)) was prepared for 10 million each.
  • the query uses 2000 points created under the same conditions as the database, and the average is the result.
  • FIG. 5 shows the relationship between accuracy and processing time for artificial data results.
  • FIG. 5A shows experimental results of 64-dimensional artificial data
  • FIG. 5B shows experimental results of 128-dimensional artificial data
  • FIG. 5C shows experimental results of 256-dimensional artificial data.
  • Table 1 shows the memory usage at this time.
  • the result of the image data is shown in FIG. 5 and 6, the horizontal axis represents accuracy, and the vertical axis represents processing time.
  • the single hash of the legend is a case where the hash table is not divided in the present invention, and the divided hash is a case where the hash table is divided.
  • BDH is improved by three additional approaches.
  • the first is the proposal of space division suitable for distance estimation
  • the second is the proposal of distance estimation based on the probability density function
  • the third is the expansion of the search area considering the data density around the query. The details will be described below.
  • V i is a unit vector in the direction of the i-th basis.
  • a bucket is defined by this vector. That is, an area where a certain vector is closest is defined as a bucket range.
  • This vector is called a representative vector.
  • the data space is divided into ⁇ i v k i regions. Therefore, the distance component between the point p and the representative value C ij in the i-th base direction, that is, the base distance BD i is
  • X represents a set of data
  • X n represents n-th data
  • BE i represents an error in the i-th principal component direction.
  • the representative value ⁇ C ij ⁇ in each base is obtained by the k-means method having the same objective function as the present invention. What is important here is how many representative values in each base are set. In order to solve this problem, all bases are divided by the same number, but in the actual data, the variance of the data projected onto the principal component basis differs greatly depending on the principal component basis, and it is not efficient to handle it equally. . Naturally, if the number of representative vectors is the same, it is better that the estimation error is smaller.
  • FIG. 7 is an explanatory diagram showing a comparative example of equal division and adaptive base division according to this embodiment.
  • the estimated distance BD i (p, j) in the i-th principal component direction is expressed as the expected value of the square base distance as follows.
  • the feature of the distance estimation proposed here is that the fitness to a general complex distribution is higher than that of the distance estimation of BDH, and at the same time, the calculation cost is low and it is suitable for high-speed processing.
  • ⁇ Fifth improvement Expansion of search radius considering data density around query>
  • a search area is generally determined according to a search radius R given as a parameter.
  • R search radius
  • well-known literature e.g., W. Dong, Z. Wang, W. Josephson, M. Charikar, and K. Li, "Modeling LSH for performance tuning," Proceeding of the 17th ACM conference on Information and knowledge management, pp .669-678 2008.
  • FIG. 8 is an explanatory diagram showing how the search radius is changed according to the density around the query as an example of this embodiment.
  • the dimension number of hash ⁇ 2.
  • the reference bucket is obtained by calculating the distance on the hash for all buckets (for example, H. Jegou, M. Douze, and C. Schmid, "Product quantization for nearest neighbor search," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.33, no.1, pp.117-128, 2011.) and implementation has a hash structure to calculate the distance on the hash for all sample points
  • the processing time is also required for specifying the nearest neighbor candidate such as the one that determines a point less than the search radius (SH or its improved method).
  • Algorithm 1 a distance mD i obtained by adding the minimum values that can be taken in each of the ⁇ i hash functions is calculated and a bucket existing within a radius R from the query is searched.
  • Algorithm 3 and “Algorithm 4” also use the condition that the distance MD i obtained by adding the maximum possible values is calculated and exists beyond the radius L from the query.
  • the distance MDi obtained by adding the minimum value mD i for the ⁇ i dimension and the maximum possible value is calculated in the first to fourth lines. In the 5th to 6th lines, initial values of L and U which are lower and upper limits of the search radius are set. In the seventh to eleventh lines, the function of algorithm 4 is called and the search is continued while the search radius is increased by ⁇ until the nearest neighbor candidate becomes c points or more.
  • the computer used in the experiment was an Opteron (tm) 6174 (2.2 GHz) CPU and 256 [GB] memory, and the experiment was performed with a single core.
  • SIFT features were extracted from images obtained every 10 seconds from the video distributed by the Instance Search task of TRECVID2010, and duplicate vectors were removed.
  • the horizontal axis is the code length [bit]
  • the vertical axis is the correlation coefficient.
  • the horizontal axis is the code length [bit]
  • the vertical axis is the rank of the nearest point. It can be seen that the average rank of the nearest points is higher in BDH than SH in any code length.
  • the ranking of the nearest neighbors is about 1/8 at 20 bits, about 1/8 at 40 bits, and about 1/13 at 80 bits compared to SH.
  • k-means BDH is obtained by applying a spatial partitioning method using k-means according to the third improvement point
  • k-means BDH P uses a probability density function which is the fourth improvement point for k-means BDH.
  • the distance estimation is applied.
  • the performance is lower than that of BDH, but improvement is seen by combining the probability density function.
  • k-means BDH P (method for fixing the search radius R) of only the fourth improvement point (distance estimation based on the probability density function) that was the fastest in FIG.
  • a comparison of k-means BDH PC with 5 improvement points (method of fixing the nearest neighbor candidate number c) is performed. The result of the comparison is shown in FIG. By reflecting the data density around the query, it was confirmed that the speed was increased by about twice, and a sufficient effect was obtained.
  • each search parameter is ⁇ for ANN, SH for Hamming distance R, and k-means BDH PC nearest neighbor number c.
  • the comparison results are shown in FIG.
  • the processing time of k-means ⁇ BDH PC is about 1/10 for ANN and about 1/6 to 1/12 for SH, compared with the same accuracy, and the speed is greatly increased. I understand that.
  • bucket number G is
  • the number of buckets increases, but it takes time to search for adjacent buckets. Therefore, a large M cannot be used easily, and if the vector has a high dimension, the M used for indexing becomes relatively small with respect to the total number of dimensions, and the approximation cannot be obtained without obtaining the accuracy of distance estimation. The performance of the nearest neighbor search is degraded.
  • the number of buckets is the data set size
  • M sets of P sets of orthogonal bases are selected from the orthogonal bases V, and the data space is expressed as a direct product of M P-dimensional subspaces.
  • V m be P orthogonal bases that span the mth subspace.
  • a centroid set C m is obtained for each subspace using the k-means algorithm to minimize the quantization error. This is equivalent to performing product quantization by dividing the vector projected onto the PM dimensional space spanned by the base into M P dimensional partial vectors.
  • the hash function H ( ⁇ ) is as follows.
  • Bucket distance an estimated amount of distance that minimizes the estimation error is derived, and the bucket distance is defined. Assuming that there is no correlation between the bases (if the principal component basis is used, non-correlation up to the second order is guaranteed), the error in the estimated distance in each base direction can be minimized independently.
  • the minimization problem is defined as follows: The data x follows the probability density function P (x), and if the event that exists in a certain region z is Z, the distribution of the data in the region z is expressed as P (x
  • Equation (24) Var [] is a function that returns an unbiased variance with the argument regarded as a sample of the population. Note that the estimated amount obtained here is not the distance from the center of gravity of the region. From the above results, the bucket distance F H in which the hash value list is H is defined as follows. In the following formula (26), u m p is the p-th principal component basis of the m-th subspace.
  • FIG. 24 shows the distribution of points in the data space, and u 1 and u 2 represent the first and second principal component bases. When the bases of bases are quantized independently as in Normal of FIG. 24A, these often have a correlation, resulting in waste of quantization. Therefore, as in the case of PCA in FIG.
  • the relationship between accuracy and processing time is verified by first examining the relationship between accuracy and processing time without limiting memory usage, and then applying memory reduction to set an upper limit on the amount of memory that can be used. Verified.
  • the problem setting is a K-neighbor search problem that searches for K points close to the query.
  • 11 Feature point extraction unit
  • 13 Search range determination unit
  • 15 Image database
  • 15h Hash table
  • 17 Nearest neighbor determination unit
  • 19 Voting unit
  • 21 Voting table
  • 23 Image selection unit

Landscapes

  • Engineering & Computer Science (AREA)
  • Library & Information Science (AREA)
  • Theoretical Computer Science (AREA)
  • Data Mining & Analysis (AREA)
  • Databases & Information Systems (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
PCT/JP2013/055440 2012-02-28 2013-02-28 Dispositif de recherche de voisin approximativement le plus proche, procédé de recherche de voisin approximativement le plus proche, et programme Ceased WO2013129580A1 (fr)

Applications Claiming Priority (4)

Application Number Priority Date Filing Date Title
JP2012042172 2012-02-28
JP2012-042172 2012-02-28
US201261684911P 2012-08-20 2012-08-20
US61/684,911 2012-08-20

Publications (1)

Publication Number Publication Date
WO2013129580A1 true WO2013129580A1 (fr) 2013-09-06

Family

ID=49082771

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/JP2013/055440 Ceased WO2013129580A1 (fr) 2012-02-28 2013-02-28 Dispositif de recherche de voisin approximativement le plus proche, procédé de recherche de voisin approximativement le plus proche, et programme

Country Status (2)

Country Link
JP (1) JPWO2013129580A1 (fr)
WO (1) WO2013129580A1 (fr)

Cited By (22)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR101721114B1 (ko) * 2016-06-27 2017-03-30 서울대학교산학협력단 위치정보가 포함된 포인트 데이터를 다축척의 웹 지도상에 클러스터링하기 위하여 격자의 크기를 결정하는 방법
WO2017065795A1 (fr) * 2015-10-16 2017-04-20 Hewlett Packard Enterprise Development Lp Mise à jour incrémentielle d'un graphe de voisinage par une indexation basée sur une transformée orthogonale
WO2017072890A1 (fr) * 2015-10-28 2017-05-04 株式会社東芝 Système de gestion de données, procédé de gestion de données et programme
CN106897258A (zh) * 2017-02-27 2017-06-27 郑州云海信息技术有限公司 一种文本差异性的计算方法及装置
GB2551504A (en) * 2016-06-20 2017-12-27 Snell Advanced Media Ltd Image Processing
WO2018159690A1 (fr) * 2017-02-28 2018-09-07 国立研究開発法人理化学研究所 Procédé et dispositif d'extraction de données de nuage de points
WO2019200264A1 (fr) * 2018-04-12 2019-10-17 Georgia Tech Research Corporation Authentification basée sur un visage préservant la confidentialité
CN110377681A (zh) * 2019-07-11 2019-10-25 拉扎斯网络科技（上海）有限公司 一种数据查询的方法、装置、可读存储介质和电子设备
CN110569244A (zh) * 2019-08-30 2019-12-13 深圳计算科学研究院 一种海明空间近似查询方法及存储介质
CN111033495A (zh) * 2017-08-23 2020-04-17 谷歌有限责任公司 用于快速相似性搜索的多尺度量化
CN111859192A (zh) * 2020-07-28 2020-10-30 科大讯飞股份有限公司 搜索方法、装置、电子设备及存储介质
CN111881767A (zh) * 2020-07-03 2020-11-03 深圳力维智联技术有限公司 高维特征的处理方法、装置、设备及计算机可读存储介质
CN112241475A (zh) * 2020-10-16 2021-01-19 中国海洋大学 基于维度分析量化器哈希学习的数据检索方法
CN112860758A (zh) * 2019-11-27 2021-05-28 阿里巴巴集团控股有限公司 搜索方法、装置、电子设备及计算机存储介质
US20210319368A1 (en) * 2018-12-27 2021-10-14 Ihi Corporation Fault diagnosis for diagnosis target system
CN113542750A (zh) * 2021-05-27 2021-10-22 绍兴市北大信息技术科创中心 采用两套及两套以上哈希表进行搜索的数据编码方法
CN113868291A (zh) * 2021-10-21 2021-12-31 深圳云天励飞技术股份有限公司 一种最近邻搜索方法、装置、终端和存储介质
CN116383281A (zh) * 2023-04-10 2023-07-04 电子科技大学 一种空间中位置点分布均匀性的评估方法
CN116401279A (zh) * 2023-04-07 2023-07-07 黑龙江大学 一种高维空间的近似最近邻查询系统
CN119513375A (zh) * 2024-11-20 2025-02-25 南京大学 一种基于近似最近邻搜索的向量检索装置
WO2025142390A1 (fr) * 2023-12-28 2025-07-03 オムロン株式会社 Dispositif de traitement d'informations, procédé de traitement d'informations et programme
US12360994B2 (en) 2020-09-29 2025-07-15 Nec Corporation Information processing apparatus, information processing method, and recording medium

Families Citing this family (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN113157688A (zh) * 2020-01-07 2021-07-23 四川大学 一种基于空间索引及相邻点信息的最近邻点搜索方法

Non-Patent Citations (2)

* Cited by examiner, † Cited by third party
Title
NAOTO MASUYAMA ET AL.: "Acceleration of the k- Nearest Neighbor Algorithm by Addition of Termination Conditions in Pattern Recognition Problems", THE TRANSACTIONS OF THE INSTITUTE OF ELECTRONICS, INFORMATION AND COMMUNICATION ENGINEERS, vol. J84-D-II, no. 3, 1 March 2001 (2001-03-01), pages 439 - 447 *
TOMOKAZU SATO ET AL.: "Gaisan Kyori no Seido Kojo ni yoru Kinji Saikinbo Tansaku no Kosokuka", IPSJ SIG NOTES, 15 October 2011 (2011-10-15), pages 1 - 6 *

Cited By (33)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2017065795A1 (fr) * 2015-10-16 2017-04-20 Hewlett Packard Enterprise Development Lp Mise à jour incrémentielle d'un graphe de voisinage par une indexation basée sur une transformée orthogonale
US11361195B2 (en) 2015-10-16 2022-06-14 Hewlett Packard Enterprise Development Lp Incremental update of a neighbor graph via an orthogonal transform based indexing
WO2017072890A1 (fr) * 2015-10-28 2017-05-04 株式会社東芝 Système de gestion de données, procédé de gestion de données et programme
US11281645B2 (en) 2015-10-28 2022-03-22 Kabushiki Kaisha Toshiba Data management system, data management method, and computer program product
JPWO2017072890A1 (ja) * 2015-10-28 2018-05-17 株式会社東芝 データ管理システム、データ管理方法およびプログラム
GB2551504A (en) * 2016-06-20 2017-12-27 Snell Advanced Media Ltd Image Processing
KR101721114B1 (ko) * 2016-06-27 2017-03-30 서울대학교산학협력단 위치정보가 포함된 포인트 데이터를 다축척의 웹 지도상에 클러스터링하기 위하여 격자의 크기를 결정하는 방법
CN106897258A (zh) * 2017-02-27 2017-06-27 郑州云海信息技术有限公司 一种文本差异性的计算方法及装置
JP2018141757A (ja) * 2017-02-28 2018-09-13 国立研究開発法人理化学研究所 点群データの抽出方法、及び点群データの抽出装置
WO2018159690A1 (fr) * 2017-02-28 2018-09-07 国立研究開発法人理化学研究所 Procédé et dispositif d'extraction de données de nuage de points
US11204243B2 (en) 2017-02-28 2021-12-21 Topcon Corporation Point cloud data extraction method and point cloud data extraction device
EP3531068A4 (fr) * 2017-02-28 2020-04-01 Riken Procédé et dispositif d'extraction de données de nuage de points
CN111033495A (zh) * 2017-08-23 2020-04-17 谷歌有限责任公司 用于快速相似性搜索的多尺度量化
US11494476B2 (en) 2018-04-12 2022-11-08 Georgia Tech Research Corporation Privacy preserving face-based authentication
US11874911B2 (en) 2018-04-12 2024-01-16 Georgia Tech Research Corporation Privacy preserving face-based authentication
WO2019200264A1 (fr) * 2018-04-12 2019-10-17 Georgia Tech Research Corporation Authentification basée sur un visage préservant la confidentialité
US20210319368A1 (en) * 2018-12-27 2021-10-14 Ihi Corporation Fault diagnosis for diagnosis target system
CN110377681A (zh) * 2019-07-11 2019-10-25 拉扎斯网络科技（上海）有限公司 一种数据查询的方法、装置、可读存储介质和电子设备
CN110569244A (zh) * 2019-08-30 2019-12-13 深圳计算科学研究院 一种海明空间近似查询方法及存储介质
CN112860758A (zh) * 2019-11-27 2021-05-28 阿里巴巴集团控股有限公司 搜索方法、装置、电子设备及计算机存储介质
CN111881767A (zh) * 2020-07-03 2020-11-03 深圳力维智联技术有限公司 高维特征的处理方法、装置、设备及计算机可读存储介质
CN111881767B (zh) * 2020-07-03 2023-11-03 深圳力维智联技术有限公司 高维特征的处理方法、装置、设备及计算机可读存储介质
CN111859192A (zh) * 2020-07-28 2020-10-30 科大讯飞股份有限公司 搜索方法、装置、电子设备及存储介质
CN111859192B (zh) * 2020-07-28 2023-01-17 科大讯飞股份有限公司 搜索方法、装置、电子设备及存储介质
US12360994B2 (en) 2020-09-29 2025-07-15 Nec Corporation Information processing apparatus, information processing method, and recording medium
CN112241475B (zh) * 2020-10-16 2022-04-26 中国海洋大学 基于维度分析量化器哈希学习的数据检索方法
CN112241475A (zh) * 2020-10-16 2021-01-19 中国海洋大学 基于维度分析量化器哈希学习的数据检索方法
CN113542750A (zh) * 2021-05-27 2021-10-22 绍兴市北大信息技术科创中心 采用两套及两套以上哈希表进行搜索的数据编码方法
CN113868291A (zh) * 2021-10-21 2021-12-31 深圳云天励飞技术股份有限公司 一种最近邻搜索方法、装置、终端和存储介质
CN116401279A (zh) * 2023-04-07 2023-07-07 黑龙江大学 一种高维空间的近似最近邻查询系统
CN116383281A (zh) * 2023-04-10 2023-07-04 电子科技大学 一种空间中位置点分布均匀性的评估方法
WO2025142390A1 (fr) * 2023-12-28 2025-07-03 オムロン株式会社 Dispositif de traitement d'informations, procédé de traitement d'informations et programme
CN119513375A (zh) * 2024-11-20 2025-02-25 南京大学 一种基于近似最近邻搜索的向量检索装置

Also Published As

Publication number Publication date
JPWO2013129580A1 (ja) 2015-07-30

Similar Documents

Publication Publication Date Title
WO2013129580A1 (fr) Dispositif de recherche de voisin approximativement le plus proche, procédé de recherche de voisin approximativement le plus proche, et programme
Zhang et al. Vector of locally and adaptively aggregated descriptors for image feature representation
Gao et al. Learning in high-dimensional multimedia data: the state of the art
He et al. Scalable similarity search with optimized kernel hashing
Wang et al. Order preserving hashing for approximate nearest neighbor search
Zhang et al. Supervised hashing with latent factor models
CN105912611B (zh) 一种基于cnn的快速图像检索方法
Wu et al. Online multi-modal distance metric learning with application to image retrieval
CN107256262A (zh) 一种基于物体检测的图像检索方法
Wang et al. Query-specific visual semantic spaces for web image re-ranking
Wang et al. Fast neighborhood graph search using cartesian concatenation
KR102590388B1 (ko) 영상 컨텐츠 추천 장치 및 방법
Tiakas et al. MSIDX: multi-sort indexing for efficient content-based image search and retrieval
Pedronette et al. Exploiting contextual information for image re-ranking and rank aggregation
Dharani et al. Content based image retrieval system using feature classification with modified KNN algorithm
CN119357433A (zh) 一种向量检索方法及装置
JP6017277B2 (ja) 特徴ベクトルの集合で表されるコンテンツ間の類似度を算出するプログラム、装置及び方法
CN118964686A (zh) 向量检索方法、装置、设备和存储介质
US9104946B2 (en) Systems and methods for comparing images
Ejaz et al. Video summarization using a network of radial basis functions
JP5833499B2 (ja) 高次元の特徴ベクトル集合で表現されるコンテンツを高精度で検索する検索装置及びプログラム
Lin et al. The distributed system for inverted multi-index visual retrieval
Zhang et al. FRWCAE: joint faster-RCNN and Wasserstein convolutional auto-encoder for instance retrieval
Yang et al. Submodular reranking with multiple feature modalities for image retrieval
JPWO2012077818A1 (ja) ハッシュ関数の変換行列を定める方法、該ハッシュ関数を利用するハッシュ型近似最近傍探索方法、その装置及びそのコンピュータプログラム

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 13755813

Country of ref document: EP

Kind code of ref document: A1

ENP Entry into the national phase

Ref document number: 2014502374

Country of ref document: JP

Kind code of ref document: A

NENP Non-entry into the national phase

Ref country code: DE

122 Ep: pct application non-entry in european phase

Ref document number: 13755813

Country of ref document: EP

Kind code of ref document: A1