Data retrieval device using a skip table

• US 8,244,739 B2
• Filed: 01/14/2010
• Issued: 08/14/2012
• Est. Priority Date: 01/23/2009
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Iwamoto, Kota, Oami, Ryoma
• Primary Examiner(s): Syed, Farhan
• Application Number:
  US12/995,144
• Publication Number:
  US 20110099177A1
• Time in Patent Office: 943 Days
• Field of Search: None
• US Class Current: 707/749
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: G06F 16/71 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/7847 using low-level visual features of the video content

Abstract

The data retrieval device includes a first skip correspondence table which corresponds to each piece of data in a retrieval target data series, and, for each possible similarity range which is taken by a similarity between corresponding data and retrieval data, records skip destination data information for specifying the data which appears first after the corresponding data among pieces of data in which similarities with the retrieval data have the possibility to have a predetermined relationship in comparison with a predetermined threshold. The data retrieval device also includes a control unit which, when retrieving data in which a similarity with the retrieval data is smaller than or equal to the threshold from among the retrieval target data series, selects data in the retrieval target data series for which calculation of a similarity with the retrieval data is necessary, using the first skip correspondence table.

Claims

1. A data retrieval device realized by a computer, the computer comprising:

a memory that stores a first skip correspondence table that corresponds to each piece of data in a retrieval target data series, and, for each possible similarity range which is taken by a similarity between corresponding data and retrieval data, records skip destination data information for specifying the data which appears first after the corresponding data among pieces of data in which similarities with the retrieval data have the possibility to have a predetermined relationship in comparison with a predetermined threshold; and

a control unit which in response to an input of retrieval data and when a similarity with the retrieval data is smaller than or equal to the threshold from among the retrieval target data series, calculates a similarity between a certain data from among the retrieval target data series and the retrieval data, selects data in the retrieval target data series which is calculated following the certain data, based on the similarity and the first skip correspondence table corresponding to the certain data, and outputs the selected data,

wherein when a similarity range including the similarity between the piece of data and the retrieved data is present in the first skip correspondence table, the control unit determines data indicated by skip destination data information, which is recorded corresponding to the similarity range present in the first skip correspondence table, to be data in the retrieval target data series for which a similarity with the retrieval data is calculated next.

2. The data retrieval device, according to claim 1, wherein

the predetermined relationship is a relationship in which a similarity with the retrieval data is smaller than or equal to the threshold.

3. The data retrieval device, according to claim 2, wherein

when a similarity with the retrieval data calculated for a piece of data in the retrieval target data series is not smaller than or equal to the threshold, the control unit determines data in the retrieval target data series for which a similarity with the retrieval data is calculated next, according to the calculated similarity and the first skip correspondence table of the piece of data.

4. The data retrieval device, according to claim 2, further comprising

a first skip correspondence table generation unit that receives the retrieval target data series and generates the first skip correspondence table of each data in the retrieval target data series.

5. The data retrieval device, according to claim 4, wherein

the first skip correspondence table generation unit calculates a similarity between subsequent data of generation target data of the first skip correspondence table and the generation target data, obtains, from the similarity and the threshold, a skip possible condition indicating a lower limit of a similarity between the generation target data and the retrieval data having no possibility that a similarity between the subsequent data and the retrieval data becomes smaller than or equal to the threshold, calculates a continuous skip possible condition indicating a maximum value of the lower limit of the similarity provided by the skip possible conditions of the self data and subsequent data preceding the self data, and according to the continuous skip possible condition calculated, generates a first skip correspondence table of the generation target data.

6. The data retrieval device, according to claim 1, wherein

the predetermined relationship is a relationship in which a similarity with the retrieval data is larger than the threshold.

7. The data retrieval device, according to claim 6, wherein

when a similarity with the retrieval data calculated for a piece of data in the retrieval target data series is smaller than or equal to the threshold, the control unit determines data in the retrieval target data series for which a similarity with the target data is calculated next, according to the calculated similarity and the first skip correspondence table of the piece of data.

8. The data retrieval device, according to claim 7, further comprising

a first skip correspondence table generation unit that receives the retrieval target data series and generates the first skip correspondence table of each data in the retrieval target data series.

9. The data retrieval device, according to claim 8, wherein

the first skip correspondence table generation unit calculates a similarity between subsequent data of generation target data of the first skip correspondence table and the generation target data, obtains, from the similarity and the threshold, a skip possible condition indicating an upper limit of a similarity between the generation target data and the retrieval data having no possibility that a similarity between the subsequent data and the retrieval data becomes larger than the threshold, calculates a continuous skip possible condition indicating a minimum value of the upper, limit of the similarity provided by the skip possible conditions of the self data and subsequent data preceding the self data, and according to the continuous skip possible condition calculated, generates a first skip correspondence table of the generation target data.

