鲁棒的无线传感器网络空间范围聚集查询处理算法

现有无线传感器网络环境下的空间范围聚集查询处理算法没有综合考虑节点移动、节点失效和通信链路失效等因素对查询处理的影响,导致查询成功率低和能量消耗大.本文提出了利用节点冗余保证查询处理过程鲁棒性的空间范围聚集查询处理算法RSA(Robust Spatial window aggregation query processing Algorithm),它将查询区域划分为若干个网格,沿一条路线依次收集各网格内所有节点的数据.RSA算法给出了一种自适应的网格大小设置方法和基于网格面积的网格代表节点选择策略,以减少算法的能量消耗和提高查询成功率;给出了基于目标矩形的方法以绕过不存在节点的区域,从而避免查询处理过程出现中断.仿真实验结果表明,RSA算法优于现有的IWQE算法.     

使用区间路径处理XML查询

近年来,在XML查询处理方法中发表了一些基于节点流栈连接的高效的分枝连接算法。然而,这些算法普遍存在这样的问题:由于它们必须扫描查询中出现的每一个元素对应的节点流,当XML节点数量很大时,查询处理的输入代价很大,效率变得低下。为了解决这个问题,提出了一个新型的标记法记为区间路径,不同于节点流的区间标记法,区间路径可以把具有相同路径的节点集索引到一个集合中。继而提出了分枝点连接算法用于XML查询处理。同基于节点流栈的分枝连接算法相比,该算法有以下优势:节点集的祖先信息直接位于区间路径中;只有和查询结果相关的节点集会被扫描到,大大降低了输入代价;支持查询通配符;对于类型为根路径的查询,只需一次输入操作代价完成查询处理。实验结果表面该算法在输入代价,执行时间和延展性方面都优于基于节点流的分枝连接算法。     

基于连接依赖信息的分布式连接查询优化算法

分析分布式数据库中站点依赖算法和片段复制算法的特性,提出基于连接依赖信息的多连接查询优化算法。该算法中,连接依赖信息用于逻辑判定基于多个站点的连接查询是否对站点依赖,以避免不必要的通信代价;片段复制用于重新分布站点数据,确保局部连接处理满足站点依赖;利用SQL应用的本地性和站点间多线程的高度并行性以缩减网络通信代价和局部计算代价。实验结果证明了该算法的有效性。     

容忍节点失效的传感器网络空间范围查询算法

提出了一种容忍节点失效的空间范围查询处理算法GSA.给出了理论上最节省能量的网格大小设置.提出了一种基于网格的查询结果收集调度策略,以避免查询结果收集过程中的消息碰撞问题.系统地分析了算法在不同节点密度、节点失效概率和查询区域大小条件下的查询成功率,以及不同节点密度、查询消息大小、感知数据大小、查询区域大小、节点失效概率条件下的能量消耗.理论和实验表明,在多数情况下,GSA算法优于现有的IWQE算法.     

一种基于bloom-filters的半连接查询优化算法

以传输费用最小为目的,提出一种新的查询优化算法。该算法以连接属性为关键字,利用半连接关系建立bloom-filters,在半连接关系间相互传送bloom-filters,从而缩减大部分不参与连接的元组,最终形成了计算结果表。通过站点间传送计算结果表来缩减连接关系,半连接的准确性比估算连接结果高,半连接查询优化算法能较准确地做出下一步的连接;新的查询优化算法能有效地得到连接操作的执行计划,从而减少了传输费用。     

一种基于数据划分的字符串相似连接外存算法

字符串相似连接操作具有广泛应用,因而将着重研究基于编辑距离的字符串相似连接。而现有的字符串相似连接算法大多为内存算法。实际应用中的数据集越来越大,有必要针对超大规模数据集研制字符串相似性连接外存算法。利用组合频率向量划分数据集,并提出了基于编辑距离的字符串相似性连接外存算法框架,证明了磁盘调度问题的难度并提出了不同的启发式磁盘调度方法。此外,还提出了基于该外存算法框架实现字符串相似性连接增量式计算的方法。实验结果表明,数据划分方法可以有效地过滤不相关的数据子集;磁盘调度算法能够有效减少磁盘IO次数;外存算法是高效的;增量式计算方法能够高效地处理数据更新。     

