Entity clustering via data services

• US 8,572,089 B2
• Filed: 12/15/2011
• Issued: 10/29/2013
• Est. Priority Date: 12/15/2011
• Status: Active Grant

• Current Assignee: LEAP Forward Gaming, Business Objects Incorporated (SAP SE)
• Original Assignee: Business Objects Incorporated (SAP SE)
• Inventors: Starks, Kimberly
• Primary Examiner(s): Richardson, James E
• Application Number:
  US13/327,587
• Publication Number:
  US 20130159305A1
• Time in Patent Office: 684 Days
• Field of Search: 707/738, 707/739
• US Class Current: 707/739
• CPC Class Codes: G06F 16/35 Clustering; Classification

Abstract

A method is provided for forming an entity cluster. In this method, a plurality of entities found in one or more data sources are identified. An entity may represent a word or a phrase found in the one or more data sources. The plurality of entities may then be organized into groups, where each group has a master entity and a set of subordinate entities. The groups are formed using a first comparison criteria. Then, using a second comparison criteria, a first group is associated with a second group. The second comparison criteria may compare the master entities associated with the first and second groups. Based on the association between the first group and the second group, the method can then determine that the first entity is related to the second entity.

Claims

1. A method comprising:

identifying, using one or more processors, a plurality of entities found in one or more data sources, each entity representing a word or a phrase found in the one or more data sources;

sorting the plurality of entities based on a sorting length, the sorting length being a value based on a function of an entity length of each of the entities, the sorting comprising;

sorting a first portion in non-descending order, the first portion including the entities that meet a length condition based on the sorting length, the length condition being based on one or more lengths of one or more of the extracted entities; and

sorting a second portion in non-descending order, the second portion including the entities that do not meet the length condition based on the sorting length, the second portion being located after the first portion;

using a first comparison criteria, organizing the sorted plurality of entities into groups by selecting a first entity in the sorted plurality of entities and comparing the selected entity to one or more remaining entities of the sorted plurality of entities, each group identifying one of the entities as a master entity and a set of entities as subordinate entities;

using a second comparison criteria, associating a first group from the groups with a second group from the groups, the second comparison criteria comparing only a first master entity associated with the first group with a second master entity associated with the second group; and

determining that a first entity is related to a second entity based on the association between the first group and the second group.

2. The method of claim 1, wherein the one or more data sources includes at least one of a document, a corpus, a file system, or a database.

3. The method of claim 1, wherein each entity is a row in a table, each row including a number of columns that identify at least one of a location, a group identifier, and an entity type.

4. The method of claim 1, wherein the first comparison criteria determines whether each master entity and the associated subordinate entities share a substring or similarity of characters.

5. The method of claim 1, wherein a particular master entity of a particular group is an entity from the particular group that is first selected from the plurality of entities to form the particular group, and subordinate entities of the particular group are entities from the plurality of entities that, when compared to the particular master entity, meet a similarity condition defined by the first comparison criteria.

6. The method of claim 1, wherein the organizing the plurality of entities into the groups further comprises breaking the entities into sub-groups based on an entity type.

7. The method of claim 1, wherein the first comparison criteria forms groups of entities within a sentence.

8. The method of claim 1, wherein the second comparison criteria forms groups of entities within a paragraph.

9. The method of claim 1, further comprising breaking one or more entities from the first group into a subgroup based on the one or more entities having a determinable morpheme.

10. The method of claim 1, wherein each entity is associated with feedback submitted by a customer.

11. The method of claim 1, wherein each entity is associated with a requirement submitted by a customer.

12. The method of claim 1, wherein the organizing of the groups includes a number of matching operations, the number of matching operations including:

selecting an entity from the plurality of entities that is not associated with any group;

using the first comparison criteria, determining a set of entities from the plurality of entities that meet a similarity threshold, the set of entities not being associated with any group; and

associating the selected entity and the set of entities with a group.

13. The method of claim 10, wherein the number of matching operations are repeated to form other groups until all the entities are associated with a group.

14. A computer system comprising:

at least one processor;

