Filtering data objects

• US 10,394,907 B2
• Filed: 01/08/2016
• Issued: 08/27/2019
• Est. Priority Date: 01/09/2015
• Status: Active Grant

• Current Assignee: Alibaba Group Holding Ltd.
• Original Assignee: Alibaba Group Holding Ltd.
• Inventors: Huang, Yicong, Li, Junliang, Fu, Dengbo, Qiang, Qi, Wang, Chao, Gan, Yunfeng
• Primary Examiner(s): Morrison, Jay A
• Assistant Examiner(s): Caiado, Antonio J
• Application Number:
  US14/991,797
• Publication Number:
  US 20160203228A1
• Time in Patent Office: 1,327 Days
• CPC Class Codes: G06F 16/1748 De-duplication implemented within the file system, e.g. based on file segments de-duplication techniques in storage systems for the management of data blocks G06F3/0641
• CPC Class Codes: G06F 16/289 Object oriented databases
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 16/954 Navigation, e.g. using categorised browsing
• CPC Class Codes: G06F 7/24 Sorting, i.e. extracting data from one or more carriers, rearranging the data in numerical or other ordered sequence, and rerecording the sorted data on the original carrier or on a different carrier or set of carriers sorting methods in generalG06F7/36 takes precedence

Abstract

A method that includes establishing a layered attribute description network according to description values of the filtering requirements; extracting description values that are in the attribute description network; establishing a mapping relationship between the filtering requirements and the attribute description network, generating a path dependency graph; performing traversal comparison between the description values included in the description information of the data object to be filtered and description values in the path dependency graph; if all description values of one description path are included in the description information of the data object to be filtered, recording the description path as a matching path of the data object to be filtered; and determining a filtering requirement that the data object to be filtered meets. The techniques combine public description values and public description sub-paths based on a path dependency graph, reduce determinations in the filtering process and reduce the time of computation.

Claims

1. A method comprising:

reading filtering requirements;

acquiring description information included in each filtering requirement;

performing syntax analysis of the acquired description information to check whether the acquired description information is valid;

transforming all or-operations included in the acquired description information into one or more logical conjunction operations;

listing description values of the filtering requirements to establish an attribute description network, the attribute description network being a layered network, a respective layer corresponding to a respective attribute field, the respective attribute field having at least one description value, layers of the attribute description network having a hierarchical relationship from high to low level;

reading description information of a data object to be filtered;

extracting, from the description information of the data object, description values including at least one description value that is in the attribute description network;

reducing data computational amount by;

establishing a mapping relationship between the filtering requirements and the attribute description network;

generating a path dependency graph according to the mapping relationship;

performing a traversal comparison between the description values included in the description information of the data object and description values in the path dependency graph, the traversal comparison including a depth-first traversal; and

when the description information of the data object to be filtered does not include a description value, skipping traversal of description paths in the path dependency graph that pass downward through the description value.

2. The method of claim 1, further comprising:

during a process of performing the traversal comparison, recording a description path as a matching path of the data object in response to determining that description values of the description path are included in the description information of the data object.

3. The method of claim 2, further comprising determining, according to the matching path of the data object, a filtering requirement that the data object meets.

4. The method of claim 1, wherein the listing description values of the filtering requirements to establish the attribute description network includes:

classifying the acquired description information according to attributes, a corresponding attribute field being set for each attribute, at least one piece of acquired description information belonging to each attribute being normalized and respectively used as at least one description value under a respective attribute field corresponding to a respective attribute; and

hierarchically arranging attribute fields according to the hierarchical relationship to form the attribute description network, a respective layer corresponding to the respective attribute field.

5. The method of claim 4, wherein the hierarchically arranging the attribute fields according to the hierarchical relationship includes:

acquiring a number of description values under each of the attribute fields; and

hierarchically arranging, in descending order of the numbers of description values under the attribute fields, the attribute fields in sequence according to the hierarchical relationship.

6. The method of claim 4, wherein the hierarchically arranging the attribute fields according to the hierarchical relationship includes:

acquiring, according to nature of the attribute fields, attribute fields in which a single description value is to be selected; and

placing, on top of other attribute fields in the hierarchical relationship,

the attribute fields in which the single description value is to be selected,

wherein an attribute field in which a single description value is to be selected refers to that, according to nature of the attribute field, description values included in the attribute field are mutually exclusive.

7. The method of claim 1, wherein in the attribute description network, different description values of a same layer are arranged in sequence according to a predetermined sorting criterion.

8. The method of claim 1, wherein the establishing the mapping relationship between the filtering requirements and the attribute description network to generate the path dependency graph according to the mapping relationship includes:

converting each filtering requirement into a description path expression form;

respectively generating at least one description path of each description path expression;

acquiring non-duplicative description paths of the filtering requirements to form a description path set; and

mapping description paths in the description path set to the attribute description network to form the path dependency graph.

