Systems and methods for high-speed searching and filtering of large datasets

• US 9,697,250 B1
• Filed: 04/04/2015
• Issued: 07/04/2017
• Est. Priority Date: 12/17/2010
• Status: Active Grant

• Current Assignee: Moonshadow Mobile, Inc.
• Original Assignee: Moonshadow Mobile, Inc.
• Inventors: Ward, Roy W.
• Primary Examiner(s): Torgrimson, Tyler
• Application Number:
  US14/678,982
• Time in Patent Office: 822 Days
• Field of Search: None
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/282 Hierarchical databases, e.g. IMS, LDAP data stores or Lotus Notes
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: G06F 40/146 Coding or compression of tree-structured data
• CPC Class Codes: G06F 40/149 Adaptation of the text data for streaming purposes, e.g. Efficient XML Interchange [EXI] format
• CPC Class Codes: G06F 40/18 of spreadsheets form-filling G06F40/174

Abstract

A binary data file embodies an inline tree data structure storing fields of a hierarchical dataset. The inline tree comprises first-level binary string segments, each comprising substantially contiguous second-level binary string segments, corresponding to subranges of first and second subsets of data fields. Size is reduced by substituting: binary string indices for alphanumeric strings; a data clump index for a set of correlated/anticorrelated strings; field masks for unoccupied data fields. A dedicated conversion program generates the inline tree from conventional database formats, which is read entirely into RAM to be searched/filtered by a dedicated search/filter program. Small size (<2 bytes/field/record) and contiguous arrangement enables searching/filtering of >10⁶ records (>100 data fields) in <500 nanoseconds/record/core. Recursive subdivision of selection field ranges can guide searches that include those selection fields. One example includes geographic searching/filtering of records that include latitude and longitude fields.

Claims

1. A computer-implemented method comprising:

receiving from one or more computer-readable storage media electronic indicia of a multitude of alphanumeric data records of a hierarchical dataset, each data record including alphanumeric data strings for multiple corresponding defined first-level and second-level data fields; and

using one or more computer processors programmed therefor and operatively coupled to the one or more storage media, generating and storing binary indicia of the multitude of alphanumeric data records as one or more binary data files stored on one or more computer-readable storage media operatively coupled to the one or more computer processors,

wherein;

the one or more data files form a single, continuous binary string including multiple first-level binary string segments and, following each first-level binary string segment, one or more corresponding second-level binary string segments;

for the first-level data fields, each range of data strings for the first-level data fields is divided into multiple corresponding first-level subranges, and the multitude of data records comprises multiple first-level subsets of the data records, wherein each first-level subset includes only those data records for which each data string of the first-level data fields falls within a corresponding one of the first-level subranges;

each first-level binary string segment encodes the data strings of the first-level data fields of a corresponding one of the first-level subsets of the data records;

each second-level binary string segment encodes data strings of the second-level data fields of that first-level subset of the data records which corresponds to the immediately preceding first-level binary string; and

arrangement of the one or more binary files enables access to the first-level and second-level binary strings in only the order in which each appears in the single, continuous binary string, without enabling random access to the binary indicia of the data strings of the multitude of data records.

2. The method of claim 1 wherein:

each data record further includes alphanumeric data strings for multiple corresponding defined third-level data fields;

the single, continuous binary string further includes, following each second-level binary string segment, one or more corresponding third-level binary string segments;

for the second-level data fields, each range of data strings for the second-level data fields is divided into multiple corresponding second-level subranges, and each one of the multiple first-level subsets of the data records comprises multiple second-level subsets of the data records, wherein each second-level subset includes only those data records for which each data string of the second-level data fields falls within a corresponding one of the second-level subranges;

each second-level binary string segment encodes the data strings of the second-level data fields of a corresponding one of the second-level subsets of the data records;

each third-level binary string segment encodes data strings of the third-level data fields of that second-level subset of the data records which corresponds to the immediately preceding second-level binary string; and

