System and method for efficient representation of dynamic ranges of numeric values

摘要

A method of efficiently representing ranged data sets may include storing a data structure representing a first data set. The data structure may include one or more nodes each representing distinct portions of the data set, and the first data set may include a range of multiple values bounded by an upper bound and a lower bound. A first node may represent the range of multiple values by storing the upper bound and the lower bound. The method may also include receiving a second data set to add to the first data set. The intersection of the first data set and the second data may include at least one value. The method may further include altering the one or more nodes in the data structure such that the union of each of the distinct portions of the data set represented by the one or more nodes is equivalent to the union of the first data set and the second data set; and such that the intersection of each of the distinct portions of the data set represented by the one or more nodes is equivalent to an empty data set.

主权项

1. A method of efficiently representing ranged data sets in a memory system, the method comprising:
storing, in the memory system, a data structure comprising one or more nodes, wherein:
the data structure comprises a binary tree data structure;each of the one or more nodes represents a unique range of numeric values by storing an upper bound and a lower bound of the range of numeric values;none of the ranges of numeric values represented by the one or more nodes overlap; andnone of the ranges of numeric values represented by the one or more nodes are adjacent; receiving, at a computer system coupled to the memory system, a first range of numeric values to add to the data structure or to remove from the data structure; altering, by the computer system, the upper bound or lower bound of at least one node in the one or more nodes to represent the addition or removal of the first range of numeric values such that:
none of the ranges of numeric values represented by the one or more nodes overlap; andnone of the ranges of numeric values represented by the one or more nodes are adjacent; and receiving, at the computer system coupled to the memory system, a second range of numeric values to add to the data structure.