数据仓库索引启发式查询优化方法

在大型数据仓库查询过程中,经常涉及多事实表的连接操作。传统的查询优化方法是在计算多关系连接时尽可能地减少中间关系的大小,并没有考虑到数据仓库中数据的海量,以读为主且事实表一般建有索引的特点,往往无法取得最优的效果。针对数据仓库查询的特点,提出了一种利用索引加快查询的启发式优化方法。理论分析与实验表明,该方法在查询处理代价和执行时间上都明显减少,方法具有有效性。     

基于Bin位图索引的多维查询优化算法

在属性基数（该属性可能的取值数）很高的情况下,简单位图索引需要占用太大存储空间。Bin位图索引可以很好解决这个问题。这种索引不像简单位图索引那样建立在不同的属性值上,而是建立在属性范围上,但候选检查往往占用大部分的查询时间。为了提高查询性能,提出一种排序方法来对各属性进行排序,以减少候选检查数目,并在此基础上提出动态预扫描算法。实验结果表明,排序和动态预扫描算法都取得了良好的效果。     

一种扩充语义的实视图重写查询技术

分组聚集查询已成为数据仓库领域研究的核心问题之一,实视图是提高分组聚集查询性能的有效手段。利用维属性间的层次关系,对一般意义上的实视图重写查询进行了扩展,讨论了单一视图重写查询的限制条件,并给出重写方法,在此基础上,提出了一种利用多个实视图重写查询的优化选择算法,并通过实验表明,该算法进一步提高了分组聚集查询效率。     

倒排索引查询处理技术

介绍索引系统的基本结构以及经典查询处理方式DAAT和TAAT ,给出在AND和OR两种布尔查询下的查询处理算法实现细节。分析结果表明,在海量索引规模查询的情况下,DAAT索引遍历方式要优于TAAT索引遍历方式,OR查询和AND查询的性能差距进一步加大,基于TREC WT2G和GOV2的多组实验验证了分析的结论。指出下一步在海量索引规模下搜索引擎查询处理研究的方向。     

空间关键字个性化语义近似查询方法

现有的空间关键字查询处理模式大都仅支持位置相近和文本相似匹配,但不能将语义相近但形式上不匹配的对象提供给用户;并且,当前的空间-文本索引结构也不能对空间对象中的数值属性进行处理。针对上述问题,本文提出了一种支持语义近似查询的空间关键字查询方法。首先,利用词嵌入技术对用户原始查询进行扩展,生成一系列与原始查询关键字语义相关的查询关键字;然后,提出了一种能够同时支持文本和语义匹配,并利用Skyline方法对数值属性进行处理的混合索引结构AIR-Tree;最后,利用AIR-Tree进行查询匹配,返回top-k个与查询条件最为相关的有序空间对象。实验分析和结果表明,与现有同类方法相比,本文方法具有较高的执行效率和较好的用户满意度;基于AIR-Tree索引的查询效率较IRS-Tree索引提高了3.6%,在查询结果准确率上较IR-Tree和IRS-Tree索引分别提高了10.14%和16.15%。     

一种基于HBase的空间关键字查询算法

针对传统关系数据库处理海量空间文本数据的不足,基于HBase数据库提出了一种结合Geohash编码与分词技术的空间文本索引方案,并基于该空间文本索引提出了一种多边形区域内的空间关键字查询算法。通过与传统经纬度索引方案的实验比较,验证了算法的高效性和可扩展性。     

Considering data skew factor in multi-way join query optimization for parallel execution

A consensus on parallel architecture for very large database management has emerged. This architecture is based on a shared-nothing hardware organization. The computation model is very sensitive to skew in tuple distribution, however. Recently, several parallel join algorithms with dynamic load balancing capabilities have been proposed to address this issue, but none of them consider multi-way join problems. In this article we propose a dynamic load balancing technique for multi-way joins, and investigate the effect of load balancing on query optimization. In particular, we present a join-ordering strategy that takes load-balancing issues into consideration. Our performance study indicates that the proposed query optimization technique can provide very impressive performance improvement over conventional approaches.An earlier version of this article was presented at the 1993 International Conference on Parallel and Distributed Information Systems in San Diego, California, U.S.A.     

基于特征的空间数据相似性查询研究