9. The method of claim 8, wherein the description path includes at least one description value.

10. The method of claim 8, wherein the description path includes a plurality of description values that that have conjunction relationships,

different description values of a respective description path being located at different layers in the attribute description network,

different description values being arranged in descending order of levels of the different layers at which the description values are located.

11. The method of claim 8, wherein the establishing the mapping relationship between the filtering requirements and the attribute description network to generate the path dependency graph according to the mapping relationship includes:

sorting the description paths based on a sorting rule that a layer at a higher level has a higher priority and a description value appearing first in a same layer has a higher priority;

mapping the description paths to the attribute description network in sequence according to a result of the sorting; and

combining parts that have completely identical high-layer description values in the description paths to generate the path dependency graph.

12. The method of claim 11, wherein the high-layer description values in the path dependency graph are completely identical includes all layers having identical description values starting downward from the highest-layer description values included in the description paths.

13. The method of claim 1, further comprising:

during a process of performing the traversal comparison, recording the description path as a matching path of the data object in response to determining that all description values of one description path are included in the description information of the data object; and

determining, according to the matching path of the data object, a filtering requirement that the data object meets, the determining includes;

determining, according to a description path expression form of a respective filtering requirement, a description path included in the respective filtering requirement; and

determining that the data object meets the filtering requirement, in response to determining that the description path included in the respective filtering requirement is included in the matching path of the data object.

14. The method of claim 13, wherein the determining, according to the matching path of the data object, the filtering requirement that the data object meets further includes:

determining all filtering requirements that the data object meets.

15. The method of claim 14, further comprising classifying the data object into different categories according to the filtering requirements that the data object meets.

16. An apparatus comprising:

a filtering requirement reading unit that reads filtering requirements;

an attribute description network establishment unit that lists description values of the filtering requirements to establish an attribute description network, the attribute description network being a layered network, a respective layer corresponding to a respective attribute field, the respective attribute field having at least one description value, layers of the attribute description network having a hierarchical relationship from high to low level, the attribute description network establishment unit including a description information acquiring sub-unit that acquires description information included in each filtering requirement, performs syntax analysis of the acquired description information to check whether the acquired description information is valid, transforms all or-operations included in the acquired description information into one or more logical conjunction operations;

a data-object-to-be-filtered reading unit that reads description information of a data object and extracts, from the description information of the data object, description values including at least one description value that is in the attribute description network;

a path dependency graph generating unit that reduces data computational amount by establishing a mapping relationship between the filtering requirements and the attribute description network, and generating a path dependency graph according to the mapping relationship; and

a traversal comparison unit that performs a traversal comparison including a depth-first traversal between the description values of the data object and description values in the path dependency graph, during a process of performing the traversal comparison, records a description path as a matching path of the data object in response to determining that description values of the description path are included in the description information of the data object, and when the description information of the data object to be filtered does not include a description value, skipping traversal of description paths in the path dependency graph that pass downward through the description value.

17. The apparatus of claim 16, further comprising:

a filtering requirement determining unit that determines, according to the matching path of the data object, a filtering requirement that the data object meets.

18. One or more memories stored thereon computer-executable instructions, executable by one or more processors, to cause the one or more processors to perform acts comprising:

reading filtering requirements;

acquiring description information included in each filtering requirement;

performing syntax analysis of the acquired description information to check whether the acquired description information is valid;

transforming all or-operations included in the acquired description information into one or more logical conjunction operations;

listing description values of the filtering requirements to establish an attribute description network,

the attribute description network being a layered network, a respective layer corresponding to a respective attribute field,

the respective attribute field having at least one description value,

layers of the attribute description network having a hierarchical relationship from high to low level;

reading description information of a data object to be filtered;

extracting, from the description information of the data object, description values including at least one description value that is in the attribute description network;

establishing a mapping relationship between the filtering requirements and the attribute description network to generate a path dependency graph according to the mapping relationship;

performing a traversal comparison between the description values of the data object and description values in the path dependency graph, the traversal comparison including a depth-first traversal; and

when the description information of the data object to be filtered does not include a description value, skipping traversal of description paths in the path dependency graph that pass downward through the description value.

19. The one or more memories of claim 18, wherein the acts further comprise:

during a process of performing the traversal comparison, recording a description path as a matching path of the data object in response to determining that description values of the description path are included in the description information of the data object; and

determining, according to the matching path of the data object, a filtering requirement that the data object meets.

20. The one or more memories of claim 18, wherein the listing description values of the filtering requirements to establish the attribute description network includes:

classifying the acquired description information according to attributes, a corresponding attribute field being set for each attribute, at least one piece of acquired description information belonging to each attribute being normalized and respectively used as at least one description value under a respective attribute field corresponding to a respective attribute; and

hierarchically arranging attribute fields according to the hierarchical relationship to form the attribute description network, a respective layer corresponding to the respective attribute field.