Keyword analysis and arrangement

• US 7,765,208 B2
• Filed: 06/06/2005
• Issued: 07/27/2010
• Est. Priority Date: 06/06/2005
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Giacobbe, Gail B., Wall, Jeffrey J, Starbuck, Bryan T
• Primary Examiner(s): Jalil; Neveen Abel
• Assistant Examiner(s): Chbouki; Tarek
• Application Number:
  US11/146,887
• Publication Number:
  US 20060277208A1
• Time in Patent Office: 1,877 Days
• Field of Search: 707 1- 10, 707/100, 707/101, 707/102, 709/218, 709/206
• US Class Current: 707/736
• CPC Class Codes: G06Q 10/107 Computer-aided management of electronic mailing [e-mailing]

Abstract

Keyword analysis and arrangement are described. In an implementation, a method includes processing a plurality of items to extract a plurality of keywords contained in the items. One or more of the keywords is output for display as arranged in one or more hierarchies such that at least one of the keywords is selectable to navigate to items that are configured as emails and relate to that keyword.

Claims

1. A method implemented at a computing device having a processor, the method comprising:

processing, by the processor of the computing device, a plurality of items to extract a plurality of keywords contained in the items, the processing including forming two or more of the plurality of keywords into keyword phrases, wherein the processing is performed at least in part based on a relative closeness of the plurality of keywords, one to another, the relative closeness partially defining a relevancy of one of said items to another of said items;

forming a plurality of groupings of the keywords based on the relative closeness;

combining the plurality of groupings to build balanced keyword hierarchies that comprise a predetermined number of balanced top-level islands, the combining comprising;

organizing the plurality of groupings to create a plurality of small islands based on the relative closeness of the plurality of groupings;

reducing number of the plurality of small islands to form the predetermined number of top-level hierarchical islands, the reducing comprising;

combining the plurality of small islands to multiple high-level islands each having a hierarchy of a subset of the plurality of small islands, the multiple high-level islands having at least a first high-level island and a second high-level island;

determining that a set of small islands to be combined to the first high-level island will cause the first high-level island to include an unbalanced number of small islands;

maintaining the first high-level island balanced by moving the set of small islands to be combined to the second high-level island, wherein the second high-level island has less closeness value than the first high-level island, and

repeating the combining, determining and maintaining until the predetermined number of top-level hierarchical islands are formed;

outputting one or more of the predetermined number of top-level hierarchical islands for display on a display device as arranged in one or more hierarchies such that at least one of the plurality of keywords is selectable on the display device, wherein the one or more of the predetermined number of top-level hierarchical islands include the keyword phrases;

receiving, from a user input via an input device, a selection of one of the plurality of keyword phrases; and

navigating, at the computing device based on the selection, to a subset of the plurality of items that;

are configured as emails; and

include or relate to the one of the plurality of keywords.

2. A method as described in claim 1, wherein:

the processing includes forming two or more of the plurality of keywords into a keyword phrase; and

the outputting includes outputting the keyword phrase and at least one of the two or more of the plurality of keywords for display.

3. A method as described in claim 1, wherein the processing includes:

forming a single dictionary of keywords for the plurality of items; and

forming a dictionary of keywords for each said item.

4. A method as described in claim 1, wherein the plurality of items include instant messages, contacts, appointments and documents which are accessible on the client device.

5. A method as described in claim 1, wherein:

a plurality of the displayed keywords is concurrently selectable;

the receiving comprises receiving, from the user, concurrent selections of two or more of the plurality of the displayed keywords; and

the navigating comprises navigating to a subset of the plurality of items that include or relate to the two or more of the plurality of the displayed keywords that are selected by the user.

6. A method as described in claim 1, wherein the keywords may toggle between people keywords, non-people keywords, and both people keywords and non-people key words.

7. A method as described in claim 1, wherein a preview pane displays results of navigating a hierarchy of groupings concurrent with the navigating.

8. A method as described in claim 1 further comprising receiving a plurality of selections of keywords while a button is pressed, and navigating to emails having the plurality of selected keywords.

19. One or more computer readable storage media having stored thereon a plurality of executable instructions that, when executed by a computing device having one or more processors, configure the one or more processors to implement the method as recited in claim 1.

9. A method implemented at a client device having a processor, the method comprising:

extracting, at the computing device, a plurality of keywords from a plurality of items on the client device, the extracting comprising;

determining a number of instances of each word contained in the plurality of items,

determining a total number of words contained in the plurality of items,

determining, for each of the plurality of items, a number of instances of each word contained in that item,

determining, for each of the plurality of items, a total number of words contained in that item, and

