DATA RETRIEVAL DEVICE

• US 20110099177A1
• Filed: 01/14/2010
• Published: 04/28/2011
• Est. Priority Date: 01/23/2009
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Iwamoto, Kota, Oami, Ryoma
• Granted Patent: US 8,244,739 B2
• Time in Patent Office: Days
• 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, comprising:

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 that, 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.

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

if 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 3, wherein

if 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.

5. 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.

6. The data retrieval device, according to claim 5, 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.

7. 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.

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

if 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.

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

if 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.

10. 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.

11. The data retrieval device, according to claim 10, 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.

12. The data retrieval device, according to claim 6, 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.

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

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

14. 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.

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

if 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

if 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.

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

if 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

if 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.

17. The data retrieval device, according to claim 14, 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.

18. The data retrieval device, according to claim 17, 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.

19. The data retrieval device, according to claim 18, 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.

20. The data retrieval device, according to claim 17, 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.

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

the data is a feature vector, and

the similarity is a distance between feature vectors.

22. A data retrieving method, comprising, using 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, 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,

selecting data in the retrieval target data series for which calculation of a similarity with the retrieval data is necessary.

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

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

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

the selecting includes, if 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.

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

the selecting includes, if 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.

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

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

27. The data retrieving method, according to claim 26, 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.

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

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

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

the selecting includes, if 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.

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

the selecting includes, if 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.

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

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

32. The data retrieving method, according to claim 31, 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.

33. The data retrieving method, according to claim 27, 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.

34. The data retrieving method, according to claim 25, 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.

35. The data retrieving method, according to claim 23, 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.

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

the selecting includes,

if 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

if 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.

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

the selecting includes,

if 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

if 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.

38. The data retrieving method, according to any of claims claim 35, 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.

39. The data retrieving method, according to claim 38, 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.

40. The data retrieving method, according to claim 39, 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.

41. The data retrieving method, according to claim 38, 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.

42. The data retrieving method, according to any of claim 22, wherein

the data is a feature vector, and

the similarity is a distance between feature vectors.

43. A program for causing a computer to perform, using 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, 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,

a process of selecting 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.