Indexing and filtering using composite data stores

• US 8,392,426 B2
• Filed: 03/21/2011
• Issued: 03/05/2013
• Est. Priority Date: 08/30/2007
• Status: Active Grant

• Current Assignee: Perfect Search Corporation
• Original Assignee: Perfect Search Corporation
• Inventors: Millett, Ronald P.
• Primary Examiner(s): MENG, JAU SHYA
• Application Number:
  US13/052,399
• Publication Number:
  US 20110167072A1
• Time in Patent Office: 715 Days
• Field of Search: None
• US Class Current: 707/741
• CPC Class Codes: G06F 16/319 Inverted lists

Abstract

Data stores are combined into a composite data store. A method includes referencing a first index entry for a user specified first parameter pattern. The first index entry includes references to record addresses for records in the composite data store which include the first parameter pattern. A first beginning composite data store address of a first selected data store is referenced. A determination is made that the first beginning composite data store address is at or above an address at or above a predetermined threshold above the first record address. Based on determining that the first beginning composite data store address is at or above a predetermined threshold above the first record address, a speed-up data structure is used to eliminate one or more comparisons of record entries in the first index entry between the first record address and the first beginning composite data store address.

Claims

1. In a computing environment comprising a plurality of data stores, a method, performed by one or more processors, of finding records in one or more of the data stores based on user specified search patterns and based on selected data stores, the method comprising:

combining a plurality of data stores into a composite data store, by renumbering addresses in one of more of the data stores such that the composite data store stores the data stores sequentially, such that each data store in the composite data store is in a range comprising a beginning composite data store address and an ending composite data store address;

storing composite data store addresses corresponding to the renumbered beginning of each data store such that locations of each data store in the composite data store is identified by reference to the beginning composite data store address that corresponds to a beginning of a data store included in the composite data store;

indexing data items in the composite data store to identify occurrences of the data items in records of the composite data store;

referencing a first index entry for a user specified first data item, the first index entry including references to record addresses for records in the composite data store which include the first data item, further comprising referencing a first record address in the first index entry;

selecting a first data store from among the plurality of data stores in the composite data store to search for the user specified first data item;

referencing a first beginning composite data store address of the first selected data store wherein the first selected data store is selected from the plurality of data stores;

determining that the first beginning composite data store address is above a predetermined threshold above the first record address; and

based on determining that the first beginning composite data store address is above the predetermined threshold above the first record address, using a speed-up data structure to eliminate one or more comparisons of record entries in the first index entry between the first record address and the first beginning composite data store address.

2. The method of claim 1, wherein the composite data store is stored on a mobile device.

3. The method of claim 1, wherein the composite data store comprise one or more of an email data store, a contacts data store, a calendar data store or a tasks data store.

4. The method of claim 1, further comprising:

referencing the first index entry, including referencing a second record address after the first beginning composite data store address;

referencing a second index entry for a second user specified second data item, including referencing a third record address in the second index entry;

determining that the second record address and the third record address are the same address; and

based on determining that the second record address and the third record address are the same address, providing an indication that a hit has been found at the second record address.

5. The method of claim 1, further comprising:

referencing the first index entry, including referencing a second record address after the first beginning composite data store address;

referencing a first ending composite data store address of the first selected data store;

determining that the second record address exceeds the first ending composite data store address; and

in response to determining that the second record address exceeds the first ending composite data store address;

referencing a second beginning composite data store address of a second selected data store;

determining that the second beginning composite data store address is at an address that exceeds a predetermined threshold above the second record address; and

based on determining that the second beginning composite data store address is at an address that exceeds a predetermined threshold above the second record address, using a speed-up data structure to eliminate one or more comparisons of record entries in the first index entry between the second record address and the second beginning composite data store address.

6. The method of claim 1, wherein the speed-up data structure comprises an offset correlation table.

7. The method of claim 1, wherein the speed-up data structure comprises a level bit shifting data structure.

8. The method of claim 7, wherein the level bit shifting data structure uses a five bit shift to shift between levels.

9. The method of claim 1, further comprising:

referencing the first index entry, including referencing a second record address after the first beginning composite data store address;

referencing a first ending composite data store address of the first selected data store;

determining that the second record address is at or exceeds the first ending composite data store address; and

in response to determining that the second record address is at or exceeds the first ending composite data store address;

determining that the first selected data store is the last data store selected for searching; and

providing an indication that the first selected data store is the last data store selected for searching.