针对目前空间数据相似性查询的广泛应用需求和实际应用情况,提出基于特征的空间数据相似性查询（Feature Based Spatial Data Similarity Query,FBSDQ）的概念,并给出了形式化定义,分析指出了FBSDQ的特点。提出了统一的FBSDQ处理框架及其实现的关键技术,以典型的度量空间高维索引结构VP树为例,讨论了基于距离的度量空间高维索引技术,为空间数据相似性查询的研究提供了技术支持。     

基于复杂模式索引的XML查询优化*

分析了XML模式与XML文档之间的关系以及XML查询的特点,提出了一种基于复杂模式索引的XML查询优化方法.该方法对XML模式中的节点建立索引,查询时考虑XML模式中带有环的情况.首先对查询树进行去除重复元素的预处理,并将查询树分解成主路径和分支路径;然后利用索引查找潜在目标节点的XML模式编号;最后在XML文档中对对应节点进行筛选,找到目标节点.该方法可以减少连接操作的次数,提高查询操作的效率,能处理较复杂的XML模式.     

基于查询优化器的分布式空间查询优化方法

为了实现分布式空间数据库之间的互操作,需要对分布式查询进行优化处理,这种查询处理指的是在任何一个数据处理语句中它访问的是各个节点的数据而不是仅仅对发起查询的节点。提出了一种查询优化器的体系结构,针对上述查询最优化做了详细的讨论,着重讨论包含空间选择和连接的复杂空间查询。建立了典型的空间数据库的案例程序,通过分析表明,带有过滤和修正的查询优化器在时间与空间上的效率优势比较明显,获得了具有参考价值的结果。     

一种基于路网的多源聚合距离Skyline查询算法

基于路网距离的多源Skyline查询在地图服务中广泛使用,但现有的Skyline查询方法对于复杂的路网距离计算效率低下,并且随着查询点数量的增加查询结果集变得过于庞大,无法为用户提供精简有效的查询结果。为了提高查询结果的有效性和查询效率,提出一种基于最小聚合距离的倒排索引Skyline查询算法,该算法对道路网建立QG-tree索引,提高聚合距离的计算效率;同时对兴趣点集建立倒排索引,结合剪枝策略对兴趣点进行检索,减少聚合距离计算和支配判定的开销,有效地提高查询效率。在真实道路网上的实验表明,所提出的算法效率比现有算法DSR和N3S快1~3个数量级,可以有效地处理道路网环境下多源Skyline查询问题。     

Multiple query optimization in middleware using query teamwork

Multiple concurrent queries occur in many database settings. This paper describes the use of middleware as an optimization tool for such queries. Since common subexpressions derive from common data and the data is usually greatest at the source, the middleware exploits the presence of sharable access patterns to underlying data, especially scans of large portions of tables or indexes, in environments where query queuing or batching is an acceptable approach. The results show that simultaneous queries with such sharable accesses have a tendency to form synchronous groups (teams) which benefit each other through the operation of the disk cache, in effect using it as an implicit pipeline. The middleware exploits this tendency by queuing and scheduling the queries to promote this interaction, using an algorithm designed to promote such teamwork. This is implemented as middleware for use with a commercial database engine. The results include tests using the query mix from the TPC Benchmark^? R, achieving a speed‐up of 2.34 over the default scheduling provided by one database. Other results show that the success depends on the details of the computing environment. Copyright © 2004 John Wiley & Sons, Ltd.     

基于标签编码的Deep Web查询接口识别方法

通过对现有查询接口的识别方法进行的深入研究,针对计算、维护复杂以及匹配歧义性等问题,提出一种基于标签编码的Deep Web查询接口识别方法。该方法根据查询接口排列的方向性和不规则性进行标签编码并分组,然后以每一个标签组作为一个独立单位进行特征信息识别,提出了简单属性、复合属性的识别方法以及孤立文本的处理方法。通过对标签下标的约束确定与元素匹配的文本,大大减少了文本与元素匹配中需要考虑的文本数量,避免了由大量启发式算法引发的匹配歧义性问题;通过两次聚类有效解决了接口层次嵌套问题。     

基于快照的大规模动态图相似节点查询算法

