海量数据top-k查询系统的设计与实现
发布时间：2021-11-20 17:21
海量数据上的top-k查询是一项非常重要的查询类型,top-k查询是根据指定的评分函数返回分数最高的k个对象给用户,本文研究top-k查询的两种扩展:top-k selection查询和top-k skyline查询。Top-k selection查询是以对象自身属性值的范围作为选择条件,而top-k skyline查询是以对象与对象间的关系作为选择条件;最终返回满足选择条件且分数最高的k个对象,为用户提供决策支持。首先,在top-k selection研究中,本文提出top-k selection查询基线算法BASel,BASel算法顺序扫描数据集,选择出满足选择条件并且分数最高的k个元组;为了提高top-k selection查询的速度,本文提出基于预排序的top-k selection查询算法PTS,PTS算法对数据集进行预排序,顺序扫描有序表获取top-k selection查询结果,根据数据分布的特点,提出早结束条件,减少I/O次数;为了进一步改善PTS算法的效率,本文提出两个剪枝方法:选择剪枝和分数剪枝;在预排序的基础上,PTS算法结合两种剪枝策略,进一步提高查询速度。实验...
【文章来源】：哈尔滨工业大学黑龙江省 211工程院校 985工程院校
【文章页数】：84 页
【学位级别】：硕士
【部分图文】：
012-2018年中国在线咨询量及在线医疗市场规模
哈尔滨工业大学工程硕士学位论文-2-数据量的剧增引起科学研究者对处理海量数据的兴趣；如图1-2所示，图中的点表示饭店数据库，横轴表示饭店的人均消费价格，纵轴表示当前查询用户位置到饭店的距离；当用户在决定去哪吃饭之前，利用用户自身的偏好，确定评分函数，根据评分函数返回分数为top-k的饭店；不同的用户可能对应不同的偏好，那么就对应不同的评分函数；比如：有的用户比较在意价格，那么对于这一类用户在为他们进行top-k查询时，评分函数中价格的权重百分比很高，而距离的权重百分比很小，根据价格和距离进行综合评分；而有的用户在时间很紧迫的时候，希望饭店距离自己的位置越近越好，这样可以节省大量时间，这种查询情况将距离属性的权重变高，而价格属性的权重百分比很校对于不同的用户，无法确定用户对于不同属性的偏好，所以饭店数据库系统无法直接返回查询结果给用户，而需要用户指定每个评分属性的权重，最后返回top-k查询结果给用户。图1-2饭店数据库Top-k查询的应用领域非常广泛，不仅可以应用在网页搜索、信息检索以及k近邻近似匹配中，而且可以为用户提供决策支持，以及在城市导航系统中为用户提供距离更近的行驶路线，并且与多媒体数据库相似性查询，skyline查询，最近邻搜索等多个研究有关。由于数据量非常大，进行top-k查询是非常困难的，而且选择合适的评分函数也是非常困难的。例如：用户在购买房子时，房子会具有一些属性，比如房屋的位置、房屋的层数、房屋在几层以及房屋已经使用的年限，这些属性都会影响购买者对房子的评分，因此房屋中介会根据用户对这些属性的偏好，对房屋进行有效评分，这些评分会直接影响返回的房屋查询结果；而中介肯定希望返回的查询结果尽量满足购买者的需求；所以选
哈尔滨工业大学工程硕士学位论文-3-择更加准确的评分函数是非常重要的。出于对现实意义的考虑，还是以购买房屋为例，有的购买者是老年人，他们要求房屋所在的楼层是低于或等于3层，并且根据位置、年限属性等进行评分；那么购买者提出的“楼层是低于或等于3层”是一个选择条件，必须在满足这个条件的基础上，再根据评分函数返回分数top-k的房屋；上面例子的查询与传统的top-k查询不同，该查询是基于选择条件的查询，这类查询称为top-k选择查询。Top-k选择查询将选择条件和top-k查询融合在一起，其更符合现在用户的查询需求，因为大多数用户在进行查询时，会提出若干个选择条件，在满足选择条件的对象中选择分数top-k的对象，所以这类查询具有重大的理论意义和应用价值。上面例子中的选择条件是利用对象自身的属性值进行判断，而另一种选择条件是根据对象与对象之间的关系进行确定，确定满足选择条件的子集，这个过程称为skyline查询。Skyline查询是另一种偏好查询，skyline查询返回只能支配其余元组，不能被其余元组所支配的元组；skyline查询的应用领域非常广泛，可以为用户做出决策等。Borzsonyi等人[1]在2001年首次提出关于skyline查询的形象定义，是因为skyline查询结果点连接在一起像天际线，故取名为“Skyline查询”。图1-3待租房skyline示意图如图1-3展示待租房屋的skyline示意图，表示以价格、与工作地点的距离为skyline属性，图中用直线连接的点为skyline查询结果。例如：应届毕业生刚到公司入职时，会选择在公司的附近租房子，租房网站对房子的数据进行统计，筛选出离公司较近和价格更便宜的房屋，给用户返回一个房屋列表，供用户进行选择。然而现实情况下，价格与距离之间可能是相互矛盾的，也就是说，
本文编号：3507793
【文章来源】：哈尔滨工业大学黑龙江省 211工程院校 985工程院校
【文章页数】：84 页
【学位级别】：硕士
【部分图文】：
012-2018年中国在线咨询量及在线医疗市场规模
哈尔滨工业大学工程硕士学位论文-2-数据量的剧增引起科学研究者对处理海量数据的兴趣；如图1-2所示，图中的点表示饭店数据库，横轴表示饭店的人均消费价格，纵轴表示当前查询用户位置到饭店的距离；当用户在决定去哪吃饭之前，利用用户自身的偏好，确定评分函数，根据评分函数返回分数为top-k的饭店；不同的用户可能对应不同的偏好，那么就对应不同的评分函数；比如：有的用户比较在意价格，那么对于这一类用户在为他们进行top-k查询时，评分函数中价格的权重百分比很高，而距离的权重百分比很小，根据价格和距离进行综合评分；而有的用户在时间很紧迫的时候，希望饭店距离自己的位置越近越好，这样可以节省大量时间，这种查询情况将距离属性的权重变高，而价格属性的权重百分比很校对于不同的用户，无法确定用户对于不同属性的偏好，所以饭店数据库系统无法直接返回查询结果给用户，而需要用户指定每个评分属性的权重，最后返回top-k查询结果给用户。图1-2饭店数据库Top-k查询的应用领域非常广泛，不仅可以应用在网页搜索、信息检索以及k近邻近似匹配中，而且可以为用户提供决策支持，以及在城市导航系统中为用户提供距离更近的行驶路线，并且与多媒体数据库相似性查询，skyline查询，最近邻搜索等多个研究有关。由于数据量非常大，进行top-k查询是非常困难的，而且选择合适的评分函数也是非常困难的。例如：用户在购买房子时，房子会具有一些属性，比如房屋的位置、房屋的层数、房屋在几层以及房屋已经使用的年限，这些属性都会影响购买者对房子的评分，因此房屋中介会根据用户对这些属性的偏好，对房屋进行有效评分，这些评分会直接影响返回的房屋查询结果；而中介肯定希望返回的查询结果尽量满足购买者的需求；所以选
哈尔滨工业大学工程硕士学位论文-3-择更加准确的评分函数是非常重要的。出于对现实意义的考虑，还是以购买房屋为例，有的购买者是老年人，他们要求房屋所在的楼层是低于或等于3层，并且根据位置、年限属性等进行评分；那么购买者提出的“楼层是低于或等于3层”是一个选择条件，必须在满足这个条件的基础上，再根据评分函数返回分数top-k的房屋；上面例子的查询与传统的top-k查询不同，该查询是基于选择条件的查询，这类查询称为top-k选择查询。Top-k选择查询将选择条件和top-k查询融合在一起，其更符合现在用户的查询需求，因为大多数用户在进行查询时，会提出若干个选择条件，在满足选择条件的对象中选择分数top-k的对象，所以这类查询具有重大的理论意义和应用价值。上面例子中的选择条件是利用对象自身的属性值进行判断，而另一种选择条件是根据对象与对象之间的关系进行确定，确定满足选择条件的子集，这个过程称为skyline查询。Skyline查询是另一种偏好查询，skyline查询返回只能支配其余元组，不能被其余元组所支配的元组；skyline查询的应用领域非常广泛，可以为用户做出决策等。Borzsonyi等人[1]在2001年首次提出关于skyline查询的形象定义，是因为skyline查询结果点连接在一起像天际线，故取名为“Skyline查询”。图1-3待租房skyline示意图如图1-3展示待租房屋的skyline示意图，表示以价格、与工作地点的距离为skyline属性，图中用直线连接的点为skyline查询结果。例如：应届毕业生刚到公司入职时，会选择在公司的附近租房子，租房网站对房子的数据进行统计，筛选出离公司较近和价格更便宜的房屋，给用户返回一个房屋列表，供用户进行选择。然而现实情况下，价格与距离之间可能是相互矛盾的，也就是说，
本文编号：3507793
本文链接：https://www.wllwen.com/kejilunwen/ruanjiangongchenglunwen/3507793.html
