不确定数据库中概率top-k和排序查询算法
周帆;李树全;肖春静;吴跃
【期刊名称】《计算机应用》
【年(卷),期】2010(030)010
【摘要】传感器网络等技术的广泛应用产生了大量不确定数据.近年来,对于不确定数据的处理和查询成为数据库和数据挖掘领域研究的热点.其中,传统关系数据库中的top-k查询和排序查询怎样拓展到不确定数据是其中的焦点之一.研究近年来提出的不确定数据库上top-k查询和排序查询算法,归纳和比较目前各种不同查询算法所适应的语义世界和应用场景,并详细分析各种算法的执行效率和算法复杂度.另外,对于不确定数据top-k查询和排序查询所面临的挑战和可能的研究方向进行了总结.
【总页数】5页(P2605-2609)
【作者】周帆;李树全;肖春静;吴跃
【作者单位】电子科技大学,计算机科学与工程学院,成都,611731;电子科技大学,计算机科学与工程学院,成都,611731;电子科技大学,计算机科学与工程学院,成
都,611731;电子科技大学,计算机科学与工程学院,成都,611731
【正文语种】中文
【中图分类】TP311.13
【相关文献】
1.基于上下文偏好的Web数据库查询结果Top-K排序方法 [J], 孟祥福;马宗民;李昕;张霄雁;王星
2.不确定数据库中基于x-tuple的高效Top-k查询处理算法 [J], 刘德喜;万常选;刘喜平
3.基于不确定数据的top-k概率相互最近邻查询 [J], 梁瑜;张剡;周嵩;柏文阳
4.关系型数据库中不确定性数据的Top-k查询研究 [J], 李雪娇;余建桥;冯静
5.基于参数化排序的不确定Top-k查询算法 [J], 邹志文;张翅
因版权原因，仅展示原文概要，查看原文内容请购买。
TopK算法详解问题描述百度⾯试题：搜索引擎会通过⽇志⽂件把⽤户每次检索使⽤的所有检索串都记录下来，每个查询串的长度为1-255字节。
假设⽬前有⼀千万个记录（这些查询串的重复度⽐较⾼，虽然总数是1千万，但如果除去重复后，不超过3百万个。
⼀个查询串的重复度越⾼，说明查询它的⽤户越多，也就是越热门。
），请你统计最热门的10个查询串，要求使⽤的内存不能超过1G。
必备知识：什么是哈希表？哈希表（Hash table，也叫散列表），是根据关键码值(Key value)⽽直接进⾏访问的数据结构。
也就是说，它通过把关键码值映射到表中⼀个位置来访问记录，以加快查找的速度。
这个映射函数叫做散列函数，存放记录的数组叫做散列表。
哈希表的做法其实很简单，就是把Key通过⼀个固定的算法函数既所谓的哈希函数转换成⼀个整型数字，然后就将该数字对数组长度进⾏取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间⾥。
⽽当使⽤哈希表进⾏查询的时候，就是再次使⽤哈希函数将key转换为对应的数组下标，并定位到该空间获取value，如此⼀来，就可以充分利⽤到数组的定位性能进⾏数据定位（⽂章第⼆、三部分，会针对Hash表详细阐述）。
问题解析：要统计最热门查询，⾸先就是要统计每个Query出现的次数，然后根据统计结果，找出Top 10。
所以我们可以基于这个思路分两步来设计该算法。
即，此问题的解决分为以下俩个步骤：第⼀步：Query统计Query统计有以下俩个⽅法，可供选择：1、直接排序法⾸先我们最先想到的的算法就是排序了，⾸先对这个⽇志⾥⾯的所有Query都进⾏排序，然后再遍历排好序的Query，统计每个Query出现的次数了。
但是题⽬中有明确要求，那就是内存不能超过1G，⼀千万条记录，每条记录是255Byte，很显然要占据2.375G内存，这个条件就不满⾜要求了。
让我们回忆⼀下数据结构课程上的内容，当数据量⽐较⼤⽽且内存⽆法装下的时候，我们可以采⽤外排序的⽅法来进⾏排序，这⾥我们可以采⽤归并排序，因为归并排序有⼀个⽐较好的时间复杂度O(NlgN)。
空间数据上Top-k关键词模糊查询算法胡骏;范举;李国良;陈姗姗【期刊名称】《计算机学报》【年(卷),期】2012(035)011【摘要】基于位置的服务(LBS)变得日益普及,越来越多的研究开始关注如何对空间中的兴趣点(POI)做有效的检索.现有的方法提出了空间数据上的关键词检索,研究如何根据查询的位置和关键词找到相关的POI点.然而,现有方法主要对查询关键词进行精确匹配,不能支持模糊查询:当查询关键词与底层数据存在微小差异的时候,LBS 系统不能返回相关的结果.为了满足移动用户的模糊查询需求,文中对空间数据上的Top-k关键词模糊查询问题进行研究:给定一组POI点,检索与查询关键词近似匹配且空间上距离相近的Top-k个结果.为了提供高效的模糊查询,文中首先定义了一种新型的相关性函数,综合考虑了文本相似性和空间距离,进而提出了一种有效的索引结构RegionTrie,并基于RegionTrie设计了高效的Top-k算法.真实数据集上的实验结果表明,文中提出的Top-k算法十分高效,性能远好于对比方法.%Location-Based Services (LBSXhave become more and more popular recently. Existing LBS systems employ a spatial keyword search method to provide services, which finds the relevant POIs by considering textual relevance and spatial distance when given a set of points-of-in-terest (POIs). Existing methods only allow exact matches for query keywords and fail to support fuzzy search. To provide error-tolerance search experiences, we study the top-k fuzzy spatial keyword search problem in this paper: Given a set of POIs and a query with location and keywords, we find the relevant POIshaving similar keywords with the query. It calls for efficient algorithms to provide real-time search for mobile users. To address this challenge, we introduce a novel function to quantify the relevance between POIs and the query, by considering the similarity between keywords and spatial distance. Then, we devise an effective index structure, called RegionTrie to organize the POIs and develop efficient search algorithm based on the RegionTrie. We conducted experiments on real datasets, and the experimental results show that our algorithms achieve high performance.【总页数】10页(P2237-2246)【作者】胡骏;范举;李国良;陈姗姗【作者单位】清华大学计算机科学与技术系数据库研究组北京100084;清华大学计算机科学与技术系数据库研究组北京100084;清华大学计算机科学与技术系数据库研究组北京100084;清华大学计算机科学与技术系数据库研究组北京100084【正文语种】中文【中图分类】TP311【相关文献】1.关系数据库上基于非数值属性关键词的模糊查询 [J], 杨路明;王佳宜;谢东EP:海量数据上一种有效的Top-K查询处理算法 [J], 韩希先;杨东华;李建中3.BTreeU-Topk:基于二叉树的不确定数据上的Top-k查询算法 [J], 张慧;郑吉平;韩秋廷4.多数据源上Top-k中间模式的产生算法 [J], 丁国辉;王国仁;赵相国5.基于MPB-Tree索引的空间数据多关键词模糊查询算法研究 [J], 张素智;赵亚楠;杨芮因版权原因，仅展示原文概要，查看原文内容请购买。
