Systems and Methods for Searching Heterogeneous Indexes of Metadata and Tags in File Systems
First Claim
1. An apparatus for processing queries in a heterogeneous index, comprising:
- a receiver configured to receive a query from a user, wherein the query comprises at least one desired attribute of a desired file;
a processor coupled to the receiver and configured to search the heterogeneous index by;
receiving the query from the receiver;
testing a bloom filter of a storage partition that comprises a plurality of data structures comprising a k-dimensional tree (kd-tree) and a key-value store (kv-store) in the heterogeneous index for existence of the desired attribute after receipt of the query;
ignoring the storage partition and proceeding to a next storage partition in the heterogeneous index when the bloom filter indicates that the desired attribute is not present in the storage partition; and
searching the storage partition to determine which one or more files of the storage partition have the desired attribute when the bloom filter indicates that the desired attribute is present in the storage partition.
1 Assignment
0 Petitions
Accused Products
Abstract
An apparatus for processing queries in a heterogeneous index. The apparatus comprises a receiver configured to receive a query from a user, wherein the query comprises at least one desired attribute of a desired file, and a processor coupled to the receiver and configured to search the heterogeneous index. The processor is configured to search the heterogeneous index by receiving the query from the receiver, testing a bloom filter of a storage partition in the heterogeneous index for existence of the desired attribute after receipt of the query, ignoring the storage partition and proceeding to a next storage partition in the heterogeneous index when the bloom filter indicates that the desired attribute is not present in the storage partition, and searching the storage partition to determine which one or more files of the storage partition have the desired attribute when the bloom filter indicates that the desired attribute is present in the storage partition.
35 Citations
23 Claims
-
1. An apparatus for processing queries in a heterogeneous index, comprising:
-
a receiver configured to receive a query from a user, wherein the query comprises at least one desired attribute of a desired file; a processor coupled to the receiver and configured to search the heterogeneous index by; receiving the query from the receiver; testing a bloom filter of a storage partition that comprises a plurality of data structures comprising a k-dimensional tree (kd-tree) and a key-value store (kv-store) in the heterogeneous index for existence of the desired attribute after receipt of the query; ignoring the storage partition and proceeding to a next storage partition in the heterogeneous index when the bloom filter indicates that the desired attribute is not present in the storage partition; and searching the storage partition to determine which one or more files of the storage partition have the desired attribute when the bloom filter indicates that the desired attribute is present in the storage partition. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
12. A method for updating a heterogeneous search index for a storage partition comprising a plurality of data structures, comprising:
-
receiving an update message from a user, wherein the update message indicates an operation to be performed on the heterogeneous search index that comprises attributes comprising metadata and tags; recording a log entry indicating receipt of the update message from the user; determining the operation that is to be performed according to the update message; updating the heterogeneous search index according to the update message; and recording a log entry indicating that the update message received from the user was executed successfully. - View Dependent Claims (13, 14, 15, 16, 17, 18, 19)
-
-
20. A method of recovering from a system failure in a heterogeneous search index comprising:
-
entering a plurality of actions to be performed into a log at a time of receipt prior to execution of the actions, wherein the actions to be performed comprise at least two of; updating a bloom filter of the heterogeneous search index that indicates an existence of a tag or metadata in the heterogeneous search index; updating a k-dimensional tree of the heterogeneous search index; and updating a key-value store of the heterogeneous search index; and entering the actions performed into the log at a time of completion to indicate successful execution of a first of the actions and a progression to a second of the actions. - View Dependent Claims (21, 22, 23)
-
Specification