Method and apparatus for fast searching of hand-held contacts lists

• US 6,557,004 B1
• Filed: 05/02/2000
• Issued: 04/29/2003
• Est. Priority Date: 01/06/2000
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Shields, Kevin T., Ben-Shachar, Ido, Chew, Chee H.
• Primary Examiner(s): Breene, John
• Assistant Examiner(s): LEWIS, CHERYL RENEA
• Application Number:
  US09/562,689
• Time in Patent Office: 1,092 Days
• Field of Search: 707/3, 707/7, 707/102
• US Class Current: 707/706
• CPC Class Codes: G06F 16/3322 using system suggestions G06F16/3325 takes precedence
• CPC Class Codes: G06F 16/9577 Optimising the visualization of content, e.g. distillation of HTML documents
• CPC Class Codes: Y10S 707/922 Communications
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

The present invention provides a quick searching method for filtering a contact list in a hand-held device. Under the method, upon receiving a search string from a user, a database object is opened that is sorted alphabetically on the first name of each contact. A search is then performed on the sorted list to retrieve the ID'"'"'s of the first record in the sorted list and the last record in the sorted list that have a first name that matches the search string. A second database object is then opened that is sorted alphabetically on a “filed as” field. The “filed as” list is then searched to find the first and last records that match the search string. The first name search results and the “filed as” search results are then combined. The records in the combination are then displayed to the user.

Claims

1. A method of generating a user interface on a hand-held device, the method comprising:

receiving a search string from the user;

generating a first database object from a database containing contacts records, each record comprising a first field and a second field, the first database object being sorted on the first field;

searching for the search string in the first database object and retrieving search-based record ID'"'"'s for records with first field entries that begin with the search string;

generating a second database object that is sorted on the second field;

searching for the search string in the second database object and retrieving search-based record indices for records with second field entries that begin with the search string;

combining the search-based record ID'"'"'s with the search-based record indices to produce a full list of indices; and

displaying at least one field of at least one record identified by the full list of indices.

2. The method of claim 1 wherein generating a first database object comprises opening a b-tree.

3. The method of claim 2 wherein searching for the search string in the first database object comprises performing an n-ary search using the b-tree structure of the first database object.

4. The method of claim 1 wherein searching for the search string in the first database object comprises performing a binary search.

5. The method of claim 1 wherein generating a second database object comprises opening a b-tree.

6. The method of claim 5 wherein searching for the search string in the second database object comprises performing an n-ary search using the b-tree structure of the second database object.

7. The method of claim 1 wherein searching for the search string in the second database object comprises performing a binary search.

8. The method of claim 1 wherein combining the search-based record ID'"'"'s with the search-based record indices comprises converting the search-based record ID'"'"'s into conversion record indices by searching for the search-based record ID'"'"'s in the second database object and retrieving conversion record indices for records with record ID entries that match the search-based record ID'"'"'s.

9. The method of claim 8 wherein combining the search-based record ID'"'"'s with the search-based record indices further comprises combining the conversion record indices with the search-based record indices through steps comprising:

sorting the conversion record indices;

identifying a starting search-based record index, the starting search-based record index being the lowest search-based record index;

identifying an ending search-based record index, the ending search-based record index being the highest search-based record index;

inserting conversion record indices that are less than the starting search-based record index into a full index list;

inserting the search-based record indices into the full index list; and

inserting conversion record indices that are greater than the ending search-based record index into the full index list.

10. The method of claim 9 wherein combining the conversion record indices with the search-based record indices further comprises converting the full index list into a full ID list by converting the indices in the full index list into record ID'"'"'s using the second database object.

11. The method of claim 10 wherein displaying at least one field of at least one record identified by the full list of indices comprises displaying at least one field of at least one record identified by a record ID in the full ID list.

12. The method of claim 1 wherein the first field is a first name field containing first names and the second field is a “

filed as”

field containing at least one of a first name, last name, or company name.

13. A storage medium for a hand-held electronic device, the storage medium having instructions for performing steps comprising:

generating contact records in a contacts database, each contact record containing a filed as field and a first name field;

receiving a search string;

searching the first name field for the search string in fewer than all of the records of the contacts database to produce a first name search result;

searching the filed as field for the search string in fewer than all of the records of the contacts database to produce a filed as search result;

combining the first name search result and the filed as search result to produce a full search result, the full search result comprising a reference to all records in the contacts database that have entries in either the first name field or the filed as field that begin with the search string; and

displaying at least one field of at least one record identified in the full search result.

14. The storage medium of claim 13 wherein searching the first name field comprises generating a first data structure sorted on the first name field and searching for the search string in the first data structure.

15. The storage medium of claim 14 wherein the first data structure is a b-tree.

16. The storage medium of claim 15 wherein searching the first data structure comprises performing an n-ary search of the b-tree.

17. The storage medium of claim 14 wherein searching the first data structure comprises performing a binary search.

18. The storage medium of claim 14 wherein searching the first data structure comprises:

searching for a first record in the first data structure that has a first name entry that begins with the search string;

searching for the last record in the first data structure that has a first name entry that begins with the search string; and

producing the first name search result from the records between the first record found by searching to the last record found by searching.

19. The storage medium of claim 18 wherein searching for the last record in the first data structure comprises appending a string of “

z”

characters to the end of the search string to produce a modified search string and searching for the modified search string in the first data structure.

20. The storage medium of claim 14 wherein searching the filed as field comprises generating a second data structure sorted on the filed as field and searching for the search string in the second data structure.

21. The storage medium of claim 20 wherein the second data structure is a b-tree.

22. The storage medium of claim 21 wherein searching the second data structure comprises performing an n-ary search of the b-tree.

23. The storage medium of claim 20 wherein searching the second data structure comprises performing a binary search.

24. The storage medium of claim 20 wherein the first name search result is a list of record ID'"'"'s and the filed as search result is a list of indices designating record positions in the second data structure and wherein combining the first name search result and the filed as search result comprises:

converting the record ID'"'"'s in the first name search result into indices designating the position of records in the second data structure; and

combining the indices from the first name search result with the indices of the filed as search result.

25. The storage medium of claim 24 wherein combining the indices from the first name search result with the indices from the filed as search result comprises:

sorting the indices of the first name result to form a sorted first name index list;

inserting all indices of the sorted first name index list that are less than the lowest index of the filed as search result into a combined index array;

inserting all of the indices of the filed as search result into the combined index array; and

inserting all indices of the sorted first name index list that are greater than the highest index of the filed as search result into the combined index array.

26. The storage medium of claim 25 wherein combining the indices from the first name search result with the indices of the filed as search result further comprises converting the indices of the combined index array into record ID'"'"'s to produce the full search result.