10. The data retrieval device, according to claim 5, wherein

the first skip correspondence table generation unit combines a plurality of continuous similarity ranges in the generated first skip correspondence table into one similarity range, and assigns most preceding data of a plurality of skip destination data corresponding to the similarity ranges before combination, as skip destination data corresponding to the combined similarity range.

11. The data retrieval device, according to claim 1, wherein the first skip correspondence table generation unit generates the first skip correspondence table only for partial data of the retrieval target data series.

12. The data retrieval device, according to claim 2, further comprising

a second skip correspondence table that corresponds to each piece of data in a retrieval target data series, and, for each possible similarity range which is taken by a similarity between corresponding data and retrieval data, records skip destination data information for specifying the data which appears first after the corresponding data among pieces of data in which similarities with the retrieval data have the possibility not to have the predetermined relationship with the threshold, wherein

the control unit selects data in the retrieval target data series for which calculation of a similarity with the retrieval data is necessary, using the first skip correspondence table and the second skip correspondence table.

13. The data retrieval device, according to claim 12, wherein

when a similarity with the retrieval data calculated for a piece of data in the retrieval target data series is not smaller than or equal to the threshold, the control unit determines data in the retrieval target data series for which a similarity with the retrieval data is calculated next, according to the calculated similarity and the first skip correspondence table of the piece of data, and

when a similarity with the retrieval data calculated for a piece of data in the retrieval target data series is smaller than or equal to the threshold, the control unit determines data in the retrieval target data series for which a similarity with the target data is calculated next, according to the calculated similarity and the second skip correspondence table of the piece of data.

14. The data retrieval device, according to claim 13, wherein

when a similarity range including the similarity between the piece of data and the retrieval data is present in the first skip correspondence table, the control unit determines data indicated by skip destination data information, which is recorded corresponding to the similarity range present in the first skip correspondence table, to be data in the retrieval target data series for which a similarity with the retrieval data is calculated next, and

when the similarity range including the similarity between the piece of data and the retrieval data is present in the second skip correspondence table, the control unit determines data indicated by skip destination data information, which is recorded corresponding to the similarity range present in the first skip correspondence table, to be data in the retrieval target data series for which a similarity with the retrieval data is calculated next.

15. The data retrieval device, according to claim 12, further comprising:

a first skip correspondence table generation unit that receives the retrieval target data series and generates the first skip correspondence table of each data in the retrieval target data series, and

a second skip correspondence table generation unit that receives the retrieval target data series and generates the second skip correspondence table of each data in the retrieval target data series.

16. The data retrieval device, according to claim 15, wherein

the first skip correspondence table generation unit calculates a similarity between subsequent data of generation target data of the first skip correspondence table and the generation target data, obtains, from the similarity and the threshold, a skip possible condition indicating a lower limit of a similarity between the generation target data and the retrieval data having no possibility that a similarity between the subsequent data and the retrieval data becomes smaller than or equal to the threshold, calculates a continuous skip possible condition indicating a maximum value of the lower limit of the similarity provided by the skip possible conditions of the self data and subsequent data preceding the self data, and according to the continuous skip possible condition calculated, generates a first skip correspondence table of the generation target data, and

the second skip correspondence table generation unit calculates a similarity between subsequent data of generation target data of the second skip correspondence table and the generation target data, obtains, from the similarity and the threshold, a skip possible condition indicating an upper limit of a similarity between the generation target data and the retrieval data having no possibility that a similarity between the subsequent data and the retrieval data becomes larger than the threshold, calculates a continuous skip possible condition indicating a minimum value of the upper limit of the similarity provided by the skip possible conditions of the self data and subsequent data preceding the self data, and according to the continuous skip possible condition calculated, generates a second skip correspondence table of the generation target data.

17. The data retrieval device, according to claim 16, wherein

the first skip correspondence table generation unit combines a plurality of continuous similarity ranges in the generated first skip correspondence table into one similarity range, and assigns most preceding data of a plurality of skip destination data corresponding to the similarity ranges before combination, as skip destination data corresponding to the combined similarity range, and

the second skip correspondence table generation unit combines a plurality of continuous similarity ranges in the generated second skip correspondence table into one similarity range, and assigns most preceding data of a plurality of skip destination data corresponding to the similarity ranges before combination, as skip destination data corresponding to the combined similarity range.

18. The data retrieval device, according to claim 15, wherein

the first skip correspondence table generation unit generates the first skip correspondence table only for partial data of the retrieval target data series, and

the second skip correspondence table generation unit generates the second skip correspondence table only for partial data of the retrieval target data series.

19. The data retrieval device, according to claim 1, wherein