an entity extraction module implemented by the at least one processor and configured to identify a plurality of entities found in one or more data sources, each entity representing a word or a phrase found in the one or more data sources;

a sorting module implemented by the at least one processor and configured to sort the plurality of entities based on a sorting length, the sorting length being a value based on a function of an entity length of each of the entities, the sorting comprising;

sorting a first portion in non-descending order, the first portion including the entities that meet a length condition based on the sorting length, the length condition being based on one or more lengths of one or more of the extracted entities; and

sorting a second portion in non-descending order, the second portion including the entities that do not meet the length condition based on the sorting length, the second portion being located after the first portion;

an entity matching module implemented by the at least one processor and configured to;

organize the sorted plurality of entities into groups using a first comparison criteria by selecting a first entity in the sorted plurality of entities and comparing the selected entity to one or more remaining entities of the sorted plurality of entities, each group identifying one of the entities as a master entity and a set of entities as subordinate entities;

associate a first group from the groups with a second group from the groups using a second comparison criteria that compares only a first master entity associated with the first group with a second master entity associated with the second group; and

a group association module implemented by the at least one processor and configured to determine that a first entity is related to a second entity based on the association between the first group and the second group.

15. The computer system of claim 14, wherein the one or more data sources includes at least one of a document, a corpus, a file system, or a database.

16. The computer system of claim 14, wherein each entity is a row in a table, each row including a number of columns that identify at least one of a location, a group identifier, and an entity type.

17. The computer system of claim 14, wherein the first comparison criteria determines whether each master entity and the associated subordinate entities share a substring.

18. The computer system of claim 14, wherein a particular master entity of a particular group is an entity from the particular group that is first selected from the plurality of entities to form the particular group, and subordinate entities of the particular group are entities from the plurality of entities that, when compared to the particular master entity, meet a similarity condition defined by the first comparison criteria.

19. The computer system of claim 14, wherein the entity matching module is further configured to break the entities into sub-groups based on an entity type.

20. The computer system of claim 14, wherein the first comparison criteria forms groups of entities within a sentence.

21. The computer system of claim 14, the second comparison criteria forms groups of entities within a paragraph.

22. The computer system of claim 14, wherein entities from the first group are filtered into a subgroup based on the one or more entities having a determinable affix.

23. The computer system of claim 14, wherein each entity is associated with feedback submitted by a customer.

24. The computer system of claim 14, wherein each entity is associated with a requirement submitted by a customer.

25. The computer system of claim 14, wherein the entity matching module is further configured to perform a number of matching operations, the number of matching operations involves the matching module being configured to:

select an entity from the plurality of entities that is not associated with any group;

using the first comparison criteria, determine a set of entities from the plurality of entities that meet a similarity threshold, the set of entities not being associated with any group; and

associate the selected entity and the set of entities with a group.

26. The computer system of claim 25, wherein the entity matching module is further configured to perform the number of matching operations to form other groups until all the entities are associated with a group.

27. A non-transitory computer-readable storage medium storing instructions for causing a processor to implement operations, the operations comprising:

identifying a plurality of entities found in one or more data sources, each entity representing a word or a phrase found in the one or more data sources;

sorting the plurality of entities based on a sorting length, the sorting length being a value based on a function of an entity length of each of the entities, the sorting comprising;

sorting a first portion in non-descending order, the first portion including the entities that meet a length condition based on the sorting length, the length condition being based on one or more lengths of one or more of the extracted entities; and

sorting a second portion in non-descending order, the second portion including the entities that do not meet the length condition based on the sorting length, the second portion being located after the first portion;

using a first comparison criteria, organizing the sorted plurality of entities into groups by selecting a first entity in the sorted plurality of entities and comparing the selected entity to one or more remaining entities of the sorted plurality of entities, each group identifying one of the entities as a master entity and a set of entities as subordinate entities;

using a second comparison criteria, associating a first group from the groups with a second group from the groups, the second comparison criteria comparing only a first master entity associated with the first group with a second master entity associated with the second group; and

determining that a first entity is related to a second entity based on the association between the first group and the second group.