CSpace  > 中国科学院计算技术研究所期刊论文  > 英文
Partial Sorting Problem on Evolving Data
Huang, Qin1,5; Liu, Xingwu2,3,4; Sun, Xiaoming4,5; Zhang, Jialin4,5
2017-11-01
发表期刊ALGORITHMICA
ISSN0178-4617
卷号79期号:3页码:960-983
摘要In this paper we investigate the top-k-selection problem, i.e. to determine and sort the top k elements, in the dynamic data model. Here dynamic means that the underlying total order evolves over time, and that the order can only be probed by pair-wise comparisons. It is assumed that at each time step, only one pair of elements can be compared. This assumption of restricted access is reasonable in the dynamic model, especially for massive data sets where it is impossible to access all the data before the next change occurs. Previously only two special cases were studied (Anagnostopoulos et al. in 36th international colloquium on automata, languages and programming (ICALP). LNCS, vol 5566, pp 339-350, 2009) in this model: selecting the element of a given rank, and sorting all elements. This paper systematically deals with 1 <= k <= n. Specifically, we identify the critical point k* such that the top-k-selection problem can be solved error-free with probability 1 - 0(1) if and only if k = 0(k*). A lower bound of the error when k = Omega(k*) is also determined, which actually is tight under some conditions. In contrast, we show that the top-k-set problem, which means finding the top k elements without sorting them, can be solved error-free with probability 1 - o(1) for all 1 <= k <= n. Additionally, we consider some extensions of the dynamic data model and show that most of these results still hold.
DOI10.1007/s00453-017-0295-3
收录类别SCI
语种英语
资助项目National Key Research and Development Program of China[2016YFB1000201] ; National Key Research and Development Program of China[2016YFB1000604] ; State Key Laboratory of Software Development Environment Open Fund[SKLSDE-2016KF-01] ; Science Foundation of Shenzhen City in China[JCYJ20160419152942010] ; National Natural Science Foundation of China[61222202] ; National Natural Science Foundation of China[61433014] ; National Natural Science Foundation of China[61502449] ; National Natural Science Foundation of China[61602440] ; China National Program for support of Top-notch Young Professionals
WOS研究方向Computer Science ; Mathematics
WOS类目Computer Science, Software Engineering ; Mathematics, Applied
WOS记录号WOS:000410381100018
出版者SPRINGER
引用统计
文献类型期刊论文
条目标识符http://119.78.100.204/handle/2XEOYT63/6682
专题中国科学院计算技术研究所期刊论文_英文
通讯作者Liu, Xingwu
作者单位1.Beihang Univ, State Key Lab Software Dev Environm, Beijing, Peoples R China
2.Beihang Univ Shenzhen, Res Inst, Shenzhen, Peoples R China
3.Chinese Acad Sci, Inst Comp Technol, Beijing, Peoples R China
4.Univ Chinese Acad Sci, Beijing, Peoples R China
5.Chinese Acad Sci, CAS Key Lab Network Data Sci & Technol, Inst Comp Technol, Beijing, Peoples R China
推荐引用方式
GB/T 7714
Huang, Qin,Liu, Xingwu,Sun, Xiaoming,et al. Partial Sorting Problem on Evolving Data[J]. ALGORITHMICA,2017,79(3):960-983.
APA Huang, Qin,Liu, Xingwu,Sun, Xiaoming,&Zhang, Jialin.(2017).Partial Sorting Problem on Evolving Data.ALGORITHMICA,79(3),960-983.
MLA Huang, Qin,et al."Partial Sorting Problem on Evolving Data".ALGORITHMICA 79.3(2017):960-983.
条目包含的文件
条目无相关文件。
个性服务
推荐该条目
保存到收藏夹
查看访问统计
导出为Endnote文件
谷歌学术
谷歌学术中相似的文章
[Huang, Qin]的文章
[Liu, Xingwu]的文章
[Sun, Xiaoming]的文章
百度学术
百度学术中相似的文章
[Huang, Qin]的文章
[Liu, Xingwu]的文章
[Sun, Xiaoming]的文章
必应学术
必应学术中相似的文章
[Huang, Qin]的文章
[Liu, Xingwu]的文章
[Sun, Xiaoming]的文章
相关权益政策
暂无数据
收藏/分享
所有评论 (0)
暂无评论
 

除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。