the data is a feature vector, and

the similarity is a distance between feature vectors.

20. A data retrieval method for controlling a computer, the method comprising:

storing a first skip correspondence table that corresponds to each piece of data in a retrieval target data series, and, for each possible similarity range which is taken by a similarity between corresponding data and retrieval data, records skip destination data information for specifying the data which appears first after the corresponding data among pieces of data in which similarities with the retrieval data have the possibility to have a predetermined relationship in comparison with a predetermined threshold; and

in response to an input of retrieval data and when a similarity with the retrieval data is smaller than or equal to the threshold from among the retrieval target data series, calculates a similarity between a certain data from among the retrieval target data series and the retrieval data, selects data in the retrieval target data series which is calculated following the certain data, based on the similarity and the first skip correspondence table corresponding to the certain data, and outputs the selected data,

wherein the selecting includes, when a similarity range including the similarity between the piece of data and the retrieved data is present in the first skip correspondence table, the control unit determines data indicated by skip destination data information, which is recorded corresponding to the similarity range present in the first skip correspondence table, to be data in the retrieval target data series for which a similarity with the retrieval data is calculated next.

21. The data retrieving method, according to claim 20, wherein

the predetermined relationship is a relationship in which a similarity with the retrieval data is smaller than or equal to the threshold.

22. The data retrieving method, according to claim 21, wherein

the selecting includes, when a similarity with the retrieval data calculated for a piece of data in the retrieval target data series is not smaller than or equal to the threshold, determining data in the retrieval target data series for which a similarity with the retrieval data is calculated next, according to the calculated similarity and the first skip correspondence table of the piece of data.

23. The data retrieving method, according to claim 21, further comprising

receiving the retrieval target data series and generating the first skip correspondence table of each data in the retrieval target data series.

24. The data retrieving method, according to claim 23, wherein

the generating the first skip correspondence table includes calculating a similarity between subsequent data of generation target data of the first skip correspondence table and the generation target data, obtaining, from the similarity and the threshold, a skip possible condition indicating a lower limit of a similarity between the generation target data and the retrieval data having no possibility that a similarity between the subsequent data and the retrieval data becomes smaller than or equal to the threshold, calculating a continuous skip possible condition indicating a maximum value of the lower limit of the similarity provided by the skip possible conditions of the self data and subsequent data preceding the self data, and according to the continuous skip possible condition calculated, generating a first skip correspondence table of the generation target data.

25. The data retrieving method, according to claim 20, wherein

the predetermined relationship is a relationship in which a similarity with the retrieval data is larger than the threshold.

26. The data retrieving method, according to claim 25, wherein

the selecting includes, when a similarity with the retrieval data calculated for a piece of data in the retrieval target data series is smaller than or equal to the threshold, determining data in the retrieval target data series for which a similarity with the target data is calculated next, according to the calculated similarity and the first skip correspondence table of the piece of data.

27. The data retrieving method, according to claim 25, further comprising

receiving the retrieval target data series and generating the first skip correspondence table of each data in the retrieval target data series.

28. The data retrieving method, according to claim 27, wherein

the generating the first skip correspondence table includes calculating a similarity between subsequent data of generation target data of the first skip correspondence table and the generation target data, obtaining, from the similarity and the threshold, a skip possible condition indicating an upper limit of a similarity between the generation target data and the retrieval data having no possibility that a similarity between the subsequent data and the retrieval data becomes larger than the threshold, calculating a continuous skip possible condition indicating a minimum value of the upper limit of the similarity provided by the skip possible conditions of the self data and subsequent data preceding the self data, and according to the continuous skip possible condition calculated, generating a first skip correspondence table of the generation target data.

29. The data retrieving method, according to claim 24, wherein

the generating the first skip correspondence table includes combining a plurality of continuous similarity ranges in the generated first skip correspondence table into one similarity range, and assigning most preceding data of a plurality of skip destination data corresponding to the similarity ranges before combination, as skip destination data corresponding to the combined similarity range.

30. The data retrieving method, according to claim 20, wherein

in the generating the first skip correspondence table, the first skip correspondence table is generated only for partial data of the retrieval target data series.

31. The data retrieving method, according to claim 22, further comprising

the selecting includes, in addition to the first skip correspondence table, using a second skip correspondence table that corresponds to each piece of data in the retrieval target data series, and, for each possible similarity range which is taken by a similarity between corresponding data and retrieval data, records skip destination data information for specifying the data which appears first after the corresponding data among pieces of data in which similarities with the retrieval data have the possibility not to have the predetermined relationship with the threshold, selecting data in the retrieval target data series for which calculation of a similarity with the retrieval data is necessary.

32. The data retrieving method, according to claim 31, wherein

