skyline 查询 和 验证索引数据结构MR-tree的构建
文章目录
简介
多维数据库的一种重要的查询类型 -- skyline.
skyline的定义
the skyline S is the set of all points p such that there is no other point q which dominates p
dominate的定义
q is said to dominate p if q is better than p in at least one dimension and not worse than p in all other dimensions.
ADS 验证数据结构
MR-tree 在 VLDB “Authenticated indexing for outsourced spatial databases” 首次提出。综合了MB-tree 和 R* tree.
Node Structure
叶子节点:一个叶子节点包含若干关键字(这里一个关键字是一个points或者data objects)。 叶子节点的摘要由节点里的所有关键字的摘要取串联。
中间节点:一个中间节点的包含若干项,每一项(pi, MBRi, Hi), pi是指针,MBRi是minimum bounding rectangle, Hi是第i个孩子的摘要。The digest summarizes child nodes’ MBRs(MBR1-MBRf ), in addition to their digests (H1−Hf).
Query Processing in MRtree
Example of MR-tree




评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论