Method and System for Database Storage Management
AssigneeThe Board of Trustees of the Leland Stanford Junior University
InventorsAbhijeet Mohapatra, Michael Genesereth
Life of this patent
Estimating the term…
Abstract
Embodiments of the present invention relate to run-length encoded sequences and supporting efficient offset-based updates of values while allowing fast lookups. In an embodiment of the present invention, an indexing scheme is disclosed, herein called count indexes, that supports O(log n) offset-based updates and lookups on a run-length sequence with n runs. In an embodiment, count indexes of the present invention support O(log n) updates on bitmapped sequences of size n. Embodiments of the present invention can be generalize to be applied to block-oriented storage systems.
Claims27
A computer-implemented method for performing database storage management, comprising:
- encoding a first sequence of information, wherein the encoded first sequence of information includes a compression of at least one successive repetition of values in the first sequence of information;
- grouping the encoded first sequence of information into at least one first level of sets having at most a first predetermined number of nodes and each having an associated count;
- and
- generating at least one hierarchical count of the first level of sets wherein nodes at each level of hierarchy maintain a sum of nodes for child levels of hierarchy.
A computer-readable medium including instructions that, when executed by a processing unit, cause the processing unit to perform database storage management, by performing the steps of:
- encoding a first sequence of information, wherein the encoded first sequence of information includes a compression of at least one successive repetition of values in the first sequence of information;
- grouping the encoded first sequence of information into at least one first level of sets having at most a first predetermined number of nodes and each having an associated count;
- and
- generating at least one hierarchical count of the first level of sets wherein nodes at each level of hierarchy maintain a sum of nodes for child levels of hierarchy.
A computing device comprising:
- a data bus;
- a memory unit coupled to the data bus;
- a processing unit coupled to the data bus and configured to
- encode a first sequence of information, wherein the encoded first sequence of information includes a compression of at least one successive repetition of values in the first sequence of information;
- group the encoded first sequence of information into at least one first level of sets having at most a first predetermined number of nodes and each having an associated count;
- and
- generate at least one hierarchical count of the first level of sets wherein nodes at each level of hierarchy maintain a sum of nodes for child levels of hierarchy.
Dependencies are inferred from the claim text.