动态图拓扑结构演进过程中,为了量化在一定时间域内节点间联系的变化情况,定义了一种泛相似节点的概念,通过衡量其与当前节点的联系是否频繁、分布是否均匀来确定与当前节点的泛相似程度,并提出了一种基于快照的大规模动态图泛相似节点查询处理算法。具体包括:图动态演进过程的快照集表示,即演进动态图;图动态演进过程中的节点泛相似的语义及其形式化表示方式,从联系的频繁程度与分布的均匀程度对节点的相似程度进行了刻画;节点泛相似语义的矩阵表示及处理方式;针对这种语义的泛相似节点查询处理算法。真实数据集和合成数据集上的实验结果均表明算法能够处理大规模动态图上泛相似节点的查询问题,并在实际应用中运用实现。     

基于综合赋权的包推荐查询松弛方法

针对包推荐系统的推荐结果用户满意度较低的问题,提出一种基于综合赋权的包推荐查询松弛方法。该方法引入改进的熵权法,综合考虑用户的主观意图和客观情况,计算属性权重;根据初始查询返回结果情况,计算松弛阈值;并利用不同属性值域大小情况下数据相似性不同的原理以及隶属度方法,确定数值型属性相似性,计算松弛区间。实验结果表明,所提出方法的权重评估结果合理;在多个不同类型的查询条件下,所提方法在未增加额外时间开销基础上,相较于QRRR方法效用提升更加明显,验证了所提方法的有效性。     

基于位置演进模型的两类时空查询算法

为减少历史时间窗时空查询结果偏差,通过假定移动对象在连续位置更新间做匀速直线运动,获取该对象的近似轨迹函数,基于此函数提出简化的位置演进模型。由该模型求解对象轨迹与查询区域边界相交时间点集;由轨迹函数计算对象与查询中心点间距离函数,求解距离函数间相交时间点集。给出基于简化位置演进模型的时间窗时空范围查询、最近邻查询算法。仿真结果表明,与传统算法相比,所提两类查询算法的结果准确度更高。     

脏数据库的查询方法研究

对于给定的约束,多个数据源分别是一致的,但是在它们集成时可能是脏的.已经存在的技术能够通过特别的方法识别出数据集成环境下的脏数据,但是不能进行有效处理.分析查询对应的连接图是否为有向连接图,判断查询是否可重写,并且给出了元组概率计算和基本查询重写方法.使用TPC-H基准的数据和查询比较脏数据多粒度的执行性能,实验显示方法是可行的.     

一种LAS数据快速调度方法

为了提高数据分类处理时对大数据量LAS数据的访问速度,算法充分利用点集凸包的概念,提出了一种新的建立索引和快速调度的方法.通过实验证明,该方法在完全保留LAS数据原始文件存储的基础上,调度速度得到显著提高,完全可以满足数据分类处理的需要.     

The DR-tree: A Main Memory Data Structure for Complex Multi-dimensional Objects

An efficient index structure for complex multi-dimensional objects is one of the most challenging requirements in non-traditional applications such as geographic information systems, computer-aided design, and multimedia databases. In this paper we first propose a main memory data structure for complex multi-dimensional objects. Then, we present an extension of the existing multi-dimensional index structure. Among existing multi-dimensional index structures, the popular R*-tree is selected. The R*-tree is coupled with the main memory data structure to improve the performance of spatial query processing. An analytical model is developed for our index structure. Experimental results show that the analytical model is accurate, the relative error being below 15%. The performance of our index structure is compared with that of a state-of-the-art index structure by experimental measurements. Our index structure outperforms the state-of-the-art index structure due to its ability to reduce a large amount of storage.     

基于自然语言理解的SPARQL本体查询

为了用户能够方便地获取本体知识,提出了基于自然语言理解的SPARQL本体查询。利用Stanford Parser分析用户的自然语言查询,根据语法构建查询三元组,与关键词的方法相比,有效地减少了组合的个数。结合用户词典,能较准确地把查询三元组的词汇映射到本体实体。分值计算时除了考虑词语的形式相似和语义相似外,还考虑了概念的模糊性,尽量返回具体的概念。利用本体推理获取隐藏在本体中的信息,对查询进行过滤和限制,提高了准确率。用户通过图形交互界面和系统进行交互,选择需要的结果,最后返回树形查询结果,并能看到相关的信息。实验结果表明,该方法达到了预期的效果。