arrangement of the one or more binary files enables access to the first-level, second-level, and third-level binary strings in only the order in which each appears in the single, continuous binary string, without enabling random access to the binary indicia of the data records of the multitude of data records.

3. The method of claim 1 wherein each of the first-level binary string segments includes a corresponding first-level header portion and each of the second-level binary string segments includes a corresponding second-level header portion, wherein:

one or more of the first-level header portions indicate which of several of the first-level data fields have data strings encoded by the corresponding first-level binary string segment; and

one or more of the second-level header portions indicate which of several of the second-level data fields have data strings encoded by the corresponding second-level binary string segment.

4. The method of claim 1 wherein:

each combination of specific data strings, for a selected subset of the defined first-level data fields, that occurs in the dataset is assigned a corresponding composite data string; and

the selected subset of the defined data fields is encoded in a corresponding one of the first-level binary string segments by binary indicia of only the composite data string.

5. The method of claim 4 wherein the selected subset of the defined data fields includes the first set of data fields.

6. An article comprising a tangible, non-transitory computer-readable medium encoded to store one or more binary data files generated and stored by a method comprising:

receiving from one or more computer-readable storage media electronic indicia of a multitude of alphanumeric data records of a hierarchical dataset, each data record including alphanumeric data strings for multiple corresponding defined first-level and second-level data fields; and

using one or more computer processors programmed therefor and operatively coupled to the one or more storage media, generating and storing binary indicia of the multitude of alphanumeric data records as one or more binary data files stored on the tangible, non-transitory computer-readable medium,

wherein;

the one or more data files form a single, continuous binary string including multiple first-level binary string segments and, following each first-level binary string segment, one or more corresponding second-level binary string segments;

for the first-level data fields, each range of data strings for the first-level data fields is divided into multiple corresponding first-level subranges, and the multitude of data records comprises multiple first-level subsets of the data records, wherein each first-level subset includes only those data records for which each data string of the first-level data fields falls within a corresponding one of the first-level subranges;

each first-level binary string segment encodes the data strings of the first-level data fields of a corresponding one of the first-level subsets of the data records;

each second-level binary string segment encodes data strings of the second-level data fields of that first-level subset of the data records which corresponds to the immediately preceding first-level binary string; and

arrangement of the one or more binary files enables access to the first-level and second-level binary strings in only the order in which each appears in the single, continuous binary string, without enabling random access to the binary indicia of the data strings of the multitude of data records.

7. The article of claim 6 wherein the one or more binary data files have a total size that is less than about 2 bytes per field per data record of the multitude.

8. The article of claim 6 wherein the tangible, non-transitory computer-readable medium is directly accessible to a computer processor.

9. The article of claim 6 wherein the tangible, non-transitory computer-readable medium comprises random access memory.

10. The article of claim 9 wherein the one or more binary data files have a total size that is less than about 2 bytes per field per data record of the multitude.

11. A computer-implemented method for using the article of claim 6 to search the one or more binary data files stored on the tangible, non-transitory computer-readable medium, the method comprising:

(a) receiving an electronic query for data records, or an enumeration thereof, having certain data strings in one or more of the first-level or second-level data fields that fall within corresponding specified search subranges for those data fields;

(b) in response to the query of part (a), with a computer processor programmed therefor, automatically electronically interrogating each of the first-level binary string segments, in only the order in which each appears in the single, continuous binary string, to identify one or more first-level binary string segments that encode data strings falling within a corresponding one of the specified search subranges queried in part (a);

(c) in response to the query of part (a), with a computer processor programmed therefor, after each identification of part (b) and before interrogation of the next first-level binary string segment, automatically electronically interrogating, in only the order in which each appears in the single, continuous binary string, those corresponding second-level binary string segments that follow, in the single, continuous binary string, the corresponding first-level binary string segment, to identify one or more second-level binary string segments that encode data strings falling within a corresponding one of the specified search subranges queried in part (a); and

(d) generating a list or an enumeration of the one or more data records corresponding to the second-level binary string segments identified in part (c).

12. The method of claim 11 wherein:

