Data Storage System

• US 20140229489A1
• Filed: 05/24/2012
• Published: 08/14/2014
• Est. Priority Date: 05/24/2011
• Status: Abandoned Application

• Current Assignee: Apple Inc.
• Original Assignee: Acunu Ltd. (Apple Inc.)
• Inventors: Low, Richard, Suffield, Andrew
• Application Number:
  US14/118,432
• Publication Number:
  US 20140229489A1
• Time in Patent Office: Days
• US Class Current: 707/741
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/9014 hash tables

Abstract

A system (1) comprises a plurality of data structures. Each of the data structures comprises an association to a disjoint key range Ri=[k_i,k_{i+1}), where k_i is an ordered sequence arranged to be held in an internal memory (3) key range index. The system is arranged to allow membership queries for a key within the system to be performed by searching the key range index for the unique range Ri containing the key, and then querying the data structure associated with the range Ri for membership of the key.

Claims

1. A system for staging on a data processing apparatus, the system comprising a plurality of data structures, each of said data structures comprising an association to a disjoint key range Ri=[k_i,k_{i+1}), wherein k_i is an ordered sequence arranged to be held in an internal memory key range index, and wherein the system is arranged to allow membership queries for a key within the system to be performed by searching the key range index for the unique range Ri containing the key, and then querying the data structure associated with the range Ri for membership of the key.

2. A system as claimed in claim 1, wherein the plurality of data structures each comprises a Bloom filter.

3. A system as claimed in claim 2, wherein the Bloom filter uses a murmur hash.

4. A system as claimed in claim 1, 2 or 3, wherein the plurality of data structures each comprises an external memory Bloom filter.

5. A system as claimed in claim 1, wherein the key range index comprises a b-tree, a binary tree, an in-memory array, or other searchable data structure.

6. A system as claimed in claim 1, wherein the data structures each have a fixed amount of memory.

7. A system as claimed in claim 6, wherein the fixed amount of memory for each data structure is independent of the total dataset size.

8. A system as claimed in claim 1, wherein the data structures are constructed during the merge of two or more key arrays.

9. A system as claimed in claim 1, wherein each data structure comprises a fixed number of distinct keys in the range [k_i,k_{i+1}).

10. A system as claimed in claim 1, wherein an auxiliary index structure is maintained on the boundary keys k_—

0,k_—

1, . . . , k_{r+1}.

11. A method for constructing a system as claimed in claim 1 from a sequence of sorted keys, comprising assembling each of the plurality of data structures from a contiguous set of keys, flushing the set of keys from memory when full, then inserting a key range Ri=[k_—

i,k_{i+1}) into the key range index, wherein k_i is the smallest key added into the data structure, and [k_{i+1} is the smallest key greater than k_i not included in the data structure.

12. A method as claimed in claim 11, wherein the keys to be inserted are presented in sequential order.

13. A computer readable data storage medium for storing one or more data records in a system as claimed in claim 1.

14. A method of performing a membership query for a key within a system containing data, wherein the system comprises a plurality of data structures, each of said data structures comprising an association to a disjoint key range Ri=[k_i,k_{i+1}), wherein k_i is an ordered sequence arranged to be held in an internal memory key range index, the method comprising:

searching the key range index for the unique range Ri containing the key, and

querying the data structure associated with the range Ri for membership of the key.

15. A method as claimed in claim 14, wherein the plurality of data structures each comprises a Bloom filter.

16. A method as claimed in claim 15, wherein the Bloom filter uses a murmur hash.

17. A method as claimed in claim 14, wherein the plurality of data structures each comprises an external memory Bloom filter.

18. A method as claimed in claim 14, wherein the key range index comprises a b-tree, a binary tree, an in-memory array, or other searchable data structure.

19. A method as claimed in claim 14, wherein the data structures each have a fixed amount of memory.

20. A method as claimed in claim 19, wherein the fixed amount of memory for each data structure is independent of the total dataset size.

21. A method as claimed in claim 14, wherein the data structures are constructed during the merge of two or more key arrays.

22. A method as claimed in claim 14, wherein each data structure comprises a fixed number of distinct keys in the range [k_i,k{i+1}).

23. A method as claimed in claim 14, wherein an auxiliary index structure is maintained on the boundary keys k_—

0,k_—

1, . . . , k_{r+1}.