The smart grid has caught great attentions in recent years, which is poised to transform a centralized, producer-controlled network to a decentralized, consumer- interactive network that＇s supported by fine-grained m...The smart grid has caught great attentions in recent years, which is poised to transform a centralized, producer-controlled network to a decentralized, consumer- interactive network that＇s supported by fine-grained monitoring. Large-scale WSNs （Wireless Sensor Networks） have been considered one of the very promising technologies to support the implementation of smart grid. WSNs are applied in almost every aspect of smart grid, including power generation, power transmission, power distribution, power utilization and power dispatch, and the data query processing of ＇WSNs in power grid＇ become an hotspot issue due to the amount of data of power grid is very large and the requirement of response time is very high. To meet the demands, top-k query processing is a good choice, which performs the cooperative query by aggregating the database objects＇ degree of match for each different query predicate and returning the best k matching objects. In this paper, a framework that can effectively apply top-k query to wireless sensor network in smart grid is proposed, which is based on the cluster-topology sensor network. In the new method, local indices are used to optimize the necessary query routing and process intermediate results inside the cluster to cut down the data traffic, and the hierarchical join query is executed based on the local results.Besides, top-k query results are verified by the clean-up process, and two schemes are taken to deal with the problem of node＇s dynamicity, which further reduce communication cost. Case studies and experimental results show that our algorithm has outperformed the current existing one with higher quality results and better efficiently.展开更多
Top-k ranking of websites according to traffic volume is important for Internet Service Providers(ISPs) to understand network status and optimize network resources. However, the ranking result always has a big deviati...Top-k ranking of websites according to traffic volume is important for Internet Service Providers(ISPs) to understand network status and optimize network resources. However, the ranking result always has a big deviation with actual rank for the existence of unknown web traffic, which cannot be identified accurately under current techniques. In this paper, we introduce a novel method to approximate the actual rank. This method associates unknown web traffic with websites according to statistical probabilities. Then, we construct a probabilistic top-k query model to rank websites. We conduct several experiments by using real HTTP traffic traces collected from a commercial ISP covering an entire city in northern China. Experimental results show that the proposed techniques can reduce the deviation existing between the ground truth and the ranking results vastly. In addition, we find that the websites providing video service have higher ratio of unknown IP as well as higher ratio of unknown traffic than the websites providing text web page service. Specifically, we find that the top-3 video websites have more than 90% of unknown web traffic. All these findings are helpful for ISPs understanding network status and deploying Content Distributed Network(CDN).展开更多
There have been many researches and semantics in answering top-k queries on uncertain data in various applications. However, most of these semantics must consume much of their time in computing position probability. O...There have been many researches and semantics in answering top-k queries on uncertain data in various applications. However, most of these semantics must consume much of their time in computing position probability. Our approach to support various top-k queries is based on position probability distribution （PPD） sharing. In this paper, a PPD-tree structure and several basic operations on it are proposed to support various top-k queries. In addition, we proposed an approximation method to improve the efficiency of PPD generation. We also verify the effectiveness and efficiency of our approach by both theoretical analysis and experiments.展开更多
In the XML community, exact queries allow users to specify exactly what they want to check and/or retrieve in an XML document. When they are applied to a semi-structured document or to a document with an overly comple...In the XML community, exact queries allow users to specify exactly what they want to check and/or retrieve in an XML document. When they are applied to a semi-structured document or to a document with an overly complex model, the lack or the ignorance of the explicit document model (DTD—Document Type Definition, Schema, etc.) increases the risk of obtaining an empty result set when the query is too specific, or, too large result set when it is too vague (e.g. it contains wildcards such as “*”). The reason is that in both cases, users write queries according to the document model they have in mind;this can be very far from the one that can actually be extracted from the document. Opposed to exact queries, preference queries are more flexible and can be relaxed to expand the search space during their evaluations. Indeed, during their evaluation, certain constraints (the preferences they contain) can be relaxed if necessary to avoid precisely empty results;moreover, the returned answers can be filtered to retain only the best ones. This paper presents an algorithm for evaluating such queries inspired by the TreeMatch algorithm proposed by Yao et al. for exact queries. In the proposed algorithm, the best answers are obtained by using an adaptation of the Skyline operator (defined in relational databases) in the context of documents (trees) to incrementally filter into the partial solutions set, those which satisfy the maximum of preferential constraints. The only restriction imposed on documents is No-Self-Containment.展开更多
The purpose of this work aims is to automatically build top-k(the number of suggested results)light weight service based systems(LitSBSs)on the basis of user-given keywords.Compared with our previous work,we use a sco...The purpose of this work aims is to automatically build top-k(the number of suggested results)light weight service based systems(LitSBSs)on the basis of user-given keywords.Compared with our previous work,we use a score(oscore)to evaluate the keyword matching degree and QoS performance of a service so that we could find top-k LitSBSs with both high keyword matching degree and great QoS performance at the same time.In addition,to guarantee the quality of found top-k LitSBSs and improve the time efficiency,we redesign the database-driven algorithm(LitDB).We add the step of referential services selecting into the process of the LitDB,which could prioritize services with high quality(high keyword matching degree and great QoS performance).We design comprehensive experiments to demonstrate the great time performance of LitDB.展开更多
With the rapid growth of spatial data,POI(Point of Interest)is becoming ever more intensive,and the text description of each spatial point is also gradually increasing.The traditional query method can only address the...With the rapid growth of spatial data,POI(Point of Interest)is becoming ever more intensive,and the text description of each spatial point is also gradually increasing.The traditional query method can only address the problem that the text description is less and single keyword query.In view of this situation,the paper proposes an approximate matching algorithm to support spatial multi-keyword.The fuzzy matching algorithm is integrated into this algorithm,which not only supports multiple POI queries,but also supports fault tolerance of the query keywords.The simulation results demonstrate that the proposed algorithm can improve the accuracy and efficiency of query.展开更多
To efficiently retrieve relevant document from the rapid proliferation of large information collections, a novel immune algorithm for document query optimization is proposed. The essential ideal of the immune algorith...To efficiently retrieve relevant document from the rapid proliferation of large information collections, a novel immune algorithm for document query optimization is proposed. The essential ideal of the immune algorithm is that the crossover and mutation of operator are constructed according to its own characteristics of information retrieval. Immune operator is adopted to avoid degeneracy. Relevant documents retrieved are merged to a single document list according to rank formula. Experimental results show that the novel immune algorithm can lead to substantial improvements of relevant document retrieval effectiveness.展开更多
近年来,基于位置服务的技术迅猛发展,产生了海量的路网轨迹数据。而路径范围查询作为一种路网轨迹查询类型,是支持其他查询类型的基础。为了实现对海量路网轨迹数据的高效索引,同时提供精确的路径范围查询服务,提出了一种基于道格拉斯-...近年来,基于位置服务的技术迅猛发展,产生了海量的路网轨迹数据。而路径范围查询作为一种路网轨迹查询类型,是支持其他查询类型的基础。为了实现对海量路网轨迹数据的高效索引,同时提供精确的路径范围查询服务,提出了一种基于道格拉斯-普克算法的学习型索引结构(Douglas-Peuker Based Learned Index Structure,DPLI)。首先将轨迹数据分为多个轨迹段,然后取轨迹段中的点作为轨迹数据的表征,利用映射函数将其映射为一维映射值序列,而后根据键值数量将其划分为多个数据分片。在分片内将首尾数据组成一条线段,然后计算其余数据点距离线段的拟合误差,将超过误差阈值的数据点作为新的线段端点,递归分割原有的直线段,直到所有数据点的拟合误差小于阈值,从而拟合分段线性函数。采用多个路网数据和轨迹数据进行了充分的实验,实验结果表明:与传统索引方法相比,DPLI具有更快的构建效率和磁盘访问效率;与学习索引方法相比,DPLI保持了构建效率的优势,并且达到了100%查询召回率。展开更多
文摘The smart grid has caught great attentions in recent years, which is poised to transform a centralized, producer-controlled network to a decentralized, consumer- interactive network that＇s supported by fine-grained monitoring. Large-scale WSNs （Wireless Sensor Networks） have been considered one of the very promising technologies to support the implementation of smart grid. WSNs are applied in almost every aspect of smart grid, including power generation, power transmission, power distribution, power utilization and power dispatch, and the data query processing of ＇WSNs in power grid＇ become an hotspot issue due to the amount of data of power grid is very large and the requirement of response time is very high. To meet the demands, top-k query processing is a good choice, which performs the cooperative query by aggregating the database objects＇ degree of match for each different query predicate and returning the best k matching objects. In this paper, a framework that can effectively apply top-k query to wireless sensor network in smart grid is proposed, which is based on the cluster-topology sensor network. In the new method, local indices are used to optimize the necessary query routing and process intermediate results inside the cluster to cut down the data traffic, and the hierarchical join query is executed based on the local results.Besides, top-k query results are verified by the clean-up process, and two schemes are taken to deal with the problem of node＇s dynamicity, which further reduce communication cost. Case studies and experimental results show that our algorithm has outperformed the current existing one with higher quality results and better efficiently.
基金supported by 111 Project of China under Grant No.B08004
文摘Top-k ranking of websites according to traffic volume is important for Internet Service Providers(ISPs) to understand network status and optimize network resources. However, the ranking result always has a big deviation with actual rank for the existence of unknown web traffic, which cannot be identified accurately under current techniques. In this paper, we introduce a novel method to approximate the actual rank. This method associates unknown web traffic with websites according to statistical probabilities. Then, we construct a probabilistic top-k query model to rank websites. We conduct several experiments by using real HTTP traffic traces collected from a commercial ISP covering an entire city in northern China. Experimental results show that the proposed techniques can reduce the deviation existing between the ground truth and the ranking results vastly. In addition, we find that the websites providing video service have higher ratio of unknown IP as well as higher ratio of unknown traffic than the websites providing text web page service. Specifically, we find that the top-3 video websites have more than 90% of unknown web traffic. All these findings are helpful for ISPs understanding network status and deploying Content Distributed Network(CDN).
基金Supported by the National High Technology Research and Development Program of China(863 Program 2012AA011004)the National Natural Science Foundation of China(61232002,61202033)Natural Science Foundation of Hubei Province(2011CDB448)
文摘There have been many researches and semantics in answering top-k queries on uncertain data in various applications. However, most of these semantics must consume much of their time in computing position probability. Our approach to support various top-k queries is based on position probability distribution （PPD） sharing. In this paper, a PPD-tree structure and several basic operations on it are proposed to support various top-k queries. In addition, we proposed an approximation method to improve the efficiency of PPD generation. We also verify the effectiveness and efficiency of our approach by both theoretical analysis and experiments.
文摘In the XML community, exact queries allow users to specify exactly what they want to check and/or retrieve in an XML document. When they are applied to a semi-structured document or to a document with an overly complex model, the lack or the ignorance of the explicit document model (DTD—Document Type Definition, Schema, etc.) increases the risk of obtaining an empty result set when the query is too specific, or, too large result set when it is too vague (e.g. it contains wildcards such as “*”). The reason is that in both cases, users write queries according to the document model they have in mind;this can be very far from the one that can actually be extracted from the document. Opposed to exact queries, preference queries are more flexible and can be relaxed to expand the search space during their evaluations. Indeed, during their evaluation, certain constraints (the preferences they contain) can be relaxed if necessary to avoid precisely empty results;moreover, the returned answers can be filtered to retain only the best ones. This paper presents an algorithm for evaluating such queries inspired by the TreeMatch algorithm proposed by Yao et al. for exact queries. In the proposed algorithm, the best answers are obtained by using an adaptation of the Skyline operator (defined in relational databases) in the context of documents (trees) to incrementally filter into the partial solutions set, those which satisfy the maximum of preferential constraints. The only restriction imposed on documents is No-Self-Containment.
文摘The purpose of this work aims is to automatically build top-k(the number of suggested results)light weight service based systems(LitSBSs)on the basis of user-given keywords.Compared with our previous work,we use a score(oscore)to evaluate the keyword matching degree and QoS performance of a service so that we could find top-k LitSBSs with both high keyword matching degree and great QoS performance at the same time.In addition,to guarantee the quality of found top-k LitSBSs and improve the time efficiency,we redesign the database-driven algorithm(LitDB).We add the step of referential services selecting into the process of the LitDB,which could prioritize services with high quality(high keyword matching degree and great QoS performance).We design comprehensive experiments to demonstrate the great time performance of LitDB.
文摘With the rapid growth of spatial data,POI(Point of Interest)is becoming ever more intensive,and the text description of each spatial point is also gradually increasing.The traditional query method can only address the problem that the text description is less and single keyword query.In view of this situation,the paper proposes an approximate matching algorithm to support spatial multi-keyword.The fuzzy matching algorithm is integrated into this algorithm,which not only supports multiple POI queries,but also supports fault tolerance of the query keywords.The simulation results demonstrate that the proposed algorithm can improve the accuracy and efficiency of query.
基金TheNationalHigh TechDevelopment 863ProgramofChina (No .2 0 0 3AA1Z2 610 )
文摘To efficiently retrieve relevant document from the rapid proliferation of large information collections, a novel immune algorithm for document query optimization is proposed. The essential ideal of the immune algorithm is that the crossover and mutation of operator are constructed according to its own characteristics of information retrieval. Immune operator is adopted to avoid degeneracy. Relevant documents retrieved are merged to a single document list according to rank formula. Experimental results show that the novel immune algorithm can lead to substantial improvements of relevant document retrieval effectiveness.
文摘近年来,基于位置服务的技术迅猛发展,产生了海量的路网轨迹数据。而路径范围查询作为一种路网轨迹查询类型,是支持其他查询类型的基础。为了实现对海量路网轨迹数据的高效索引,同时提供精确的路径范围查询服务,提出了一种基于道格拉斯-普克算法的学习型索引结构(Douglas-Peuker Based Learned Index Structure,DPLI)。首先将轨迹数据分为多个轨迹段,然后取轨迹段中的点作为轨迹数据的表征,利用映射函数将其映射为一维映射值序列,而后根据键值数量将其划分为多个数据分片。在分片内将首尾数据组成一条线段,然后计算其余数据点距离线段的拟合误差,将超过误差阈值的数据点作为新的线段端点,递归分割原有的直线段,直到所有数据点的拟合误差小于阈值,从而拟合分段线性函数。采用多个路网数据和轨迹数据进行了充分的实验,实验结果表明:与传统索引方法相比,DPLI具有更快的构建效率和磁盘访问效率;与学习索引方法相比,DPLI保持了构建效率的优势,并且达到了100%查询召回率。