each combination of specific data strings, for a selected subset of the defined first-level data fields, that occurs in the dataset is assigned a corresponding composite data string; and

the selected subset of the defined data fields is encoded in a corresponding one of the first-level binary string segments by binary indicia of only the composite data string.

13. The method of claim 11 wherein part (b) includes, for each first-level binary segment, skipping to the next first-level binary string segment, without interrogating the intervening second-level binary string segments, if the corresponding first-level binary string segment does not encode a data string that falls at least overlaps a corresponding one of the specified search subranges.

14. The method claim 11 wherein the tangible, non-transitory computer-readable medium is directly accessible to the computer processor of part (b) or (c).

15. The method of claim 14 further comprising loading sequentially, according to location within the single, continuous binary string, the first-level binary string segments into a processor cache computer memory.

16. The method of claim 15 further comprising loading sequentially, according to location within the single, continuous binary string, into a processor cache computer memory, those second-level binary string segments interrogated in part (c).

17. The method of claim 11 wherein the tangible, non-transitory computer-readable medium comprises random-access memory.

18. The method of claim 11 wherein part (b) includes, for each first-level binary segment, skipping to the next first-level binary string segment according a length or position indicated by a first-level header portion of the corresponding first-level binary string segment, without interrogating the intervening second-level binary string segments, if the corresponding first-level binary string segment does not encode a data string that at least overlaps a corresponding one of the specified search subranges.

19. The method of claim 11 wherein the one or more binary data files indicate at least 100,000 data records, and the interrogations of parts (b) and (c) are performed in less than 500 nanoseconds per data record per processor core.

20. The method of claim 11 wherein the one or more binary data files indicate at least 1,000,000 data records, and the interrogations of parts (b) and (c) are performed in less than 500 nanoseconds per data record per processor core.

21. The method of claim 11 further comprising:

(e) receiving an electronic indicator of one or more designated filter data fields and corresponding filter subranges for each filter data field;

(f) with a computer processor programmed therefor, automatically identifying one or more of the data records identified in part (c) that have a data string in each of the filter data fields that falls within the corresponding indicated filter subrange; and

(g) generating a list or an enumeration of one or more data records identified in part (f).

22. A computer-implemented method comprising:

receiving from one or more computer-readable storage media electronic indicia of multitudes of alphanumeric data records of a hierarchical dataset, each data record including alphanumeric data strings for multiple corresponding defined first-level and second-level data fields;

for each of one or more designated selection data fields of each data record, using one or more computer processors programmed therefor and operatively coupled to the one or more storage media, automatically recursively subdividing into multiple selection field subranges a corresponding range of data strings of the selection data fields, wherein each different combination of selection field subranges indicates a different corresponding selected multitude of data records of the hierarchical dataset, wherein each corresponding selected multitude includes only those data records for which each data string of the selection data fields falls within a corresponding selection field subrange;

for each one of the selected multitudes of data records, using one or more computer processors programmed therefor and operatively coupled to the one or more storage media, generating and storing binary indicia of the selected multitude of alphanumeric data records as one or more binary data files stored on one or more computer-readable storage media operatively coupled to the one or more computer processors; and

using one or more computer processors programmed therefor and operatively coupled to the one or more storage media, generating and storing binary indicia of a binary header string in one or more of the binary data files,

wherein;

for each one of the selected multitudes of data records, the one or more data files form a single, continuous binary string including multiple first-level binary string segments and, following each first-level binary string segment, one or more corresponding second-level binary string segments;

for the first-level data fields, each range of data strings for the first-level data fields is divided into multiple corresponding first-level subranges, and the multitude of data records comprises multiple first-level subsets of the data records, wherein each first-level subset includes only those data records for which each data string of the first-level data fields falls within a corresponding one of the first-level subranges;

each first-level binary string segment encodes the data strings of the first-level data fields of a corresponding one of the first-level subsets of the data records;

each second-level binary string segment encodes data strings of the second-level data fields of that first-level subset of the data records which corresponds to the immediately preceding first-level binary string; and

