AUGMENTED LIST FOR SEARCHING LARGE INDEXES

• US 20100162175A1
• Filed: 12/22/2008
• Published: 06/24/2010
• Est. Priority Date: 12/22/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Paek, Tim, Lee, Bongshin, Thiesson, Bo
• Granted Patent: US 8,635,236 B2
• Time in Patent Office: Days
• US Class Current: 715/860
• CPC Class Codes: G06F 3/0482 Interaction with lists of selectable items, e.g. menus

Abstract

An augmented large index searching system and method for searching a database of items using a device having a limited input mechanism. Embodiments of the system and method present to a user in an augmented list view or a regular list view a list of items matching a sub-string search. The augmented list view contains a list of sub-group representations so that each sub-group is represented by an item in the sub-group most likely to be selected by the user. The user can select an item wanted by the user or refine the sub-string search by pinning a character to append the character to the sub-string and generated a revised sub-string. The above process is repeated using the revised sub-string. The list can be augmented by displaying visual features that indicate quantity and distinguish between items or characters by using coloring, highlighting, shading, size, and so forth.

Claims

1. A method for obtaining an item desired by a user from a database of items, comprising:

using a general-purpose computing device to perform the following;

inputting an original sub-string to be matched to items in the database of items;

obtaining a count of matches to the original sub-string of items in the database of items;

comparing the count of sub-string matches to a list threshold to determine whether to use an augmented list view or a regular list view to present at least some of the items in the sub-string matches;

determining whether the desired item is in the augmented list view or the regular list view; and

revising the original sub-string if the desired item is not in the augmented list view or the regular list view.

2. The method of claim 1, further comprising:

determining that the desired item is not in the augmented list view or the regular list view; and

revising the original sub-string by pinning a character in the augmented list view or the regular list view to generate a revised sub-string, where pinning the character involves appending the character to the original sub-string.

3. The method of claim 1, further comprising:

finding that the count of sub-string matches is greater than the list threshold; and

generating the augmented list view using a hash table and an information retrieval system such that the augmented list view contains sub-groups of items and each sub-group is represented by a single item in that sub-group.

4. The method of claim 3, further comprising:

selecting a first sub-group for processing such that each available character has an associated sub-group; and

determining whether a count of items for the first sub-group is in the hash table to retrieve the count of items for the first sub-group.

5. The method of claim 4, further comprising:

finding that the count of items for the first sub-group is not in the hash table;

looking up matches for an expanded sub-string, where the expanded sub-string is the original sub-string plus a character associated with the sub-group being processed; and

obtaining a count of matches of the expanded sub-string using the information retrieval system.

6. The method of claim 4, further comprising:

finding that the count of items for the first sub-group is in the hash table; and

retrieving the count of item for the first sub-group from the hash table.

7. The method of claim 4, further comprising:

determining an item in the sub-group being processed that is most likely to be selected by the user based on scoring criteria and using the information retrieval system; and

representing the sub-group being processed by the item in the sub-group being processed that is most likely to be selected by the user.

8. The method of claim 7, further comprising:

repeating the above process actions for each sub-group;

generating the augmented list view of items based on the original sub-string; and

representing each of the sub-groups by its respective item in the sub-group being processed that is most likely to be selected by the user, where the number of sub-groups is less than or equal to a number of available characters.

9. The method of claim 1, further comprising:

finding that the count of sub-string matches is less than or equal to the list threshold; and

generating the regular list view using an information retrieval system.

10. The method of claim 9, further comprising:

retrieving matches of the original sub-string using the information retrieval system; and

generating the regular list view of items based on the original sub-string, where a number of items in the regular list view is less than or equal to the list threshold.

11. The method of claim 7, further comprising displaying at least one of the following quantity representations adjacent a name of the item in the sub-group being processed that is most likely to be selected by the user:

(a) a number;

(b) a bar graph, where the quantity representation represents a count of items in a sub-group.

12. The method of claim 1, further comprising:

defining an item in focus as an item on which a cursor is over in the augmented list view or the regular list view; and

displaying at least one of the following item focus representations to differentiate the item in focus from other items on the augmented list view or the regular list view;

(a) a fish-eye lens such that the item in focus is larger than the other items on the augmented list view or the regular list view;

(b) a fish-eye lens such that those items on the augmented list view or the regular list view that surround the item in focus get progressively smaller;

(c) highlight the item in focus;

(d) color the item in focus such that the item in focus is a different color from the other items on the augmented list view or the regular list view.

13. The method of claim 12, further comprising:

defining a character in focus as a character in the item in focus on which the cursor is over; and

