基于顺序读取的分布式top-k查询算法

发布时间：2018-10-10 17:47

【摘要】：top-k查询是一种被广泛应用的操作,通过把已有top-k算法作为分析和研究的基础,根据现有算法所存在的不足提出自己的解决方案。提出SRTA(Sequential-Read Threshold Algorithm),相比NRA算法对数据的存储进行了重新的规划,创建一个新的表将内存上的开销转换到较廉价的外存开销,只需顺序读取就可以进行有效的top-k查询,同时将表进行了划分,在并行处理的情况下更能提高程序的效率,能够很好地运行在内存有限的环境中。在SRTA基础上提出的DSRTA(Distributed Sequential-Read Threshold Algorithm),适用于分布式环境中。DSRTA先采用ID划分的方式把原有数据集划分为多个子空间,然后再进行数据规划,发挥分布式的性能优势,进一步提高了SRTA的查询效率。
[Abstract]:Top-k query is a widely used operation. By taking the existing top-k algorithm as the basis of analysis and research, this paper puts forward its own solution according to the shortcomings of the existing algorithms. In this paper, SRTA (Sequential-Read Threshold Algorithm), compared with NRA) algorithm is proposed to replan the storage of data, and to create a new table to convert the memory overhead to the lower cost of external storage, so that the efficient top-k query can be carried out only by sequential reading. At the same time, the table is partitioned, which can improve the efficiency of the program and run in the environment of limited memory under the condition of parallel processing. DSRTA (Distributed Sequential-Read Threshold Algorithm), proposed on the basis of SRTA is suitable for distributed environment. DSRTA divides the original data set into several subspaces by ID partitioning, and then carries out data planning to give play to the advantage of distributed performance. The query efficiency of SRTA is further improved.
【作者单位】： 中国矿业大学(徐州)计算机科学与技术学院;
【基金】：国家自然科学基金资助项目(60970032) 江苏省自然科学基金资助项目(BK2007035)
【分类号】：TP301.6;TP333

【参考文献】

相关期刊论文 前1条

1 毛杰;佘名高;;海量数据库查询优化研究[J];软件导刊;2010年05期

相关博士学位论文 前1条

1 吴超;信息检索中top-k问题的并行算法及优化研究[D];中国科学技术大学;2011年

【共引文献】

相关期刊论文 前10条

1 黄菁华;;基于业务流程的数据库应用系统优化[J];广东科技;2012年05期

2 杨柳;刘铁英;;基于GPU的并行集群系统的发展[J];计算机光盘软件与应用;2013年18期

3 金晋;杨明;金华;;一种基于分区缓存的海量数据检索方法[J];中国人民公安大学学报(自然科学版);2014年03期

4 徐兴雷;汪婵婵;;反范式在海量数据库设计中的应用[J];科技传播;2011年05期

5 张成华;李晓峰;;无人机数据共享平台结构及功能设计[J];舰船电子工程;2013年03期

6 周腾腾;陈林祥;胡奥;;RRTA:一种基于顺序读取的有效Top-K查询算法[J];计算机工程与应用;2013年17期

7 魏贤全;郑洪源;丁秋林;;一种海量分布式数据Top-k查询算法[J];计算机工程与科学;2013年10期

8 慈祥;马友忠;孟小峰;;一种云环境下的大数据Top-K查询方法[J];软件学报;2014年04期

9 冯大伟;孙瑞志;曹振丽;;低内存占用的分布式top-k监测算法[J];计算机工程与设计;2015年03期

10 张正本;蔡鹏飞;;海量数据查询优化[J];信息与电脑(理论版);2010年11期

相关硕士学位论文 前10条

1 李永盛;基于PCEDM的数据查询模型研究[D];东北石油大学;2011年

2 曹立新;基于星型模式的top-kjoin算法研究[D];哈尔滨工业大学;2011年

3 曾雪;海量数据的快速查询算法研究[D];南京邮电大学;2012年

4 李青振;基于Top-k高维检索算法的海量数据存储及调度方法研究[D];浙江工业大学;2012年

5 解朝良;融合文本属性和数值属性的语义Top-N查询处理[D];河北大学;2013年

6 王威;面向云计算的海量数据检索技术研究与应用[D];电子科技大学;2013年

7 崔凯;数字化城市管理模式的研究与设计[D];东北石油大学;2013年

8 王静;电梯制造合同管理信息系统的设计与实现[D];东北大学;2012年

9 刘宾;支持文本属性和数值属性的关系Top-N查询处理[D];河北大学;2014年

10 刘飞飞;基于p-范数距离的Top-N查询处理[D];河北大学;2014年

【二级参考文献】

相关期刊论文 前6条

1 谷震离;基于SQL查询语句的查询优化方法[J];计算机时代;2005年02期

2 何源,戴小鹏,张林峰;数据查询优化算法综述[J];计算机与现代化;2005年04期

3 陈波;高秀娥;陈来杰;;基于等价变换的分布式查询优化方法研究[J];计算机工程与设计;2006年03期

4 谷震离;;SQL Server数据库应用程序性能优化方法[J];计算机工程与设计;2006年15期

5 张俊霞;张焕杰;李会民;;基于龙芯2F的国产万亿次高性能计算机KD-50-I的研制[J];中国科学技术大学学报;2008年01期

6 陈越洲;杨树强;贾焰;;基于CORBA的并行海量数据处理系统的研究[J];中南林学院学报;2006年06期

相关博士学位论文 前2条

1 张琦;多核系统中的程序性能优化研究[D];中国科学技术大学;2010年

2 苗乾坤;面向共享存储系统的计算模型及性能优化[D];中国科学技术大学;2010年

，

本文编号：2262717