arrangement of the one or more binary files enables access to the first-level and second-level binary strings in only the order in which each appears in the single, continuous binary string, without enabling random access to the binary indicia of the data strings of the multitude of data records;

the binary selection header string comprises a linked list of indicia of multiple combinations of selection field subranges, and the linked list is linked in a manner that reflects the recursive subdivision of the selection field subranges; and

each terminal record in the linked list indicates a corresponding one of the selected multitudes of data records.

23. The method of claim 22 wherein (i) the dataset comprises a set of data records linked to geographical coordinates, (ii) the designated selection fields are latitude and longitude, (iii) the first-level data fields are related to street segments, and (iv) the second-level data fields are related to street addresses.

24. The method of claim 22 wherein the recursive subdivision is terminated based on a selected absolute or relative numerical limit on a number of data records in each selected multitude.

25. An article comprising a tangible, non-transitory computer-readable medium encoded to store one or more binary data files generated and stored by a method comprising:

receiving from one or more computer-readable storage media electronic indicia of multitudes of alphanumeric data records of a hierarchical dataset, each data record including alphanumeric data strings for multiple corresponding defined first-level and second-level data fields;

for each of one or more designated selection data fields of each data record, using one or more computer processors programmed therefor and operatively coupled to the one or more storage media, automatically recursively subdividing into multiple selection field subranges a corresponding range of data strings of the selection data fields, wherein each different combination of selection field subranges indicates a different corresponding selected multitude of data records of the hierarchical dataset, wherein each corresponding selected multitude includes only those data records for which each data string of the selection data fields falls within a corresponding selection field subrange;

for each one of the selected multitudes of data records, using one or more computer processors programmed therefor and operatively coupled to the one or more storage media, generating and storing binary indicia of the selected multitude of alphanumeric data records as one or more binary data files stored on one or more computer-readable storage media operatively coupled to the one or more computer processors; and

using one or more computer processors programmed therefor and operatively coupled to the one or more storage media, generating and storing binary indicia of a binary header string in one or more of the binary data files,

wherein;

for each one of the selected multitudes of data records, the one or more data files form a single, continuous binary string including multiple first-level binary string segments and, following each first-level binary string segment, one or more corresponding second-level binary string segments;

for the first-level data fields, each range of data strings for the first-level data fields is divided into multiple corresponding first-level subranges, and the multitude of data records comprises multiple first-level subsets of the data records, wherein each first-level subset includes only those data records for which each data string of the first-level data fields falls within a corresponding one of the first-level subranges;

each first-level binary string segment encodes the data strings of the first-level data fields of a corresponding one of the first-level subsets of the data records;

each second-level binary string segment encodes data strings of the second-level data fields of that first-level subset of the data records which corresponds to the immediately preceding first-level binary string; and

arrangement of the one or more binary files enables access to the first-level and second-level binary strings in only the order in which each appears in the single, continuous binary string, without enabling random access to the binary indicia of the data strings of the multitude of data records;

the binary selection header string comprises a linked list of indicia of multiple combinations of selection field subranges, and the linked list is linked in a manner that reflects the recursive subdivision of the selection field subranges; and

each terminal record in the linked list indicates a corresponding one of the selected multitudes of data records.

26. A computer-implemented method for using the article of claim 25 to search the one or more binary data files stored on the tangible, non-transitory computer-readable medium, the method comprising:

(a) receiving an electronic query for data records, or an enumeration thereof, having data strings in one or more designated selection data fields, and certain data strings in one or more of the first-level or second-level data fields, that fall within corresponding specified search subranges for each of those data fields;

(b) in response to the query of part (a), with a computer processor programmed therefor, automatically electronically interrogating the binary selection header string to identify one or more of the selected multitudes of data records that have designated selection data field data strings within the one or more specified search subranges queried in part (a);

(c) in response to the query of part (a), with a computer processor programmed therefor, for each selected multitude identified in part (b), automatically electronically interrogating each one of the first-level binary string segments of the corresponding single, continuous binary string, in only the order in which each appears in that single, continuous binary string, to identify one or more first-level binary string segments that encode data strings falling within the one or more specified search subranges queried in part (a);