determining the plurality of keywords by selecting a number of the words each having a ratio that exceeds a threshold, wherein the ratio is calculated as

ratio=X/Y/a/b

where;

X is the number of instances of the word contained in a particular item;

Y is the total number of words contained in the particular item;

a is the total number of instances of the word contained in the plurality of items; and

b is the total number of words found in the plurality of items;

automatically creating, at the client device, top-level hierarchies from the plurality of keywords, each of the top-level hierarchies having a plurality of keywords positioned at different hierarchical levels, the creating comprising;

organizing the plurality of keywords to create a plurality of small hierarchies based on the relative closeness of the plurality of keywords;

reducing number of the plurality of small hierarchies to form a predetermined number of top-level hierarchies, the reducing comprising;

combining the plurality of small hierarchies to multiple high-level hierarchies each having a subset of the plurality of small hierarchies, the multiple high-level hierarchies having at least a first high-level hierarchy and a second high-level hierarchy;

determining that a set of small hierarchies to be combined to the first high-level hierarchy will cause the first high-level hierarchy to include an unbalanced number of small hierarchies;

maintaining the first high-level hierarchy balanced by moving the set of small hierarchies to be combined to the second high-level hierarchy, wherein the second high-level hierarchy has less closeness value than the first high-level hierarchy, and wherein the closeness value defines a relevancy of one of the plurality of small hierarchies to another one of the plurality of small hierarchies; and

repeating the combining, determining and maintaining until the predetermined number of top-level hierarchies are formed; and

categorizing a collection of said items on the client device based on words contained in the respective items according to the created hierarchies for display at the client device.

10. A method as described in claim 9, wherein the plurality of items include email, instant messages, contacts, appointments, photos, music, videos and documents which are accessible on the client device.

11. A method as described in claim 10, wherein metadata is associated with one or more said items.

12. A method as described in claim 9, further comprising outputting one or more said keywords for display as arranged in the created hierarchies such that each said keyword is selectable to navigate to messages having that keyword.

13. A method as described in claim 12, wherein a plurality of the displayed keywords are concurrently selectable to navigate to messages having one or more of the selected keywords.

14. A method as described in claim 9, wherein:

the collection of said items are contacts;

at least one said keyword is generated to describe the collection of said items; and

the at least one said keyword is generated based on analysis of the collection of said items.

20. One or more computer readable storage media having stored thereon a plurality of executable instructions that, when executed by a computing device having one or more processors, configure the one or more processors to implement the method as recited in claim 9.

15. A method of producing a keyword hierarchy, the method being implemented at a computing device and comprising:

mapping, at the computing device, closeness of a plurality of keywords extracted from a plurality of items, one to another, the closeness partially defining a relevancy of one of the plurality of keywords to another of the plurality of keywords and the closeness being generated by;

for each one of the plurality of keywords;

creating a hash table comprising information that includes;

a number of the plurality of items having the one of the plurality of keywords as a root keyword;

a number of a sum of ranks of the plurality of items that have the root keyword;

a first structure pointing to the plurality of keywords that are likely included in the plurality of items that have the root keyword; and

a second structure storing closeness value for each of the plurality of keywords in the first structure;

assigning an inertia for each one of the plurality of keywords in the first structure;

walking each one of the plurality of keywords in the first structure and adjusting its inertia based at least in part on likelihood of the plurality of items having the each one of the plurality of keywords as a keyword;

calculating one or more steps that the each one of the plurality of keywords is away from the root keyword in distance and adjusting the inertia of the each one of the plurality of keywords based at least in part on the one or more steps;

taking the each one of the plurality of keywords that are two or three steps away from the root keyword; and

adding the current inertia of the each one of the plurality of keywords to the closeness value stored in the second structure each time the each one of the plurality of keywords in the first structure points back to the root keyword;

forming, at the computing device, a plurality of groupings of the keywords based on the mapped closeness, wherein the plurality of groupings include two or more of the plurality of keywords into keyword phrases;

combining the plurality of groupings based at least in part on closeness of the plurality of groupings until a predetermined number of groupings remain; and

outputting said keyword phrases corresponding to the plurality of groupings for display at the computing device such that each of the keyword phrases, when output, is configured to be selectable to navigate to one or more corresponding said items that have the keyword phrase.

16. A method as described in claim 15, wherein the predetermined number of groupings is defined as a range.

17. A method as described in claim 15, wherein the combining is performed such that the number of keywords contained in each said grouping is approximately balanced, one to another.

18. A method as described in claim 15, wherein at least two said keywords form a keyword phrase.

21. One or more computer readable storage media having stored thereon a plurality of executable instructions that, when executed by a computing device having one or more processors, configure the one or more processors to implement the method as recited in claim 15.