w******c
发帖数: 574 | 1 assume there are a set of data objects O = {o_1, ..., o_n}, each of which
has two attributes a and b. given a subset of objects P \in O, which data
structure (index) should we build on O, such that for a specific value of
attribute a, we could obtain the value range for objects on attribute b.
for instance, assuming we have object o_1, o_3, o_7 and know the attribute
values for these objects, we want to know the value on attribute b for
objects o_i such that o_i.a is equal to a specific value. what data
structure should we build on ojbect set O, both space and time efficient?
thanks. | S**I
发帖数: 15689 | 2 objects in O should be sorted according to the value of a, so I think binary
tree.
【在 w******c 的大作中提到】
: assume there are a set of data objects O = {o_1, ..., o_n}, each of which
: has two attributes a and b. given a subset of objects P \in O, which data
: structure (index) should we build on O, such that for a specific value of
: attribute a, we could obtain the value range for objects on attribute b.
: for instance, assuming we have object o_1, o_3, o_7 and know the attribute
: values for these objects, we want to know the value on attribute b for
: objects o_i such that o_i.a is equal to a specific value. what data
: structure should we build on ojbect set O, both space and time efficient?
: thanks.
| w******c
发帖数: 574 | 3 thanks for your quick response.
i forgot to mention that objects could have duplicate values on attribute a
or b. is binary tree still good in such case?
binary
【在 S**I 的大作中提到】
: objects in O should be sorted according to the value of a, so I think binary
: tree.
| S**I
发帖数: 15689 | 4 Of course; for example, C++ STL has multiset and multimap, which allow
existence of elments with equivalent keys. Also, both of them have a member
function equal_range, which does exactly what you want.
a
【在 w******c 的大作中提到】
: thanks for your quick response.
: i forgot to mention that objects could have duplicate values on attribute a
: or b. is binary tree still good in such case?
:
: binary
|
|
