Area Query Processing Based on Gray Code in Wireless Sensor Networks

Area query processing is significant for various applications of wireless sensor networks since it can request information of particular areas in the monitored environment. Existing query processing techniques cannot solve area queries. Intuitively, centralized processing on Base Station can accomplish area queries via collecting information from all sensor nodes. However, this method is not suitable for wireless sensor networks with limited energy since a large amount of energy is wasted for reporting useless data. This motivates us to propose an energy-efficient in-network area query processing scheme. In our scheme, the monitored area is partitioned into grids, and a unique gray code number is used to represent a Grid ID (GID), which is also an effective way to describe an area. Furthermore, a reporting tree is constructed to process area merging and data aggregations. Based on the properties of GIDs, subareas can be merged easily and useless data can be discarded as early as possible to reduce energy consumption. For energy-efficiently answering continuous queries, we also design an incremental update method to continuously generate query results. In essence, all of these strategies are pivots to conserve energy consumption. With a thorough simulation study, it is shown that our scheme is effective and energy-efficient.     

A New Generalized Similarity-Based Topic Distillation Algorithm

The procedure of hypertext induced topic search based on a semantic relation model is analyzed, and the reason for the topic drift of HITS algorithm was found to prove that Web pages are projected to a wrong latent semantic basis. A new concept-generalized similarity is introduced and, based on this, a new topic distillation algorithm GSTDA（generalized similarity based topic distillation algorithm） was presented to improve the quality of topic distillation. GSTDA was applied not only to avoid the topic drift, but also to explore relative topics to user query. The experimental results on 10 queries show that GSTDA reduces topic drift rate by 10% to 58% compared to that of HITS（hypertext induced topic search） algorithm, and discovers several relative topics to queries that have multiple meanings.     

一种无线传感器网络中基于缓冲区管理的查询处理方法

对于大型无线传感器网络中要求同时支持大量的周期查询和ad hoc查询的软实时应用,提出了一种查询处理方法.设计网络存储结构,为查询处理设置合适的执行区域使其形成查询处理缓冲区,缓冲区内的节点映射了远程节点数据,并使查询和数据在缓冲区汇聚,及时得到处理.基于排队论建立缓冲区中查询任务管理模型,设计其优化策略,得到缓冲区的合适宽度和位置,并基于此设计查询处理算法.实验结果表明,该方法可以降低查询错失率并节约能量.     

A Deep Web Query Interfaces Classification Method Based on RBF Neural Network

This paper proposes a new approach for classification for query interfaces of Deep Web, which extracts features from the form＇s text data on the query interfaces, assisted with the synonym library, and uses radial basic function neural network （RBFNN） algorithm to classify the query interfaces. The applied RBFNN is a kind of effective feed-forward artificial neural network, which has a simple networking structure but features with strength of excellent nonlinear approximation, fast convergence and global convergence. A TEL_8 query interfaces＇ data set from UIUC on-line database is used in our experiments, which consists of 477 query interfaces in 8 typical domains. Experimental results proved that the proposed approach can efficiently classify the query interfaces with an accuracy of 95.67%.     

Twig Pattern Matching Based on Compressed Path Labeling Scheme

Holistic twig query processing techniques based on region encoding have been developed to minimize the intermediate results, namely, those root-to-leaf path matches that are not in the final twig results. These algorithms have to scan all the streams of tags in query patterns. However, useless path matches cannot be completely avoided. TJFast which is based on the labeling scheme of Extended Dewey has been proposed to avoid useless intermediate results, and it only needs to access the labels of the leaf query nodes. However, it don＇t concern about the characteristics of elements with the same parent, and it has to merge join all the intermediate results which are evaluated during the first phrase. We propose a new labeling scheme to compress the XML elements which have the same characteristic. Based on the compressed path-labeled streams, a new novel holistic twig query algorithm named CPJoin is designed. Finally, implementation results are provided to show that CPJoin has good performance on both real and synthetic data.     

Distributed Aggregation Algorithms for Mobile Sensor Networks with Group Mobility Model

In many applications of mobile sensor networks, such as water flow monitoring and disaster rescue, the nodes in the network can move together or separate temporarily. The dynamic network topology makes traditional spanning-tree-based aggregation algorithms invalid in mobile sensor networks. In this paper, we first present a distributed clustering algorithm which divides mobile sensor nodes into several groups, and then propose two distributed aggregation algorithms, Distance-AGG (Aggregation based on Distance), and Probability-AGG (Aggregation based on Probability). Both of these two algorithms conduct an aggregation query in three phases: query dissemination, intra-group aggregation, and inter-group aggregation. These two algorithms are efficient especially in mobile networks. We evaluate the performance of the proposed algorithms in terms of aggregation accuracy, energy efficiency, and query delay through ns-2 simulations. The results show that Distance-AGG and Probability-AGG can obtain higher accuracy with lower transmission and query delay than the existing aggregation algorithms.     

Automatic Question Answering from Web Documents

A passage retrieval strategy for web-based question answering （QA） systems is proposed in our QA system. It firstly analyzes the question based on semantic patterns to obtain its syntactic and semantic information and then form initial queries. The queries are used to retrieve documents from the World Wide Web （WWW） using the Google search engine. The queries are then rewritten to form queries for passage retrieval in order to improve the precision. The relations between keywords in the question are employed in our query rewrite method. The experimental result on the question set of the TREC-2003 passage task shows that our system performs well for factoid questions.     

Web Database Query Interface Annotation Based on User Collaboration

A vision based query interface annotation meth od is used to relate attributes and form elements in form based web query interfaces, this method can reach accuracy of 82%. And a user participation method is used to tune the result; user can answer ＂yes＂ or ＂no＂ for existing annotations, or manually annotate form elements. Mass feedback is added to the annotation algorithm to produce more accurate result. By this approach, query interface annotation can reach a perfect accuracy.     

TwigStack^＋： Holistic Twig Join Pruning Using Extended Solution Extension

XML has been used extensively in many applications as a de facto standard for information representation and exchange over internet. Huge volumes of data are organized or exported in tree-structured form and the desired information can be got by traversing the whole tree structure using a twig pattern query. A new definition, Extended Solution Extension, is proposed in this paper to check the usefulness of an element from both forward and backward directions. Then a novel Extended Solution Extension based algorithm, TwigStack^＋, is also proposed to reduce the query processing cost, simply because it can check whether other elements can be processed together with the current one. Compared with existing methods, query evaluation cost can be largely reduced. The experimental results on various datasets indicate that the proposed algorithm performs significantly better than the existing ones.     

Dynamically Computing Approximate Frequency Counts in Sliding Window over Data Stream

This paper presents two one-pass algorithms for dynamically computing frequency counts in sliding window over a data stream-computing frequency counts exceeding user-specified threshold ε. The first algorithm constructs subwindows and deletes expired sub-windows periodically in sliding window, and each sub-window maintains a summary data structure. The first algorithm outputs at most 1/ε ＋ 1 elements for frequency queries over the most recent N elements. The second algorithm adapts multiple levels method to deal with data stream. Once the sketch of the most recent N elements has been constructed, the second algorithm can provides the answers to the frequency queries over the most recent n （ n≤N） elements. The second algorithm outputs at most 1/ε ＋ 2 elements. The analytical and experimental results show that our algorithms are accurate and effective.     

Automatic user goals identification based on anchor text and click-through data

Understanding the underlying goal behind a user＇s Web query has been proved to be helpful to improve the quality of search. This paper focuses on the problem of automatic identification of query types according to the goals. Four novel entropy-based features extracted from anchor data and click-through data are proposed, and a support vector machines （SVM） classifier is used to identify the user＇s goal based on these features. Experi- mental results show that the proposed entropy-based features are more effective than those reported in previous work. By combin- ing multiple features the goals for more than 97% of the queries studied can be correctly identified. Besides these, this paper reaches the following important conclusions： First, anchor-based features are more effective than click-through-based features; Second, the number of sites is more reliable than the number of links; Third, click-distribution- based features are more effective than session-based ones.     

移动对象范围监视查询研究

范围监视查询在空间数据库的相关领域中具有越来越广泛的应用,基于此提出了一种范围监视查询管理技术,该技术可以较好地适应大量移动对象的环境,同时有效地缩减了移动通信的成本,减轻了服务器的负载.     

复合滑动窗口连接算法

