没有合适的资源?快使用搜索试试~ 我知道了~
实时Web流上的连续Top-K查询
实时Web流上的连续Top-K查询Despoina Vouzoukidou引用此版本:Despoina Vouzoukidou。实时Web流上的连续Top K查询。数据结构和算法[cs.DS]。皮埃尔和玛丽·居里大学-巴黎第六大学,2015年。英语。NNT:2015PA066659。电话:01366673HAL ID:电话:01366673https://theses.hal.science/tel-01366673提交日期:2016年HAL是一个多学科的开放存取档案馆,用于存放和传播科学研究论文,无论它们是否被公开。论文可以来自法国或国外的教学和研究机构,也可以来自公共或私人研究中心。L’archive ouverte pluridisciplinaire这是医生的事l’UNIVERSIT皮埃尔和玛丽·居里他的名字叫信息学计算机科学、电信、通信和电子学院(Paris)P是不可能的耐莉·沃祖基杜要获得的等级E大学博士皮埃尔和玛丽·居里T'ese的主题:对请求的认可,你可以合作。ALargeEcHelle实时Web流上的2015年 9月17日由评审团支持:M.贝恩德·A·曼M.VassilisCHRISTOPHIDESSihem夫人AMER-YAHIAEvaggeliaPITOURA夫人T'Hese总监共同监督人R贡献人R贡献人M.LudovicDNOYER检查员M.ThemisPALPANAS检查器M.DanVODISLAV审查员我摘要在实时网络时代,在线新闻媒体聚合器(如谷歌新闻)和社交媒体网站(如Twitter)都在努力为数百万用户有效地过滤大量信息考虑到每分钟在Web上发布的信息的巨大多样性和突发性,过滤、排名和向感兴趣的用户提供内容流成为一项具有挑战性的任务。此外,关于内容的反馈信号,例如点击或分享,提供关于内容重要性的有用信息,但是还需要更复杂的操作技术来过滤这些流。在此上下文中,评分函数考虑静态和动态排名因素,如配置文件相关性、信息的最近性和动态反馈信号。现有的实时Web工作无法以在线方式处理这样的动态评分函数,而是采用了一种迭代执行快照查询的方法。在本论文中,我们感兴趣的是基于文本和反馈流的连续高k查询的有效评估技术,这些查询具有捕捉动态排名方面的广义评分函数。作为第一个贡献,我们通过引入一个将查询无关的项目重要性与查询相关的内容相关性和反映信息新鲜度的连续评分衰减相结合的非齐次评分函数的一般族,概括了最先进的连续Top-k查询模型我们的第二个贡献是定义和实现高效的内存中数据结构,用于索引和评估这一新的连续顶k查询家族。我们的实验表明,我们的解决方案是可扩展的,并且在局限于异构函数时优于其他现有的最先进的解决方案。更进一步,在本文的第二部分中,我们考虑了将动态反馈信号合并到原始评分函数中的问题,并提出了一个新的通用实时查询评估框架,该框架具有一系列新的算法,用于在实时网络环境中有效地处理具有动态反馈评分的连续TOP-K查询最后,将这些工作的结果放在一起,我们提出了MeowsReader,一个实时新闻排名和过滤原型,它说明了一个通用的连续Top-k查询类如何提供一个适合的抽象,用于建模和实现结合关键字搜索和实时Web活动的连续在线信息过滤iii内容内容III图7列表1引言11.1背景:Web 2.0。 . . . . . . . . . . . . . . . . . . . . . . . . . . . ... ...11.2在Web 2.0中访问信息 . . . . . . . . . . . . . . . . . . . . ...31.2.1新闻聚合和RSS联合。 . . . . . . . . . ... ...31.2.2实时网络。 . . . . . . . . . . . . . . . . . . . . . . . . . ... ...51.3方法:文本流上的连续top-k查询 . . . . . . ... ...61.4贡献 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ... ...71.5本论文的组织 . . . . . . . . . . . . . . . . . . . . . . . ... ...92 相关工作112.1过滤技术和排名模型122.1.1基于结构化数据的筛选122.1.2过滤文本流162.1.3社交媒体流182.1.4连续查询与定期快照查询执行2.1.5信息............................................................................................... 的建模212.2在文本流上对............................................................................... 函数进行评分232.2.1文本相似性242.2.2项目和项目的2.2.3媒体焦点252.2.4多样性2.2.5用户注意力和反馈信号262.2.6信息的新鲜度26iv2.3索引和查询评估算法272.3.1第二十七章预备役2.3.2基于文本流的连续Top-k查询评估内容2.3.3Twitter上的实时搜索323 基于文本流的查询过滤373.1问题陈述............................................................................................................... 383.1.1问题、项目和分数...................................................................................393.1.2项目流和分数衰减403.1.3连续顶部-k查询413.2查询筛选443.2.1不衰减的查询过滤443.2.2衰减过滤503.3索引513.3.1矩形网格...................................................................................................523.3.2已售出的桶543.3.3已分类的查询543.3.4密度桶553.4近似解:概率模型553.5相关工作583.5.1连续Top-k文本查询处理3.5.2多维索引583.5.3IR59中的查询相关和独立分数3.6实验603.6.1实验设置603.6.2均匀评分无衰减场景613.6.3衰减场景63的均匀评分3.6.4衰变场景65的非均匀分数3.6.5关于实验的66v3.7摘要664 考虑反馈的实时搜索694.1问题陈述............................................................................................................... 704.1.1查询、项目和事件流...............................................................................704.1.2评分功能714.1.3衰变分数72vi我内容4.1.4连续的Top-k查询。 . . . . . . . . . . . . . . . . . . . . ...724.2事件 处理程序算法。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...744.2.1AR算法。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...744.2.2R2TS算法。 . . . . . . . . . . . . . . . . . . . . . . .784.2.3成本分析。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...... ...824.3候选索引854.3.1精炼操作要求...........................................................................................864.3.2简单事件处理程序884.3.3有序事件处理程序884.3.4项目分区事件处理程序914.4实验924.4.1实验设置924.4.2实验:θmax. ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...934.4.3实验:θi的精确值。 . . . . . . . . . . . . . .954.4.4实验:查询的数量。 . . . . . . . . . . . . ...974.4.5实验:γ值。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 1004.4.6实验:在k值上。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...1004.4.7实验:每个项目的事件数。 . . . . . . . . ...1034.4.8关于实验的1034.5摘要..................................................................................................................... 1045 MeowsReader:一个支持反馈的排名过滤原型1075.1框架..................................................................................................................... 1085.2MeowsReader架构1095.2.1Top-K过滤1105.2.2趋势检测1105.3MeowsReader用户界面111vii5.4摘要...................................................................................................................... 1126 结论1156.1研究摘要1156.2前景1166.2.1使用动态连续查询116viii内容6.2.2物联网117参考书目119ix图列表1.1社交媒体。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...21.2用户每分钟生成的内容 . . . . . . . . . . . . . . . . . . . ... ...41.3我们提出的连续查询评估模型。 . . . . . . . . . . . ... ...82.1Tapestry13支持的查询2.2不同过滤技术..............................................................................................................的查询结果152.3缺少定期快照查询执行..............................................................................................的结果202.4使用窗口......................................................................................................................或衰减函数对最近度进行建模2.5文本流..........................................................................................................................上的连续Top-k索引3.1项目处理程序组件......................................................................................................383.2查询表示......................................................................................................................453.3查询索引......................................................................................................................533.4在某个位置找到的查询的更新概率(Smin(q),ωq,t0)。573.5匹配时间和内存成本..................................................................................................之间的权衡3.6根据..........................................................................................................................................索引查询数量的增加匹配时间要求613.7分数快速衰减的时间要求(线性衰减)643.8超过快速衰减分数的时间要求3.9增加α值的时间要求,使用线性衰减653.10 使用指数衰减65增加α值的时间要求4.1事件处理程序组件......................................................................................................704.2前2名查询Q74的演变结果4.3按网格上的项目和事件更新解决方案......................................................................76x我4.4事件处理程序索引......................................................................................................864.5更新查询候选人..........................................................................................................874.6事件处理程序:θmax实验. ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...964.7事件处理程序:全球θ...............................................................................98上的实验4.8事件处理程序:查询......................................................................................... 实验994.9事件处理程序:γ参数..................................................................................101的实验xi图列表4.10 事件处理程序:k参数.................................................................................102的实验4.11 事件处理程序:每个项目的事件数实验............................................................... 1045.1具有用户反馈的.......................................................................................................1085.2MeowsReader架构..................................................................................................1095.3MeowsReader:用户界面.......................................................................................1125.4MeowsReader:更新...............................................................................................1125.5MeowsReader:趋势和订阅...................................................................................1125.6MeowsReader:沙盒版本.......................................................................................1121简介1.1背景:Web 2.0在过去的十年里,Web 2.0技术的出现已经将Web转变为一个充满活力的内容交换、协作和通信的信息场所。第一代万维网,通常称为Web 1.0,被设计为超链接网页和文档的"只读"环境。虽然Web可以被视为一个巨大的公共库,但最终用户的角色仅限于通过直接提交URL、跟随链接或使用搜索引擎通过浏览器访问信息。Web 2.0通过为最终用户分配一个积极的角色,从根本上改变了人们对Web的看法:从被动的内容消费者,他们现在可以通过自己生成内容、表达自己的意见和对发布的信息提供反馈来积极参与。社交网络(例如Facebook1)、博客和微博(例如Twitter2)、照片、mu-sic和视频共享平台(如 Flickr3、YouTube4)以及评论和评级网站(如Yelp5)只是用户生成的社交媒体应用程序的几个例子内容(图1.1)这样的应用程序变得非常受欢迎,因为它们为我们在专业、住宅和公共空间的广泛日常生活活动提供了以人为本的感觉,涵盖了例如用户对信息、交流、娱乐和购物的需求。统计数据显示,2014年,社交网络和微博占平均用户在线活动的40%以上与此同时,传统的新闻来源,如报纸、电视-广播和广播,在网络上有很强的影响力。事实上,新闻阅读仍然是最受欢迎的在线活动之一,用户更喜欢在线新闻媒体网站,而不是印刷媒体。随着大量用户生成内容的可用性1www.facebook.com2www.twitter.com3www.flickr.com4www.youtube.com5www.yelp.com6GlobalWebIndex:http://insight.globalwebindex.net/hs-fs/hub/304927/file-1414878665-pdf/Re-端口/GWI 2014年第三季度媒体消费摘要。pdf121.1.背景:Web 2.0图1.1:对话棱镜(Conversationprism.com),描述了最流行的社交媒体,按其使用情况分类每一分钟在社交媒体上,传统的信息生产者,为用户提供所有必要的工具,并鼓励他们通过评论,分享和一般表达他们对发布信息的意见积极参与。 这种互动主要由社交媒体应用程序支持,与新闻媒体网站紧密或松散地结合在一起,并提供有价值的反馈,以评估所发布信息的重要性。此外,为了适应实时网络时代,需要在发生信息时立即提供信息,在线新闻媒体每天不断发布有关现实生活事件的新信息和更新。3第一章。简介1.2Web 2.0随着每分钟发布的大量信息和信息反馈,以及数百万新闻和社交媒体用户期望实时接收新信息,Web作为访问信息的最初角色提出了新的挑战。图1.2描述了信息溢出效应:每分钟发布的信息超过 在Web1.0Web 2.0内容的流媒体性质为数百万用户实现有效的、近实时的信息感知创造了至关重要的需求。在搜索Web 2.0信息的动态流的上下文中,已经提出的研究问题包括连续信息过滤[MP11,HMA10,VAC12]、趋势和功能[MK10,CDCS10,HMA12]、搜索和查找[MZL+11,ZXL+12]以及流数据索引[CLOW11,WLXX13]。1.2.1新闻聚合和RSS联合在新闻媒体的背景下,回到Web 1.0,当在线可用的来源数量有限时,简单的用户可以直接访问他们喜欢的新闻网站并阅读任何新闻更新。今天,考虑到新闻来源的数量不断增加,而且每一条新闻的发布率都很高,这种方法几乎是不可能的。在线新闻聚合系统,如Google News7、Yahoo!新闻8或MSNBC新闻9,但也博客搜索引擎,如谷歌博客搜索10承担的作用,收集这些信息流从广泛的来源,排名并使其可供数百万用户使用。更重要的是,他们可以使用用户明确提供的信息,如他们的兴趣(关键字查询)或通过监视他们的行为(点击,反馈)隐式收集的信息,在流上提供个性化的视图。个性化可以超越用户首选项,并考虑用户背景(例如社交网络中的朋友)以及7news.google.com8news.yahoo.com9www.msnbc.com10www.google.com/blogsearch41.2.Web 2.0(a)(b)图1.2:(a)2011年和(b)2013年用户每分钟生成的内容(来源:www.domo.com/learn/data-never-sleeps-2)用户与系统交互的信息(例如位置、时间和设备特性)。RSS联合(真正简单的联合或富站点摘要)在21世纪初开始流行,允许向用户及时分发流信息。RSS背后的想法是,用户应该在新信息可用时尽快得到通知,而不是访问网站(例如,原始新闻源或聚合器)并手动检查更新。RSS提要是包含多个项目的文档,即信息块,每个信息块都有标题、摘要和一些元数据,包括发布日期和源链接新项目由发布者插入到RSS提要中,而旧项目可以删除。用户可以使用RSS阅读器订阅这些提要(例如11),谁理解检查和交付更新的任务RSS和Atom,一个类似的流媒体数据的交付得到了大多数新闻媒体和新闻的支持11www.feedly.com
下载后可阅读完整内容,剩余1页未读,立即下载
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功