1591125
Multi-scale histograms for answering queries over time series data
Similarity-based time series data retrieval has been used in many real world applications, such as stock data or weather data analysis. Two types of queries on time series data are generally studied: pattern existence queries and exact match queries. Here, we describe a technique to answer both pattern existence queries and exact match queries. A typical application that needs answers to both queries is an interactive analysis of time series data. We propose a histogram-based representation to approximate time series data.
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.
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.
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.
18717814
Research on Distributed Data Mining Tool Used in Control System
In this paper, A distributed data mining tool that suitable for distributed and isomeric database environment of intelligent control system by borrowing ideas from architecture of grid is introduced. It can also perform incremental data mining based on history mining result. This tool makes full use of Metadata of each kind of resources. The resources associated in the data mining are all packed into form of web service, which is give a description by respective attribute document of the XML format. SOAP takes charge of the communication between the separated parts of the whole data mining process.
616754
Automated Planning of CPICH Power for Enhancing HSDPA Performance at Cell Edges with Preserved Control of R99 Soft Handover
We present and demonstrate a novel approach for automated planning of common pilot channel (CPICH) power in mobile networks with co-existing HSDPA and R99 services. CPICH power allocation greatly influences the cell coverage pattern. A conventional strategy is to uniformly allocate a constant proportion of the total power to CPICH. We study non-uniform CPICH and optimize its allocation for enhancing HSDPA performance. We focus on HSDPA performance at cell edges, where user throughput is typically very low. Our approach is based on a linear-integer mathematical model; solving the model results in a power allocation that both ensures CPICH coverage and optimizes HSDPA performance at cell edges. Moreover, the model allows for precise control of soft handover (SHO) regions for R99 service. Experimental results show that our approach yields significant enhancement of HSDPA performance at cell edges with preserved R99 SHO control.
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.
7211665
Dynamic data dependence tracking and its application to branch prediction
To continue to improve processor performance, microarchitects seek to increase the effective instruction level parallelism (ILP) that can be exploited in applications. A fundamental limit to improving ILP is data dependences among instructions. If data dependence information is available at run-time, there are many uses to improve ILP. Prior published examples include decoupled branch execution architectures and critical instruction detection. In this paper, we describe an efficient hardware mechanism to dynamically track the data dependence chains of the instructions in the pipeline. This information is available on a cycle-by-cycle basis to the microengine for optimizing its performance. We then use this design in a new value-based branch prediction design using available register value information (ARVI). From the use of data dependence information, the ARVI branch predictor has better prediction accuracy over a comparably sized hybrid branch predictor With ARVI used as the second-level branch predictor the improved prediction accuracy results in a 12.6% performance improvement on average across the SPEC95 integer benchmark suite.
22510443
Universal Approximation and QoS Violation Application of Extreme Learning Machine
Neural networks have been successfully applied to many applications due to their approximation capability. However, complicated network structures and algorithms will lead to computational and time-consuming burdens. In order to satisfy demanding real-time requirements, many fast learning algorithms were explored in the past. Recently, a fast algorithm, Extreme Learning Machine (ELM) (Huang et al. 70:489–501, 2006) was proposed. Unlike conventional algorithms whose neurons need to be tuned, the input-to-hidden neurons of ELM are randomly generated. Though a large number of experimental results have shown that input-to-hidden neurons need not be tuned, there lacks a rigorous proof whether ELM possesses the universal approximation capability. In this paper, based on the universal approximation property of an orthonormal method, we firstly illustrate the equivalent relationship between ELM and the orthonormal method, and further prove that neural networks with ELM are also universal approximations. We also successfully apply ELM to the identification of QoS violation in the multimedia transmission.