作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2011, Vol. 37 ›› Issue (19): 56-58. doi: 10.3969/j.issn.1000-3428.2011.19.017

• 软件技术与数据库 • 上一篇    下一篇

一种最大向量平均个数的估计方法

杨永滔,王意洁   

  1. (国防科技大学计算机学院并行与分布处理国家重点实验室,长沙 410073)
  • 收稿日期:2011-05-20 出版日期:2011-10-05 发布日期:2011-10-05
  • 作者简介:杨永滔(1981-),男,博士研究生、CCF会员,主研方向:不确定数据管理,数据流查询;王意洁,教授、博士生导师
  • 基金资助:
    国家“973”计划基金资助项目(2011CB302601);国家自然科学基金资助项目(60873215);湖南省自然科学杰出青年基金资 助项目(S2010J5050);高等学校博士学科点专项科研基金资助项目(200899980003)

Estimating Method of Maxima Vector Average Number

YANG Yong-tao, WANG Yi-jie   

  1. (National Key Laboratory for Parallel and Distributed Processing, School of Computer, National University of Defense Technology, Changsha 410073, China)
  • Received:2011-05-20 Online:2011-10-05 Published:2011-10-05

摘要: 提出一种估计n个d维向量中最大向量平均个数的方法。该方法通过分析单个向量与其他向量子集的支配关系,求出最大向量平均个数的解析式。证明解析式满足已知的递归关系,得到最大向量平均个数的近似估计。与已有方法相比,该方法可应用到估计k个其他向量支配的平均个数问题。

关键词: 最大向量, 平均个数, 支配, 近似估计上界, 复杂性计算, skyline查询

Abstract: A new method is proposed for estimating the average number of maxima in a set of n vectors in d-dimensional space. The new method reveals the probability that a vector is dominated by a set of other vectors, and obtains the analytic form of the average number of the maxima. After the fact that the analytic form satisfies a known recurrence is proved, the estimation of the average number can be derived naturally. Compared with the existed methods, the new method can be extended to the general problem of estimating the average number of the vectors that are only dominated by other k vectors.

Key words: maxima vector, average number, dominance, asymptotic estimation upper bound, complexity computation, skyline queries

中图分类号: