基于网格的传感器网络K近邻查询处理算法

综合考虑了能量消耗、查询延迟、查询结果正确性等因素,提出了一种基于网格的传感器网络K近邻查询处理算法GKNN。它优化现有的查询区域佑计方法以减少算法的能量消耗。利用网格对节点进行管理,将查询区域中的网格划分成多个网格区,由各个网格区并行处理查询从而减少延迟。另外,GKNN利用节点冗余降低了节点失效对查询结果的影响,提高了查询结果的正确性。仿真实验结果表明,GKNN优于现有的算法。     

DKNNS:面向延迟敏感型应用的可扩展精确分布式K近邻搜索算法研究

为了降低用户访问延迟,延迟敏感型网络应用需要选择合适的邻近服务节点响应用户访问请求.分布式K近邻搜索通过可扩展的选择距任意用户节点邻近的K个服务节点,可以有效满足网络应用延迟优化的目的.已有工作在精确度以及可扩展性等方面存在不足.针对可扩展精确的K近邻搜索问题,文中提出了分布式K近邻搜索方法DKNNS(distributed K nearest neighbor search).DKNNS将大量的服务节点组织为邻近性感知的多级环,通过最远节点搜索机制选择优化的K近邻搜索初始化节点,然后基于回退方式快速的在目标节点邻近区域发现K个近邻.基于理论分析,模拟测试以及真实环境下的部署实验发现,在不同规模的节点集合下,DKNNS算法能够确定近似最优的K个服务节点.且DKNNS的查询延迟,查询开销均显著低于Meridian算法.最后,DKNNS的返回结果相对于Meridian具有较高的稳定性.     

能量高效的无线传感器网络空间范围查询处理算法

现有无线传感器网络空间范围查询处理算法能量消耗大且当节点失效时查询处理过程易被中断,无法返回查询结果.文中提出了一种能量高效的算法ESA(Energy-efficient Spatial window query processing Algorithm).它将查询区域划分为若干个网格,每个网格中有一个簇头节点负责收集...     

传感器网络中节点个数约束查询处理算法

对传感器网络中一类新查询--节点个数约束查询,提出能量有效的查询处理算法.算法主要由查询下发和结果回收两部分构成.查询下发算法首先根据节点个数约束查询的特点提出相关节点选择以及基于Steiner树的查询下发算法.然后对该下发算法以及一种基于洪泛的能量有效查询下发算法的能量消耗进行分析,并对比两种算法的能量消耗从中选择适当的下发算法.结果回收算法提出直接和间接两种结果回收方式,并给出两种方式在进行结果回收时能够节省能量的条件.仿真实验表明,提出的能量有效节点个数约束查询处理算法能够在满足用户查询精度的同时,使其能量消耗低于其他查询处理算法.     

一种道路网络中移动对象的k近邻多查询处理算法

在实际应用中,服务器时常会收到许多查询请求,因此如何高效地进行多查询处理,并且获得良好的吞吐量具有重要的意义.研究了道路网络中连续的K近邻多查询处理技术.在已知查询点位置和运动速度的情况下,将道路网络上的查询点进行聚类,提出了基于聚类的K近邻多查询处理算法,使同一聚类中的查询共享执行,从而大大提高多查询处理的效率.算法还进一步利用扩展树存储查询结果,提高连续的K近邻多查询处理性能.理论分析和实验结果表明提出的算法是可行的、高效的.     

链路感知的传感器网络空间范围查询处理算法

在无线传感器网络环境中,用户经常提交空间范围查询以获取网络某局部区域的统计信息,如最大温度、平均湿度等。现有的基于路线的空间范围查询处理算法假设节点通信模型为理想的圆盘模型,而实际的网络并不满足该假设,导致其能量消耗大且查询结果质量差。提出了一种链路感知的空间范围查询处理算法LSA,它根据网络拓扑和链路质量动态地将查询区域划分为若干个网格,依次收集各网格中节点的感知数据,以生成最终的查询结果。LSA算法通过遍历查询区域内的所有网格,保证了算法查询结果的质量。提出了启发式的网格划分方法以降低节点间数据通信的丢包率,给出链路感知的数据收集算法,以减少算法的能量消耗,提高查询结果的质量。通过仿真实验系统地分析和比较了LSA算法和现有的IWQE算法的能量消耗及查询结果质量,结果表明,在绝大多数情况下,LSA算法优于IWQE算法。     

空间数据库中的线段k近邻查询研究

K近邻查询是空间数据库中的重要查询之一,k近邻查询在内容的相似性检索、模式识别、地理信息系统中有重要应用。针对现有k近邻查询都是基于点查询的情况,提出基于平面线段的k近邻查询,查找线段集中给定查询点的k个最近线段。给出基于Voronoi图的线段k近邻查询算法及给出相关定理和证明。该算法通过线段Voronoi图的邻接特性找到一个候选集,然后从中找到最终结果。通过随机数据的实验证明,所提算法明显优于线性扫描算法和基于R树的k近邻查询算法。     

无线传感器网络数据环区域查询处理算法

针对无线传感器网络节点能量高效问题以及Skyline查询位置属性决策问题,提出了基于无线传感器网络数据环区域查询处理算法。该算法以查询位置P为中心进行数据环划分,查询位置P最近的K个Skyline值时,根据剪枝策略只需对距离小于P的其它属性值进行比较,从而缩小了数据规模,提高了查询效率。另外,环内节点采用链簇式结构组织,环内查询处理过程采用串行数据处理与并行数据处理模式,从而提高了K-Skyline的数据查询能耗与节点处理延迟。仿真实验表明,数据环区域查询处理算法比Flooding算法与TAG算法具有更小的数据处理能耗和延迟。     

MOQ-QR:基于QR-树的连续K近邻查询算法研究*

综合分析了R-树和四叉树在处理移动对象的连续K近邻（简称CKNN）查询算法中的不足,提出了一种基于R树和四叉树索引结构,去解决移动对象连续K近邻查询算法。该算法通过对移动对象分配静态空间,并在研究区域内利用QR-树和hash表作为索引去存储移动对象以此计算查询点与移动对象之间的空间距离。实验证明,该算法与现有算法相比,不仅提高了数据的查询效率,而且降低了系统资源的消耗。     

无线传感器网络环境下时-空查询处理方法

在无线传感器网络环境中,观察者感兴趣的是由传感器网络监测得到的与时间-空间相关的事件,而不是传感器本身或者大量无关的观察数据.观察者会经常提出与事件相关的时-空查询,例如:“网络覆盖的某地理区域R中10:00~11:00发生了哪些事件?”.由于每个传感器节点只有有限的能量,因此,研究能量有效性的时-空查询处理算法成为一个重要的研究课题.给出了一种以数据为中心的时-空查询处理算法.针对3种不同的存储策略:以数据为中心的存储、外部存储和节点本地存储,分析比较了节点的能量消耗.系统地研究了在3种不同的数据存储策略下,事件发生的概率,节点密度,事件类型数目,查询数目,时-空查询地理区域的大小以及时-空查询时间窗口的大小对节点能量消耗的影响.理论与实验结果表明,在多数情况下,这种以数据为中心的时-空查询处理算法的能量消耗少于基于外部存储和本地存储的时-空查询处理算法.     

大规模图上具有约束的多起点路径规划算法

路径规划查询是图数据上的一个基本问题,在众多的领域都有重要的应用价值。通常在实际问题中查询的路径是具有约束的,例如在外卖配送和共享出行问题中路径具有节点约束,其路径需要满足节点之间的先后关系约束。目前对于具有节点约束的路径查询问题,大多数的工作都在研究单起点的节点约束路径查询,但很难拓展到多起点节点约束问题中。因为具有节点约束的多起点路径查询问题是NP-hard的,所以该问题的大多数已有方法是使用贪心增量处理,但对于处理静态规则集拓展性不足。因此,提出了基于子路径的启发式算法和基于约束集拓展的精确算法,并在真实数据集上验证了算法的有效性。实验结果表明,启发式算法能够给出问题的精确解,而启发式算法能快速给出较好的近似解。     

无线传感器网络多查询的节能优化

提出了一个无线传感器网络多查询的节能优化方案。该方案通过建立相似查询判断算法把多查询中的相似查询分为一组,并在每一组找一个能使传输能耗达到最小的中继节点作为处理节点。组内节点的数据都传送到该处理节点,并由该节点利用数据处理函数处理数据,然后再传到基站。这样就减少了网络中数据的传输量,从而有效地节省了网络的能量,达到能量的最大化利用。     

Representing and processing lineages over uncertain data based on the Bayesian network

Processing lineages (also called provenances) over uncertain data consists in tracing the origin of uncertainty based on the process of data production and evolution. In this paper, we focus on the representation and processing of lineages over uncertain data, where we adopt Bayesian network (BN), one of the popular and important probabilistic graphical models (PGMs), as the framework of uncertainty representation and inferences. Starting from the lineage expressed as Boolean formulae for SPJ (Selection–Projection–Join) queries over uncertain data, we propose a method to transform the lineage expression into directed acyclic graphs (DAGs) equivalently. Specifically, we discuss the corresponding probabilistic semantics and properties to guarantee that the graphical model can support effective probabilistic inferences in lineage processing theoretically. Then, we propose the function-based method to compute the conditional probability table (CPT) for each node in the DAG. The BN for representing lineage expressions over uncertain data, called lineage BN and abbreviated as LBN, can be constructed while generally suitable for both safe and unsafe query plans. Therefore, we give the variable-elimination-based algorithm for LBN's exact inferences to obtain the probabilities of query results, called LBN-based query processing. Then, we focus on obtaining the probabilities of inputs or intermediate tuples conditioned on query results, called LBN-based inference query processing, and give the Gibbs-sampling-based algorithm for LBN's approximate inferences. Experimental results show the efficiency and effectiveness of our methods.     

Opportunistic sampling-based query processing in wireless sensor networks