displaying at least one of the following character focus representations to differentiate the character in focus from other surrounding characters;

(a) highlight the character in focus using a first color;

(b) highlight subsequent characters in focus using colors that are different from the first color;

(c) align items on the augmented list view or the regular list view to the character in focus.

14. A process for searching a database of items for a specific item in the database of items, comprising:

obtaining matches of an original sub-string using a matching technique;

organizing the sub-string matches into sub-groups containing items from the database of items;

associating a single available character with the sub-group of items such that a number of sub-groups is less than or equal to a number of available characters;

for each of the sub-groups, select an item in the sub-group to represent that sub-group using the information retrieval system and based on scoring criteria;

generate an augmented list view of items containing sub-group representations of at most each of the sub-groups where the sub-group representation for each of the sub-groups is a name of the item in the sub-group selected to represent that sub-group;

determining whether the specific item is contained in the augmented list view; and

revising the original sub-string using a pinned character from the augmented list view to generate a revised sub-string that includes the pinned character.

15. The process of claim 14, further comprising:

obtaining a count of matches to the revised sub-string; and

determining whether to use the augmented list view or a regular list view by comparing the count of revised sub-string matches to a list threshold.

16. The process of claim 15, further comprising:

determining that the count of matches to the revised sub-string is greater than the list threshold;

selecting a sub-group for processing from the matches such that each available character has an associated sub-group;

determining whether a count of items in the sub-group be processed in contained in a hash table;

if the count of items is not contained in the hash table, then defining an expanded sub-string as the revised sub-string plus a character from the available characters for the sub-group being processed and looking up matches for the expanded sub-string and obtaining a count of the matches for the expanded sub-string using an information retrieval system; and

if the count of items is in the hash table, then retrieving a count of items for the sub-group being processed from the hash table.

17. The process of claim 16, further comprising using the information retrieval system to determine an item in the sub-group being processed to be used to represent the sub-group being processed based on scoring criteria.

18. The process of claim 17, wherein the scoring criteria further comprises:

(a) a general popularity of each item based on many users;

(b) a specific popularity of each item based on a personal preference of a specific user;

(c) a measure of popularity based on a number of hits each item receives;

(d) a measure of popularity based on a number of times an item was opened;

(e) how recently an item was used, such that an item used more recently than another item is more likely to be selected by the user;

or (f) recommendations of other users or professionals in the field to which the items are associated.

19. A method for navigating a database of items to find a specific item in the database of items that is desired by a user, comprising:

using a portable media player having a limited input mechanism to perform the following;

inputting an empty sub-string;

obtaining a count of matches for the empty sub-string from a hash table;

selecting a sub-group for processing from the matches for the empty sub-string, where there is a sub-group for each available English language character, and for each of the sub-groups performing the following actions;

determining whether a count of items for the sub-group being processed is in the hash table;

if the count of items for the sub-group being processed is not in the hash table, then looking up matches for an expanded sub-string and obtaining a count of the matches for the expanded sub-string using an information retrieval system, where the expanded sub-string is defined as the empty sub-string plus an additional character associated with the sub-group being processed;

if the count of items for the sub-group being processed is in the hash table, then retrieving the count of items for the sub-group being processed from the hash table;

selecting an item in the sub-group being processed to represent the sub-group by using the information retrieval system and based on scoring criteria;

generating an augmented list view of items based on the empty sub-string, where each of the sub-groups are represented in the augmented list view by the item selected to represent the sub-group, and where the number of sub-groups represented in the augmented list view is less than or equal to a number of available characters;

determining that the specific item in the database of items that is desired by the user is not shown in the augmented list view;

pinning a character shown in the augmented list view using the limited input mechanism to obtain a pinned character;

revising the empty sub-string based on pinned character to generate a revised sub-string, such that the revised sub-string includes the pinned character; and

repeating the above process actions by substituting the revised sub-string for the empty sub-string and determining whether a count of matches for the revised sub-string is greater than a list threshold.

20. The method of claim 19, further comprising:

if the count of matches for the revised sub-string is greater than the list threshold, then generate an augmented list view of items based on the revised sub-string using the hash table and the information retrieval system;

if the count of matches for the revised sub-string is less than or equal to the list threshold, then generate a regular list view based on the revised sub-string using the information retrieval system;

augmenting the augmented list view or the regular list view by adding the following augmentations;

(a) a quantity representation that represent a number of items in a particular sub-group in the augmented list view;

(b) an item focus representation that differentiates and distinguishes an item in focus from other items on the augmented list view or the regular list view;

(c) a character focus representation that differentiates a character in focus from other surrounding characters in the augmented list view or the regular list view.