滑动窗口是对数据流进行连续查询处理、得出近似查询结果的一种常用的数据采样技术．连续查询处理的执行方式有2类：一类是立即执行方式；一类是周期执行方式、在已有的研究工作中，基于滑动窗口的连接算法都是适用于立即执行的连续查询．提出了适用于周期执行的连续查询的复合滑动窗口连接算法，即CSWSNLJ算法和CSWSNHJ算法．理论分析和试验结果表明CSWSNHJ算法具有较好的性能．     

基于启发函数的网格数据库查询算法

查询处理技术是网格数据库研究的核心,但是传统的查询处理技术无法适应动态变化的网格环境,导致网格资源利用率低、查询效率不高。给出了基于副本的网格数据库查询处理代价模型和两种查询处理算法,利用不同的数据集和网格环境参数进行实验验证。实验结果表明,基于启发函数的网格数据库查询算法在一定程度上提高了查询处理效率,生成子查询时间代价为O(n),消耗时间比采用穷举策略下降10%左右。     

基于多目标规划的WSN路径动态选择算法

为解决无线传感器网络中查询的能量有效和实时性之间的矛盾,提出一种基于多目标规划理论的动态路径选择算法(MOPEH).该算法结合了最低能耗路由策略(ME)和最小跳步数路由策略(MH),运用多目标规划模型,将能量代价和传输时延同时作为路由算法的设计目标,利用深度优先搜索策略建立了节点间的所有可行路径集合,并从中选择能耗低于平均能耗的路径.根据查询要求设定网络性能函数,动态调整两项性能指标,从可行路径集合中选择满足要求的路径,得到最优解.实验证明该算法能够能量有效地处理实时查询.     

KNN查询处理算法性能研究

KNN查询是多媒体数据库管理系统中最具代表性的查询方式之一,它将k个与查询点最接近的对象作为查询结果返回。对于树型多维索引结构,KNN查询处理算法主要有RKV算法和HS算法。本文针对这两种不同处理算法进行了性能研究,通过试验确定了算法的不同适用场景,最后就应用中的KNN查询实现给出了相应的建议。     

传感器网络中基于过滤的概率Skyline查询算法

针对感知数据固有的不确定性问题,研究了无线传感器网络中概率Skyline查询的处理与优化技术.首先分析了概率Skyline查询的性质,证明了概率Skyline查询的不可分解性,因而无法直接利用网内计算方法求解;进而提出了无线传感器网络中基于过滤的概率Skyline查询处理算法(filter basedprobabilisticSkylinequeryprocessingalgorithminWSN,FPSP).FPSP算法将感知数据划分为候选数据、相关数据和无关数据;只需要候选数据和相关数据即可求得概率Skyline查询结果,可以在传感器节点过滤无关数据以避免大量的数据网内传输.仿真实验结果表明,FPSP算法可以有效降低传感器节点的数据传输量,极大地延长了无线传感器网络的使用寿命.     

一种数据流上基于截止期的多查询过载预测模型

为保证数据流上查询处理的实时性要求,定义了截止期作为连续查询的实时性约束,提出了一种数据流上基于截止期的多查询过载预测模型.模型预测的过载点给出了能够保证数据流系统内所有查询满足各自截止期的临界情况.在多查询环境下,通过找到某一查询作为截止期瓶颈,使得该查询处理结束后剩余查询的处理能力正好大于系统的输入流速,从而计算出过载点.仿真实验结果证明,该模型预测出的过载点能够保证所有查询满足各自的截止期,并且预测算法具有良好的准确性和计算复杂性.     

KDS-CM： A Cache Mechanism Based on Top-K Data Source for Deep Web Query

Caching is an important technique to enhance the efficiency of query processing. Unfortunately, traditional caching mechanisms are not efficient for deep Web because of storage space and dynamic maintenance limitations. In this paper, we present on providing a cache mechanism based on Top-K data source （KDS-CM） instead of result records for deep Web query. By integrating techniques from IR and Top-K, a data reorganization strategy is presented to model KDS-CM. Also some measures about cache management and optimization are proposed to improve the performances of cache effectively. Experimental results show the benefits of KDS-CM in execution cost and dynamic maintenance when compared with various alternate strategies.