10. The method of claim 9, wherein providing an indication that the that first selected data store is the last data store selected for searching comprises returning search results from one or more selected data stores.

11. The method of claim 1, further comprising:

determining a selection of results to be displayed to a user;

performing index comparisons until the selection of results is obtained; and

suspending index comparisons until user input is received indicating that more results should be displayed.

12. In a computing environment comprising a plurality of data stores, a method, performed by one or more processors, of finding records in one or more of the data stores based on user specified search patterns and based on selected data stores, the method comprising:

combining a plurality of data stores into a composite data store, by renumbering addresses in one of more of the data stores such that the composite data store stores the data stores sequentially, such that each data store in the composite data store is in a range comprising a beginning composite data store address and an ending composite data store address;

storing composite data store addresses corresponding to the renumbered beginning of each data store such that locations of each data store in the composite data store is identified by reference to the beginning composite data store address that corresponds to a beginning of a data store included in the composite data store;

indexing data items in the composite data store to identify occurrences of the data items in records of the composite data store;

referencing a first index entry for a user specified first, the first index entry including references to record addresses for records in the composite data store which include the first data item, further comprising referencing a first record address in the first index entry;

referencing a second index entry for a user specified second data item, the second index entry including references to record addresses for records in the composite data store which include the second data item, further comprising referencing a second record address in the second index entry;

selecting a first data store from among the plurality of data stores in the composite data store to search for the user specified first data item;

referencing a first beginning composite data store address of the first selected data store, the first selected data store being a data store from among the plurality of data stores in the composite data store;

determining that the first beginning composite data store address is above a predetermined threshold above at least one of the first record address or the second record address; and

based on determining that the first beginning composite data store address is above the predetermined threshold above at least one of the first record address or the second record address, using a speed-up data structure to eliminate one or more comparisons of record entries in the first index entry between at least one of the first record address and the second record address and the first beginning composite data store address.

13. The method of claim 12, wherein determining that the first beginning composite data store address is at or above a predetermined threshold above at least one of the first record address or the second record address comprises:

assigning the first record address as a low address;

assigning the second record address as a high address;

determining that the first beginning composite data store address is greater than the second record address;

as a result of determining that the first beginning composite data store address is greater than the second record address, assigning the first beginning composite data store address as the high address; and

comparing the high address to the low address to determine if the high address is above the low address by at least the predetermined threshold.

14. The method of claim 12, wherein the speed-up data structure comprises an offset correlation table.

15. The method of claim 12, wherein the speed-up data structure comprises a level bit shifting data structure.

16. The method of claim 15, wherein the level bit shifting data structure uses a five bit shift to shift between levels.

17. The method of claim 12, wherein the composite data store is stored on a mobile device.

18. The method of claim 12, wherein the composite data store comprise one or more of an email data store, a contacts data store, a calendar data store or a tasks data store.

19. A computing system comprising:

one or more processors;

one or more physical storage media coupled to the one or more processors, wherein the one or more physical storage media comprise computer executable instruction that when executed by the one or more processors cause the one or more processors to perform the following;

combining a plurality of data stores into a composite data store, by renumbering addresses in one of more of the data stores such that the composite data store stores the data stores sequentially, such that each data store in the composite data store is in a range comprising a beginning composite data store address and an ending composite data store address;

storing composite data store addresses corresponding to the renumbered beginning of each data store such that locations of each data store in the composite data store is identified by reference to the beginning composite data store address that corresponds to a beginning of a data store included in the composite data store;

indexing data items in the composite data store to identify occurrences of the data items in records of the composite data store;

reference a first index entry for a user specified first data item, the first index entry including references to record addresses for records in the composite data store which include the first data item, further comprising referencing a first record address in the first index entry;

selecting a first data store from among the plurality of data stores in the composite data store to search for the user specified first data item;

reference a first beginning composite data store address of a first selected data store wherein the first selected data store is selected from the plurality of data stores;

determine that the first beginning composite data store address is at or above an address at or above a predetermined threshold above the first record address; and

based on determining that the first beginning composite data store address is at or above the predetermined threshold above the first record address, using a speed-up data structure to eliminate one or more comparisons of record entries in the first index entry between the first record address and the first beginning composite data store address.

20. The computing system of claim 19, wherein the speed-up data structure comprises a level bit shifting data structure and wherein the level bit shifting data structure uses a five bit shift to shift between levels.