基于查询优化策略的语义缓存谓词化简

语义缓存技术可以有效地支持移动计算应用。现有的语义缓存查询处理算法在时空效率和裁剪的复杂度上较高,限制了语义缓存的实用性。为此,本文提出20条逻辑规则和语义缓存动态合并策略,来降低查询裁剪的复杂性。在Android系统上的实验表明,在简单查询下,采用全合并的缓存管理策略和谓词析取式优化算法相结合的方法,能较好地优化查询处理。在复杂查询方面,基于谓词复杂度的语义缓存动态合并策略能很好地平衡缓存与查询两端的谓词复杂度,有效地提高语义缓存的查询处理效率。     

一种分布式查询优化算法

分布式查询是一种网络通信成本较大的查询过程，设计、开发有效的查询策略和技术是分布式查询面临的挑战。本文展示了一种新的分布式查询的算法，他结合了W算法和PERF算法的特点，进一步强化了W算法和PERF的性能。本文从理论上证明了该算法能有效降低分布式查询处理的网络传输成本。     

面向大规模网络的快速重叠社团挖掘算法

重叠社团在社交网络大数据中普遍存在.针对现有重叠社团挖掘算法易将重叠区域错误地划分为独立的社团且计算复杂的问题,提出了一种基于局部信息度量的快速重叠社团挖掘算法（Local information based Fast Overlapped Communities Detection,Li-FOCD）.首先,为节点定义局部信息度量指标——社团连接度和邻居连接度,建模节点与社团的关系,缩小了计算范围;然后,每次并行地迭代执行缩减、扩展、去重等操作,并更新局部度量指标,通过松弛每次迭代的终止条件,发现近似最优社团集合而不是最优社团,最终算法复杂度为O（m+n）.基于真实的大规模社交网络数据的试验分析表明：与当前流行的重叠社团挖掘算法相比,Li-FOCD在不损失检测质量的前提下,大幅提升了计算效率.     

基于对象的空间数据库的方位查询算法

基于方位的空间关系在地理信息系统、图像识别、空间数据库等很多领域中是很重要的，经常被用作空间查询的选择条件。主要研究基于对象的方位查询处理算法，并提出了一种全新的基于模型的开放策略。以OSS为模型的查询算法通过提高传送效率来减少Ⅰ／O和CPU的设备开销，实验数据表明此算法在性能上超越从前的变换查询算法，更适合对复杂的数据集合进行处理。     

基于直角多边形近似的R树插入算法

空间查询效率是衡量空间数据库性能的关键，而空间连接查询是最耗时、最重要的空间查询。直角多边形近似是空间数据库中一种新的空间对象近似方法，和MBR近似方法相比，它改进了空间对象的近似精度。文中主要探讨了节点是直角多边形近似的R树插入算法。     

数据流窗口连接查询处理器研究

 高速数据流处理是数据流管理系统的一个关键问题.目前已有系统一般采用查询优化、系统调度、降载等方法来提高速度,在高速数据流环境下存在明显的不足.为了最大程度地提高数据流连接操作的速度,提出专用硬件处理器WJSP及设计.针对千变万化连接条件所共同的基本操作,提出在WJSP可执行的指令系统WJSI,并提出多核处理器以提高WJSP的扩展性和并行性.实验结果显示WJSP原型比STREAM的速度提高10多倍,具有相当高的处理性能.WJSP可嵌入到路由器、交换机、传感器等设备中,提供高速数据流连接处理.     

空间近似关键字反远邻查询

空间数据集中的点普遍由空间信息及描述文本信息组成.空间近似关键字反远邻查询(Approximate String Reverse Furthest Neighbors Search,ASRFNS)问题是在一个空间数据集中搜索所有以给定查询点为最远邻,且满足文本相似度条件的目标.基于现有的空间反远邻查询算法以及近似关键字查询算法,我们提出了两个基本的解决算法:凸包最远单元交集(CHFCsJoin)算法和凸包最远单元近似字符串串行查询(CHFCASSS)算法;我们又设计了一种包含空间和关键字信息的外存索引结构Filter-Rtree,并给出了相应的凸包最远单元过滤R树(CHFilterRtree)高效算法.通过真实数据集的实验测试,验证这三种算法的有效性,并分析比较了其性能与效率.     

