|
|||||
|
|
| 一种基于逆支配点集的数据流Top-k计算方法 | |
| 引用本文： | 甘亮,于莉莉,李润恒,贾焰,金鑫.一种基于逆支配点集的数据流Top-k计算方法[J].计算机工程与科学,2012,34(6):59-64. |
| 作者姓名： | 甘亮 于莉莉 李润恒 贾焰 金鑫 |
| 作者单位： | 1. 国防科学技术大学计算机学院,湖南 长沙 410073;第二炮兵指挥学院三系,湖北 武汉 430012 2. 北京航空航天大学计算机学院,北京,100191 3. 国防科学技术大学计算机学院,湖南 长沙,410073 4. 长沙民政职业技术学院软件学院,湖南 长沙,410004 |
| 基金项目： | 国家863计划资助项目 |
| 摘 要： | 网格索引构造简单,常用于数据流系统计算top-k和skyline。但是,网格索引结构粗略,查询过程可能访问大量非top-k结点。为了提高网格索引计算top-k查询的精确度,本文提出基于数据点逆支配点集性质的网格索引方法,将查询访问集缩小到网格索引的"k-最大运算区域区域k-MCA"中,有效地减少了网格索引存储量和查询计算开销。同时,给出了k-MCA索引结构及适应于数据流计算的k-MCA维护更新算法。理论分析和实验结果均验证了上述方法的有效性。 |
| 关 键 词： | 偏好top-k查询 网格索引 逆支配点集 数据流 |
A Reverse Dominant Point Set Based Algorithm for Top- k Queries in DSMS |
|
| GAN Liang , YU Li-li , LI Run-heng , JIA Yan , JIN Xin.A Reverse Dominant Point Set Based Algorithm for Top- k Queries in DSMS[J].Computer Engineering & Science,2012,34(6):59-64. | |
| Authors: | GAN Liang YU Li-li LI Run-heng JIA Yan JIN Xin |
| Affiliation: | 1.School of Computer Science,National University of Defense Technology,Changsha 410073;2.Department Three,The Second Artillery Command College,Wuhan 430012;3.School of Computer Science and Engineering,Beihang University,Beijing 100191;4.Changsha Social Work College,Changsha 410004,China) |
| Abstract: | Grid index is often used in the query of top-k and skyline in DSMS,but it is coarse-grained.In this paper,we propose a Reverse Dominant Point Set(RDPS) algorithm which is based on grid index,and prune a number of cells in grid index using the characteristics of RDPS to improve the precision of top-k queries,thus accessing the data set in queries is limited to the k-max calculating region.So,it reduces the memory usage of grid index and the overhead of queries.Analytical and experimental evidences show the efficiency of the proposed approaches. |
| Keywords: | preference top-k queries grid index reserve dominant point set data stream |
| 本文献已被 CNKI 万方数据 等数据库收录！ | |
| 点击此处可从《计算机工程与科学》浏览原始摘要信息 | |
| 点击此处可从《计算机工程与科学》下载全文 | |