the selecting includes,

when a similarity with the retrieval data calculated for a piece of data in the retrieval target data series is not smaller than or equal to the threshold, determining data in the retrieval target data series for which a similarity with the retrieval data is calculated next, according to the calculated similarity and the first skip correspondence table of the piece of data, and

when a similarity with the retrieval data calculated for a piece of data in the retrieval target data series is smaller than or equal to the threshold, determining data in the retrieval target data series for which a similarity with the target data is calculated next, according to the calculated similarity and the second skip correspondence table of the piece of data.

33. The data retrieving method, according to claim 32, wherein

the selecting includes,

when a similarity range including the similarity between the piece of data and the retrieval data is present in the first skip correspondence table, determining data indicated by skip destination data information, which is recorded corresponding to the similarity range present in the first skip correspondence table, to be data in the retrieval target data series for which a similarity with the retrieval data is calculated next, and

when the similarity range including the similarity between the piece of data and the retrieval data is present in the second skip correspondence table, determining data indicated by skip destination data information, which is recorded corresponding to the similarity range present in the first skip correspondence table, to be data in the retrieval target data series for which a similarity with the retrieval data is calculated next.

34. The data retrieving method, according to claim 31, further comprising:

receiving the retrieval target data series and generating the first skip correspondence table of each data in the retrieval target data series, and

receiving the retrieval target data series and generating the second skip correspondence table of each data in the retrieval target data series.

35. The data retrieving method, according to claim 34, wherein

the generating the first skip correspondence table includes calculating a similarity between subsequent data of generation target data of the first skip correspondence table and the generation target data, obtaining, from the similarity and the threshold, a skip possible condition indicating a lower limit of a similarity between the generation target data and the retrieval data having no possibility that a similarity between the subsequent data and the retrieval data becomes smaller than or equal to the threshold, calculating a continuous skip possible condition indicating a maximum value of the lower limit of the similarity provided by the skip possible conditions of the self data and subsequent data preceding the self data, and according to the continuous skip possible condition calculated, generating a first skip correspondence table of the generation target data, and

the generating the second skip correspondence table includes calculating a similarity between subsequent data of generation target data of the second skip correspondence table and the generation target data, obtaining, from the similarity and the threshold, a skip possible condition indicating an upper limit of a similarity between the generation target data and the retrieval data having no possibility that a similarity between the subsequent data and the retrieval data becomes larger than the threshold, calculating a continuous skip possible condition indicating a minimum value of the upper limit of the similarity provided by the skip possible conditions of the self data and subsequent data preceding the self data, and according to the continuous skip possible condition calculated, generating a second skip correspondence table of the generation target data.

36. The data retrieving method, according to claim 35, wherein

the generating the first skip correspondence table includes combining a plurality of continuous similarity ranges in the generated first skip correspondence table into one similarity range, and assigning most preceding data of a plurality of skip destination data corresponding to the similarity ranges before combination, as skip destination data corresponding to the combined similarity range, and

the generating the second skip correspondence table includes combining a plurality of continuous similarity ranges in the generated second skip correspondence table into one similarity range, and assigning most preceding data of a plurality of skip destination data corresponding to the similarity ranges before combination, as skip destination data corresponding to the combined similarity range.

37. The data retrieving method, according to claim 34, wherein

in the generating the first skip correspondence table, the first skip correspondence table is generated only for partial data of the retrieval target data series, and

in the generating the second skip correspondence table, the second skip correspondence table is generated only for partial data of the retrieval target data series.

38. The data retrieving method, according to claim 20, wherein

the data is a feature vector, and

the similarity is a distance between feature vectors.

39. A non-transitory computer-readable medium having instructions to cause a computer to execute a method for controlling the computer, the method comprising:

storing a first skip correspondence table that corresponds to each piece of data in a retrieval target data series, and, for each possible similarity range which is taken by a similarity between corresponding data and retrieval data, records skip destination data information for specifying the data which appears first after the corresponding data among pieces of data in which similarities with the retrieval data have the possibility to have a predetermined relationship in comparison with a predetermined threshold; and

in response to an input of retrieval data and when a similarity with the retrieval data is smaller than or equal to the threshold from among the retrieval target data series, calculates a similarity between a certain data from among the retrieval target data series and the retrieval data, selects data in the retrieval target data series which is calculated following the certain data, based on the similarity and the first skip correspondence table corresponding to the certain data, and outputs the selected data,

wherein the selecting includes, when a similarity range including the similarity between the piece of data and the retrieved data is present in the first skip correspondence table, the control unit determines data indicated by skip destination data information, which is recorded corresponding to the similarity range present in the first skip correspondence table, to be data in the retrieval target data series for which a similarity with the retrieval data is calculated next.