混合维定性空间查询语言MQS-SQL

定性空间推理的RCC理论能够比较全面地表达空间对象的拓扑关系.但由于不支持混合维空间对象,RCC不能直接用于空间查询.本文扩展了RCC,建立了能表达混合维空间关系,更适合于空间查询的空间关系模型MRCC.该模型采用GIS中常用的数据结构,支持混合维空间对象的全拓扑(mereotopology)关系,并根据混合维对象的特点建立了与维数无关的统一的方向、距离关系.利用该模型扩充了标准SQL语言的关系代数,实现了混合维定性空间查询语言MQS-SQL.     

SCBT-index:基于谱编码的子图索引算法

随着图模型规模的扩大,单机算法难以适应大规模数据集下的子图查询.而现有的分布式算法基于无索引的简单遍历,join过程容易出现内存溢出,而且查询图分布异常时易出现负载不均衡.提出了一种基于谱编码的二叉索引树（SCBT-index）,首先对数据图中的顶点谱编码,根据编码信息构建二叉索引树.然后对查询图使用最小查询计划进行分解,最后join过程使用3个剪枝策略：基于拓扑结构的预剪枝、序列化join和基于分布式下的join优化.实验结果表明,SCBT-index在图集下的综合性能优于现有主流算法,单图下的查询时间为现有算法的1/2到1/4.     

An intelligent user interface for browsing satellite data catalogs

A large scale domain-independent spatial data management expert system that serves as a front-end to databases containing spatial data is described. This system is unique for two reasons. First, it uses spatial search techniques to generate a list of all the primary keys that fall within a user's spatial constraints prior to invoking the database management system, thus substantially decreasing the amount of time required to answer a user's query. Second, a domain-independent query expert system uses a domain-specific rule base to preprocess the user's English query, effectively mapping a broad class of queries into a smaller subset that can be handled by a commercial natural language processing system. The methods used by the spatial search module and the query expert system are explained, and the system architecture for the spatial data management expert system is described. The system is applied to data from the International Ultraviolet Explorer (IUE) satellite, and results are given.     

一些国家和地区的电话号码查询业务

电话号码查询是一种基本电信业务,不但可服务于用户,甚至可成为一项赢利的业务。电话号码查询按查询方式可分为非在线号码查询(包括白页和黄页)及在线号码查询。目前一些国家和地区的号码查询业务随着更多运营商的加入而变得复杂,因此,管制机构开始重新修订规则,出台了一系列的规定和规范,以便提高号码查询业务的服务质量。     

Novel multimedia retrieval technique: progressive query (why wait?)

A novel multimedia retrieval technique, called progressive query (PQ) is presented. PQ is designed to bring an effective solution, especially when querying large-scale multimedia databases. In addition, PQ produces intermediate query retrieval results during the execution of the query. The series of intermediate query results finally converges to the full-scale search retrieval in a faster way and with no minimum system requirements. Experimental progressive query retrieval results show that intermediate retrieval results may be satisfactory and further query processing time may be avoided.     

p XCube云模型的任务划分技术

Query efficiency is bottleneck of XML data cube aggregate query. p XCube is a kind of XML data cube model based on path calculation. Join operations are avoided in this model, but the query efficiency of fact cell is become a new bottleneck. This paper focuses on parallel technology of cloud computing to improve query efficiency of p XCube. Mixed partitioning strategy for fact and dimensions is applied in p XCube cloud model, and the same partitioned vector is adopted. Query parallel algorithm of p XCube cloud model is presented as well. Experiments show that the query cost of p XCube cloud model decreases with the increasing number of parallel nodes gradually. The query cost of fact fragments of each node are close to or even lower than join operations of dimensions , and the Speedup is with better linear. So the model is well suited for decision supported query.