14090386
In-network Outlier Cleaning for Data Collection in Sensor Networks
Outliers are very common in the environmental data monitored by a sensor network consisting of many inexpensive, low fidelity, and frequently failed sensors. The limited battery power and costly data transmission have introduced a new challenge for outlier cleaning in sensor networks: it must be done innetwork to avoid spending energy on transmitting outliers. In this paper, we propose an in-network outlier cleaning approach, including wavelet based outlier correction and neighboring DTW(Dynamic Time Warping) distance-based outlier removal. The cleaning process is accomplished during multi-hop data forwarding process, and makes use of the neighboring relation in the hop-count based routing algorithm. Our approach guarantees that most of the outliers can be either corrected, or removed from further transmission within 2 hops. We have simulated a spatialtemporal correlated environmental area, and evaluated the outlier cleaning approach in it. The results show that our approach can effectively clean the sensing data and reduce outlier traffic.
262231
Monochromatic and bichromatic reverse skyline search over uncertain databases
Reverse skyline queries over uncertain databases have many important applications such as sensor data monitoring and business planning. Due to the existence of uncertainty in many real-world data, answering reverse skyline queries accurately and efficiently over uncertain data has become increasingly important. In this paper, we model the probabilistic reverse skyline query on uncertain data, in both monochromatic and bichromatic cases, and propose effective pruning methods to reduce the search space of query processing. Moreover, efficient query procedures have been presented seamlessly integrating the proposed pruning methods. Extensive experiments have demonstrated the efficiency and effectiveness of our proposed approach with various experimental settings.
8931794
Speed up semantic search in p2p networks
Peer-to-peer architectures become popular in modern massively distributed systems, which are often in very large scale and contain a huge volume of heterogeneous data. To facilitate the information retrieval process in P2P networks, we consider semantic search approach, where syntax-based queries are shipped to peers based on semantic correlations. Motivated by an interesting experience in Web information retrieval, we propose a novel ontology-based scheme to measure similarity of peer interests accurately and consistently in a decentralized way, and group peers under a scalable hierarchical overlay network. Given queries, our approach either floods them within local peer groups or guides them towards remote groups based on the similarity of interests. Our work overcomes the limitations of the existing P2P hybrid-search approaches by avoiding costly data popularity measurement. Performance evaluation and comparison against baseline algorithms show that our approach provides a better solution for information retrieval in large-scale P2P networks.
7517195
Spotting Significant Changing Subgraphs in Evolving Graphs
Graphs are popularly used to model structural relationships between objects. In many application domains such as social networks, sensor networks and telecommunication, graphs evolve over time. In this paper, we study a new problem of discovering the subgraphs that exhibit significant changes in evolving graphs. This problem is challenging since it is hard to define changing regions that are closely related to the actual changes (i.e., additions/deletions of edges/nodes) in graphs. We formalize the problem, and design an efficient algorithm that is able to identify the changing subgraphs incrementally. Our experimental results on real datasets show that our solution is very efficient and the resultant subgraphs are of high quality.
8704395
Summarization Graph Indexing: Beyond Frequent Structure-Based Approach
Graph is an important data structure to model complex structural data, such as chemical compounds, proteins, and XML documents. Among many graph data-based applications, sub-graph search is a key problem, which is defined as given a query Q, retrieving all graphs containing Q as a sub-graph in the graph database. Most existing sub-graph search methods try to filter out false positives (graphs that are not possible in the results) as many as possible by indexing some frequent sub-structures in graph database, such as [20, 22, 4, 23]. However, due to ignoring the relationships between sub-structures, these methods still admit a high percentage of false positives. In this paper, we propose a novel concept, Summarization Graph, which is a complete graph and captures most topology information of the original graph, such as sub-structures and their relationships. Based on Summarization Graphs, we convert the filtering problem into retrieving objects with set-valued attributes. Moreover, we build an efficient signature file-based index to improve the filtering process. We prove theoretically that the pruning power of our method is larger than existing structure-based approaches. Finally, we show by extensive experimental study on real and synthetic data sets that the size of candidate set generated by Summarization Graph-based approach is only about 50% of that left by existing graph indexing methods, and the total response time of our method is reduced 2-10 times.
9576587
Non-Threshold based Event Detection for 3D Environment Monitoring in Sensor Networks
Event detection is a crucial task for wireless sensor network applications, especially environment monitoring. Existing approaches for event detection are mainly based on some predefined threshold values, and thus are often inaccurate and incapable of capturing complex events. For example, in coal mine monitoring scenarios, gas leakage or water osmosis can hardly be described by the overrun of specified attribute thresholds, but some complex pattern in the full-scale view of the environmental data. To address this issue, we propose a non-threshold based approach for the real 3D sensor monitoring environment. We employ energy-efficient methods to collect a time series of data maps from the sensor network and detect complex events through matching the gathered data to spatio-temporal data patterns. Finally, we conduct trace driven simulations to prove the efficacy and efficiency of this approach on detecting events of complex phenomena from real-life records.
2891159
Convex incremental extreme learning machine
Unlike the conventional neural network theories and implementations, Huang et al. [Universal approximation using incremental constructive feedforward networks with random hidden nodes, IEEE Transactions on Neural Networks 17(4) (2006) 879-892] have recently proposed a new theory to show that single-hidden-layer feedforward networks (SLFNs) with randomly generated additive or radial basis function (RBF) hidden nodes (according to any continuous sampling distribution) can work as universal approximators and the resulting incremental extreme learning machine (I-ELM) outperforms many popular learning algorithms. I-ELM randomly generates the hidden nodes and analytically calculates the output weights of SLFNs, however, I-ELM does not recalculate the output weights of all the existing nodes when a new node is added. This paper shows that while retaining the same simplicity, the convergence rate of I-ELM can be further improved by recalculating the output weights of the existing nodes based on a convex optimization method when a new hidden node is randomly added. Furthermore, we show that given a type of piecewise continuous computational hidden nodes (possibly not neural alike nodes), if SLFNs f"n(x)=@?i=1n@b"iG(x,a"i,b"i) can work as universal approximators with adjustable hidden node parameters, from a function approximation point of view the hidden node parameters of such ''generalized'' SLFNs (including sigmoid networks, RBF networks, trigonometric networks, threshold networks, fuzzy inference systems, fully complex neural networks, high-order networks, ridge polynomial networks, wavelet networks, etc.) can actually be randomly generated according to any continuous sampling distribution. In theory, the parameters of these SLFNs can be analytically determined by ELM instead of being tuned.
9389346
Efficient encoding of quasi-cyclic low-density parity-check codes
Efficient Encoding of Quasi-Cyclic Low-Density Parity-Check Codes Quasi-cyclic (QC) low-density parity-check (LDPC) codes form an important subclass of LDPC codes. These codes have encoding advantage over other types of LDPC codes. This paper addresses the issue of efficient encoding of QC-LDPC codes. Two methods are presented to find the generator matrices of QC-LDPC codes in systematic-circulant form from their parity-check matrices given in circulant form. Based on the systematic-circulation form of the generator matrix of a QC-LDPC code, various types of encoding circuits using simple shift registers are devised. It is shown that the encoding complexity of a QC-LDPC code is linearly proportional to the number of parity bits of the code for serial encoding, and to the length of the code for high-speed parallel encoding.
183594
Efficient Type Checking for a Subclass of Regular Expression Types
Type checking is an important problem in statically typed XML processing languages. Most type systems are implemented based on tree automata for the tree structure of XML documents and schemas. It is known that the complexity of inclusion problem for tree automata is in EXPTIME. In fact, most definitions in XML Schema are actually DTDs. The inclusion problem of DTDs can be reduced to inclusion of one-unambiguous regular expressions in DTDs. We have developed a method for type checking that works for regular expression types which are DTDs. The method is based onone-unambiguous regular expressions together with using the information of labels in DTDs, which can work in top-down or bottom-up manner. Although our method supports DTDs only now, it is general and can support more general schemas by integrating with the conventional method of type checking. The experiments show that our method is more efficient in practice.
14979419
QoS-aware routing based on bandwidth estimation for mobile ad hoc networks
Routing protocols for mobile ad hoc networks (MANETs) have been explored extensively in recent years. Much of this work is targeted at finding a feasible route from a source to a destination without considering current network traffic or application requirements. Therefore, the network may easily become overloaded with too much traffic and the application has no way to improve its performance under a given network traffic condition. While this may be acceptable for data transfer, many real-time applications require quality-of-service (QoS) support from the network. We believe that such QoS support can be achieved by either finding a route to satisfy the application requirements or offering network feedback to the application when the requirements cannot be met. We propose a QoS-aware routing protocol that incorporates an admission control scheme and a feedback scheme to meet the QoS requirements of real-time applications. The novel part of this QoS-aware routing protocol is the use of the approximate bandwidth estimation to react to network traffic. Our approach implements these schemes by using two bandwidth estimation methods to find the residual bandwidth available at each node to support new streams. We simulate our QoS-aware routing protocol for nodes running the IEEE 802.11 medium access control. Results of our experiments show that the packet delivery ratio increases greatly, and packet delay and energy dissipation decrease significantly, while the overall end-to-end throughput is not impacted, compared with routing protocols that do not provide QoS support.
17397024
Multi-level secure video streaming over SRTP
In this paper, we propose a set of solutions to four different levels on data selection for encrypting Motion JPEG video frames over SRTP. These solutions are based on our intensive analysis of the JPEG image compression procedure. We select the most important data which contains most information of an image for encryption; in consequence provide a set of balances between security and computation for different hardware environments. Extensive experiments are conducted and performance data has been analyzed to evaluate the proposed solutions. Results show that these solutions are well suited in different scenarios with various computation power and security requirements.