High resolution sampling of physical phenomenon is a prime application of large scale wireless sensor networks (WSNs). With hundreds of nodes deployed over vast tracts of land, monitoring data can now be generated at unprecedented spatio-temporal scales. However, the limited battery life of individual nodes in the network mandates smart ways of collecting this data by maximizing localized processing of information at the node level. In this paper, we propose a WSN query processing method that enhances localized information processing by harnessing the two inherent aspects of WSN communication, i.e., multihop and multipath data transmission. In an active WSN where data collection queries are regularly processed, multihop and multipath routing leads to a situation where a significant proportion of nodes relay and overhear data generated by other nodes in the network. We propose that nodes opportunistically sample this data as they communicate. We model the data communication process in a WSN and show that opportunistic sampling during data communication leads to surprisingly accurate global knowledge at each node. We present an opportunistic query processing system that uses the accumulated global knowledge to limit the data collection requirements for future queries while ensuring temporal freshness of the results.     

基于时间权重值的共识算法研究

针对联盟链中广泛应用的PBFT算法网络复杂度高、共识速度慢以及查询速度上的不足进行了研究,并提出了一种基于时间权重值(time-weighted value,TWV)的共识算法.首先,针对网络复杂度高和共识速度慢的问题,TWV共识算法通过节点的时间权重值选择合适的共识节点缩小了共识节点的规模,并且结合PBFT算法中的视图更换协议,将此时的共识节点替换为具有较高时间权重值的节点;其次利用共识节点延迟低、在线时间长以及数据存储量的特点,提升了数据查询和同步的效率;最后,通过本地多节点的仿真对比实验证明,TWV共识算法的数据查询效率以及吞吐量较PBFT共识算法有所提升,并且有效降低了节点达成共识的时间.     

XMin: Minimizing Tree Pattern Queries with Minimality Guarantee

Due to wide use of XPath, the problem of efficiently processing XPath queries has recently received a lot of attention. In particular, a considerable effort has been devoted to minimizing XPath queries since the efficiency of query processing greatly depends on the size of the query. Research work in this area can be classified into two categories: constraint-independent minimization and constraint-dependent minimization. The former minimizes queries in the absence of integrity constraints while the latter in the presence of them. For a linear path query, which is an XPath query without branching predicates, existing constraint-independent minimization methods are generally known to be unable to minimize the query without processing the query itself. Most recently, however, by using the DataGuide, a representative structural summary of XML data, a constraint-independent method that minimizes linear path queries in a top-down fashion has been proposed. Nevertheless, this method can fail to find a minimal query since it minimizes a query by merely erasing labels from the original query whereas a minimal query could include labels that are not present in the original query. In this paper, we propose a bottom-up approach called XMin that guarantees finding a minimal query for a given tree pattern query by using the DataGuide without processing the query itself. For the linear path query, we first show that the sequence of labels occurring in the minimal query is a subsequence of every schema label sequence that matches the original query. Here, the schema label sequence for a node is the sequence of labels from the root of XML data to the node. We then propose iterative subsequence generation that iteratively generates subsequences from the shortest schema label sequence matching the original query in a bottom-up fashion and tests query equivalence. Using iterative subsequence generation, we can always find a minimal query and we formally prove this guarantee. We also propose an extended algorithm that guarantees the minimality for the tree pattern query, which is a linear path query with branching predicates. These methods have been prototyped in a full-fledged object-relational DBMS. The experimental results using real and synthetic data sets show the practicality of our method.     

Efficient Processing of Distributed Twig Queries Based on Node Distribution

Massive XML data are increasingly generated for the representation, storage and exchange of web information. Twig query processing over massive XML data has become a research focus. However, most traditional algorithms cannot be directly implemented in a distributed manner. Some of the existing distributed algorithms generate a lot of useless intermediate results and execute many join operations of partial results in most cases; others require the priori knowledge of query pattern before XML partition, storage and query processing, which is impractical in the cases of large-scale data or frequent incoming new queries. To improve efficiency and scalability, in this paper, we propose a 3-phase distributed algorithm DisT3 based on node distribution mechanism to avoid unnecessary intermediate results. Furthermore, we propose a lightweight local index ReP with an enhanced XML partitioning approach using arbitrary partitioning strategy, and based on ReP we propose an improved 2-phase distributed algorithm DisT2ReP to further reduce the communication cost. After the performance guarantees are analyzed, extensive experiments are conducted to verify the efficiency and scalability of our proposed algorithms in distributed twig query applications.     

面向信息网模型的动态数据划分算法

针对分布式信息网数据库管理系统中因跨节点的复杂查询带来的昂贵通信开销,提出一种基于信息网模型和查询的数据动态划分算法。该算法根据信息网模型的关系特性和历史关系信息得到数据之间的初始关联,并结合历史查询信息挖掘数据之间的潜在关联,将关联性较强的数据动态调整到同一个处理节点上,使复杂查询跨节点的数量减少。最后,在标准合成数据集WatDiv上进行大量的实验评估。实验结果表明：在保证节点之间的对象个数和关系对占比负载均衡的情况下,该算法在周期内的查询时间与一致性哈希算法相比缩短了35%~55%,并将多个周期相同查询的时间波动控制在5%~10%,保证了复杂查询的稳定性。