A Redis module implementing the Wavelet Tree data structure.
The Wavelet Tree is a versatile data structure which provides some primitive operations over a sequence with less time and memory complexity and many useful applications has been found on top of it. See Wavelet Tree - Wikipedia for more detail and for further reference.
This module is under development. Module interfaces, internal implementations and complexity could be changed in near future.
To build the module run
make
Then load the built module build/libwvltr.so
to Redis server.
Available commands are described below with time and space complexities where N
is the number of elements in a sequence represented by a wavelet tree and A
is the number of distinct elements in a sequence.
NOTICE: In current implementation, A
is fixed to 2^32
.
- Time complexity:
O(N log A)
- Space complexity:
O(N log A)
Builds a wavelet tree from the list given by the specified key
and stores it in destination
.
- Time complexity:
O(log A)
Returns the element at index index
in the wavelet tree stored at key
.
- Time complexity:
O(log A)
Returns the number of occurrences of value
in elements before the index index
of the wavelet tree stored at key
.
- Time complexity:
O(log^2 A)
Return the index of value
at the count
-th element of the wavelet tree stored at key
.
- Time complexity:
O(log A)
Return the count
-th smallest element in the elements within the given index range [from
, to
) of the wavlet tree stored at key
.
- Time complexity:
O(log A)
Count the number of elements ranging from min
to min
within the given index range [from
, to
) of the wavelet tree stored at key
.
- Time complexity:
O(k log A)
wherek
is the number of target elements
List the elements with frequency ranging from min
to min
within the given index range [from
, to
) of the wavelet tree stored at key
.
- Time complexity:
O(log A)
Return the maximum element x
which satisfies min <= x < max
within the given index range [from
, to
) of the wavelet tree stored at key
.
- Time complexity:
O(log A)
Return the minimum element x
which satisfies min < x <= max
within the given index range [from
, to
) of the wavelet tree stored at key
.
- Time complexity
O(min(to-from, A) log A)
in worst caseO(k log A)
when there is large frequency deviation
List k
elements in frequent order with frequency within the given index range [from
, to
) of the wavelet tree stored at key
.
- Time complexity:
O(k log A)
List k
elements in ascending order with frequency within the given index range [from
, to
) of the wavelet tree stored at key
.
- Time complexity:
O(k log A)
List k
elements in descending order with frequency within the given index range [from
, to
) of the wavelet tree stored at key
.
Please see LICENSE.