(d) in response to the query of part (a), with a computer processor programmed therefor, after each identification of part (c) and before interrogation of the next first-level binary string segment, automatically electronically interrogating, in only the order in which each appears in the single, continuous binary string, those corresponding second-level binary string segments that follow, in the single, continuous binary string, the corresponding first-level binary string segment, to identify one or more second-level binary string segments that encode data strings falling within the one or more specified search subranges queried in part (a); and

(e) generating a list or an enumeration of one or more data records identified in part (d).

27. The method of claim 26 wherein (i) the dataset comprises a set of data records linked to geographical coordinates, (ii) the designated selection fields are latitude and longitude, (iii) the first-level data fields are related to street segments, and (iv) the second-level data fields are related to street addresses.

28. The method of claim 26 wherein the tangible, non-transitory computer-readable medium is directly accessible to the computer processor of part (b) and the computer processor of part (c).

29. The method of claim 28 wherein the tangible, non-transitory computer-readable medium comprises random access memory.

30. A computer system comprising one or more computer processors and one or more computer-readable storage media operatively coupled to one or more of the computer processors, wherein the computer system is structured, connected, and programmed to perform a method comprising:

receiving from one or more of the computer-readable storage media electronic indicia of a multitude of alphanumeric data records of a hierarchical dataset, each data record including alphanumeric data strings for multiple corresponding defined first-level and second-level data fields; and

using one or more of the computer processors, generating and storing binary indicia of the multitude of alphanumeric data records as one or more binary data files stored on one or more of the computer-readable storage media,

wherein;

the one or more data files form a single, continuous binary string including multiple first-level binary string segments and, following each first-level binary string segment, one or more corresponding second-level binary string segments;

for the first-level data fields, each range of data strings for the first-level data fields is divided into multiple corresponding first-level subranges, and the multitude of data records comprises multiple first-level subsets of the data records, wherein each first-level subset includes only those data records for which each data string of the first-level data fields falls within a corresponding one of the first-level subranges;

each first-level binary string segment encodes the data strings of the first-level data fields of a corresponding one of the first-level subsets of the data records;

each second-level binary string segment encodes data strings of the second-level data fields of that first-level subset of the data records which corresponds to the immediately preceding first-level binary string; and

arrangement of the one or more binary files enables access to the first-level and second-level binary strings in only the order in which each appears in the single, continuous binary string, without enabling random access to the binary indicia of the data strings of the multitude of data records.

31. An article comprising a tangible, non-transitory medium encoding computer-readable instructions that, when applied to a computer system comprising at least one processor, instruct the computer system to perform a method comprising:

receiving from one or more computer-readable storage media electronic indicia of a multitude of alphanumeric data records of a hierarchical dataset, each data record including alphanumeric data strings for multiple corresponding defined first-level and second-level data fields; and

using one or more computer processors programmed therefor and operatively coupled to the one or more storage media, generating and storing binary indicia of the multitude of alphanumeric data records as one or more binary data files stored on one or more computer-readable storage media operatively coupled to the one or more computer processors,

wherein;

the one or more data files form a single, continuous binary string including multiple first-level binary string segments and, following each first-level binary string segment, one or more corresponding second-level binary string segments;

for the first-level data fields, each range of data strings for the first-level data fields is divided into multiple corresponding first-level subranges, and the multitude of data records comprises multiple first-level subsets of the data records, wherein each first-level subset includes only those data records for which each data string of the first-level data fields falls within a corresponding one of the first-level subranges;

each first-level binary string segment encodes the data strings of the first-level data fields of a corresponding one of the first-level subsets of the data records;

each second-level binary string segment encodes data strings of the second-level data fields of that first-level subset of the data records which corresponds to the immediately preceding first-level binary string; and

arrangement of the one or more binary files enables access to the first-level and second-level binary strings in only the order in which each appears in the single, continuous binary string, without enabling random access to the binary indicia of the data strings of the multitude of data records.