8426233
Gradient Boundary Detection for Time Series Snapshot Construction in Sensor Networks
In many applications of sensor networks, the sink needs to keep track of the history of sensed data of a monitored region for scientific analysis or supporting historical queries. We call these historical data a time series of value distributions or snapshots. Obviously, to build the time series snapshots by requiring all of the sensors to transmit their data to the sink periodically is not energy efficient. In this paper, we introduce the idea of gradient boundary and propose the gradient boundary detection (GBD) algorithm to construct these time series snapshots of a monitored region. In GBD, a monitored region is partitioned into a set of subregions and all sensed data in one subregion are within a predefined value range, namely, the gradient interval. Sensors located on the boundaries of the subregions are required to transmit the data to the sink and, then, the sink recovers all subregions to construct snapshots of the monitored area. In this process, only the boundary sensors transmit their data and, therefore, energy consumption is greatly reduced. The simulation results show that GBD is able to build snapshots with a comparable accuracy and has up to 40 percent energy savings compared with the existing approaches for large gradient intervals.
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.
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.
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.
6162473
The Effects of Mobility and Redundancy on Wireless Video Streaming over MANETs
This study examines the extended use of different coding schemes (Scalable vs. Multiple Description or MD) in different video formats (MPEG vs. Motion JPEG or MJPEG) in a Mobile Ad Hoc Network (MANET) environment and proposes a set of redundancy solutions at different coding levels. Simulations and analysis demonstrate and explain the relationship among the coding schemes, video formats, level and amount of redundancy, mobility of mobile devices, CPU load and battery life and frame loss rate at the receiver side. Finally, two practical scenarios are used to illustrate these findings and proposed solutions.
22672181
Inclusion Test Algorithms for One-Unambiguous Regular Expressions
One-unambiguous regular expressions are used in DTD. It is known that inclusion for one-unambiguous regular expressions is in PTIME. However, there has been no study on algorithms for the inclusion. In this paper we present algorithms for checking inclusion of one-unambiguous regular expressions. A classical way is based on automata, following which one algorithm is provided and improvements are given. The other algorithm is based on derivatives, utilizing a property introduced here that the number of derivatives of a one-unambiguous regular expression is finite. We conducted preliminary experiments by implementing typechecking of XML using the algorithms. The results show that typechecking using the new algorithms is more efficient than the typechecking used for XDuce.
18409692
An Interference Free Data Aggregation Protocol for Clustered Wireless Sensor Networks
An interference free cluster-based TDMA protocol (IFCT) for wireless sensor networks was proposed in previous study. IFCT uses a distributed frame assignment algorithm (FA) to assign different frames for neighboring clusters. In this paper, we propose a interference-free data aggregation protocol (IFDA) for clustered based TDMA wireless sensor networks based on IFCT. IFDA alters the FA algorithm of IFCT and uses a channel expansion algorithm CE to increase average per cluster channel usage ratio. The expected message cost for both FA and CE algorithms of IFDA is O(1). The expected running time complexity for both FA and CE is bound to polynomial of D, where D is the maximum neighboring cluster count of a cluster. Simulation results show that FA algorithm of IFDA requires less message cost than that of IFCT. Besides, IFDA improves the average per cluster channel usage ratio by about 80%compared with IFCT.
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.
29666362
Algebraic Laws for BSP Programming
The Bulk-Synchronous Parallel (BSP) model of computation reflects the capabilities and costs of communication on a wide range of general-purpose parallel architectuers. Thus it allows general-purpose parallel software and hardware to be developed independently of one another; much as the von Neumann model provides the same facility for sequential computation. This paper presents a simple programming notation for shared-memory programming, based upon BSP constructs. The notation is defined formally by its effect upon process states. Algebraic laws are given which allow program derivation. A further set of laws allow transformation of finite programs to a normal form.