|
TECHNOLOGY : DOT NET
DOMAIN : IEEE TRANSACTIONS ON NETWORKING
|
| S.No | TITLE | ABSTRACT | YEAR |
|
|
An Efficient Adaptive Deadlock-Free Routing Algorithm for Torus Networks. | A deadlock-free minimal routing algorithm called clue is first proposed for VCT (virtual cut-through)-switched tori. Only two virtual channels are required. One channel is applied in the deadlock-free routing algorithm for the mesh sub network based on a known base routing scheme, such as, negative-first or dimension-order routing. | 2012 |
|
|
The Three-Tier Security Scheme in Wireless Sensor Networks with Mobile Sinks | This Paper describes a three-tier general framework that permits the use of any pairwise key predistribution scheme as its basic component. The new frame- work requires two separate key pools, one for the mobile sink to access the network, and one for pairwise key establishment between the sensors. | 2012 |
|
|
Latency Equalization as a New Network Service Primitive | Multiparty interactive network applications such as teleconferencing, network gaming, and online trading are gaining popularity. In addition to end-to-end latency bounds, these applications require that the delay difference among multiple clients of the service is minimized for a good interactive experience. We propose a Latency EQualization (LEQ) service, which equalizes the perceived latency for all clients participating in an interactive network application. | 2012 |
|
|
Efficient Error Estimating Coding: Feasibility and Applications | This paper proposes the novel concept of error estimating coding (EEC). Without correcting the errors in the packet, EEC enables the receiver of the packet to estimate the packet’s bit error rate, which is perhaps the most important meta-information of a partially correct packet. | 2012 |
|
|
Independent Directed Acyclic Graphs for Resilient Multipath Routing | In this paper. Link-independent (node-independent) DAGs satisfy the property that any path from a source to the root on one DAG is link-disjoint (node-disjoint) with any path from the source to the root on the other DAG. Given a network, we develop polynomial-time algorithms to compute link-independent and node-independent DAGs. | 2012 |
|
|
Modeling and Analysis of Communication Networks in Multicluster Systems under Spatio-Temporal Bursty Traffic | Multi cluster systems have emerged as a promising infrastructure for provisioning of cost-effective high-performance computing and communications. Analytical models of communication networks in cluster systems have been widely reported. | 2012 |
|
|
Improving End-to-End Routing Performance of Greedy Forwarding in Sensor Networks | We propose a topology aware routing (TAR) protocol that efficiently encodes a network topology into a low-dimensional virtual coordinate space where hop distances between pairwise nodes are preserved. Based on precise hop distance comparison, TAR can assist greedy forwarding to find the right neighbor that is one hop closer to the destination and achieve high success ratio of packet delivery without location information. | 2012 |
|
|
DCS: Distributed Asynchronous Clock Synchronization in Delay Tolerant Networks | In this paper, we propose distributed asynchronous clock synchronization (DCS) protocol for Delay Tolerant Networks (DTNs). Different from existing clock synchronization protocols, the proposed DCS protocol can achieve global clock synchronization among mobile nodes within the network over asynchronous and intermittent connections with long delays. | 2012 |
|
|
Semantic-Aware Metadata Organization Paradigm in Next-Generation File Systems | This paper proposes a novel decentralized semantic-aware metadata organization, called Smart Store, which exploits semantics of files’ metadata to judiciously aggregate correlated files into semantic-aware groups by using information retrieval tools. | 2012 |
|
|
A Greedy Link Scheduler for Wireless Networks With Gaussian Multiple-Access and Broadcast Channels | In this paper, we address the problem of link scheduling in multihop wireless networks containing nodes with BC and MAC capabilities. We first propose an interference model that extends protocol interference models, originally designed for point-to-point channels, to include the possibility of BCs and MACs. | 2012 |
|
|
Finding Cheap Routes in Prot-Driven Opportunistic Spectrum Access Networks: A Truthful Mechanism Design Approach | In this paper, we explore the economic aspects of routing/relaying in a pro?t-driven opportunistic spectrum access (OSA) network. In this network, primary users lease their licensed spectrum to secondary radio (SR) providers, who in turn provide opportunistic routing/relaying service to end-users if this service is portable. | 2012 |
|
|
MeasuRouting: A Framework for Routing Assisted Traffic Monitoring | In this paper we present a theoretical framework for MeasuRouting. Furthermore, as proofs-of-concept, we present synthetic and practical monitoring applications to showcase the utility enhancement achieved with MeasuRouting. | 2012 |
|
|
AMPLE: An Adaptive Traffic Engineering System Based on Virtual Routing Topologies | In this article, we introduce AMPLE – an efficient traffic engineering and management system that performs adaptive traffic control by using multiple virtualized routing topologies. | 2012 |
|
|
Throughput and Energy Efficiency in Wireless Ad Hoc Networks With Gaussian Channels
|
This paper studies the bottleneck link capacity under the Gaussian channel model in strongly connected random wireless ad hoc networks, with n nodes independently and uniformly distributed in a unit square. We assume that each node is equipped with two transceivers (one for transmission and one for reception) and allow all nodes to transmit simultaneously. We draw lower and upper bounds, in terms of bottleneck link capacity, for homogeneous networks (all nodes have the same transmission power level) and propose an energy-efficient power assignment algorithm (CBPA) for heterogeneous networks (nodes may have different power levels), with a provable bottleneck link capacity guarantee of Ω(Blog(1+1/√nlog2n)), where B is the channel bandwidth. In addition, we develop a distributed implementation of CBPA with O(n2) message complexity and provide extensive simulation results
|
2012 |
|
|
Cross-Layer Analysis of the End-to-End Delay Distribution in Wireless Sensor Networks
|
Emerging applications of wireless sensor networks (WSNs) require real-time quality-of-service (QoS) guarantees to be provided by the network. Due to the nondeterministic impacts of the wireless channel and queuing mechanisms, probabilistic analysis of QoS is essential. One important metric of QoS in WSNs is the probability distribution of the end-to-end delay. Compared to other widely used delay performance metrics such as the mean delay, delay variance, and worst-case delay, the delay distribution can be used to obtain the probability to meet a specific deadline for QoS-based communication in WSNs. To investigate the end-to-end delay distribution, in this paper, a comprehensive cross-layer analysis framework, which employs a stochastic queueing model in realistic channel environments, is developed. This framework is generic and can be parameterized for a wide variety of MAC protocols and routing protocols. Case studies with the CSMA/CA MAC protocol and an anycast protocol are conducted to illustrate how the developed framework can analytically predict the distribution of the end-to-end delay. Extensive test-bed experiments and simulations are performed to validate the accuracy of the framework for both deterministic and random deployments. Moreover, the effects of various network parameters on the distribution of end-to-end delay are investigated through the developed framework. To the best of our knowledge, this is the first work that provides a generic, probabilistic cross-layer analysis of end-to-end delay in WSNs.
|
2012 |
|
|
Routing for Power Minimization in the Speed Scaling Model | We study network optimization that considers power minimization as an objective. Studies have shown that mechanisms such as speed scaling can significantly reduce the power consumption of telecommunication networks by matching the consumption of each network element to the amount of processing required for its carried traffic. Most existing research on speed scaling focuses on a single network element in isolation. We aim for a network-wide optimization. Specifically, we study a routing problem with the objective of provisioning guaranteed speed/bandwidth for a given demand matrix while minimizing power consumption. Optimizing the routes critically relies on the characteristic of the speed-power curve f(s), which is how power is consumed as a function of the processing speed s. If f is superadditive, we show that there is no bounded approximation in general for integral routing, i.e., each traffic demand follows a single path. This contrasts with the well-known logarithmic approximation for subadditive functions. However, for common speed-power curves such as polynomials f(s) = μsα, we are able to show a constant approximation via a simple scheme of randomized rounding. We also generalize this rounding approach to handle the case in which a nonzero startup cost σ appears in the speed-power curve, i.e., f(s) = {σ + μsα, if s >; 0; 0, if s = 0. We present an O((σ/μ)1/α)-approximation, and we discuss why coming up with an approximation ratio independent of the startup cost may be hard. Finally, we provide simulation results to validate our algorithmic approaches | 2012 |
|
|
BloomCast: Efficient and Effective Full-Text Retrieval in Unstructured P2P Networks | Efficient and effective full-text retrieval in unstructured peer-to-peer networks remains a challenge in the research community. First, it is difficult, if not impossible, for unstructured P2P systems to effectively locate items with guaranteed recall. Second, existing schemes to improve search success rate often rely on replicating a large number of item replicas across the wide area network, incurring a large amount of communication and storage costs. In this paper, we propose BloomCast, an efficient and effective full-text retrieval scheme, in unstructured P2P networks. By leveraging a hybrid P2P protocol, BloomCast replicates the items uniformly at random across the P2P networks, achieving a guaranteed recall at a communication cost of O(√N), where N is the size of the network. Furthermore, by casting Bloom Filters instead of the raw documents across the network, BloomCast significantly reduces the communication and storage costs for replication. We demonstrate the power of BloomCast design through both mathematical proof and comprehensive simulations based on the query logs from a major commercial search engine and NIST TREC WT10G data collection. Results show that BloomCast achieves an average query recall of 91 percent, which outperforms the existing WP algorithm by 18 percent, while BloomCast greatly reduces the search latency for query processing by 57 percent. | 2012 |
|
Load-Balancing Multipath Switching System with Flow Slice | Multipath Switching systems (MPS) are intensely used in state-of-the-art core routers to provide terabit or even petabit switching capacity. One of the most intractable issues in designing MPS is how to load balance traffic across its multiple paths while not disturbing the intraflow packet orders. Previous packet-based solutions either suffer from delay penalties or lead to O(N2 ) hardware complexity, hence do not scale. Flow-based hashing algorithms also perform badly due to the heavy-tailed flow-size distribution. In this paper, we develop a novel scheme, namely, Flow Slice (FS) that cuts off each flow into flow slices at every intraflow interval larger than a slicing threshold and balances the load on a finer granularity. Based on the studies of tens of real Internet traces, we show that setting a slicing threshold of 1-4 ms, the FS scheme achieves comparative load-balancing performance to the optimal one. It also limits the probability of out-of-order packets to a negligible level (10-6) on three popular MPSes at the cost of little hardware complexity and an internal speedup up to two. These results are proven by theoretical analyses and also validated through trace-driven prototype simulations. | 2012 |
|
A New Cell-Counting-Based Attack Against Tor | Various low-latency anonymous communication systems such as Tor and Anonymizer have been designed to provide anonymity service for users. In order to hide the communication of users, most of the anonymity systems pack the application data into equal-sized cells (e.g., 512 B for Tor, a known real-world, circuit- based, low-latency anonymous communication network). Via extensive experiments on Tor, we found that the size of IP packets in the Tor network can be very dynamic because a cell is an application concept and the IP layer may repack cells. Based on this finding, we investigate a new cell-counting-based attack against Tor, which allows the attacker to confirm anonymous communication relationship among users very quickly. In this attack, by marginally varying the number of cells in the target traffic at the malicious exit onion router, the attacker can embed a secret signal into the variation of cell counter of the target traffic. The embedded signal will be carried along with the target traffic and arrive at the malicious entry onion router. Then, an accomplice of the attacker at themalicious entry onion router will detect the embedded signal based on the received cells and confirm the communication relationship among users. We have implemented this attack against Tor, and our experimental data validate its feasibility and effectiveness. There are several unique features of this attack. First, this attack is highly efficient and can confirm very short communication sessions with only tens of cells. Second, this attack is effective, and its detection rate approaches 100% with a very low false positive rate. Third, it is possible to implement the attack in a way that appears to be very difficult for honest participants to detect (e.g., using our hopping-based signal embedding | 2012 |
|
corman a novel cooperative opportunistic routing scheme in mobile ad hoc networks- projects 2012 | The link quality variation of wireless channels has been a challenging issue in data communications until recent explicit exploration in utilizing this characteristic. The same broadcast transmission may be perceived significantly differently, and usually independently, by receivers at different geographic locations. Furthermore, even the same stationary receiver may experience drastic link quality fluctuation over time. The combination of link-quality variation with the broadcasting nature of wireless channels has revealed a direction in the research of wireless networking, namely, cooperative communication. Research on cooperative communication started to attract interests in the community at the physical layer but more recently its importance and usability have also been realized at upper layers of the network protocol stack. In this article, we tackle the problem of opportunistic data transfer in mobile ad hoc networks. Our solution is called Cooperative Opportunistic Routing in Mobile Ad hoc Networks (CORMAN). It is a pure network layer scheme that can be built atop off-the-shelf wireless networking equipment. Nodes in the network use a lightweight proactive source routing protocol to determine a list of intermediate nodes that the data packets should follow en route to the destination. Here, when a data packet is broadcast by an upstream node and has happened to be received by a downstream node further along the route, it continues its way from there and thus will arrive at the destination node sooner. This is achieved through cooperative data communication at the link and network layers. This work is a powerful extension to the pioneering work of ExOR. We test CORMAN and compare it to AODV, and observe significant performance improvement in varying mobile settings.
|
2012 |
|
TAM: A Tiered Authentication of Multicast Protocol for Ad-Hoc Networks – projects 2012 | Ad-hoc networks are becoming an effective tool for many mission critical applications such as troop coordination in a combat field, situational awareness, etc. These applications are characterized by the hostile environment that they serve in and by the multicast-style of communication traffic. Therefore, authenticating the source and ensuring the integrity of the message traffic become a fundamental requirement for the operation and management of the network. However, the limited computation and communication resources, the large scale deployment and the unguaranteed connectivity to trusted authorities make known solutions for wired and single-hop wireless networks inappropriate. This paper presents a new Tiered Authentication scheme for Multicast traffic (TAM) for large scale dense ad-hoc networks. TAM combines the advantages of the time asymmetry and the secret information asymmetry paradigms and exploits network clustering to reduce overhead and ensure scalability. Multicast traffic within a cluster employs a one-way hash function chain in order to authenticate the message source. Cross-cluster multicast traffic includes message authentication codes (MACs) that are based on a set of keys. Each cluster uses a unique subset of keys to look for its distinct combination of valid MACs in the message in order to authenticate the source. The simulation and analytical results demonstrate the performance advantage of TAM in terms of bandwidth overhead and delivery delay | 2012 |
|
Privacy- and Integrity-Preserving Range Queries in Sensor Networks – projects 2012 | The architecture of two-tiered sensor networks, where storage nodes serve as an intermediate tier between sensors and a sink for storing data and processing queries, has been widely adopted because of the benefits of power and storage saving for sensors as well as the efficiency of query processing. However, the importance of storage nodes also makes them attractive to attackers. SafeQ, a protocol is proposed, that prevents attackers from gaining information from both sensor collected data and sink issued queries. SafeQ also allows a sink to detect compromised storage nodes when they misbehave. To preserve privacy, SafeQ uses a novel technique to encode both data and queries such that a storage node can correctly process encoded queries over encoded data without knowing their values. To preserve integrity, two schemes has been proposed, one using Merkle hash trees and another using a new data structure called neighborhood chains, to generate integrity verification information so that a sink can use this information to verify whether the result of a query contains exactly the data items that satisfy the query. | 2012 |
|
|
A Mathematical Framework for Analyzing Adaptive Incentive Protocols in P2P Networks | In peer-to-peer (P2P) networks, incentive protocol is used to encourage cooperation among end-nodes so as to deliver a scalable and robust service. However, the design and analysis of incentive protocols have been ad hoc and heuristic at best. The objective of this paper is to provide a simple yet general framework to analyze and design incentive protocols. We consider a class of incentive protocols that can learn and adapt to other end-nodes’ strategies. Based on our analytical framework, one can evaluate the expected performance gain and, more importantly, the system robustness of a given incentive protocol. To illustrate the framework, we present two adaptive learning models and three incentive policies and show the conditions in which the P2P networks may collapse and the conditions in which the P2P networks can guarantee a high degree of cooperation. We also show the connection between evaluating incentive protocol and evolutionary game theory so one can easily identify robustness characteristics of a given policy. Using our framework, one can gain the understanding on the price of altruism and system stability, as well as the correctness of the adaptive incentive policy.
|
2012 |
|
|
Abnormally Malicious Autonomous Systems and Their Internet Connectivity | While many attacks are distributed across botnets, investigators and network operators have recently identified malicious networks through high profile autonomous system (AS) depeerings and network shutdowns. In this paper, we explore whether some ASs indeed are safe havens for malicious activity. We look for ISPs and ASs that exhibit disproportionately high malicious behavior using 10 popular blacklists, plus local spam data, and extensive DNS resolutions based on the contents of the blacklists. We find that some ASs have over 80% of their routable IP address space blacklisted. Yet others account for large fractions of blacklisted IP addresses. Several ASs regularly peer with ASs associated with significant malicious activity. We also find that malicious ASs as a whole differ from benign ones in other properties not obviously related to their malicious activities, such as more frequent connectivity changes with their BGP peers. Overall, we conclude that examining malicious activity at AS granularity can unearth networks with lax security or those that harbor cybercrime.
|
2012 |
|
|
BGP Churn Evolution A Perspective From the Core | The scalability limitations of BGP have been a major concern lately. An important aspect of this issue is the rate of routing updates (churn) that BGP routers must process. This paper presents an analysis of the evolution of churn in four networks at the backbone of the Internet over a period of seven years and eight months, using BGP update traces from the RouteViews project. The churn rate varies widely over time and between networks. Instead of descriptive “black-box” statistical analysis, we take an exploratory data analysis approach attempting to understand the reasons behind major observed characteristics of the churn time series. We find that duplicate announcements are a major churn contributor, responsible for most large spikes. Remaining spikes are mostly caused by routing incidents that affect a large number of prefixes simultaneously. More long-term intense periods of churn, on the other hand, are caused by misconfigurations or other special events at or close to the monitored autonomous system (AS). After filtering pathologies and effects that are not related to the long-term evolution of churn, we analyze the remaining “baseline” churn and find that it is increasing at a rate that is similar to the growth of the number of ASs. | 2012 |
|
|
Congestion-Dependent Pricing and Forward Contracts for Complementary Segments of a Communication Network | Congestion-dependent pricing is a form of traffic management that ensures the efficient allocation of bandwidth between users and applications. As the unpredictability of congestion prices creates revenue uncertainty for network providers and cost uncertainty for users, it has been suggested that forward contracts could be used to manage these risks. We develop a novel game-theoretic model of a multiprovider communication network with two complementary segments and investigate whether forward contracts would be adopted by service providers. Service on the upstream segment is provided by a single Internet service provider (ISP) and priced dynamically to maximize profit, while several smaller ISPs sell connectivity on the downstream network segment, with the advance possibility of entering into forward contracts with their users for some of their capacity. We show that the equilibrium forward contracting volumes are necessarily asymmetric, with one downstream provider entering into fewer forward contracts than the other competitors, thus ensuring a high subsequent downstream price level. In practice, network providers will choose the extent of forward contracting strategically based not only on their risk tolerance, but also on the market structure in the interprovider network and their peers’ actions. | 2012 |
|
|
DAC Generic and Automatic Address Configuration for Data Center Networks | Data center networks encode locality and topology information into their server and switch addresses for performance and routing purposes. For this reason, the traditional address configuration protocols such as DHCP require a huge amount of manual input, leaving them error-prone. In this paper, we present DAC, a generic and automatic Data center Address Configuration system. With an automatically generated blueprint that defines the connections of servers and switches labeled by logical IDs, e.g., IP addresses, DAC first learns the physical topology labeled by device IDs, e.g., MAC addresses. Then, at the core of DAC is its device-to-logical ID mapping and malfunction detection. DAC makes an innovation in abstracting the device-to-logical ID mapping to the graph isomorphism problem and solves it with low time complexity by leveraging the attributes of data center network topologies. Its malfunction detection scheme detects errors such as device and link failures and miswirings, including the most difficult case where miswirings do not cause any node degree change. We have evaluated DAC via simulation, implementation, and experiments. Our simulation results show that DAC can accurately find all the hardest-to-detect malfunctions and can autoconfigure a large data center with 3.8 million devices in 46 s. In our implementation, we successfully autoconfigure a small 64-server BCube network within 300 ms and show that DAC is a viable solution for data center autoconfiguration. | 2012 |
|
|
Distributed -Optimal User Association and Cell Load Balancing in Wireless Networks | In this paper, we develop a framework for user association in infrastructure-based wireless networks, specifically focused on flow-level cell load balancing under spatially inhomogeneous traffic distributions. Our work encompasses several different user association policies: rate-optimal, throughput-optimal, delay-optimal, and load-equalizing, which we collectively denote α-optimal user association. We prove that the optimal load vector ρ* that minimizes a generalized system performance function is the fixed point of a certain mapping. Based on this mapping, we propose and analyze an iterative distributed user association policy that adapts to spatial traffic loads and converges to a globally optimal allocation. We then address admission control policies for the case where the system is overloaded. For an appropriate system-level cost function, the optimal admission control policy blocks all flows at cells edges. However, providing a minimum level of connectivity to all spatial locations might be desirable. To this end, a location-dependent random blocking and user association policy are proposed. | 2012 |
|
|
Efficient Error Estimating Coding Feasibility and Applications | Motivated by recent emerging systems that can leverage partially correct packets in wireless networks, this paper proposes the novel concept of error estimating coding (EEC). Without correcting the errors in the packet, EEC enables the receiver of the packet to estimate the packet’s bit error rate, which is perhaps the most important meta-information of a partially correct packet. Our EEC design provides provable estimation quality with rather low redundancy and computational overhead. To demonstrate the utility of EEC, we exploit and implement EEC in two wireless network applications, Wi-Fi rate adaptation and real-time video streaming. Our real-world experiments show that these applications can significantly benefit from EEC. | 2012 |
|
|
Exploiting Data Fusion to Improve the Coverage of Wireless Sensor Networks | Wireless sensor networks (WSNs) have been increasingly available for critical applications such as security surveillance and environmental monitoring. An important performance measure of such applications is sensing coverage that characterizes how well a sensing field is monitored by a network. Although advanced collaborative signal processing algorithms have been adopted by many existing WSNs, most previous analytical studies on sensing coverage are conducted based on overly simplistic sensing models (e.g., the disc model) that do not capture the stochastic nature of sensing. In this paper, we attempt to bridge this gap by exploring the fundamental limits of coverage based on stochastic data fusion models that fuse noisy measurements of multiple sensors. We derive the scaling laws between coverage, network density, and signal-to-noise ratio (SNR). We show that data fusion can significantly improve sensing coverage by exploiting the collaboration among sensors when several physical properties of the target signal are known. In particular, for signal path loss exponent of (typically between 2.0 and 5.0), ρf = O(ρd1-1/k, where ρf and ρd are the densities of uniformly deployed sensors that achieve full coverage under the fusion and disc models, respectively. Moreover, data fusion can also reduce network density for regularly deployed networks and mobile networks where mobile sensors can relocate to fill coverage holes. Our results help understand the limitations of the previous analytical results based on the disc model and provide key insights into the design of WSNs that adopt data fusion algorithms. Our analyses are verified through extensive simulations based on both synthetic data sets and data traces collected in a real deployment for vehicle detection.
|
2012 |
|
|
Finding Cheap Routes in Profit-Driven Opportunistic Spectrum Access Networks A Truthful Mechanism Design Approach | In this paper, we explore the economic aspects of routing/relaying in a profit-driven opportunistic spectrum access (OSA) network. In this network, primary users lease their licensed spectrum to secondary radio (SR) providers, who in turn provide opportunistic routing/relaying service to end-users if this service is profitable, i.e., if the payment offered by the end-user (a.k.a. the price) exceeds the SR’s relaying spectrum cost. This cost is considered private information known only to SRs. Therefore, the end-user has to rely on costs reported by SRs to determine his routing and payment strategy. The challenge comes from the selfish nature of SRs; an SR may exaggerate his cost to achieve greater profit. To give incentive to an SR to report the true cost, the payment must typically be higher than the actual cost. However, from the end-user’s perspective, “overpayment” should be avoided as much as possible. Therefore, we are interested in the “optimal” route selection and payment determination mechanism that minimizes the price of the selected route while simultaneously guaranteeing truthful cost reporting by SRs. We formulate this problem as finding the least-priced path (LPP), and we investigate it without and with link capacity constraints. In the former case, polynomial-time algorithm is developed to find LPP and calculate its truthful price. In the latter case, we show that calculating the truthful price of the LPP is in general computationally infeasible. Consequently, we consider a suboptimal but computationally feasible approximate solution, which we refer to as truthful low-priced path (LOPP) routing. A polynomial-time algorithm is proposed to find the LOPP and efficiently calculate its truthful price. A payment materialization algorithm is also developed to guarantee truthful capacity reporting by SRs. The effectiveness of our algorithms in terms of price saving is verified through extensive simulations.
|
2012 |
|
|
IEEE 802.11 Saturation Throughput Analysis in the Presence of Hidden Terminals | Due to its usefulness and wide deployment, IEEE 802.11 has been the subject of numerous studies, but still lacks a complete analytical model. Hidden terminals are common in IEEE 802.11 and cause the degradation of throughput. Despite the importance of the hidden terminal problem, there have been a relatively small number of studies that consider the effect of hidden terminals on IEEE 802.11 throughput, and many are not accurate for a wide range of conditions. In this paper, we present an accurate new analytical saturation throughput model for the infrastructure case of IEEE 802.11 in the presence of hidden terminals. Simulation results show that our model is accurate in a wide variety of cases. | 2012 |
|
|
MeasuRouting A Framework for Routing Assisted Traffic Monitoring | Monitoring transit traffic at one or more points in a network is of interest to network operators for reasons of traffic accounting, debugging or troubleshooting, forensics, and traffic engineering. Previous research in the area has focused on deriving a placement of monitors across the network toward the end of maximizing the monitoring utility of the network operator for a given traffic routing. However, both traffic characteristics and measurement objectives can dynamically change over time, rendering a previously optimal placement of monitors suboptimal. It is not feasible to dynamically redeploy/reconfigure measurement infrastructure to cater to such evolving measurement requirements. We address this problem by strategically routing traffic subpopulations over fixed monitors. We refer to this approach as MeasuRouting. The main challenge for MeasuRouting is to work within the constraints of existing intradomain traffic engineering operations that are geared for efficiently utilizing bandwidth resources, or meeting quality-of-service (QoS) constraints, or both. A fundamental feature of intradomain routing, which makes MeasuRouting feasible, is that intradomain routing is often specified for aggregate flows. MeasuRouting can therefore differentially route components of an aggregate flow while ensuring that the aggregate placement is compliant to original traffic engineering objectives. In this paper, we present a theoretical framework for MeasuRouting. Furthermore, as proofs of concept, we present synthetic and practical monitoring applications to showcase the utility enhancement achieved with MeasuRouting. | 2012 |
|
|
Obtaining Provably Legitimate Internet Topologies | What topologies should be used to evaluate protocols for interdomain routing? Using the most current Internet topology is not practical since its size is prohibitive for detailed, packet-level interdomain simulations. Besides being of moderate size, the topology should be policy-aware, that is, it needs to represent business relationships between adjacent nodes (that represent autonomous systems). In this paper, we address this issue by providing a framework to generate small, realistic, and policy-aware topologies. We propose HBR, a novel sampling method, which exploits the inherent hierarchy of the policy-aware Internet topology. We formally prove that our approach generates connected and legitimate topologies, which are compatible with the policy-based routing conventions and rules. Using simulations, we show that HBR generates topologies that: 1) maintain the graph properties of the real topology; 2) provide reasonably realistic interdomain simulation results while reducing the computational complexity by several orders of magnitude as compared to the initial topology. Our approach provides a permanent solution to the problem of interdomain routing evaluations: Given a more accurate and complete topology, HBR can generate better small topologies in the future.
|
2012 |
|
|
On the Impact of TCP and Per-Flow Scheduling on Internet Performance | Internet performance is tightly related to the properties of TCP and UDP protocols, jointly responsible for the delivery of the great majority of Internet traffic. It is well understood how these protocols behave under FIFO queuing and what are the network congestion effects. However, no comprehensive analysis is available when flow-aware mechanisms such as per-flow scheduling and dropping policies are deployed. Previous simulation and experimental results leave a number of unanswered questions. In the paper, we tackle this issue by modeling via a set of fluid non-linear ODEs the instantaneous throughput and the buffer occupancy of N long-lived TCP sources under three per-flow scheduling disciplines (Fair Queuing, Longest Queue First, Shortest Queue First) and with longest queue drop buffer management. We study the system evolution and analytically characterize the stationary regime: closed-form expressions are derived for the stationary throughput/sending rate and buffer occupancy which give a thorough understanding of short/long-term fairness for TCP traffic. Similarly, we provide the characterization of the loss rate experienced by UDP flows in presence of TCP traffic. As a result, the analysis allows to quantify benefits and drawbacks related to the deployment of flow-aware scheduling mechanisms in different networking contexts. The model accuracy is confirmed by a set of ns2 simulations and by the evaluation of the three scheduling disciplines in a real implementation in the Linux kernel. | 2012 |
|
|
Opportunistic Spectrum Access in Multiple-Primary-User Environments Under the Packet Collision Constraint | Cognitive radio (CR) technology has great potential to alleviate spectrum scarcity in wireless communications. It allows secondary users (SUs) to opportunistically access spectrum licensed by primary users (PUs) while protecting PU activity. The protection of the PUs is central to the adoption of this technology since no PU would accommodate SU access to its own detriment. In this paper, we consider an SU that must protect multiple PUs simultaneously. We focus on the PU packet collision probability as the protection metric. The PUs are unslotted and may have different idle/busy time distributions and protection requirements. Under general idle time distributions, we determine the form of the SU optimal access policy and identify two special cases for which the computation of the optimal policy is significantly reduced. We also present a simple algorithm to determine these policies using principles of convex optimization theory. We then derive the optimal policy for the same system when an SU has extra “side information” on PU activity. We evaluate the performance of these policies through simulation. | 2012 |
|
|
Performance of PCN-Based Admission Control Under Challenging Conditions | Precongestion notification (PCN) is a packet-marking technique for IP networks to notify egress nodes of a so-called PCN domain whether the traffic rate on some links exceeds certain configurable bounds. This feedback is used by decision points for admission control (AC) to block new flows when the traffic load is already high. PCN-based AC is simpler than other AC methods because interior routers do not need to keep per-flow states. Therefore, it is currently being standardized by the IETF. We discuss various realization options and analyze their performance in the presence of flash crowds or with multipath routing by means of simulation and mathematical modeling. Such situations can be aggravated by insufficient flow aggregation, long round-trip times, on/off traffic, delayed media, inappropriate marker configuration, and smoothed feedback | 2012 |
|
|
Routing for Power Minimization in the Speed Scaling Model | We study network optimization that considers power minimization as an objective. Studies have shown that mechanisms such as speed scaling can significantly reduce the power consumption of telecommunication networks by matching the consumption of each network element to the amount of processing required for its carried traffic. Most existing research on speed scaling focuses on a single network element in isolation. We aim for a network-wide optimization. Specifically, we study a routing problem with the objective of provisioning guaranteed speed/bandwidth for a given demand matrix while minimizing power consumption. Optimizing the routes critically relies on the characteristic of the speed-power curve f(s), which is how power is consumed as a function of the processing speed s. If f is superadditive, we show that there is no bounded approximation in general for integral routing, i.e., each traffic demand follows a single path. This contrasts with the well-known logarithmic approximation for subadditive functions. However, for common speed-power curves such as polynomials f(s) = μsα, we are able to show a constant approximation via a simple scheme of randomized rounding. We also generalize this rounding approach to handle the case in which a nonzero startup cost σ appears in the speed-power curve, i.e., f(s) = {σ + μsα, if s >; 0; 0, if s = 0. We present an O((σ/μ)1/α)-approximation, and we discuss why coming up with an approximation ratio independent of the startup cost may be hard. Finally, we provide simulation results to validate our algorithmic approaches. | 2012 |
|
|
Scaffold Filling under the Breakpoint and Related Distances | Motivated by the trend of genome sequencing without completing the sequence of the whole genomes, a problem on filling an incomplete multichromosomal genome (or scaffold) I with respect to a complete target genome G was studied. The objective is to minimize the resulting genomic distance between I’ and G, where I’ is the corresponding filled scaffold. We call this problem the one-sided scaffold filling problem. In this paper, we conduct a systematic study for the scaffold filling problem under the breakpoint distance and its variants, for both unichromosomal and multichromosomal genomes (with and without gene repetitions). When the input genome contains no gene repetition (i.e., is a fragment of a permutation), we show that the two-sided scaffold filling problem (i.e., G is also incomplete) is polynomially solvable for unichromosomal genomes under the breakpoint distance and for multichromosomal genomes under the genomic (or DCJ-Double-Cut-and-Join) distance. However, when the input genome contains some repeated genes, even the one-sided scaffold filling problem becomes NP-complete when the similarity measure is the maximum number of adjacencies between two sequences. For this problem, we also present efficient constant-factor approximation algorithms: factor-2 for the general case and factor 1.33 for the one-sided case. | 2012 |
|
|
Scalable Video Multicast With Adaptive Modulation and Coding in Broadband Wireless Data Systems | Future mobile broadband networks are characterized with high data rate and improved coverage, which will enable real-time video multicast and broadcast services. Scalable video coding (SVC), combined with adaptive modulation and coding schemes (MCS) and wireless multicast, provides an excellent solution for streaming video to heterogeneous wireless devices. By choosing different MCSs for different video layers, SVC can provide good video quality to users in good channel conditions while maintaining basic video quality for users in bad channel conditions. A key issue to apply SVC to wireless multicast streaming is to choose appropriate MCS for each video layer and to determine the optimal resource allocation among multiple video sessions. We formulate this problem as total utility maximization, subject to the constraint of available radio resources. We prove that the formulated problem is NP-hard and propose an optimal, two-step dynamic programming solution with pseudo-polynomial time complexity. Simulation results show that our algorithm offers significant improvement on the video quality over a naive algorithm and an adapted greedy algorithm, especially in the scenarios with multiple real video sequences and limited radio resources. | 2012 |
|
|
SLAW Self-Similar Least-Action Human Walk | Many empirical studies of human walks have reported that there exist fundamental statistical features commonly appearing in mobility traces taken in various mobility settings. These include: 1) heavy-tail flight and pause-time distributions; 2) heterogeneously bounded mobility areas of individuals; and 3) truncated power-law intercontact times. This paper reports two additional such features: a) The destinations of people (or we say waypoints) are dispersed in a self-similar manner; and b) people are more likely to choose a destination closer to its current waypoint. These features are known to be influential to the performance of human-assisted mobility networks. The main contribution of this paper is to present a mobility model called Self-similar Least-Action Walk (SLAW) that can produce synthetic mobility traces containing all the five statistical features in various mobility settings including user-created virtual ones for which no empirical information is available. Creating synthetic traces for virtual environments is important for the performance evaluation of mobile networks as network designers test their networks in many diverse network settings. A performance study of mobile routing protocols on top of synthetic traces created by SLAW shows that SLAW brings out the unique performance features of various routing protocols.
|
2012 |
|
|
Throughput and Energy Efficiency in Wireless Ad Hoc Networks With Gaussian Channels | This paper studies the bottleneck link capacity under the Gaussian channel model in strongly connected random wireless ad hoc networks, with n nodes independently and uniformly distributed in a unit square. We assume that each node is equipped with two transceivers (one for transmission and one for reception) and allow all nodes to transmit simultaneously. We draw lower and upper bounds, in terms of bottleneck link capacity, for homogeneous networks (all nodes have the same transmission power level) and propose an energy-efficient power assignment algorithm (CBPA) for heterogeneous networks (nodes may have different power levels), with a provable bottleneck link capacity guarantee of Ω(Blog(1+1/√nlog2n)), where B is the channel bandwidth. In addition, we develop a distributed implementation of CBPA with O(n2) message complexity and provide extensive simulation results.
|
2012 |
|
|
Towards a Better Understanding of Large-Scale Network Models | Connectivity and capacity are two fundamental properties of wireless multihop networks. The scalability of these properties has been a primary concern for which asymptotic analysis is a useful tool. Three related but logically distinct network models are often considered in asymptotic analyses, viz. the dense network model, the extended network model, and the infinite network model, which consider respectively a network deployed in a fixed finite area with a sufficiently large node density, a network deployed in a sufficiently large area with a fixed node density, and a network deployed in with a sufficiently large node density. The infinite network model originated from continuum percolation theory and asymptotic results obtained from the infinite network model have often been applied to the dense and extended networks. In this paper, through two case studies related to network connectivity on the expected number of isolated nodes and on the vanishing of components of finite order respectively, we demonstrate some subtle but important differences between the infinite network model and the dense and extended network models. Therefore, extra scrutiny has to be used in order for the results obtained from the infinite network model to be applicable to the dense and extended network models. Asymptotic results are also obtained on the expected number of isolated nodes, the vanishingly small impact of the boundary effect on the number of isolated nodes, and the vanishing of components of finite order in the dense and extended network models using a generic random connection model. | 2012 |
| 44 | Tracking Low-Precision Clocks With Time-Varying Drifts Using Kalman Filtering | Clock synchronization is essential for a large number of applications ranging from performance measurements in wired networks to data fusion in sensor networks. Existing techniques are either limited to undesirable accuracy or rely on specific hardware characteristics that may not be available in certain applications. In this paper, we examine the clock synchronization problem in networks where nodes lack the high-accuracy oscillators or programmable network interfaces some previous protocols depend on. This paper derives a general model for clock offset and skew and demonstrates its application to real clock oscillators. We design an efficient algorithm based on this model to achieve high synchronization accuracy. This algorithm applies the Kalman filter to track the clock offset and skew. We demonstrate the performance advantages of our schemes through extensive simulations and real clock oscillator measurements | 2012 |
| 45 | ViNEYard Virtual Network Embedding Algorithms With Coordinated Node and Link Mapping | Network virtualization allows multiple heterogeneous virtual networks (VNs) to coexist on a shared infrastructure. Efficient mapping of virtual nodes and virtual links of a VN request onto substrate network resources, also known as the VN embedding problem, is the first step toward enabling such multiplicity. Since this problem is known to be NP-hard, previous research focused on designing heuristic-based algorithms that had clear separation between the node mapping and the link mapping phases. In this paper, we present ViNEYard-a collection of VN embedding algorithms that leverage better coordination between the two phases. We formulate the VN embedding problem as a mixed integer program through substrate network augmentation. We then relax the integer constraints to obtain a linear program and devise two online VN embedding algorithms D-ViNE and R-ViNE using deterministic and randomized rounding techniques, respectively. We also present a generalized window-based VN embedding algorithm (WiNE) to evaluate the effect of lookahead on VN embedding. Our simulation experiments on a large mix of VN requests show that the proposed algorithms increase the acceptances. | 2012 |
| TECHNOLOGY : DOT NET
DOMAIN : IEEE TRANSACTIONS ON NETWORK SECURITY |
| S.NO | TITLES | ABSTRACT | YEAR |
|
|
Extending Attack Graph-Based Security Metrics and Aggregating Their Application | The attack graph is an abstraction that reveals the ways an attacker can leverage vulnerabilities in a network to violate a security policy. When used with attack graph-based security metrics, the attack graph may be used to quantitatively assess security relevant aspects of a network. | 2012 |
|
|
Secured Trust: A Dynamic Trust Computation Model for Secured Communication in Multi agent Systems | We present in this paper a dynamic trust computation model called “SecuredTrust.” In this paper, we first analyze the different factors related to evaluating the trust of an agent and then propose a comprehensive quantitative model for measuring such trust. We also propose a novel load-balancing algorithm based on the different factors defined in our model. | 2012 |
|
|
Persuasive Cued Click-Points: Design, Implementation, and Evaluation of a Knowledge-Based Authentication Mechanism | This paper presents an integrated evaluation of the Persuasive Cued Click-Points graphical password scheme, including usability and security evaluations, and implementation considerations. An important usability goal for knowledge-based authentication systems is to support users in selecting passwords of higher security, in the sense of being from an expanded effective security space. | 2012 |
|
|
Detecting Spam Zombies by Monitoring Outgoing Messages | We develop an effective spam zombie detection system named SPOT by monitoring outgoing messages of a network. SPOT is designed based on a powerful statistical tool called Sequential Probability Ratio Test, which has bounded false positive and false negative error rates. | 2012 |
|
|
Iterative Trust and Reputation Management Using Belief Propagation | In this paper, we introduce the first application of the belief propagation algorithm in the design and evaluation of trust and reputation management systems. We approach the reputation management problem as an inference problem and describe it as computing marginal likelihood distributions from complicated global functions of many variables. | 2012 |
|
|
Data-Provenance Verification For Secure Hosts | Malicious software typically resides stealthily on a user’s computer and interacts with the user’s computing resources. Our goal in this work is to improve the trustworthiness of a host and its system data. Specifically, we provide a new mechanism that ensures the correct origin or provenance of critical system information and prevents adversaries from 53utilizing host resources. | 2012 |
|
|
Risk-Aware Mitigation for MANET Routing Attacks | In this paper, we propose a risk-aware response mechanism to systematically cope with the identified routing attacks. Our risk-aware approach is based on an extended Dempster-Shafer mathematical theory of evidence introducing a notion of importance factors. | 2012 |
|
|
Characterizing the Efficacy of the NRL Network Pump in Mitigating Covert Timing Channels | The Naval Research Laboratory (NRL) Network Pump, or Pump, is a standard for mitigating covert channels that arise in a multilevel secure (MLS) system when a high user (HU) sends acknowledgements to a low user (LU). The issue here is that HU can encode information in the “timings” of the acknowledgements. | 2012 |
|
|
Detecting and Resolving Firewall Policy Anomalies | The advent of emerging computing technologies such as service-oriented architecture and cloud computing has enabled us to perform business services more efficiently and effectively. However, we still suffer from unintended security leakages by unauthorized actions in business services | 2012 |
|
|
Revisiting Defenses against Large-Scale Online Password Guessing Attacks
|
Brute force and dictionary attacks on password-only remote login services are now widespread and ever increasing.Enabling convenient login for legitimate users while preventing such attacks is a difficult problem. Automated Turing Tests (ATTs) continue to be an effective, easy-to-deploy approach to identify automated malicious login attempts with reasonable cost of inconvenience to users. In this paper, we discuss the inadequacy of existing and proposed login protocols designed to address large scale online dictionary attacks (e.g., from a botnet of hundreds of thousands of nodes). We propose a new Password Guessing Resistant Protocol (PGRP), derived upon revisiting prior proposals designed to restrict such attacks. While PGRP limits the total number of login attempts from unknown remote hosts to as low as a single attempt per username, legitimate users in most cases (e.g., when attempts are made from known, frequently-used machines) can make several failed login attempts before being challenged with an ATT. We analyze the performance of PGRP with two real-world data sets and find it more promising than existing proposals. | 2012 |
|
|
Enhanced Privacy ID: A Direct Anonymous Attestation Scheme with Enhanced Revocation Capabilities 2012 Dotnet Network Security
|
Direct Anonymous Attestation (DAA) is a scheme that enables the remote authentication of a Trusted Platform Module (TPM) while preserving the user’s privacy. A TPM can prove to a remote party that it is a valid TPM without revealing its identity and without linkability. In the DAA scheme, a TPM can be revoked only if the DAA private key in the hardware has been extracted and published widely so that verifiers obtain the corrupted private key. If the unlinkability requirement is relaxed, a TPM suspected of being compromised can be revoked even if the private key is not known. However, with the full unlinkability requirement intact, if a TPM has been compromised but its private key has not been distributed to verifiers, the TPM cannot be revoked. Furthermore, a TPM cannot be revoked from the issuer, if the TPM is found to be compromised after the DAA issuing has occurred. In this paper, we present a new DAA scheme called Enhanced Privacy ID (EPID) scheme that addresses the above limitations. While still providing unlinkability, our scheme provides a method to revoke a TPM even if the TPM private key is unknown. This expanded revocation property makes the scheme useful for other applications such as for driver’s license. Our EPID scheme is efficient and provably secure in the same security model as DAA, i.e., in the random oracle model under the strong RSA assumption and the decisional Diffie-Hellman assumption.
|
2012 |
|
Design and Implementation of TARF: A Trust-Aware Routing Framework for WSNs | The multi-hop routing in wireless sensor networks (WSNs) offers little protection against identity deception through replaying routing information. An adversary can exploit this defect to launch various harmful or even devastating attacks against the routing protocols, including sinkhole attacks, wormhole attacks and Sybil attacks. The situation is further aggravated by mobile and harsh network conditions. Traditional cryptographic techniques or efforts at developing trust-aware routing protocols do not effectively address this severe problem. To secure the WSNs against adversaries misdirecting the multi-hop routing, we have designed and implemented TARF, a robust trust-aware routing framework for dynamic WSNs. Without tight time synchronization or known geographic information, TARF provides trustworthy and energy-efficient route. Most importantly, TARF proves effective against those harmful attacks developed out of identity deception; the resilience of TARF is verified through extensive evaluation with both simulation and empirical experiments on large-scale WSNs under various scenarios including mobile and RF-shielding network conditions. | 2012 |
|
Design and Implementation of TARF: A Trust-Aware Routing Framework for WSNs- projects 2012 Dependable and Secure Computing | The multihop routing in wireless sensor networks (WSNs) offers little protection against identity deception through replaying routing information. An adversary can exploit this defect to launch various harmful or even devastating attacks against the routing protocols, including sinkhole attacks, wormhole attacks, and Sybil attacks. The situation is further aggravated by mobile and harsh network conditions. Traditional cryptographic techniques or efforts at developing trust-aware routing protocols do not effectively address this severe problem. To secure the WSNs against adversaries misdirecting the multihop routing, we have designed and implemented TARF, a robust trust-aware routing framework for dynamic WSNs. Without tight time synchronization or known geographic information, TARF provides trustworthy and energy-efficient route. Most importantly, TARF proves effective against those harmful attacks developed out of identity deception; the resilience of TARF is verified through extensive evaluation with both simulation and empirical experiments on large-scale WSNs under various scenarios including mobile and RF-shielding network conditions. Further, we have implemented a low-overhead TARF module in TinyOS; as demonstrated, this implementation can be incorporated into existing routing protocols with the least effort. Based on TARF, we also demonstrated a proof-of-concept mobile target detection application that functions well against an antidetection mechanism. | 2012 |
|
Fast Zone-Based Node Compromise Detection and Revocation in Wireless Sensor Networks Using Sequential Hypothesis Testing- projects 2012 | Due to the unattended nature of wireless sensor networks, an adversary can physically capture and compromise sensor nodes and then mount a variety of attacks with the compromised nodes. To minimize the damage incurred by the compromised nodes, the system should detect and revoke them as soon as possible. To meet this need, researchers have recently proposed a variety of node compromise detection schemes in wireless ad hoc and sensor networks. For example, reputation-based trust management schemes identify malicious nodes but do not revoke them due to the risk of false positives. Similarly, software-attestation schemes detect the subverted software modules of compromised nodes. However, they require each sensor node to be attested periodically, thus incurring substantial overhead. To mitigate the limitations of the existing schemes, we propose a zone-based node compromise detection and revocation scheme in wireless sensor networks. The main idea behind our scheme is to use sequential hypothesis testing to detect suspect regions in which compromised nodes are likely placed. In these suspect regions, the network operator performs software attestation against sensor nodes, leading to the detection and revocation of the compromised nodes. Through quantitative analysis and simulation experiments, we show that the proposed scheme detects the compromised nodes with a small number of samples while reducing false positive and negative rates, even if a substantial fraction of the nodes in the zone are compromised. Additionally, we model the detection problem using a game theoretic analysis, derive the optimal strategies for the attacker and the defender, and show that the attacker’s gain from node compromise is greatly limited by the defender when both the attacker and the defender follow their optimal strategies | 2012 |
|
Bounding the Impact of Unbounded Attacks in Stabilization | Self-stabilization is a versatile approach to fault-tolerance since it permits a distributed system to recover from any transient fault that arbitrarily corrupts the contents of all memories in the system. Byzantine tolerance is an attractive feature of distributed systems that permits to cope with arbitrary malicious behaviors. Combining these two properties proved difficult: it is impossible to contain the spatial impact of Byzantine nodes in a self-stabilizing context for global tasks such as tree orientation and tree construction. We present and illustrate a new concept of Byzantine containment in stabilization. Strong Stabilization enables to contain the impact of Byzantine nodes if they actually perform too many Byzantine actions. Derived impossibility results for strong stabilization and present strongly stabilizing protocols for tree orientation and tree construction that are optimal with respect to the number of Byzantine nodes that can be tolerated in a self-stabilizing context. | 2012 |
|
Balancing the Tradeoffs between Query Delay and Data Availability in MANETs – projects 2012 | In mobile ad hoc networks (MANETs), nodes move freely and link/node failures are common, which leads to frequent network partitions. When a network partition occurs, mobile nodes in one partition are not able to access data hosted by nodes in other partitions, and hence significantly degrade the performance of data access. To deal with this problem, we apply data 63replication techniques. Existing data replication solutions in both wired and wireless networks aim at either reducing the query delay or improving the data availability, but not both. As both metrics are important for mobile nodes, we propose schemes to balance the tradeoffs between data availability and query delay under different system settings and requirements. Extensive simulation results show that the proposed schemes can achieve a balance between these two metrics and provide satisfying system performance. | 2012 |
|
|
A Stochastic Model of Multivirus Dynamics | Understanding the spreading dynamics of computer viruses (worms, attacks) is an important research problem, and has received much attention from the communities of both computer security and statistical physics. However, previous studies have mainly focused on single-virus spreading dynamics. In this paper, we study multivirus spreading dynamics, where multiple viruses attempt to infect computers while possibly combating against each other because, for example, they are controlled by multiple botmasters. Specifically, we propose and analyze a general model (and its two special cases) of multivirus spreading dynamics in arbitrary networks (i.e., we do not make any restriction on network topologies), where the viruses may or may not coreside on computers. Our model offers analytical results for addressing questions such as: What are the sufficient conditions (also known as epidemic thresholds) under which the multiple viruses will die out? What if some viruses can “rob” others? What characteristics does the multivirus epidemic dynamics exhibit when the viruses are (approximately) equally powerful? The analytical results make a fundamental connection between two types of factors: defense capability and network connectivity. This allows us to draw various insights that can be used to guide security defense.
|
2012 |
|
|
A Taxonomy of Buffer Overflow Characteristics | Significant work on vulnerabilities focuses on buffer overflows, in which data exceeding the bounds of an array is loaded into the array. The loading continues past the array boundary, causing variables and state information located adjacent to the array to change. As the process is not programmed to check for these additional changes, the process acts incorrectly. The incorrect action often places the system in a nonsecure state. This work develops a taxonomy of buffer overflow vulnerabilities based upon characteristics, or preconditions that must hold for an exploitable buffer overflow to exist. We analyze several software and hardware countermeasures to validate the approach. We then discuss alternate approaches to ameliorating this vulnerability. | 2012 |
|
|
Compiler-Directed Soft Error Mitigation for Embedded Systems | The protection of processor-based systems to mitigate the harmful effect of transient faults (soft errors) is gaining importance as technology shrinks. At the same time, for large segments of embedded markets, parameters like cost and performance continue to be as important as reliability. This paper presents a compiler-based methodology for facilitating the design of fault-tolerant embedded systems. The methodology is supported by an infrastructure that permits to easily combine hardware/software soft errors mitigation techniques in order to best satisfy both usual design constraints and dependability requirements. It is based on a generic microprocessor architecture that facilitates the implementation of software-based techniques, providing a uniform isolated-from-target hardening core that allows the automatic generation of protected source code (hardened code). Two case studies are presented. In the first one, several software-based mitigation techniques are implemented and evaluated showing the flexibility of the infrastructure. In the second one, a customized fault tolerant embedded system is designed by combining selective protection on both hardware and software. Several trade-offs among performance, code size, reliability, and hardware costs have been explored. Results show the applicability of the approach. Among the developed software-based mitigation techniques, a novel selective version of the well known SWIFT-R is presented. | 2012 |
|
|
Conditional Diagnosability of Augmented Cubes under the PMC Model | Processor fault diagnosis has played an important role in measuring the reliability of a multiprocessor system, and the diagnosability of many well-known multiprocessor systems has been widely investigated. The conditional diagnosability is a novel measure of diagnosability by adding an additional condition that any faulty set cannot contain all the neighbors of any node in a system. In this paper, we evaluate the conditional diagnosability for augmented cubes under the PMC model. We show that the conditional diagnosability of an n-dimensional augmented cube is 8n – 27 for n≥5. | 2012 |
|
|
Data-Provenance Verification For Secure Hosts | Malicious software typically resides stealthily on a user’s computer and interacts with the user’s computing resources. Our goal in this work is to improve the trustworthiness of a host and its system data. Specifically, we provide a new mechanism that ensures the correct origin or provenance of critical system information and prevents adversaries from utilizing host resources. We define data-provenance integrity as the security property stating that the source where a piece of data is generated cannot be spoofed or tampered with. We describe a cryptographic provenance verification approach for ensuring system properties and system-data integrity at kernel-level. Its two concrete applications are demonstrated in the keystroke integrity verification and malicious traffic detection. Specifically, we first design and implement an efficient cryptographic protocol that enforces keystroke integrity by utilizing on-chip Trusted Computing Platform (TPM). The protocol prevents the forgery of fake key events by malware under reasonable assumptions. Then, we demonstrate our provenance verification approach by realizing a lightweight framework for restricting outbound malware traffic. This traffic-monitoring framework helps identify network activities of stealthy malware, and lends itself to a powerful personal firewall for examining all outbound traffic of a host that cannot be bypassed. | 2012 |
|
|
Detecting and Resolving Firewall Policy Anomalies | The advent of emerging computing technologies such as service-oriented architecture and cloud computing has enabled us to perform business services more efficiently and effectively. However, we still suffer from unintended security leakages by unauthorized actions in business services. Firewalls are the most widely deployed security mechanism to ensure the security of private networks in most businesses and institutions. The effectiveness of security protection provided by a firewall mainly depends on the quality of policy configured in the firewall. Unfortunately, designing and managing firewall policies are often error prone due to the complex nature of firewall configurations as well as the lack of systematic analysis mechanisms and tools. In this paper, we represent an innovative policy anomaly management framework for firewalls, adopting a rule-based segmentation technique to identify policy anomalies and derive effective anomaly resolutions. In particular, we articulate a grid-based representation technique, providing an intuitive cognitive sense about policy anomaly. We also discuss a proof-of-concept implementation of a visualization-based firewall policy analysis tool called Firewall Anomaly Management Environment (FAME). In addition, we demonstrate how efficiently our approach can discover and resolve anomalies in firewall policies through rigorous experiments | 2012 |
|
|
Enforcing Mandatory Access Control in Commodity OS to Disable Malware | Enforcing a practical Mandatory Access Control (MAC) in a commercial operating system to tackle malware problem is a grand challenge but also a promising approach. The firmest barriers to apply MAC to defeat malware programs are the incompatible and unusable problems in existing MAC systems. To address these issues, we manually analyze 2,600 malware samples one by one and two types of MAC enforced operating systems, and then design a novel MAC enforcement approach, named Tracer, which incorporates intrusion detection and tracing in a commercial operating system. The approach conceptually consists of three actions: detecting, tracing, and restricting suspected intruders. One novelty is that it leverages light-weight intrusion detection and tracing techniques to automate security label configuration that is widely acknowledged as a tough issue when applying a MAC system in practice. The other is that, rather than restricting information flow as a traditional MAC does, it traces intruders and restricts only their critical malware behaviors, where intruders represent processes and executables that are potential agents of a remote attacker. Our prototyping and experiments on Windows show that Tracer can effectively defeat all malware samples tested via blocking malware behaviors while not causing a significant compatibility problem | 2012 |
|
|
Extending Attack Graph-Based Security Metrics and Aggregating Their Application | The attack graph is an abstraction that reveals the ways an attacker can leverage vulnerabilities in a network to violate a security policy. When used with attack graph-based security metrics, the attack graph may be used to quantitatively assess security-relevant aspects of a network. The Shortest Path metric, the Number of Paths metric, and the Mean of Path Lengths metric are three attack graph-based security metrics that can extract security-relevant information. However, one’s usage of these metrics can lead to misleading results. The Shortest Path metric and the Mean of Path Lengths metric fail to adequately account for the number of ways an attacker may violate a security policy. The Number of Paths metric fails to adequately account for the attack effort associated with the attack paths. To overcome these shortcomings, we propose a complimentary suite of attack graph-based security metrics and specify an algorithm for combining the usage of these metrics. We present simulated results that suggest that our approach reaches a conclusion about which of two attack graphs correspond to a network that is most secure in many instances. | 2012 |
|
|
Incentive Compatible Privacy-Preserving Distributed Classification | In this paper, we propose game-theoretic mechanisms to encourage truthful data sharing for distributed data mining. One proposed mechanism uses the classic Vickrey-Clarke-Groves (VCG) mechanism, and the other relies on the Shapley value. Neither relies on the ability to verify the data of the parties participating in the distributed data mining protocol. Instead, we incentivize truth telling based solely on the data mining result. This is especially useful for situations where privacy concerns prevent verification of the data. Under reasonable assumptions, we prove that these mechanisms are incentive compatible for distributed data mining. In addition, through extensive experimentation, we show that they are applicable in practice. | 2012 |
|
|
Iterative Trust and Reputation Management Using Belief Propagation | In this paper, we introduce the first application of the belief propagation algorithm in the design and evaluation of trust and reputation management systems. We approach the reputation management problem as an inference problem and describe it as computing marginal likelihood distributions from complicated global functions of many variables. However, we observe that computing the marginal probability functions is computationally prohibitive for large-scale reputation systems. Therefore, we propose to utilize the belief propagation algorithm to efficiently (in linear complexity) compute these marginal probability distributions; resulting a fully iterative probabilistic and belief propagation-based approach (referred to as BP-ITRM). BP-ITRM models the reputation system on a factor graph. By using a factor graph, we obtain a qualitative representation of how the consumers (buyers) and service providers (sellers) are related on a graphical structure. Further, by using such a factor graph, the global functions factor into products of simpler local functions, each of which depends on a subset of the variables. Then, we compute the marginal probability distribution functions of the variables representing the reputation values (of the service providers) by message passing between nodes in the graph. We show that BP-ITRM is reliable in filtering out malicious/unreliable reports. We provide a detailed evaluation of BP-ITRM via analysis and computer simulations. We prove that BP-ITRM iteratively reduces the error in the reputation values of service providers due to the malicious raters with a high probability. Further, we observe that this probability drops suddenly if a particular fraction of malicious raters is exceeded, which introduces a threshold property to the scheme. Furthermore, comparison of BP-ITRM with some well-known and commonly used reputation management techniques (e.g., Averaging Scheme, Bayesian Approach, and Cluster Filtering) indicates the superiority of – he proposed scheme in terms of robustness against attacks (e.g., ballot stuffing, bad mouthing). Finally, BP-ITRM introduces a linear complexity in the number of service providers and consumers, far exceeding the efficiency of other schemes. | 2012 |
|
|
Large Margin Gaussian Mixture Models with Differential Privacy | As increasing amounts of sensitive personal information is aggregated into data repositories, it has become important to develop mechanisms for processing the data without revealing information about individual data instances. The differential privacy model provides a framework for the development and theoretical analysis of such mechanisms. In this paper, we propose an algorithm for learning a discriminatively trained multiclass Gaussian mixture model-based classifier that preserves differential privacy using a large margin loss function with a perturbed regularization term. We present a theoretical upper bound on the excess risk of the classifier introduced by the perturbation. | 2012 |
|
|
Low Energy Online Self-Test of Embedded Processors in Dependable WSN Nodes | Wireless Sensor Network (WSN) nodes are often deployed in harsh environments where the possibility of permanent and especially intermittent faults due to environmental hazards is significantly increased, while silicon aging effects are also exacerbated. Thus, online and in-field testing is necessary to guarantee correctness of operation. At the same time, online testing of processors integrated in WSN nodes has the requirement of minimum energy consumption, because these devices operate on battery, cannot be connected to any external power supply, and the battery duration determines the lifetime of the system. Software-Based Self-Test (SBST) has emerged as an effective strategy for online testing of processors integrated in nonsafety critical applications. However, the notion of dependability includes not only reliability but also availability. Thus, in order to encase both aspects we present a methodology for the optimization of SBST routines from the energy perspective. The refined methodology presented in this paper is able to be effectively applied in the case that the SBST routines are not initially available and need to be downloaded to the WSN nodes, as well as the case that the SBST routines are available in a flash memory. The methodology is extended to maximize the energy gains for WSN architectures offering clock gating or Dynamic Frequency Scaling features. Simulation results show that energy savings at processor level are up to 36.5 percent, which depending on the characteristics of the WSN system, can translate in several weeks of increased lifetime, especially if the routines need to be downloaded to the WSN node. | 2012 |
|
|
M-Score A Misuseability Weight Measure | Detecting and preventing data leakage and data misuse poses a serious challenge for organizations, especially when dealing with insiders with legitimate permissions to access the organization’s systems and its critical data. In this paper, we present a new concept, Misuseability Weight, for estimating the risk emanating from data exposed to insiders. This concept focuses on assigning a score that represents the sensitivity level of the data exposed to the user and by that predicts the ability of the user to maliciously exploit this data. Then, we propose a new measure, the M-score, which assigns a misuseability weight to tabular data, discuss some of its properties, and demonstrate its usefulness in several leakage scenarios. One of the main challenges in applying the M-score measure is in acquiring the required knowledge from a domain expert. Therefore, we present and evaluate two approaches toward eliciting misuseability conceptions from the domain expert.
|
2012 |
|
|
Quantitative Analysis of Consensus Algorithms | Consensus is one of the key problems in fault-tolerant distributed computing. Although the solvability of consensus is now a well-understood problem, comparing different algorithms in terms of efficiency is still an open problem. In this paper, we address this question for round-based consensus algorithms using communication predicates, on top of a partial synchronous system that alternates between good and bad periods (synchronous and nonsynchronous periods). Communication predicates together with the detailed timing information of the underlying partially synchronous system provide a convenient and powerful framework for comparing different consensus algorithms and their implementations. This approach allows us to quantify the required length of a good period to solve a given number of consensus instances. With our results, we can observe several interesting issues, such as the number of rounds of an algorithm is not necessarily a good metric for its performance. | 2012 |
|
|
Recommendation Models for Open Authorization | Major online platforms such as Facebook, Google, and Twitter allow third-party applications such as games, and productivity applications access to user online private data. Such accesses must be authorized by users at installation time. The Open Authorization protocol (OAuth) was introduced as a secure and efficient method for authorizing third-party applications without releasing a user’s access credentials. However, OAuth implementations don’t provide the necessary fine-grained access control, nor any recommendations, i.e., which access control decisions are most appropriate. We propose an extension to the OAuth 2.0 authorization that enables the provisioning of fine-grained authorization recommendations to users when granting permissions to third-party applications. We propose a multicriteria recommendation model that utilizes application-based, user-based, and category-based collaborative filtering mechanisms. Our collaborative filtering mechanisms are based on previous user decisions, and application permission requests to enhance the privacy of the overall site’s user population. We implemented our proposed OAuth extension as a browser extension that allows users to easily configure their privacy settings at application installation time, provides recommendations on requested privacy permissions, and collects data regarding user decisions. Our experiments on the collected data indicate that the proposed framework efficiently enhanced the user awareness and privacy related to third-party application authorizations. | 2012 |
|
|
Remote Attestation with Domain-Based Integrity Model and Policy Analysis | We propose and implement an innovative remote attestation framework called DR@FT for efficiently measuring a target system based on an information flow-based integrity model. With this model, the high integrity processes of a system are first measured and verified, and these processes are then protected from accesses initiated by low integrity processes. Toward dynamic systems with frequently changed system states, our framework verifies the latest state changes of a target system instead of considering the entire system information. Our attestation evaluation adopts a graph-based method to represent integrity violations, and the graph-based policy analysis is further augmented with a ranked violation graph to support high semantic reasoning of attestation results. As a result, DR@FT provides efficient and effective attestation of a system’s integrity status, and offers intuitive reasoning of attestation results for security administrators. Our experimental results demonstrate the feasibility and practicality of DR@FT.
|
2012 |
|
|
Revisiting Defenses against Large-Scale Online Password Guessing Attacks | Brute force and dictionary attacks on password-only remote login services are now widespread and ever increasing. Enabling convenient login for legitimate users while preventing such attacks is a difficult problem. Automated Turing Tests (ATTs) continue to be an effective, easy-to-deploy approach to identify automated malicious login attempts with reasonable cost of inconvenience to users. In this paper, we discuss the inadequacy of existing and proposed login protocols designed to address large-scale online dictionary attacks (e.g., from a botnet of hundreds of thousands of nodes). We propose a new Password Guessing Resistant Protocol (PGRP), derived upon revisiting prior proposals designed to restrict such attacks. While PGRP limits the total number of login attempts from unknown remote hosts to as low as a single attempt per username, legitimate users in most cases (e.g., when attempts are made from known, frequently-used machines) can make several failed login attempts before being challenged with an ATT. We analyze the performance of PGRP with two real-world data sets and find it more promising than existing proposals. | 2012 |
|
|
Risk-Aware Mitigation for MANET Routing Attacks | Mobile Ad hoc Networks (MANET) have been highly vulnerable to attacks due to the dynamic nature of its network infrastructure. Among these attacks, routing attacks have received considerable attention since it could cause the most devastating damage to MANET. Even though there exist several intrusion response techniques to mitigate such critical attacks, existing solutions typically attempt to isolate malicious nodes based on binary or naïve fuzzy response decisions. However, binary responses may result in the unexpected network partition, causing additional damages to the network infrastructure, and naïve fuzzy responses could lead to uncertainty in countering routing attacks in MANET. In this paper, we propose a risk-aware response mechanism to systematically cope with the identified routing attacks. Our risk-aware approach is based on an extended Dempster-Shafer mathematical theory of evidence introducing a notion of importance factors. In addition, our experiments demonstrate the effectiveness of our approach with the consideration of several performance metrics. | 2012 |
|
|
Secure Failure Detection and Consensus in TrustedPals | We present a modular redesign of TrustedPals, a smart card-based security framework for solving Secure Multiparty Computation (SMC). Originally, TrustedPals assumed a synchronous network setting and allowed to reduce SMC to the problem of fault-tolerant consensus among smart cards. We explore how to make TrustedPals applicable in environments with less synchrony and show how it can be used to solve asynchronous SMC. Within the redesign we investigate the problem of solving consensus in a general omission failure model augmented with failure detectors. To this end, we give novel definitions of both consensus and the class oP of failure detectors in the omission model, which we call ◇P(om), and show how to implement ◇P(om) and have consensus in such a system with very weak synchrony assumptions. The integration of failure detection and consensus into the TrustedPals framework uses tools from privacy enhancing techniques such as message padding and dummy traffic. | 2012 |
|
|
Stabilization Enabling Technology | In this work, we suggest hardware and software components that enable the creation of a self-stabilizing os/vmm on top of an off-the-shelf, nonself-stabilizing processor. A simple “watchdog” hardware that is called a periodic reset monitor (prm) provides a basic solution. The solution is extended to stabilization enabling hardware (seh) which removes any real time requirement from the os/vmm. A stabilization enabling system that extends the seh with software components provides the user (an os/vmm designer) with a self-stabilizing processor abstraction. The method uses only a modest addition of hardware, which is external to the microprocessor. We demonstrate our approach on the XScale core by Intel. Moreover, we suggest methods for the adaptation of existing system code (e.g., code for operating systems) to be self-stabilizing. One method allows capturing and enforcing the configuration used by the program, thus reducing the work of the self-stabilizing algorithm designer to considering only the dynamic (nonconfigurational) parts of the state. Another method is suggested for ensuring that, eventually, addresses of branch commands are examined using a sanity check segment. This method is then used to ensure that a sanity check is performed before critical operations. One application of the latter method is for enforcing a full separation of components in the system. | 2012 |
|
|
ZoneTrust Fast Zone-Based Node Compromise Detection and Revocation in Wireless Sensor Networks Using Sequential Hypothesis Testing | Due to the unattended nature of wireless sensor networks, an adversary can physically capture and compromise sensor nodes and then mount a variety of attacks with the compromised nodes. To minimize the damage incurred by the compromised nodes, the system should detect and revoke them as soon as possible. To meet this need, researchers have recently proposed a variety of node compromise detection schemes in wireless ad hoc and sensor networks. For example, reputation-based trust management schemes identify malicious nodes but do not revoke them due to the risk of false positives. Similarly, software-attestation schemes detect the subverted software modules of compromised nodes. However, they require each sensor node to be attested periodically, thus incurring substantial overhead. To mitigate the limitations of the existing schemes, we propose a zone-based node compromise detection and revocation scheme in wireless sensor networks. The main idea behind our scheme is to use sequential hypothesis testing to detect suspect regions in which compromised nodes are likely placed. In these suspect regions, the network operator performs software attestation against sensor nodes, leading to the detection and revocation of the compromised nodes. Through quantitative analysis and simulation experiments, we show that the proposed scheme detects the compromised nodes with a small number of samples while reducing false positive and negative rates, even if a substantial fraction of the nodes in the zone are compromised. Additionally, we model the detection problem using a game theoretic analysis, derive the optimal strategies for the attacker and the defender, and show that the attacker’s gain from node compromise is greatly limited by the defender when both the attacker and the defender follow their optimal strategies | 2012 |
| TECHNOLOGY : DOT NET
DOMAIN : IEEE TRANSACTIONS ON DATA MINIG |
| S.NO | TITLES | ABSTRACT | YEAR |
|
|
Scalable Learning Of Collective Behavior | This study of collective behavior is to understand how individuals behave in a social networking environment. Oceans of data generated by social media like Facebook, Twitter, Flickr, and YouTube present opportunities and challenges to study collective behavior on a large scale. we aim to learn to predict collective behavior in social media | 2012 |
|
|
Outsourced Similarity Search on Metric Data Assets | This paper considers a cloud computing setting in which similarity querying of metric data is outsourced to a service provider. The data is to be revealed only to trusted users, not to the service provider or anyone else. Users query the server for the most similar data objects to a query example. Outsourcing offers the data owner scalability and a low-initial investment. | 2012 |
|
|
Semi-Supervised Maximum Margin Clustering With Pairwise Constraints | This paper presents an analysis that suggests this problem degrades the quality of the clustering result, and it presents a new link-based approach, which improves the conventional matrix by discovering unknown entries through similarity between clusters in an ensemble. In particular, an efficient link-based algorithm is proposed for the underlying similarity assessment | 2012 |
|
|
Multiparty Access Control for Online Social Networks: Model and Mechanisms | In this paper, we propose an approach to enable the protection of shared data associated with multiple users in Online social networks. We formulate an access control model to capture the essence of multiparty authorization requirements, along with a multiparty policy speci?cation scheme and a policy enforcement mechanism | 2012 |
|
|
Manifold Adaptive Experimental Design for Text Categorization | In this paper, we propose a novel active learning algorithm which is performed in the data manifold adaptive kernel space. The manifold structure is incorporated into the kernel space by using graph Laplacian. This way, the manifold adaptive kernel space reflects the underlying geometry of the data | 2012 |
|
|
TSCAN: A Content Anatomy Approach to Temporal Topic Summarization | This paper defined as a seminal event or activity along with all directly related events and activities. It is represented by a chronological sequence of documents published by different authors on the Internet. In this study, we define a task called topic anatomy, which summarizes and associates the core parts of a topic temporally so that readers can understand the content easily | 2012 |
|
|
Slicing: A New Approach for Privacy Preserving Data Publishing Dotnet
|
Several anonymization techniques, such as generalization and bucketization, have been designed for privacy preserving
microdata publishing. Recent work has shown that generalization loses considerable amount of information, especially for highdimensional data. Bucketization, on the other hand, does not prevent membership disclosure and does not apply for data that do not have a clear separation between quasi-identifying attributes and sensitive attributes. In this paper, we present a novel technique called slicing, which partitions the data both horizontally and vertically. We show that slicing preserves better data utility than generalization and can be used for membership disclosure protection. Another important advantage of slicing is that it can handle high-dimensional data. We show how slicing can be used for attribute disclosure protection and develop an efficient algorithm for computing the sliced data that obey the ‘-diversity requirement. Our workload experiments confirm that slicing preserves better utility than generalization and is more effective than bucketization in workloads involving the sensitive attribute. Our experiments also demonstrate that slicing can be used to prevent membership disclosure. |
2012 |
|
|
Effective Pattern Discovery for Text Mining | Many data mining techniques have been proposed for mining useful patterns in text documents. However, how to effectively use and update discovered patterns is still an open research issue, especially in the domain of text mining. Since most existing text mining methods adopted term-based approaches, they all suffer from the problems of polysemy and synonymy. Over the years, people have often held the hypothesis that pattern (or phrase)-based approaches should perform better than the term-based ones, but many experiments do not support this hypothesis. This paper presents an innovative and effective pattern discovery technique which includes the processes of pattern deploying and pattern evolving, to improve the effectiveness of using and updating discovered patterns for finding relevant and interesting information. Substantial experiments on RCV1 data collection and TREC topics demonstrate that the proposed solution achieves encouraging performance | 2012 |
|
|
Decentralized probabilistic text clustering | Text clustering is an established technique for improving quality in information retrieval, for both centralized and distributed environments. However, traditional text clustering algorithms fail to scale on highly distributed environments, such as peer-to-peer networks. Our algorithm for peer-to-peer clustering achieves high scalability by using a probabilistic approach for assigning documents to clusters. It enables a peer to compare each of its documents only with very few selected clusters, without significant loss of clustering quality. The algorithm offers probabilistic guarantees for the correctness of each document assignment to a cluster. Extensive experimental evaluation with up to 1 million peers and 1 million documents demonstrates the scalability and effectiveness of the algorithm | 2012 |
|
|
Joint Top-K Spatial Keyword Query Processing | Web users and content are increasingly being geopositioned, and increased focus is being given to serving local content in response to web queries. This development calls for spatial keyword queries that take into account both the locations and textual descriptions of content. We study the efficient, joint processing of multiple top-k spatial keyword queries. Such joint processing is attractive during high query loads and also occurs when multiple queries are used to obfuscate a user’s true query. We propose a novel algorithm and index structure for the joint processing of top-k spatial keyword queries. Empirical studies show that the proposed solution is efficient on real data sets. We also offer analytical studies on synthetic data sets to demonstrate the efficiency of the proposed solution
|
2012 |
|
|
A Query Formulation Language for the Data Web | We present a query formulation language (called MashQL) in order to easily query and fuse structured data on the web. The main novelty of MashQL is that it allows people with limited IT skills to explore and query one (or multiple) data sources without prior knowledge about the schema, structure, vocabulary, or any technical details of these sources. More importantly, to be robust and cover most cases in practice, we do not assume that a data source should have – an offline or inline – schema. This poses several language-design and performance complexities that we fundamentally tackle. To illustrate the query formulation power of MashQL, and without loss of generality, we chose the Data web scenario. We also chose querying RDF, as it is the most primitive data model; hence, MashQL can be similarly used for querying relational databases and XML. We present two implementations of MashQL, an online mashup editor, and a Firefox add on. The former illustrates how MashQL can be used to query and mash up the Data web as simple as filtering and piping web feeds; and the Firefox add on illustrates using the browser as a web composer rather than only a navigator. To end, we evaluate MashQL on querying two data sets, DBLP and DBPedia, and show that our indexing techniques allow instant user interaction.
|
2012 |
|
|
A Genetic Programming Approach to Record Deduplication | Several systems that rely on consistent data to offer high-quality services, such as digital libraries and e-commerce brokers, may be affected by the existence of duplicates, quasi replicas, or near-duplicate entries in their repositories. Because of that, there have been significant investments from private and government organizations for developing methods for removing replicas from its data repositories. This is due to the fact that clean and replica-free repositories not only allow the retrieval of higher quality information but also lead to more concise data and to potential savings in computational time and resources to process this data. In this paper, we propose a genetic programming approach to record deduplication that combines several different pieces of evidence extracted from the data content to find a deduplication function that is able to identify whether two entries in a repository are replicas or not. As shown by our experiments, our approach outperforms an existing state-of-the-art method found in the literature. Moreover, the suggested functions are computationally less demanding since they use fewer evidence. In addition, our genetic programming approach is capable of automatically adapting these functions to a given fixed replica identification boundary, freeing the user from the burden of having to choose and tune this parameter. | 2012 |
|
|
A Knowledge-Driven Approach to Activity Recognition in Smart Homes | This paper introduces a knowledge-driven approach to real-time, continuous activity recognition based on multisensor data streams in smart homes. The approach goes beyond the traditional data-centric methods for activity recognition in three ways. First, it makes extensive use of domain knowledge in the life cycle of activity recognition. Second, it uses ontologies for explicit context and activity modeling and representation. Third and finally, it exploits semantic reasoning and classification for activity inferencing, thus enabling both coarse-grained and fine-grained activity recognition. In this paper, we analyze the characteristics of smart homes and Activities of Daily Living (ADL) upon which we built both context and ADL ontologies. We present a generic system architecture for the proposed knowledge-driven approach and describe the underlying ontology-based recognition process. Special emphasis is placed on semantic subsumption reasoning algorithms for activity recognition. The proposed approach has been implemented in a function-rich software system, which was deployed in a smart home research laboratory. We evaluated the proposed approach and the developed system through extensive experiments involving a number of various ADL use scenarios. An average activity recognition rate of 94.44 percent was achieved and the average recognition runtime per recognition operation was measured as 2.5 seconds. | 2012 |
|
|
A Framework for Personal Mobile Commerce Pattern Mining and Prediction | Due to a wide range of potential applications, research on mobile commerce has received a lot of interests from both of the industry and academia. Among them, one of the active topic areas is the mining and prediction of users’ mobile commerce behaviors such as their movements and purchase transactions. In this paper, we propose a novel framework, called Mobile Commerce Explorer (MCE), for mining and prediction of mobile users’ movements and purchase transactions under the context of mobile commerce. The MCE framework consists of three major components: 1) Similarity Inference Model (SIM) for measuring the similarities among stores and items, which are two basic mobile commerce entities considered in this paper; 2) Personal Mobile Commerce Pattern Mine (PMCP-Mine) algorithm for efficient discovery of mobile users’ Personal Mobile Commerce Patterns (PMCPs); and 3) Mobile Commerce Behavior Predictor (MCBP) for prediction of possible mobile user behaviors. To our best knowledge, this is the first work that facilitates mining and prediction of mobile users’ commerce behaviors in order to recommend stores and items previously unknown to a user. We perform an extensive experimental evaluation by simulation and show that our proposals produce excellent results.
|
2012 |
|
|
A Multidimensional Sequence Approach to Measuring Tree Similarity | Tree is one of the most common and well-studied data structures in computer science. Measuring the similarity of such structures is key to analyzing this type of data. However, measuring tree similarity is not trivial due to the inherent complexity of trees and the ensuing large search space. Tree kernel, a state of the art similarity measurement of trees, represents trees as vectors in a feature space and measures similarity in this space. When different features are used, different algorithms are required. Tree edit distance is another widely used similarity measurement of trees. It measures similarity through edit operations needed to transform one tree to another. Without any restrictions on edit operations, the computation cost is too high to be applicable to large volume of data. To improve efficiency of tree edit distance, some approximations were introduced into tree edit distance. However, their effectiveness can be compromised. In this paper, a novel approach to measuring tree similarity is presented. Trees are represented as multidimensional sequences and their similarity is measured on the basis of their sequence representations. Multidimensional sequences have their sequential dimensions and spatial dimensions. We measure the sequential similarity by the all common subsequences sequence similarity measurement or the longest common subsequence measurement, and measure the spatial similarity by dynamic time warping. Then we combine them to give a measure of tree similarity. A brute force algorithm to calculate the similarity will have high computational cost. In the spirit of dynamic programming two efficient algorithms are designed for calculating the similarity, which have quadratic time complexity. The new measurements are evaluated in terms of classification accuracy in two popular classifiers (k-nearest neighbor and support vector machine) and in terms of search effectiveness and efficiency in k-nearest neighbor similarity search, using three differ- nt data sets from natural language processing and information retrieval. Experimental results show that the new measurements outperform the benchmark measures consistently and significantly. | 2012 |
|
|
A Query Formulation Language for the Data Web | We present a query formulation language (called MashQL) in order to easily query and fuse structured data on the web. The main novelty of MashQL is that it allows people with limited IT skills to explore and query one (or multiple) data sources without prior knowledge about the schema, structure, vocabulary, or any technical details of these sources. More importantly, to be robust and cover most cases in practice, we do not assume that a data source should have – an offline or inline – schema. This poses several language-design and performance complexities that we fundamentally tackle. To illustrate the query formulation power of MashQL, and without loss of generality, we chose the Data web scenario. We also chose querying RDF, as it is the most primitive data model; hence, MashQL can be similarly used for querying relational databases and XML. We present two implementations of MashQL, an online mashup editor, and a Firefox add on. The former illustrates how MashQL can be used to query and mash up the Data web as simple as filtering and piping web feeds; and the Firefox add on illustrates using the browser as a web composer rather than only a navigator. To end, we evaluate MashQL on querying two data sets, DBLP and DBPedia, and show that our indexing techniques allow instant user interaction. | 2012 |
|
|
A Temporal Pattern Search Algorithm for Personal History Event Visualization | We present Temporal Pattern Search (TPS), a novel algorithm for searching for temporal patterns of events in historical personal histories. The traditional method of searching for such patterns uses an automaton-based approach over a single array of events, sorted by time stamps. Instead, TPS operates on a set of arrays, where each array contains all events of the same type, sorted by time stamps. TPS searches for a particular item in the pattern using a binary search over the appropriate arrays. Although binary search is considerably more expensive per item, it allows TPS to skip many unnecessary events in personal histories. We show that TPS’s running time is bounded by O(m2n lg(n)), where m is the length of (number of events) a search pattern, and n is the number of events in a record (history). Although the asymptotic running time of TPS is inferior to that of a nondeterministic finite automaton (NFA) approach (O(mn)), TPS performs better than NFA under our experimental conditions. We also show TPS is very competitive with Shift-And, a bit-parallel approach, with real data. Since the experimental conditions we describe here subsume the conditions under which analysts would typically use TPS (i.e., within an interactive visualization program), we argue that TPS is an appropriate design choice for us.
|
2012 |
|
|
A Variational Bayesian Framework for Clustering with Multiple Graphs | Mining patterns in graphs has become an important issue in real applications, such as bioinformatics and web mining. We address a graph clustering problem where a cluster is a set of densely connected nodes, under a practical setting that 1) the input is multiple graphs which share a set of nodes but have different edges and 2) a true cluster cannot be found in all given graphs. For this problem, we propose a probabilistic generative model and a robust learning scheme based on variational Bayesian estimation. A key feature of our probabilistic framework is that not only nodes but also given graphs can be clustered at the same time, allowing our model to capture clusters found in only part of all given graphs. We empirically evaluated the effectiveness of the proposed framework on not only a variety of synthetic graphs but also real gene networks, demonstrating that our proposed approach can improve the clustering performance of competing methods in both synthetic and real data.
|
2012 |
|
|
Agglomerative Mean-Shift Clustering | Mean-Shift (MS) is a powerful nonparametric clustering method. Although good accuracy can be achieved, its computational cost is particularly expensive even on moderate data sets. In this paper, for the purpose of algorithmic speedup, we develop an agglomerative MS clustering method along with its performance analysis. Our method, namely Agglo-MS, is built upon an iterative query set compression mechanism which is motivated by the quadratic bounding optimization nature of MS algorithm. The whole framework can be efficiently implemented in linear running time complexity. We then extend Agglo-MS into an incremental version which performs comparably to its batch counterpart. The efficiency and accuracy of Agglo-MS are demonstrated by extensive comparing experiments on synthetic and real data sets.
|
2012 |
|
|
Continuous Top-k Dominating Queries | Top-k dominating queries use an intuitive scoring function which ranks multidimensional points with respect to their dominance power, i.e., the number of points that a point dominates. The k points with the best (e.g., highest) scores are returned to the user. Both top-k and skyline queries have been studied in a streaming environment, where changes to the data set are very frequent. In such an environment, continuous query processing techniques are required toward efficient monitoring of query results, since periodic query re-execution is computationally intensive, and therefore, prohibitive. This work contains the first study of continuous top-k dominating queries over data streams. In comparison to continuous top-k and skyline queries, continuous top-k dominating queries pose additional challenges. Three exact algorithms (BFA, EVA, ADA) are studied, and among them ADA, which is enhanced with additional optimization techniques, shows the best overall performance. In some cases, we are willing to trade accuracy for speed. Toward this direction, two approximate algorithms are proposed (AHBA and AMSA). AHBA offers probabilistic guarantees regarding the accuracy of the result based on the Hoeffding bound, whereas AMSA performs a more aggressive computation resulting in more efficient processing. Evaluation results, based on real-life and synthetic data sets, show the efficiency and scalability of our techniques. | 2012 |
|
|
Creating Evolving User Behavior Profiles Automatically | Knowledge about computer users is very beneficial for assisting them, predicting their future actions or detecting masqueraders. In this paper, a new approach for creating and recognizing automatically the behavior profile of a computer user is presented. In this case, a computer user behavior is represented as the sequence of the commands she/he types during her/his work. This sequence is transformed into a distribution of relevant subsequences of commands in order to find out a profile that defines its behavior. Also, because a user profile is not necessarily fixed but rather it evolves/changes, we propose an evolving method to keep up to date the created profiles using an Evolving Systems approach. In this paper, we combine the evolving classifier with a trie-based user profiling to obtain a powerful self-learning online scheme. We also develop further the recursive formula of the potential of a data point to become a cluster center using cosine distance, which is provided in the Appendix. The novel approach proposed in this paper can be applicable to any problem of dynamic/evolving user behavior modeling where it can be represented as a sequence of actions or events. It has been evaluated on several real data streams.
|
2012 |
|
|
D-Cache Universal Distance Cache for Metric Access Methods | The caching of accessed disk pages has been successfully used for decades in database technology, resulting in effective amortization of I/O operations needed within a stream of query or update requests. However, in modern complex databases, like multimedia databases, the I/O cost becomes a minor performance factor. In particular, metric access methods (MAMs), used for similarity search in complex unstructured data, have been designed to minimize rather the number of distance computations than I/O cost (when indexing or querying). Inspired by I/O caching in traditional databases, in this paper we introduce the idea of distance caching for usage with MAMs – a novel approach to streamline similarity search. As a result, we present the D-cache, a main-memory data structure which can be easily implemented into any MAM, in order to spare the distance computations spent by queries/updates. In particular, we have modified two state-of-the-art MAMs to make use of D-cache – the M-tree and Pivot tables. Moreover, we present the D-file, an index-free MAM based on simple sequential search augmented by D-cache. The experimental evaluation shows that performance gain achieved due to D-cache is significant for all the MAMs, especially for the D-file | 2012 |
|
|
Extending Attribute Information for Small Data Set Classification | Data quantity is the main issue in the small data set problem, because usually insufficient data will not lead to a robust classification performance. How to extract more effective information from a small data set is thus of considerable interest. This paper proposes a new attribute construction approach which converts the original data attributes into a higher dimensional feature space to extract more attribute information by a similarity-based algorithm using the classification-oriented fuzzy membership function. Seven data sets with different attribute sizes are employed to examine the performance of the proposed method. The results show that the proposed method has a superior classification performance when compared to principal component analysis (PCA), kernel principal component analysis (KPCA), and kernel independent component analysis (KICA) with a Gaussian kernel in the support vector machine (SVM) classifier. | 2012 |
|
|
Fuzzy Orders-of-Magnitude-Based Link Analysis for Qualitative Alias Detection | Alias detection has been the significant subject being extensively studied for several domain applications, especially intelligence data analysis. Many preliminary methods rely on text-based measures, which are ineffective with false descriptions of terrorists’ name, date-of-birth, and address. This barrier may be overcome through link information presented in relationships among objects of interests. Several numerical link-based similarity techniques have proven effective for identifying similar objects in the Internet and publication domains. However, as a result of exceptional cases with unduly high measure, these methods usually generate inaccurate similarity descriptions. Yet, they are either computationally inefficient or ineffective for alias detection with a single-property based model. This paper presents a novel orders-of-magnitude based similarity measure that integrates multiple link properties to refine the estimation process and derive semantic-rich similarity descriptions. The approach is based on order-of-magnitude reasoning with which the theory of fuzzy set is blended to provide quantitative semantics of descriptors and their unambiguous mathematical manipulation. With such explanatory formalism, analysts can validate the generated results and partly resolve the problem of false positives. It also allows coherent interpretation and communication within a decision-making group, using this computing-with-word capability. Its performance is evaluated over a terrorism-related data set, with further generalization over publication and email data collections.
|
2012 |
|
|
Holistic Top-k Simple Shortest Path Join in Graphs | Motivated by the needs such as group relationship analysis, this paper introduces a new operation on graphs, named top-k path join, which discovers the top-k simple shortest paths between two given node sets. Rather than discovering the top-k simple paths between each node pair, this paper proposes a holistic join method which answers the top-k path join by finding constrained top-k simple shortest paths between two nodes, and then devises an efficient method to handle the latter problem. Specifically, we transform the graph by encoding the precomputed shortest paths to the target node, and use the transformed graph in the candidate path searching. We show that the candidate path searching on the transformed graph not only has the same result as that on the original graph but also can be terminated much earlier with the aid of precomputed results. We also discuss two other optimization strategies, including considering the join constraint in the candidate path generation as early as possible, and pruning search space in each candidate path generation with an adaptively determined threshold. The final extensive experimental results also show that our method offers a significant performance improvement over existing ones.
|
2012 |
|
|
Identifying Evolving Groups in Dynamic Multimode Networks | A multimode network consists of heterogeneous types of actors with various interactions occurring between them. Identifying communities in a multimode network can help understand the structural properties of the network, address the data shortage and unbalanced problems, and assist tasks like targeted marketing and finding influential actors within or between groups. In general, a network and its group structure often evolve unevenly. In a dynamic multimode network, both group membership and interactions can evolve, posing a challenging problem of identifying these evolving communities. In this work, we try to address this problem by employing the temporal information to analyze a multimode network. A temporally regularized framework and its convergence property are carefully studied. We show that the algorithm can be interpreted as an iterative latent semantic analysis process, which allows for extensions to handle networks with actor attributes and within-mode interactions. Experiments on both synthetic data and real-world networks demonstrate the efficacy of our approach and suggest its generality in capturing evolving groups in networks with heterogeneous entities and complex relationships. | 2012 |
|
|
Incremental Information Extraction Using Relational Databases | Information extraction systems are traditionally implemented as a pipeline of special-purpose processing modules targeting the extraction of a particular kind of information. A major drawback of such an approach is that whenever a new extraction goal emerges or a module is improved, extraction has to be reapplied from scratch to the entire text corpus even though only a small part of the corpus might be affected. In this paper, we describe a novel approach for information extraction in which extraction needs are expressed in the form of database queries, which are evaluated and optimized by database systems. Using database queries for information extraction enables generic extraction and minimizes reprocessing of data by performing incremental extraction to identify which part of the data is affected by the change of components or goals. Furthermore, our approach provides automated query generation components so that casual users do not have to learn the query language in order to perform extraction. To demonstrate the feasibility of our incremental extraction approach, we performed experiments to highlight two important aspects of an information extraction system: efficiency and quality of extraction results. Our experiments show that in the event of deployment of a new module, our incremental extraction approach reduces the processing time by 89.64 percent as compared to a traditional pipeline approach. By applying our methods to a corpus of 17 million biomedical abstracts, our experiments show that the query performance is efficient for real-time applications. Our experiments also revealed that our approach achieves high quality extraction results. | 2012 |
|
|
Learning a Propagable Graph for Semisupervised Learning Classification and Regression | In this paper, we present a novel framework, called learning by propagability, for two essential data mining tasks, i.e., classification and regression. The whole learning process is driven by the philosophy that the data labels and the optimal feature representation jointly constitute a harmonic system, where the data labels are invariant with respect to the propagation on the similarity graph constructed based on the optimal feature representation. Based on this philosophy, a unified framework of learning by propagability is proposed for the purposes of both classification and regression. Specifically, this framework has three characteristics: 1) the formulation unifies the label propagation and optimal feature representation pursuing, and thus the label propagation process is enhanced by benefiting from the refined similarity graph constructed with the derived optimal feature representation instead of the original representation; 2) it unifies the formulations for supervised and semisupervised learning in both classification and regression tasks; and 3) it can directly deal with the multiclass classification problems. Extensive experiments for the classification task on UCI toy data sets, handwritten digit recognition, face recognition, and microarray recognition as well as for the regression task of human age estimation on the FG-NET aging database, all validate the effectiveness of our proposed learning framework, compared with the state-of-the-art counterparts. | 2012 |
|
|
Locally Discriminative Coclustering | Different from traditional one-sided clustering techniques, coclustering makes use of the duality between samples and features to partition them simultaneously. Most of the existing co-clustering algorithms focus on modeling the relationship between samples and features, whereas the intersample and interfeature relationships are ignored. In this paper, we propose a novel coclustering algorithm named Locally Discriminative Coclustering (LDCC) to explore the relationship between samples and features as well as the intersample and interfeature relationships. Specifically, the sample-feature relationship is modeled by a bipartite graph between samples and features. And we apply local linear regression to discovering the intrinsic discriminative structures of both sample space and feature space. For each local patch in the sample and feature spaces, a local linear function is estimated to predict the labels of the points in this patch. The intersample and interfeature relationships are thus captured by minimizing the fitting errors of all the local linear functions. In this way, LDCC groups strongly associated samples and features together, while respecting the local structures of both sample and feature spaces. Our experimental results on several benchmark data sets have demonstrated the effectiveness of the proposed method.
|
2012 |
|
|
Manifold Adaptive Experimental Design for Text Categorization | In many information processing tasks, labels are usually expensive and the unlabeled data points are abundant. To reduce the cost on collecting labels, it is crucial to predict which unlabeled examples are the most informative, i.e., improve the classifier the most if they were labeled. Many active learning techniques have been proposed for text categorization, such as SVMActive and Transductive Experimental Design. However, most of previous approaches try to discover the discriminant structure of the data space, whereas the geometrical structure is not well respected. In this paper, we propose a novel active learning algorithm which is performed in the data manifold adaptive kernel space. The manifold structure is incorporated into the kernel space by using graph Laplacian. This way, the manifold adaptive kernel space reflects the underlying geometry of the data. By minimizing the expected error with respect to the optimal classifier, we can select the most representative and discriminative data points for labeling. Experimental results on text categorization have demonstrated the effectiveness of our proposed approach. | 2012 |
|
|
Measuring the Sky On Computing Data Cubes via Skylining the Measures | Data cube is a key element in supporting fast OLAP. Traditionally, an aggregate function is used to compute the values in data cubes. In this paper, we extend the notion of data cubes with a new perspective. Instead of using an aggregate function, we propose to build data cubes using the skyline operation as the “aggregate function.” Data cubes built in this way are called “group-by skyline cubes” and can support a variety of analytical tasks. Nevertheless, there are several challenges in implementing group-by skyline cubes in data warehouses: 1) the skyline operation is computational intensive, 2) the skyline operation is holistic, and 3) a group-by skyline cube contains both grouping and skyline dimensions, rendering it infeasible to precompute all cuboids in advance. This paper gives details on how to store, materialize, and query such cubes. | 2012 |
|
|
Mutual Information-Based Supervised Attribute Clustering for Microarray Sample Classification | Microarray technology is one of the important biotechnological means that allows to record the expression levels of thousands of genes simultaneously within a number of different samples. An important application of microarray gene expression data in functional genomics is to classify samples according to their gene expression profiles. Among the large amount of genes presented in gene expression data, only a small fraction of them is effective for performing a certain diagnostic test. Hence, one of the major tasks with the gene expression data is to find groups of coregulated genes whose collective expression is strongly associated with the sample categories or response variables. In this regard, a new supervised attribute clustering algorithm is proposed to find such groups of genes. It directly incorporates the information of sample categories into the attribute clustering process. A new quantitative measure, based on mutual information, is introduced that incorporates the information of sample categories to measure the similarity between attributes. The proposed supervised attribute clustering algorithm is based on measuring the similarity between attributes using the new quantitative measure, whereby redundancy among the attributes is removed. The clusters are then refined incrementally based on sample categories. The performance of the proposed algorithm is compared with that of existing supervised and unsupervised gene clustering and gene selection algorithms based on the class separability index and the predictive accuracy of naive bayes classifier, K-nearest neighbor rule, and support vector machine on three cancer and two arthritis microarray data sets. The biological significance of the generated clusters is interpreted using the gene ontology. An important finding is that the proposed supervised attribute clustering algorithm is shown to be effective for identifying biologically significant gene clusters with excellent predictive capability.
|
2012 |
|
|
On the Spectral Characterization and Scalable Mining of Network Communities | Network communities refer to groups of vertices within which their connecting links are dense but between which they are sparse. A network community mining problem (or NCMP for short) is concerned with the problem of finding all such communities from a given network. A wide variety of applications can be formulated as NCMPs, ranging from social and/or biological network analysis to web mining and searching. So far, many algorithms addressing NCMPs have been developed and most of them fall into the categories of either optimization based or heuristic methods. Distinct from the existing studies, the work presented in this paper explores the notion of network communities and their properties based on the dynamics of a stochastic model naturally introduced. In the paper, a relationship between the hierarchical community structure of a network and the local mixing properties of such a stochastic model has been established with the large-deviation theory. Topological information regarding to the community structures hidden in networks can be inferred from their spectral signatures. Based on the above-mentioned relationship, this work proposes a general framework for characterizing, analyzing, and mining network communities. Utilizing the two basic properties of metastability, i.e., being locally uniform and temporarily fixed, an efficient implementation of the framework, called the LM algorithm, has been developed that can scalably mine communities hidden in large-scale networks. The effectiveness and efficiency of the LM algorithm have been theoretically analyzed as well as experimentally validated. | 2012 |
|
|
Organizing User Search Histories | Users are increasingly pursuing complex task-oriented goals on the web, such as making travel arrangements, managing finances, or planning purchases. To this end, they usually break down the tasks into a few codependent steps and issue multiple queries around these steps repeatedly over long periods of time. To better support users in their long-term information quests on the web, search engines keep track of their queries and clicks while searching online. In this paper, we study the problem of organizing a user’s historical queries into groups in a dynamic and automated fashion. Automatically identifying query groups is helpful for a number of different search engine components and applications, such as query suggestions, result ranking, query alterations, sessionization, and collaborative search. In our approach, we go beyond approaches that rely on textual similarity or time thresholds, and we propose a more robust approach that leverages search query logs. We experimentally study the performance of different techniques, and showcase their potential, especially when combined together. | 2012 |
|
|
Outsourced Similarity Search on Metric Data Assets | This paper considers a cloud computing setting in which similarity querying of metric data is outsourced to a service provider. The data is to be revealed only to trusted users, not to the service provider or anyone else. Users query the server for the most similar data objects to a query example. Outsourcing offers the data owner scalability and a low-initial investment. The need for privacy may be due to the data being sensitive (e.g., in medicine), valuable (e.g., in astronomy), or otherwise confidential. Given this setting, the paper presents techniques that transform the data prior to supplying it to the service provider for similarity queries on the transformed data. Our techniques provide interesting trade-offs between query cost and accuracy. They are then further extended to offer an intuitive privacy guarantee. Empirical studies with real data demonstrate that the techniques are capable of offering privacy while enabling efficient and accurate processing of similarity queries. | 2012 |
|
|
Query Planning for Continuous Aggregation Queries over a Network of Data Aggregators | Continuous queries are used to monitor changes to time varying data and to provide results useful for online decision making. Typically a user desires to obtain the value of some aggregation function over distributed data items, for example, to know value of portfolio for a client; or the AVG of temperatures sensed by a set of sensors. In these queries a client specifies a coherency requirement as part of the query. We present a low-cost, scalable technique to answer continuous aggregation queries using a network of aggregators of dynamic data items. In such a network of data aggregators, each data aggregator serves a set of data items at specific coherencies. Just as various fragments of a dynamic webpage are served by one or more nodes of a content distribution network, our technique involves decomposing a client query into subqueries and executing subqueries on judiciously chosen data aggregators with their individual subquery incoherency bounds. We provide a technique for getting the optimal set of subqueries with their incoherency bounds which satisfies client query’s coherency requirement with least number of refresh messages sent from aggregators to the client. For estimating the number of refresh messages, we build a query cost model which can be used to estimate the number of messages required to satisfy the client specified incoherency bound. Performance results using real-world traces show that our cost-based query planning leads to queries being executed using less than one third the number of messages required by existing schemes | 2012 |
|
|
Reconstructing Missing Data in State Estimation With Autoencoders | This paper presents the proof of concept for a new solution to the problem of recomposing missing information at the SCADA of energy/distribution management systems (EMS/DMS), through the use of offline trained autoencoders. These are neural networks with a special architecture, which allows them to store knowledge about a system in a nonlinear manifold characterized by their weights. Suitable algorithms may then recompose missing inputs (measurements). The paper shows that, trained with adequate information, autoencoders perform well in recomposing missing voltage and power values, and focuses on the particularly important application of inferring the topology of the network when information about switch status is absent. Examples with the IEEE RTS 24-bus network are presented to illustrate the concept and technique.
|
2012 |
|
|
ROAD A New Spatial Object Search Framework for Road Networks | In this paper, we present a new system framework called ROAD for spatial object search on road networks. ROAD is extensible to diverse object types and efficient for processing various location-dependent spatial queries (LDSQs), as it maintains objects separately from a given network and adopts an effective search space pruning technique. Based on our analysis on the two essential operations for LDSQ processing, namely, network traversal and object lookup, ROAD organizes a large road network as a hierarchy of interconnected regional subnetworks (called Rnets). Each Rnet is augmented with 1) shortcuts and 2) object abstracts to accelerate network traversals and provide quick object lookups, respectively. To manage those shortcuts and object abstracts, two cooperating indices, namely, Route Overlay and Association Directory are devised. In detail, we present 1) the Rnet hierarchy and several properties useful in constructing and maintaining the Rnet hierarchy, 2) the design and implementation of the ROAD framework, and 3) a suite of efficient search algorithms for single-source LDSQs and multisource LDSQs. We conduct a theoretical performance analysis and carry out a comprehensive empirical study to evaluate ROAD. The analysis and experiment results show the superiority of ROAD over the state-of-the-art approaches. | 2012 |
|
|
Scalable Scheduling of Updates in Streaming Data Warehouses | We discuss update scheduling in streaming data warehouses, which combine the features of traditional data warehouses and data stream systems. In our setting, external sources push append-only data streams into the warehouse with a wide range of interarrival times. While traditional data warehouses are typically refreshed during downtimes, streaming warehouses are updated as new data arrive. We model the streaming warehouse update problem as a scheduling problem, where jobs correspond to processes that load new data into tables, and whose objective is to minimize data staleness over time (at time t, if a table has been updated with information up to some earlier time r, its staleness is t minus r). We then propose a scheduling framework that handles the complications encountered by a stream warehouse: view hierarchies and priorities, data consistency, inability to preempt updates, heterogeneity of update jobs caused by different interarrival times and data volumes among different sources, and transient overload. A novel feature of our framework is that scheduling decisions do not depend on properties of update jobs (such as deadlines), but rather on the effect of update jobs on data staleness. Finally, we present a suite of update scheduling algorithms and extensive simulation experiments to map out factors which affect their performance | 2012 |
|
|
Software Fault Prediction Using Quad Tree-Based K-Means Clustering Algorithm | Unsupervised techniques like clustering may be used for fault prediction in software modules, more so in those cases where fault labels are not available. In this paper a Quad Tree-based K-Means algorithm has been applied for predicting faults in program modules. The aims of this paper are twofold. First, Quad Trees are applied for finding the initial cluster centers to be input to the A’-Means Algorithm. An input threshold parameter δ governs the number of initial cluster centers and by varying δ the user can generate desired initial cluster centers. The concept of clustering gain has been used to determine the quality of clusters for evaluation of the Quad Tree-based initialization algorithm as compared to other initialization techniques. The clusters obtained by Quad Tree-based algorithm were found to have maximum gain values. Second, the Quad Tree- based algorithm is applied for predicting faults in program modules. The overall error rates of this prediction approach are compared to other existing algorithms and are found to be better in most of the cases. | 2012 |
|
|
Synthesizing Ontology Alignment Methods Using the Max-Sum Algorithm | This paper addresses the problem of synthesizing ontology alignment methods by maximizing the social welfare within a group of interacting agents: Specifically, each agent is responsible for computing mappings concerning a specific ontology element, using a specific alignment method. Each agent interacts with other agents with whom it shares constraints concerning the validity of the mappings it computes. Interacting agents form a bipartite factor graph, composed of variable and function nodes, representing alignment decisions and utilities, respectively. Agents need to reach an agreement to the mapping of the ontology elements consistently to the semantics of specifications with respect to their mapping preferences. Addressing the synthesis problem in such a way allows us to use an extension of the max-sum algorithm to generate near-to-optimal solutions to the alignment of ontologies through local decentralized message passing. We show the potential of such an approach by synthesizing a number of alignment methods, studying their performance in the OAEI benchmark series. | 2012 |
| 42 | Understanding Errors in Approximate Distributed Latent Dirichlet Allocation | Latent Dirichlet allocation (LDA) is a popular algorithm for discovering semantic structure in large collections of text or other data. Although its complexity is linear in the data size, its use on increasingly massive collections has created considerable interest in parallel implementations. “Approximate distributed” LDA, or AD-LDA, approximates the popular collapsed Gibbs sampling algorithm for LDA models while running on a distributed architecture. Although this algorithm often appears to perform well in practice, its quality is not well understood theoretically or easily assessed on new data. In this work, we theoretically justify the approximation, and modify AD-LDA to track an error bound on performance. Specifically, we upper bound the probability of making a sampling error at each step of the algorithm (compared to an exact, sequential Gibbs sampler), given the samples drawn thus far. We show empirically that our bound is sufficiently tight to give a meaningful and intuitive measure of approximation error in AD-LDA, allowing the user to track the tradeoff between accuracy and efficiency while executing in parallel. | 2012 |
| 43 | Weakly Supervised Joint Sentiment-Topic Detection from Text | Sentiment analysis or opinion mining aims to use automated tools to detect subjective information such as opinions, attitudes, and feelings expressed in text. This paper proposes a novel probabilistic modeling framework called joint sentiment-topic (JST) model based on latent Dirichlet allocation (LDA), which detects sentiment and topic simultaneously from text. A reparameterized version of the JST model called Reverse-JST, obtained by reversing the sequence of sentiment and topic generation in the modeling process, is also studied. Although JST is equivalent to Reverse-JST without a hierarchical prior, extensive experiments show that when sentiment priors are added, JST performs consistently better than Reverse-JST. Besides, unlike supervised approaches to sentiment classification which often fail to produce satisfactory performance when shifting to other domains, the weakly supervised nature of JST makes it highly portable to other domains. This is verified by the experimental results on data sets from five different domains where the JST model even outperforms existing semi-supervised approaches in some of the data sets despite using no labeled documents. Moreover, the topics and topic sentiment detected by JST are indeed coherent and informative. We hypothesize that the JST model can readily meet the demand of large-scale sentiment analysis from the web in an open-ended fashion. | 2012 |
| TECHNOLOGY : DOT NET
DOMAIN : IEEE TRANSACTIONS ON MOBILE COMPUTING |
| S.NO | TITLES | ABSTRACT | YEAR |
|
|
Toward Reliable Data Delivery for Highly Dynamic Mobile Ad Hoc Networks. | This paper addresses the problem of delivering data packets for highly dynamic mobile ad hoc networks in a reliable and timely manner. Most existing ad hoc routing protocols are susceptible to node mobility, especially for large-scale networks. Driven by this issue, we propose an efficient Position-based Opportunistic Routing (POR) protocol which takes advantage of the stateless property of geographic routing and the broadcast nature of wireless medium. | 2012 |
|
|
Hop-by-Hop Routing in Wireless Mesh Networks with Bandwidth Guarantees. | Wireless Mesh Network (WMN) has become an important edge network to provide Internet access to remote areas and wireless connections in a metropolitan scale. In this paper, we study the problem of identifying the maximum available bandwidth path, a fundamental issue in supporting quality-of-service in WMNs. Due to interference among links, bandwidth, a well-known bottleneck metric in wired networks, is neither concave nor additive in wireless networks. | 2012 |
|
|
Fast Data Collection in Tree-Based Wireless Sensor Networks | We investigate the following fundamental question—how fast can information be collected from a wireless sensor network organized as tree? To address this, we explore and evaluate a number of different techniques using realistic simulation models under the many-to-one communication paradigm known as converge cast. We first consider time scheduling on a single frequency channel with the aim of minimizing the number of time slots required (schedule length) to complete a converge cast. | 2012 |
|
|
Energy-Efficient Strategies for Cooperative Multichannel MAC Protocols | Distributed Information Sharing (DISH) is a new cooperative approach to designing multichannel MAC protocols. It aids nodes in their decision making processes by compensating for their missing information via information sharing through neighboring nodes. This approach was recently shown to significantly boost the throughput of multichannel MAC protocols. | 2012 |
|
|
Soft-TDMAC: A Software-Based 802.11 Overlay TDMA MAC with Microsecond Synchronization. | We implement a new software-based multi-hop TDMA MAC protocol (Soft-TDMAC) with microsecond synchronization using a novel system interface for development of 802.11 overlay TDMA MAC protocols (SySI-MAC). SySI-MAC provides a kernel independent message-based interface for scheduling transmissions and sending and receiving 802.11 packets. | 2012 |
|
|
Link Positions Matter: A Non commutative Routing Metric for Wireless Mesh Networks. | We revisit the problem of computing the path with the minimum cost in terms of the expected number of link layer transmissions) in wireless mesh networks. Unlike previous efforts, such as the popular ETX, we account for the fact that MAC protocols incorporate a finite number of transmission attempts per packet. This in turn leads to our key observation: the performance of a path depends not only on the number of the links on the path and the quality of its links, but also, on the relative positions of the links on the path | 2012 |
|
|
Local Greedy Approximation for Scheduling in Multihop Wireless Networks 2012 Dotnet Mobile Computing | In recent years, there has been a significant amount of work done in developing low-complexity scheduling schemes to
achieve high performance in multihop wireless networks. A centralized suboptimal scheduling policy, called Greedy Maximal Scheduling (GMS) is a good candidate because its empirically observed performance is close to optimal in a variety of network settings. However, its distributed realization requires high complexity, which becomes a major obstacle for practical implementation. In this paper, we develop simple distributed greedy algorithms for scheduling in multihop wireless networks. We reduce the complexity by relaxing the global ordering requirement of GMS, up to near zero. Simulation results show that the new algorithms approximate the performance of GMS, and outperform the state-of-the-art distributed scheduling policies.
|
2012 |
|
|
Network Assisted Mobile Computing with Optimal Uplink Query Processing 2012 Dotnet Mobile Computing
|
Many mobile applications retrieve content from remote servers via user generated queries. Processing these queries is often needed before the desired content can be identified. Processing the request on the mobile devices can quickly sap the limited battery resources. Conversely, processing user-queries at remote servers can have slow response times due communication latency incurred during transmission of the potentially large query. We evaluate a network-assisted mobile computing scenario where midnetwork nodes with “leasing” capabilities are deployed by a service provider. Leasing computation power can reduce battery usage on the mobile devices and improve response times. However, borrowing processing power from mid-network nodes comes at a leasing cost which must be accounted for when making the decision of where processing should occur. We study the tradeoff between battery usage, processing and transmission latency, and mid-network leasing. We use the dynamic programming framework to solve for the optimal processing policies that suggest the amount of processing to be done at each mid-network node in order to minimize the processing and communication latency and processing costs. Through numerical studies, we examine the properties of the optimal processing policy and the core tradeoffs in such systems. | 2012 |
|
|
A Cost Analysis Framework for NEMO Prefix Delegation-Based Schemes | Network Mobility (NEMO) efficiently manages the mobility of multiple nodes that moves together as a mobile network. A major limitation of the basic protocol in NEMO is the inefficient route between end hosts. A number of prefix delegation-based schemes have been proposed in the literature to solve the route optimization problem in NEMO. Approaches used by the schemes trade off delivery of packets through the partially optimized route with signaling and other processing overheads. Cost of delivering packets through the partially optimized route along with signaling and processing cost need to be measured to find out the gain from tradeoff. However, cost analysis performed so far on NEMO protocols consider only the cost of signaling. In this paper, we have developed analytical framework to measure the costs of the basic protocol for NEMO, and four representative prefix delegation-based schemes. Our results show that cost of packet delivery through the partially optimized route dominates over other costs. Therefore, optimizing the route completely is preferable to reduction of signaling as far as cost of network mobility is concerned. Our cost analysis framework will help in decision making to select the best route optimization scheme depending on the load imposed by the scheme on the infrastructure. | 2012 |
|
|
A Fade-Level Skew-Laplace Signal Strength Model for Device-Free Localization with Wireless Networks | Device-free localization (DFL) is the estimation of the position of a person or object that does not carry any electronic device or tag. Existing model-based methods for DFL from RSS measurements are unable to locate stationary people in heavily obstructed environments. This paper introduces measurement-based statistical models that can be used to estimate the locations of both moving and stationary people using received signal strength (RSS) measurements in wireless networks. A key observation is that the statistics of RSS during human motion are strongly dependent on the RSS “fade level” during no motion. We define fade level and demonstrate, using extensive experimental data, that changes in signal strength measurements due to human motion can be modeled by the skew-Laplace distribution, with parameters dependent on the position of person and the fade level. Using the fade-level skew-Laplace model, we apply a particle filter to experimentally estimate the location of moving and stationary people in very different environments without changing the model parameters. We also show the ability to track more than one person with the model. | 2012 |
|
|
A Trigger Identification Service for Defending Reactive Jammers in WSN | During the last decade, Reactive Jamming Attack has emerged as a great security threat to wireless sensor networks, due to its mass destruction to legitimate sensor communications and difficulty to be disclosed and defended. Considering the specific characteristics of reactive jammer nodes, a new scheme to deactivate them by efficiently identifying all trigger nodes, whose transmissions invoke the jammer nodes, has been proposed and developed. Such a trigger-identification procedure can work as an application-layer service and benefit many existing reactive-jamming defending schemes. In this paper, on the one hand, we leverage several optimization problems to provide a complete trigger-identification service framework for unreliable wireless sensor networks. On the other hand, we provide an improved algorithm with regard to two sophisticated jamming models, in order to enhance its robustness for various network scenarios. Theoretical analysis and simulation results are included to validate the performance of this framework.
|
2012 |
|
|
Approximation Algorithms for Data Broadcast in Wireless Networks | Broadcasting is a fundamental operation in wireless networks and plays an important role in the communication protocol design. In multihop wireless networks, however, interference at a node due to simultaneous transmissions from its neighbors makes it nontrivial to design a minimum-latency broadcast algorithm, which is known to be NP-complete. We present a simple 12-approximation algorithm for the one-to-all broadcast problem that improves all previously known guarantees for this problem. We then consider the all-to-all broadcast problem where each node sends its own message to all other nodes. For the all-to-all broadcast problem, we present two algorithms with approximation ratios of 20 and 34, improving the best result available in the literature. Finally, we report experimental evaluation of our algorithms. Our studies indicate that our algorithms perform much better in practice than the worst-case guarantees provided in the theoretical analysis and achieve up to 37 percent performance improvement over existing schemes.
|
2012 |
|
|
Link Positions Matter A Noncommutative Routing Metric for Wireless Mesh Networks | We revisit the problem of computing the path with the minimum cost in terms of the expected number of link layer transmissions (including retransmissions) in wireless mesh networks. Unlike previous efforts, such as the popular ETX, we account for the fact that MAC protocols (including the IEEE 802.11 MAC) incorporate a finite number of transmission attempts per packet. This in turn leads to our key observation: the performance of a path depends not only on the number of the links on the path and the quality of its links, but also, on the relative positions of the links on the path. Based on this observation, we propose ETOP, a path metric that accurately captures the expected number of link layer transmissions required for reliable end-to-end packet delivery. We analytically compute ETOP, which is not trivial, since ETOP is a noncommutative function of the link success probabilities. Although ETOP is a more involved metric, we show that the problem of computing paths with the minimum ETOP cost can be solved by a greedy algorithm. We implement and evaluate a routing approach based on ETOP on a 25-node indoor mesh network. Our experiments show that the path selection with ETOP consistently results in superior TCP goodput (by over 50 percent in many cases) compared to path selection based on ETX. We also perform an in-depth analysis of the measurements to better understand why the paths selected by ETOP improve the TCP performance. | 2012 |
|
|
Chameleon A Color-Adaptive Web Browser for Mobile OLED Displays | Displays based on organic light-emitting diode (OLED) technology are appearing on many mobile devices. Unlike liquid crystal displays (LCD), OLED displays consume dramatically different power for showing different colors. In particular, OLED displays are inefficient for showing bright colors. This has made them undesirable for mobile devices because much of the web content is of bright colors. To tackle this problem, we present the motivational studies, design, and realization of Chameleon, a color adaptive web browser that renders webpages with power-optimized color schemes under user-supplied constraints. Driven by the findings from our motivational studies, Chameleon provides end users with important options, offloads tasks that are not absolutely needed in real time, and accomplishes real-time tasks by carefully enhancing the codebase of a browser engine. According to measurements with OLED smartphones, Chameleon is able to reduce average system power consumption for web browsing by 41 percent and is able to reduce display power consumption by 64 percent without introducing any noticeable delay. | 2012 |
|
|
Compressed-Sensing-Enabled Video Streaming for Wireless Multimedia Sensor Networks | This paper presents the design of a networked system for joint compression, rate control and error correction of video over resource-constrained embedded devices based on the theory of Compressed Sensing (CS). The objective of this work is to design a cross-layer system that jointly controls the video encoding rate, the transmission rate, and the channel coding rate to maximize the received video quality. First, compressed sensing-based video encoding for transmission over Wireless Multimedia Sensor Networks (WMSNs) is studied. It is shown that compressed sensing can overcome many of the current problems of video over WMSNs, primarily encoder complexity and low resiliency to channel errors. A rate controller is then developed with the objective of maintaining fairness among different videos while maximizing the received video quality. It is shown that the rate of Compressed Sensed Video (CSV) can be predictably controlled by varying only the compressed sensing sampling rate. It is then shown that the developed rate controller can be interpreted as the iterative solution to a convex optimization problem representing the optimization of the rate allocation across the network. The error resiliency properties of compressed sensed images and videos are then studied, and an optimal error detection and correction scheme is presented for video transmission over lossy channels. Finally, the entire system is evaluated through simulation and test bed evaluation. The rate controller is shown to outperform existing TCP-friendly rate control schemes in terms of both fairness and received video quality. The test bed results show that the rates converge to stable values in real channels | 2012 |
|
|
Coverage Verification without Location Information | Wireless sensor networks (WSNs) have recently emerged as a prominent technology for environmental monitoring and hazardous event detection. Yet, their success depends considerably on their ability to ensure reliable event detection. Such guarantees can be provided only if the target field monitored by a WSN does not contain coverage holes that are not monitored by any sensor. Currently, the coverage-holes detection solutions require accurate knowledge of the sensors locations, which cannot be easily obtained, or they cannot provide guarantees on the coverage quality. In this study we address the challenge of designing an accurate k-coverage verification scheme, without using location information, for a predefined kges1. To this end, we present an efficient, distributed and localized k-coverage verification scheme with proven guarantees on its coverage detection quality. Our simulations show that the scheme accurately detects coverage holes of various sizes.
|
2012 |
|
|
Design of Efficient Multicast Protocol for IEEE 802.11n WLANs and Cross-Layer Optimization for Scalable Video Streaming | The legacy multicasting over IEEE 802.11-based WLANs has two well-known problems-poor reliability and low-rate transmission. In the literature, various WLAN multicast protocols have been proposed in order to overcome these problems. Existing multicast protocols, however, are not so efficient when they are used combining with the frame aggregation scheme of IEEE 802.11n. In this paper, we propose a novel MAC-level multicast protocol for IEEE 802.11n, named Reliable and Efficient Multicast Protocol (REMP). To enhance the reliability and efficiency of multicast services in IEEE 802.11n WLANs, REMP enables selective retransmissions for erroneous multicast frames and efficient adjustments of the modulation and coding scheme (MCS). In addition, we propose an extension of REMP, named scalable REMP (S-REMP), for efficient delivery of scalable video over IEEE 802.11n WLANs. In S-REMP, different MCSs are assigned to different layers of scalable video to guarantee the minimal video quality to all users while providing a higher video quality to users exhibiting better channel conditions. Our simulation results show that REMP outperforms existing multicast protocols for normal multicast traffic and S-REMP offers improved performance for scalable video streaming. | 2012 |
|
|
Differentiated Protection of Video Layers to Improve Perceived Quality | Scalable video transmission over a network is easily adaptable to different types of mobile experiencing different network conditions. However the transmission of differentiated video packets in an error-prone wireless environment remains problematic. We propose and analyze a cross-layer error control scheme that exploits priority-aware block interleaving (PBI) in the MAC layer for video broadcasting in CDMA2000 systems. The PBI scheme allocates a higher priority to protecting the data which are more critical to the decoding of a video stream, and therefore has more effect on picture quality in the application layer. The use of Reed-Solomon coding in conjunction with PBI in the MAC layer can handle error bursts more effectively if its implementation takes account of underlying error distributions in the physical layer, and differentiates between different types of video packets in the application layer. We also calculate the maximum jitter from the variability of the Reed-Solomon decoding delay and determine the size of jitter buffer needed to prevent interruptions due to buffer underrun. Simulations demonstrate the extent to which we can improve the perceived quality of scalable video. | 2012 |
|
|
Directed by Directionality Benefiting from the Gain Pattern of Active RFID Badges | Tracking of people via active badges is important for location-aware computing and for security applications. However, the human body has a major effect on the antenna gain pattern of the device that the person is wearing. In this paper, the gain pattern due to the effect of the human body is experimentally measured and represented by a first-order directional gain pattern model. A method is presented to estimate the model parameters from multiple received signal strength (RSS) measurements. An alternating gain and position estimation (AGAPE) algorithm is proposed to jointly estimate the orientation and the position of the badge using RSS measurements at known-position anchor nodes. Lower bounds on mean squared error (MSE) and experimental results are presented that both show that the accuracy of position estimates can be greatly improved by including orientation estimates in the localization system. Next, we propose a new tracking filter that accepts orientation estimates as input, which we call the orientation-enhanced extended Kalman filter (OE-EKF), which improves tracking accuracy in active RFID tracking systems.
|
2012 |
|
|
Distributed and Online Fair Resource Management in Video Surveillance Sensor Networks | Visual capability introduced to Wireless Sensor Networks (WSNs) render many novel applications that would otherwise be infeasible. However, unlike legacy WSNs which are commercially deployed in applications, visual sensor networks create additional research problems that delays the real-world implementations. Conveying real-time video streams over resource constrained sensor hardware remains to be a challenging task. As a remedy, we propose a fairness-based approach to enhance the event reporting and detection performance of the Video Surveillance Sensor Networks. Instead of achieving fairness only for flows or for nodes as investigated in the literature, we concentrate on the whole application requirement. Accordingly, our Event-Based Fairness (EBF) scheme aims at fair resource allocation for the application level messaging units called events. We identify the crucial network-wide resources as the in-queue processing turn of the frames and the channel access opportunities of the nodes. We show that fair treatment of events, as opposed to regular flow of frames, results in enhanced performance in terms of the number of frames reported per event and the reporting latency. EBF is a robust mechanism that can be used as a stand-alone or as a complementary method to other possible performance enhancement methods for video sensor networks implemented at other communication layers.
|
2012 |
|
|
Energy-Efficient Cooperative Video Distribution with Statistical QoS Provisions over Wireless Networks | For real-time video broadcast where multiple users are interested in the same content, mobile-to-mobile cooperation can be utilized to improve delivery efficiency and reduce network utilization. Under such cooperation, however, real-time video transmission requires end-to-end delay bounds. Due to the inherently stochastic nature of wireless fading channels, deterministic delay bounds are prohibitively difficult to guarantee. For a scalable video structure, an alternative is to provide statistical guarantees using the concept of effective capacity/bandwidth by deriving quality of service exponents for each video layer. Using this concept, we formulate the resource allocation problem for general multihop multicast network flows and derive the optimal solution that minimizes the total energy consumption while guaranteeing a statistical end-to-end delay bound on each network path. A method is described to compute the optimal resource allocation at each node in a distributed fashion. Furthermore, we propose low complexity approximation algorithms for energy-efficient flow selection from the set of directed acyclic graphs forming the candidate network flows. The flow selection and resource allocation process is adapted for each video frame according to the channel conditions on the network links. Considering different network topologies, results demonstrate that the proposed resource allocation and flow selection algorithms provide notable performance gains with small optimality gaps at a low computational cost. | 2012 |
|
|
Enhancing Privacy and Accuracy in Probe Vehicle-Based Traffic Monitoring via Virtual Trip Lines | Traffic monitoring using probe vehicles with GPS receivers promises significant improvements in cost, coverage, and accuracy over dedicated infrastructure systems. Current approaches, however, raise privacy concerns because they require participants to reveal their positions to an external traffic monitoring server. To address this challenge, we describe a system based on virtual trip lines and an associated cloaking technique, followed by another system design in which we relax the privacy requirements to maximize the accuracy of real-time traffic estimation. We introduce virtual trip lines which are geographic markers that indicate where vehicles should provide speed updates. These markers are placed to avoid specific privacy sensitive locations. They also allow aggregating and cloaking several location updates based on trip line identifiers, without knowing the actual geographic locations of these trip lines. Thus, they facilitate the design of a distributed architecture, in which no single entity has a complete knowledge of probe identities and fine-grained location information. We have implemented the system with GPS smartphone clients and conducted a controlled experiment with 100 phone-equipped drivers circling a highway segment, which was later extended into a year-long public deployment.
|
2012 |
|
|
Geometry and Motion-Based Positioning Algorithms for Mobile Tracking in NLOS Environments | This paper presents positioning algorithms for cellular network-based vehicle tracking in severe non-line-of-sight (NLOS) propagation scenarios. The aim of the algorithms is to enhance positional accuracy of network-based positioning systems when the GPS receiver does not perform well due to the complex propagation environment. A one-step position estimation method and another two-step method are proposed and developed. Constrained optimization is utilized to minimize the cost function which takes account of the NLOS error so that the NLOS effect is significantly reduced. Vehicle velocity and heading direction measurements are exploited in the algorithm development, which may be obtained using a speedometer and a heading sensor, respectively. The developed algorithms are practical so that they are suitable for implementation in practice for vehicle applications. It is observed through simulation that in severe NLOS propagation scenarios, the proposed positioning methods outperform the existing cellular network-based positioning algorithms significantly. Further, when the distance measurement error is modeled as the sum of an exponential bias variable and a Gaussian noise variable, the exact expressions of the CRLB are derived to benchmark the performance of the positioning algorithms. | 2012 |
|
|
On the Origins of Heavy-Tailed Delay in Dynamic Spectrum Access Networks | This paper provides an asymptotic analysis of the transmission delay experienced by SUs for dynamic spectrum access (DSA) networks. It is shown that DSA induces only light-tailed delay if both the busy time of PU channels and the message size of SUs are light tailed. On the contrary, if either the busy time or the message size is heavy tailed, then the SUs’ transmission delay is heavy tailed. For this latter case, it is proven that if one of either the busy time or the message size is light tailed and the other is regularly varying with index α, the transmission delay is regularly varying with the same index. As a consequence, the delay has an infinite mean provided α <; 1 and an infinite variance provided α <; 2. Furthermore, if both the busy time and the message size are regularly varying with different indices, then the delay tail distribution is as heavy as the one with the smaller index. Moreover, the impact of spectrum mobility and multiradio diversity on the delay performance of SUs is studied. It is shown that both spectrum mobility and multiradio diversity can greatly mitigate the heavy-tailed delay by increasing the orders of its finite moments.
|
2012 |
|
|
Positional Accuracy Measurement and Error Modeling for Mobile Tracking | This paper presents a method of determining the statistical positional accuracy of a moving object being tracked by any 2D (but particularly radiolocation) positioning system without requiring a more accurate reference system. Commonly for testing performance only static positional errors are measured, but typically for radiolocation systems the positional performance is significantly different for moving objects compared with stationary objects. When only the overall statistical performance is required, the paper describes a measurement technique based on determining 1D cross-track errors from a nominal path, and then using this data set to determine the overall 2D positional error statistics. Comparison with simulated data shows that the method has good accuracy. The method is also tested with vehicle tracking in a city and people tracking within a building. For the indoor case, static and dynamic measurements allowed the degrading effect of body-worn devices due to signal blockage to be determined. Error modeling is also performed and a Rayleigh-Gamma model is proposed to describe the radial positional errors. It is shown that this model has a good match with both indoor and outdoor field measurements | 2012 |
|
|
ProSpect A Proactive Spectrum Handoff Framework for Cognitive Radio Ad Hoc Networks without Common Control Channel | Cognitive Radio (CR) technology is a promising solution to enhance the spectrum utilization by enabling unlicensed users to exploit the spectrum in an opportunistic manner. Since unlicensed users are temporary visitors to the licensed spectrum, they are required to vacate the spectrum when a licensed user reclaims it. Due to the randomness of the appearance of licensed users, disruptions to both licensed and unlicensed communications are often difficult to prevent, which may lead to low throughput of both licensed and unlicensed communications. In this paper, a proactive spectrum handoff framework for CR ad hoc networks, ProSpect, is proposed to address these concerns. In the proposed framework, Channel-Switching (CW) policies and a proactive spectrum handoff protocol are proposed to let unlicensed users vacate a channel before a licensed user utilizes it to avoid unwanted interference. Network coordination schemes for unlicensed users are also incorporated into the spectrum handoff protocol design. Moreover, a distributed channel selection scheme to eliminate collisions among unlicensed users in a multiuser spectrum handoff scenario is proposed. In our proposed framework, unlicensed users coordinate with each other without using a Common Control Channel (CCC), which is highly adaptable in a spectrum-varying environment. We compare our proposed proactive spectrum handoff protocol with a reactive spectrum handoff protocol, under which unlicensed users switch channels after collisions with licensed transmissions occur. Simulation results show that our proactive spectrum handoff outperforms the reactive spectrum handoff approach in terms of higher throughput and fewer collisions to licensed users. Furthermore, our distributed channel selection can achieve higher packet delivery rate in a multiuser spectrum handoff scenario, compared with existing channel selection schemes.
|
2012 |
|
|
Protecting Location Privacy in Sensor Networks against a Global Eavesdropper | While many protocols for sensor network security provide confidentiality for the content of messages, contextual information usually remains exposed. Such contextual information can be exploited by an adversary to derive sensitive information such as the locations of monitored objects and data sinks in the field. Attacks on these components can significantly undermine any network application. Existing techniques defend the leakage of location information from a limited adversary who can only observe network traffic in a small region. However, a stronger adversary, the global eavesdropper, is realistic and can defeat these existing techniques. This paper first formalizes the location privacy issues in sensor networks under this strong adversary model and computes a lower bound on the communication overhead needed for achieving a given level of location privacy. The paper then proposes two techniques to provide location privacy to monitored objects (source-location privacy)-periodic collection and source simulation-and two techniques to provide location privacy to data sinks (sink-location privacy)-sink simulation and backbone flooding. These techniques provide trade-offs between privacy, communication cost, and latency. Through analysis and simulation, we demonstrate that the proposed techniques are efficient and effective for source and sink-location privacy in sensor networks. | 2012 |
|
|
Relay-Assisted Transmission with Fairness Constraint for Cellular Networks | We consider the problem of relay-assisted transmission for cellular networks. In the considered system, a source node together with n relay nodes are selected in a proportionally fair (PF) manner to transmit to the base station (BS), which uses the maximal ratio combining (MRC) to combine the signals received from the source node in the first half slot and the n relay nodes in the second half slot for successful reception. The proposed algorithm incorporates the PF criterion and cooperative diversity, and is called proportionally fair cooperation (PFC). Compared with the proportional fair scheduling (PFS) algorithm, PFC provides improved efficiency and fairness. The ordinary differential equation (ODE) analysis used to study PFS cannot be used for PFC; otherwise, one has to solve a large number of nonlinear and interrelated ODE equations which is time prohibited. In this paper, we present a mathematical framework for the performance of PFC. The cornerstone of our framework is a realistic yet simple model that captures node cooperation, fading, and fair resource allocation-induced dependencies. We obtain analytical expressions for the throughput gain of PFC over traditional PFS without node cooperation. Compared with the highly time-consuming ordinary differential equation analysis, our formulae are intuitive yet easy to evaluate numerically. To our knowledge, it is the first time that a closed-form expression is obtained for the throughput of relay-assisted transmission in a cellular network with the PF constraint. | 2012 |
|
|
Resource-Aware Video Multicasting via Access Gateways in Wireless Mesh Networks | This paper studies video multicasting in large-scale areas using wireless mesh networks. The focus is on the use of Internet access gateways that allow a choice of alternative routes to avoid potentially lengthy and low-capacity multihop wireless paths. A set of heuristic-based algorithms is described that together aim to maximize reliable network capacity: the two-tier integrated architecture algorithm, the weighted gateway uploading algorithm, the link-controlled routing tree algorithm, and the dynamic group management algorithm. These algorithms use different approaches to arrange nodes involved in video multicasting into a clustered and two-tier integrated architecture in which network protocols can make use of multiple gateways to improve system throughput. Simulation results are presented, showing that our multicasting algorithms can achieve up to 40 percent more throughput than other related published approaches | 2012 |
|
|
Risk-Aware Distributed Beacon Scheduling for Tree-Based ZigBee Wireless Networks | In a tree-based ZigBee network, ZigBee routers (ZRs) must schedule their beacon transmission time to avoid beacon collisions. The beacon schedule determines packet delivery latency from the end devices to the ZigBee coordinator at the root of the tree. Traditionally, beacon schedules are chosen such that a ZR does not reuse the beacon slots already claimed by its neighbors, or the neighbors of its neighbors. We observe, however, that beacon slots can be reused judiciously, especially when the risk of beacon collision caused by such reuse is low. The advantage of such reuse is that packet delivery latency can be reduced. We formalize our observation by proposing a node-pair classification scheme. Based on this scheme, we can easily assess the risk of slot reuse by a node pair. If the risk is high, slot reuse is disallowed; otherwise, slot reuse is allowed. This forms the essence of our ZigBee-compatible, distributed, risk-aware, probabilistic beacon scheduling algorithm. Simulation results show that on average the proposed algorithm produces a latency only 24 percent of that with conventional method, at the cost of 12 percent reduction in the fraction of associated nodes.
|
2012 |
|
|
Scalable Activity-Travel Pattern Monitoring Framework for Large-Scale City Environment | In this paper, we introduce Activity Travel Pattern (ATP) monitoring in a large-scale city environment. ATP represents where city residents and vehicles stay and how they travel around in a complex megacity. Monitoring ATP will incubate new types of value-added services such as predictive mobile advertisement, demand forecasting for urban stores, and adaptive transportation scheduling. To enable ATP monitoring, we develop ActraMon, a high-performanceATP monitoring framework. As a first step, ActraMon provides a simple but effective computational model of ATP and a declarative query language facilitating effective specification of various ATP monitoring queries. More important, ActraMon employs the shared staging architecture and highly efficient processing techniques, which address the scalability challenges caused by massive location updates, a number of ATP monitoring queries and processing complexity of ATP monitoring. Finally, we demonstrate the extensive performance study of ActraMon using realistic city-wide ATP workloads | 2012 |
|
|
Secure Initialization of Multiple Constrained Wireless Devices for an Unaided User | A number of protocols and mechanisms have been proposed to address the problem of initial secure key deployment in wireless networks. Most existing approaches work either with a small number of wireless devices (i.e., two) or otherwise rely on the presence of an auxiliary device (such as a programmable camera, computer, or Faraday cage). In this paper, we design a solution that allows a user unaided initialization (free from auxiliary devices) of a relatively large number of wireless devices. The proposed solution is based on a novel multichannel Group message Authentication Protocol (GAP), in which information is transmitted over both a radio and a visible light channel (VLC). A notable feature of GAP is that the information to be authenticated is independent of the short authentication stringo be verified by the user (an indirect binding protocol [28]). This, as we show, results in a lower communication cost compared to existing direct binding protocols. The advantage in terms of the communication cost of our GAP protocol is especially important for power-constrained devices, such as wireless sensor motes. Another appealing feature of GAP is that it is secure in the attacker model where the VLC is semiauthentic, whereas existing protocols consider VLC to be authentic. This is made possible by using joint Manchester-Berger unidirectional error-detection codes that are secure and easy to interpret by a nonspecialist and unaided end user. Our overall key deployment mechanism has minimal hardware requirements: one LED, one button and, of course, a radio transceiver, and is thus suitable for initializing devices with constrained interfaces, such as (multiple) wireless sensor motes. We demonstrate the feasibility of the proposed method via a preliminary usability study. The study indicates that the method has reasonably low execution time, minimal error rate, and is user friendly. | 2012 |
|
|
Shaping Throughput Profiles in Multihop Wireless Networks A Resource-Biasing Approach | A fundamental question in multihop wireless network protocol design is how to partition the network’s transport capacity among contending flows. A classically “fair” allocation leads to poor throughput performance for all flows because connections that traverse a large number of hops (i.e., long connections) consume a disproportionate share of resources. However, naïvely biasing against longer connections can lead to poor network utilization, because a significantly high fraction of total connections are long in large networks with spatially uniform traffic. While proportional fair allocation provides a significant improvement, we show here that there is a much richer space of resource allocation strategies for introducing a controlled bias against resource-intensive long connections in order to significantly improve the performance of shorter connections. Specifically, mixing strongly biased allocations with fairer allocations leads to efficient network utilization as well as a superior trade-off between flow throughput and fairness. We present an analytical model that offers insight into the impact of a particular resource allocation strategy on network performance, taking into account finite network size and spatial traffic patterns. We point to protocol design options to implement our resource allocation strategies by invoking the connection with the well-studied network utility maximization framework. Our simulation evaluation serves to verify the analytical design prescriptions. | 2012 |
|
TECHNOLOGY : DOT NET
DOMAIN : IEEE TRANSACTIONS ON IMAGE PROCESSING
|
| S NO | TITLES | ABSTRACT | YEAR |
|
|
Semi supervised Biased Maximum Margin Analysis for Interactive Image Retrieval | In this paper, we propose a biased maximum margin analysis (BMMA) and a semi supervised BMMA (SemiBMMA) for integrating the distinct properties of feedbacks and utilizing the information of unlabeled samples for SVM-based RF schemes For Image Retrieval process. | 2012 |
|
|
Scalable Coding of Encrypted Images | This paper proposes a novel scheme of scalable coding for encrypted images. In the encryption phase, the original pixel values are masked by a modulo-256 addition with pseudorandom numbers that are derived from a secret key. Then, the data of quantized sub image and coefficients are regarded as a set of bit streams. | 2012 |
|
|
PDE-Based Enhancement of Color Images in RGB Space | The proposed model is based on using the single vectors of the gradient magnitude and the second derivatives as a manner to relate different color components of the image. This model can be viewed as a generalization of the Bettahar–Stambouli filter to multivalued images. The proposed algorithm is more efficient than the mentioned filter and some previous works at color images denoising and deblurring without creating false colors | 2012 |
|
|
3-D Discrete Shearlet Transform and Video Processing | In this paper, we introduce a digital implementation of the 3-D shearlet transform and illustrate its application to problems of video denoising and enhancement. The shearlet representation is a multiscale pyramid of well-localized waveforms defined at various locations and orientations, which was introduced to overcome the limitations of traditional multiscale systems in dealing with multidimensional data. While the shearlet approach shares the general philosophy of curvelets and surfacelets, it is based on a very different mathematical framework, which is derived from the theory of affine systems and uses shearing matrices rather than rotations. This allows a natural transition from the continuous setting to the digital setting and a more flexible mathematical structure. The 3-D digital shearlet transform algorithm presented in this paper consists in a cascade of a multiscale decomposition and a directional filtering stage. The filters employed in this decomposition are implemented as finite-length filters, and this ensures that the transform is local and numerically efficient. To illustrate its performance, the 3-D discrete shearlet transform is applied to problems of video denoising and enhancement, and compared against other state-of-the-art multiscale techniques, including curvelets and surfacelets. | 2012 |
|
|
A Generalized Logarithmic Image Processing Model Based on the Gigavision Sensor Model | The logarithmic image processing (LIP) model is a mathematical theory providing generalized linear operations for image processing. The gigavision sensor (GVS) is a new imaging device that can be described by a statistical model. In this paper, by studying these two seemingly unrelated models, we develop a generalized LIP (GLIP) model. With the LIP model being its special case, the GLIP model not only provides new insights into the LIP model but also defines new image representations and operations for solving general image processing problems that are not necessarily related to the GVS. A new parametric LIP model is also developed. To illustrate the application of the new scalar multiplication operation, we propose an energy-preserving algorithm for tone mapping, which is a necessary step in image dehazing. By comparing with results using two state-of-the-art algorithms, we show that the new scalar multiplication operation is an effective tool for tone mapping.
|
2012 |
|
|
A Kalman-Filtering Approach to High Dynamic Range Imaging for Measurement Applications | High dynamic range imaging (HDRI) methods in computational photography address situations where the dynamic range of a scene exceeds what can be captured by an image sensor in a single exposure. HDRI techniques have also been used to construct radiance maps in measurement applications; unfortunately, the design and evaluation of HDRI algorithms for use in these applications have received little attention. In this paper, we develop a novel HDRI technique based on pixel-by-pixel Kalman filtering and evaluate its performance using objective metrics that this paper also introduces. In the presented experiments, this new technique achieves as much as 9.4-dB improvement in signal-to-noise ratio and can achieve as much as a 29% improvement in radiometric accuracy over a classic method. | 2012 |
|
|
A Parametric Level-Set Approach to Simultaneous Object Identification and Background Reconstruction for Dual-Energy Computed Tomography | Dual-energy computerized tomography has gained great interest because of its ability to characterize the chemical composition of a material rather than simply providing relative attenuation images as in conventional tomography. The purpose of this paper is to introduce a novel polychromatic dual-energy processing algorithm, with an emphasis on detection and characterization of piecewise constant objects embedded in an unknown cluttered background. Physical properties of the objects, particularly the Compton scattering and photoelectric absorption coefficients, are assumed to be known with some level of uncertainty. Our approach is based on a level-set representation of the characteristic function of the object and encompasses a number of regularization techniques for addressing both the prior information we have concerning the physical properties of the object and the fundamental physics-based limitations associated with our ability to jointly recover the Compton scattering and photoelectric absorption properties of the scene. In the absence of an object with appropriate physical properties, our approach returns a null characteristic function and, thus, can be viewed as simultaneously solving the detection and characterization problems. Unlike the vast majority of methods that define the level-set function nonparametrically, i.e., as a dense set of pixel values, we define our level set parametrically via radial basis functions and employ a Gauss-Newton-type algorithm for cost minimization. Numerical results show that the algorithm successfully detects objects of interest, finds their shape and location, and gives an adequate reconstruction of the background. | 2012 |
|
|
A Surface-Based 3-D Dendritic Spine Detection Approach From Confocal Microscopy Images | Determining the relationship between the dendritic spine morphology and its functional properties is a fundamental challenge in neurobiology research. In particular, how to accurately and automatically analyse meaningful structural information from a large microscopy image data set is far away from being resolved. As pointed out in existing literature, one remaining challenge in spine detection and segmentation is how to automatically separate touching spines. In this paper, based on various global and local geometric features of the dendrite structure, we propose a novel approach to detect and segment neuronal spines, in particular, a breaking-down and stitching-up algorithm to accurately separate touching spines. Extensive performance comparisons show that our approach is more accurate and robust than two state-of-the-art spine detection and segmentation algorithms. | 2012 |
|
|
A Variational Method for Multiple-Image Blending | The main aim of this paper is to develop an algorithm for blending of multiple images in the image-stitching process. Our idea is to propose a variational method containing an energy functional to determine both a stitched image and weighting mask functions of multiple input images for image blending. The existence of the solution of the proposed energy functional is shown. We also present an alternative minimizing algorithm to solve the proposed model numerically and show the convergence of this algorithm. Experimental results show that the proposed model works effectively and efficiently and that the proposed method is competitive with the tested existing methods under noisy conditions.
|
2012 |
|
|
Algorithms for the Digital Restoration of Torn Films | This paper presents algorithms for the digital restoration of films damaged by tear. As well as causing local image data loss, a tear results in a noticeable relative shift in the frame between the regions at either side of the tear boundary. This paper describes a method for delineating the tear boundary and for correcting the displacement. This is achieved using a graph-cut segmentation framework that can be either automatic or interactive when automatic segmentation is not possible. Using temporal intensity differences to form the boundary conditions for the segmentation facilitates the robust division of the frame. The resulting segmentation map is used to calculate and correct the relative displacement using a global-motion estimation approach based on motion histograms. A high-quality restoration is obtained when a suitable missing-data treatment algorithm is used to recover any missing pixel intensities. | 2012 |
|
|
An Edge-Adapting Laplacian Kernel For Nonlinear Diffusion Filters | In this paper, first, a new Laplacian kernel is developed to integrate into it the anisotropic behavior to control the process of forward diffusion in horizontal and vertical directions. It is shown that, although the new kernel reduces the process of edge distortion, it nonetheless produces artifacts in the processed image. After examining the source of this problem, an analytical scheme is devised to obtain a spatially varying kernel that adapts itself to the diffusivity function. The proposed spatially varying Laplacian kernel is then used in various nonlinear diffusion filters starting from the classical Perona-Malik filter to the more recent ones. The effectiveness of the new kernel in terms of quantitative and qualitative measures is demonstrated by applying it to noisy images. | 2012 |
|
|
Automatic Image Equalization and Contrast Enhancement Using Gaussian Mixture Modeling | In this paper, we propose an adaptive image equalization algorithm that automatically enhances the contrast in an input image. The algorithm uses the Gaussian mixture model to model the image gray-level distribution, and the intersection points of the Gaussian components in the model are used to partition the dynamic range of the image into input gray-level intervals. The contrast equalized image is generated by transforming the pixels’ gray levels in each input interval to the appropriate output gray-level interval according to the dominant Gaussian component and the cumulative distribution function of the input interval. To take account of the hypothesis that homogeneous regions in the image represent homogeneous silences (or set of Gaussian components) in the image histogram, the Gaussian components with small variances are weighted with smaller values than the Gaussian components with larger variances, and the gray-level distribution is also used to weight the components in the mapping of the input interval to the output interval. Experimental results show that the proposed algorithm produces better or comparable enhanced images than several state-of-the-art algorithms. Unlike the other algorithms, the proposed algorithm is free of parameter setting for a given dynamic range of the enhanced image and can be applied to a wide range of image types. | 2012 |
|
|
Bayesian Texture Classification Based on Contourlet Transform and BYY Harmony Learning of Poisson Mixtures | As a newly developed 2-D extension of the wavelet transform using multiscale and directional filter banks, the contourlet transform can effectively capture the intrinsic geometric structures and smooth contours of a texture image that are the dominant features for texture classification. In this paper, we propose a novel Bayesian texture classifier based on the adaptive model-selection learning of Poisson mixtures on the contourlet features of texture images. The adaptive model-selection learning of Poisson mixtures is carried out by the recently established adaptive gradient Bayesian Ying-Yang harmony learning algorithm for Poisson mixtures. It is demonstrated by the experiments that our proposed Bayesian classifier significantly improves the texture classification accuracy in comparison with several current state-of-the-art texture classification approaches. | 2012 |
|
|
BM3D Frames and Variational Image Deblurring | A family of the block matching 3-D (BM3D) algorithms for various imaging problems has been recently proposed within the framework of nonlocal patchwise image modeling , . In this paper, we construct analysis and synthesis frames, formalizing BM3D image modeling, and use these frames to develop novel iterative deblurring algorithms. We consider two different formulations of the deblurring problem, i.e., one given by the minimization of the single-objective function and another based on the generalized Nash equilibrium (GNE) balance of two objective functions. The latter results in the algorithm where deblurring and denoising operations are decoupled. The convergence of the developed algorithms is proved. Simulation experiments show that the decoupled algorithm derived from the GNE formulation demonstrates the best numerical and visual results and shows superiority with respect to the state of the art in the field, confirming a valuable potential of BM3D-frames as an advanced image modeling tool. | 2012 |
|
|
Counting People With Low-Level Features and Bayesian Regression | An approach to the problem of estimating the size of inhomogeneous crowds, which are composed of pedestrians that travel in different directions, without using explicit object segmentation or tracking is proposed. Instead, the crowd is segmented into components of homogeneous motion, using the mixture of dynamic-texture motion model. A set of holistic low-level features is extracted from each segmented region, and a function that maps features into estimates of the number of people per segment is learned with Bayesian regression. Two Bayesian regression models are examined. The first is a combination of Gaussian process regression with a compound kernel, which accounts for both the global and local trends of the count mapping but is limited by the real-valued outputs that do not match the discrete counts. We address this limitation with a second model, which is based on a Bayesian treatment of Poisson regression that introduces a prior distribution on the linear weights of the model. Since exact inference is analytically intractable, a closed-form approximation is derived that is computationally efficient and kernelizable, enabling the representation of nonlinear functions. An approximate marginal likelihood is also derived for kernel hyperparameter learning. The two regression-based crowd counting methods are evaluated on a large pedestrian data set, containing very distinct camera views, pedestrian traffic, and outliers, such as bikes or skateboarders. Experimental results show that regression-based counts are accurate regardless of the crowd size, outperforming the count estimates produced by state-of-the-art pedestrian detectors. Results on 2 h of video demonstrate the efficiency and robustness of the regression-based crowd size estimation over long periods of time.
|
2012 |
|
|
Curved-Region-Based Ridge Frequency Estimation and Curved Gabor Filters for Fingerprint Image Enhancement | Gabor filters (GFs) play an important role in many application areas for the enhancement of various types of images and the extraction of Gabor features. For the purpose of enhancing curved structures in noisy images, we introduce curved GFs that locally adapt their shape to the direction of flow. These curved GFs enable the choice of filter parameters that increase the smoothing power without creating artifacts in the enhanced image. In this paper, curved GFs are applied to the curved ridge and valley structures of low-quality fingerprint images. First, we combine two orientation-field estimation methods in order to obtain a more robust estimation for very noisy images. Next, curved regions are constructed by following the respective local orientation. Subsequently, these curved regions are used for estimating the local ridge frequency. Finally, curved GFs are defined based on curved regions, and they apply the previously estimated orientations and ridge frequencies for the enhancement of low-quality fingerprint images. Experimental results on the FVC2004 databases show improvements of this approach in comparison with state-of-the-art enhancement methods. | 2012 |
|
|
Design and Optimization of Color Lookup Tables on a Simplex Topology | An important computational problem in color imaging is the design of color transforms that map color between devices or from a device-dependent space (e.g., RGB/CMYK) to a device-independent space (e.g., CIELAB) and vice versa. Real-time processing constraints entail that such nonlinear color transforms be implemented using multidimensional lookup tables (LUTs). Furthermore, relatively sparse LUTs (with efficient interpolation) are employed in practice because of storage and memory constraints. This paper presents a principled design methodology rooted in constrained convex optimization to design color LUTs on a simplex topology. The use of n simplexes, i.e., simplexes in n dimensions, as opposed to traditional lattices, recently has been of great interest in color LUT design for simplex topologies that allow both more analytically tractable formulations and greater efficiency in the LUT. In this framework of n-simplex interpolation, our central contribution is to develop an elegant iterative algorithm that jointly optimizes the placement of nodes of the color LUT and the output values at those nodes to minimize interpolation error in an expected sense. This is in contrast to existing work, which exclusively designs either node locations or the output values. We also develop new analytical results for the problem of node location optimization, which reduces to constrained optimization of a large but sparse interpolation matrix in our framework. We evaluate our n -simplex color LUTs against the state-of-the-art lattice (e.g., International Color Consortium profiles) and simplex-based techniques for approximating two representative multidimensional color transforms that characterize a CMYK xerographic printer and an RGB scanner, respectively. The results show that color LUTs designed on simplexes offer very significant benefits over traditional lattice-based alternatives in improving color transform accuracy even with a much smaller number- of nodes. | 2012 |
|
|
Edge Strength Filter Based Color Filter Array Interpolation | For economic reasons, most digital cameras use color filter arrays instead of beam splitters to capture image data. As a result of this, only one of the required three color samples becomes available at each pixel location and the other two need to be interpolated. This process is called Color Filter Array (CFA) interpolation or demosaicing. Many demosaicing algorithms have been introduced over the years to improve subjective and objective interpolation quality. We propose an orientation-free edge strength filter and apply it to the demosaicing problem. Edge strength filter output is utilized both to improve the initial green channel interpolation and to apply the constant color difference rule adaptively. This simple edge directed method yields visually pleasing results with high CPSNR.
|
2012 |
|
|
Face Identification Using Large Feature Sets | With the goal of matching unknown faces against a gallery of known people, the face identification task has been studied for several decades. There are very accurate techniques to perform face identification in controlled environments, particularly when large numbers of samples are available for each face. However, face identification under uncontrolled environments or with a lack of training data is still an unsolved problem. We employ a large and rich set of feature descriptors (with more than 70 000 descriptors) for face identification using partial least squares to perform multichannel feature weighting. Then, we extend the method to a tree-based discriminative structure to reduce the time required to evaluate probe samples. The method is evaluated on Facial Recognition Technology (FERET) and Face Recognition Grand Challenge (FRGC) data sets. Experiments show that our identification method outperforms current state-of-the-art results, particularly for identifying faces acquired across varying conditions. | 2012 |
|
|
Fast Wavelet-Based Image Characterization for Highly Adaptive Image Retrieval | Adaptive wavelet-based image characterizations have been proposed in previous works for content-based image retrieval (CBIR) applications. In these applications, the same wavelet basis was used to characterize each query image: This wavelet basis was tuned to maximize the retrieval performance in a training data set. We take it one step further in this paper: A different wavelet basis is used to characterize each query image. A regression function, which is tuned to maximize the retrieval performance in the training data set, is used to estimate the best wavelet filter, i.e., in terms of expected retrieval performance, for each query image. A simple image characterization, which is based on the standardized moments of the wavelet coefficient distributions, is presented. An algorithm is proposed to compute this image characterization almost instantly for every possible separable or nonseparable wavelet filter. Therefore, using a different wavelet basis for each query image does not considerably increase computation times. On the other hand, significant retrieval performance increases were obtained in a medical image data set, a texture data set, a face recognition data set, and an object picture data set. This additional flexibility in wavelet adaptation paves the way to relevance feedback on image characterization itself and not simply on the way image characterizations are combined. | 2012 |
|
|
Gradient-Directed Multiexposure Composition | In this paper, we present a simple yet effective method that takes advantage of the gradient information to accomplish the multiexposure image composition in both static and dynamic scenes. Given multiple images with different exposures, the proposed approach is capable of producing a pleasant tone-mapped-like high-dynamic-range image by compositing them seamlessly with the guidance of gradient-based quality assessment. In particular, two novel quality measures, namely, visibility and consistency, are developed based on the observations of gradient changes among different exposures. Experiments in various static and dynamic scenes are conducted to demonstrate the effectiveness of the proposed method. | 2012 |
|
|
Group-Sensitive Multiple Kernel Learning for Object Recognition | In this paper, a group-sensitive multiple kernel learning (GS-MKL) method is proposed for object recognition to accommodate the intraclass diversity and the interclass correlation. By introducing the “group” between the object category and individual images as an intermediate representation, GS-MKL attempts to learn group-sensitive multikernel combinations together with the associated classifier. For each object category, the image corpus from the same category is partitioned into groups. Images with similar appearance are partitioned into the same group, which corresponds to the subcategory of the object category. Accordingly, intraclass diversity can be represented by the set of groups from the same category but with diverse appearances; interclass correlation can be represented by the correlation between groups from different categories. GS-MKL provides a tractable solution to adapt multikernel combination to local data distribution and to seek a tradeoff between capturing the diversity and keeping the invariance for each object category. Different from the simple hybrid grouping strategy that solves sample grouping and GS-MKL training independently, two sample grouping strategies are proposed to integrate sample grouping and GS-MKL training. The first one is a looping hybrid grouping method, where a global kernel clustering method and GS-MKL interact with each other by sharing group-sensitive multikernel combination. The second one is a dynamic divisive grouping method, where a hierarchical kernel-based grouping process interacts with GS-MKL. Experimental results show that performance of GS-MKL does not significantly vary with different grouping strategies, but the looping hybrid grouping method produces slightly better results. On four challenging data sets, our proposed method has achieved encouraging performance comparable to the state-of-the-art and outperformed several existing MKL methods. | 2012 |
|
|
Hessian-Based Norm Regularization for Image Restoration With Biomedical Applications | We present nonquadratic Hessian-based regularization methods that can be effectively used for image restoration problems in a variational framework. Motivated by the great success of the total-variation (TV) functional, we extend it to also include second-order differential operators. Specifically, we derive second-order regularizers that involve matrix norms of the Hessian operator. The definition of these functionals is based on an alternative interpretation of TV that relies on mixed norms of directional derivatives. We show that the resulting regularizers retain some of the most favorable properties of TV, i.e., convexity, homogeneity, rotation, and translation invariance, while dealing effectively with the staircase effect. We further develop an efficient minimization scheme for the corresponding objective functions. The proposed algorithm is of the iteratively reweighted least-square type and results from a majorization-minimization approach. It relies on a problem-specific preconditioned conjugate gradient method, which makes the overall minimization scheme very attractive since it can be applied effectively to large images in a reasonable computational time. We validate the overall proposed regularization framework through deblurring experiments under additive Gaussian noise on standard and biomedical images. | 2012 |
|
|
Human Gait Recognition Using Patch Distribution Feature and Locality-Constrained Group Sparse Representation | In this paper, we propose a new patch distribution feature (PDF) (i.e., referred to as Gabor-PDF) for human gait recognition. We represent each gait energy image (GEI) as a set of local augmented Gabor features, which concatenate the Gabor features extracted from different scales and different orientations together with the X-Y coordinates. We learn a global Gaussian mixture model (GMM) (i.e., referred to as the universal background model) with the local augmented Gabor features from all the gallery GEIs; then, each gallery or probe GEI is further expressed as the normalized parameters of an image-specific GMM adapted from the global GMM. Observing that one video is naturally represented as a group of GEIs, we also propose a new classification method called locality-constrained group sparse representation (LGSR) to classify each probe video by minimizing the weighted l1, 2 mixed-norm-regularized reconstruction error with respect to the gallery videos. In contrast to the standard group sparse representation method that is a special case of LGSR, the group sparsity and local smooth sparsity constraints are both enforced in LGSR. Our comprehensive experiments on the benchmark USF HumanID database demonstrate the effectiveness of the newly proposed feature Gabor-PDF and the new classification method LGSR for human gait recognition. Moreover, LGSR using the new feature Gabor-PDF achieves the best average Rank-1 and Rank-5 recognition rates on this database among all gait recognition algorithms proposed to date. | 2012 |
|
|
Image Editing With Spatiograms Transfer | Histogram equalization is a well-known method for image contrast enhancement. Nevertheless, as histograms do not include any information on the spatial repartition of colors, their application to local image editing problems remains limited. To cope with this lack of spatial information, spatiograms have been recently proposed for tracking purposes. A spatiogram is an image descriptor that combines a histogram with the mean and the variance of the position of each color. In this paper, we address the problem of local retouching of images by proposing a variational method for spatiogram transfer. More precisely, a reference spatiogram is used to modify the color value of a given region of interest of the processed image. Experiments on shadow removal and inpainting demonstrate the strength of the proposed approach. | 2012 |
|
|
Image Quality Assessment by Visual Gradient Similarity | A full-reference image quality assessment (IQA) model by multiscale visual gradient similarity (VGS) is presented. The VGS model adopts a three-stage approach: First, global contrast registration for each scale is applied. Then, pointwise comparison is given by multiplying the similarity of gradient direction with the similarity of gradient magnitude. Third, intrascale pooling is applied, followed by interscale pooling. Several properties of human visual systems on image gradient have been explored and incorporated into the VGS model. It has been found that Stevens’ power law is also suitable for gradient magnitude. Other factors such as quality uniformity, visual detection threshold of gradient, and visual frequency sensitivity also affect subjective image quality. The optimal values of two parameters of VGS are trained with existing IQA databases, and good performance of VGS has been verified by cross validation. Experimental results show that VGS is competitive with state-of-the-art metrics in terms of prediction precision, reliability, simplicity, and low computational cost. | 2012 |
|
|
Improving Various Reversible Data Hiding Schemes Via Optimal Codes for Binary Covers | In reversible data hiding (RDH), the original cover can be losslessly restored after the embedded information is extracted. Kalker and Willems established a rate-distortion model for RDH, in which they proved out the rate-distortion bound and proposed a recursive code construction. In our previous paper, we improved the recursive construction to approach the rate-distortion bound. In this paper, we generalize the method in our previous paper using a decompression algorithm as the coding scheme for embedding data and prove that the generalized codes can reach the rate-distortion bound as long as the compression algorithm reaches entropy. By the proposed binary codes, we improve three RDH schemes that use binary feature sequence as covers, i.e., an RS scheme for spatial images, one scheme for JPEG images, and a pattern substitution scheme for binary images. The experimental results show that the novel codes can significantly reduce the embedding distortion. Furthermore, by modifying the histogram shift (HS) manner, we also apply this coding method to one scheme that uses HS, showing that the proposed codes can be also exploited to improve integer-operation-based schemes. | 2012 |
|
|
Iterative Channel Decoding of FEC-Based Multiple-Description Codes | Multiple description coding has been receiving attention as a robust transmission framework for multimedia services. This paper studies the iterative decoding of FEC-based multiple description codes. The proposed decoding algorithms take advantage of the error detection capability of Reed-Solomon (RS) erasure codes. The information of correctly decoded RS codewords is exploited to enhance the error correction capability of the Viterbi algorithm at the next iteration of decoding. In the proposed algorithm, an intradescription interleaver is synergistically combined with the iterative decoder. The interleaver does not affect the performance of noniterative decoding but greatly enhances the performance when the system is iteratively decoded. We also address the optimal allocation of RS parity symbols for unequal error protection. For the optimal allocation in iterative decoding, we derive mathematical equations from which the probability distributions of description erasures can be generated in a simple way. The performance of the algorithm is evaluated over an orthogonal frequency-division multiplexing system. The results show that the performance of the multiple description codes is significantly enhanced. | 2012 |
|
|
Local Tetra Patterns A New Feature Descriptor for Content-Based Image Retrieval | In this paper, we propose a novel image indexing and retrieval algorithm using local tetra patterns (LTrPs) for content-based image retrieval (CBIR). The standard local binary pattern (LBP) and local ternary pattern (LTP) encode the relationship between the referenced pixel and its surrounding neighbors by computing gray-level difference. The proposed method encodes the relationship between the referenced pixel and its neighbors, based on the directions that are calculated using the first-order derivatives in vertical and horizontal directions. In addition, we propose a generic strategy to compute nth-order LTrP using (n – 1)th-order horizontal and vertical derivatives for efficient CBIR and analyze the effectiveness of our proposed algorithm by combining it with the Gabor transform. The performance of the proposed method is compared with the LBP, the local derivative patterns, and the LTP based on the results obtained using benchmark image databases viz., Corel 1000 database (DB1), Brodatz texture database (DB2), and MIT VisTex database (DB3). Performance analysis shows that the proposed method improves the retrieval result from 70.34%/44.9% to 75.9%/48.7% in terms of average precision/average recall on database DB1, and from 79.97% to 85.30% and 82.23% to 90.02% in terms of average retrieval rate on databases DB2 and DB3, respectively, as compared with the standard LBP. | 2012 |
|
|
Methodology for Reconstructing Early Zebrafish Development From In Vivo Multiphoton Microscopy | Investigating cell dynamics during early zebrafish embryogenesis requires specific image acquisition and analysis strategies. Multiharmonic microscopy, i.e., second- and third-harmonic generations, allows imaging cell divisions and cell membranes in unstained zebrafish embryos from 1- to 1000-cell stage. This paper presents the design and implementation of a dedicated image processing pipeline (tracking and segmentation) for the reconstruction of cell dynamics during these developmental stages. This methodology allows the reconstruction of the cell lineage tree including division timings, spatial coordinates, and cell shape until the 1000-cell stage with minute temporal accuracy and micrometer spatial resolution. Data analysis of the digital embryos provides an extensive quantitative description of early zebrafish embryogenesis.
|
2012 |
|
|
Multiple Exposure Fusion for High Dynamic Range Image Acquisition | A multiple exposure fusion to enhance the dynamic range of an image is proposed. The construction of high dynamic range images (HDRIs) is performed by combining multiple images taken with different exposures and estimating the irradiance value for each pixel. This is a common process for HDRI acquisition. During this process, displacements of the images caused by object movements often yield motion blur and ghosting artifacts. To address the problem, this paper presents an efficient and accurate multiple exposure fusion technique for the HDRI acquisition. Our method simultaneously estimates displacements and occlusion and saturation regions by using maximum a posteriori estimation and constructs motion-blur-free HDRIs. We also propose a new weighting scheme for the multiple image fusion. We demonstrate that our HDRI acquisition algorithm is accurate, even for images with large motion. | 2012 |
|
|
Nonrigid Brain MR Image Registration Using Uniform Spherical Region Descriptor | There are two main issues that make nonrigid image registration a challenging task. First, voxel intensity similarity may not be necessarily equivalent to anatomical similarity in the image correspondence searching process. Second, during the imaging process, some interferences such as unexpected rotations of input volumes and monotonic gray-level bias fields can adversely affect the registration quality. In this paper, a new feature-based nonrigid image registration method is proposed. The proposed method is based on a new type of image feature, namely, uniform spherical region descriptor (USRD), as signatures for each voxel. The USRD is rotation and monotonic gray-level transformation invariant and can be efficiently calculated. The registration process is therefore formulated as a feature matching problem. The USRD feature is integrated with the Markov random field labeling framework in which energy function is defined for registration. The energy function is then optimized by the α-expansion algorithm. The proposed method has been compared with five state-of-the-art registration approaches on both the simulated and real 3-D databases obtained from the BrainWeb and Internet Brain Segmentation Repository, respectively. Experimental results demonstrate that the proposed method can achieve high registration accuracy and reliable robustness behavior. | 2012 |
|
|
On the Construction of Topology-Preserving Deformation Fields | In this paper, we investigate a new method to enforce topology preservation on deformation fields. The method is composed of two steps. The first one consists in correcting the gradient vector fields of the deformation at the discrete level, in order to fulfill a set of conditions ensuring topology preservation in the continuous domain after bilinear interpolation. This part, although related to prior works by Karaçali and Davatzikos, proposes a new approach based on interval analysis. The second one aims to reconstruct the deformation, given its full set of discrete gradient vectors. The problem is phrased as a functional minimization problem on the convex subset K of the Hilbert space V. The existence and uniqueness of the solution of the problem are established, and the use of Lagrange’s multipliers allows to obtain the variational formulation of the problem on the Hilbert space V . Experimental results demonstrate the efficiency of the method.
|
2012 |
|
|
Onboard Low-Complexity Compression of Solar Stereo Images | We propose an adaptive distributed compression solution using particle filtering that tracks correlation, as well as performing disparity estimation, at the decoder side. The proposed algorithm is tested on the stereo solar images captured by the twin satellites system of NASA’s Solar TErrestrial RElations Observatory (STEREO) project. Our experimental results show improved compression performance w.r.t. to a benchmark compression scheme, accurate correlation estimation by our proposed particle-based belief propagation algorithm, and significant peak signal-to-noise ratio improvement over traditional separate bit-plane decoding without dynamic correlation and disparity estimation. | 2012 |
|
|
Patch-Based Near-Optimal Image Denoising | In this paper, we propose a denoising method motivated by our previous analysis of the performance bounds for image denoising. Insights from that study are used here to derive a high-performance practical denoising algorithm. We propose a patch-based Wiener filter that exploits patch redundancy for image denoising. Our framework uses both geometrically and photometrically similar patches to estimate the different filter parameters. We describe how these parameters can be accurately estimated directly from the input noisy image. Our denoising approach, designed for near-optimal performance (in the mean-squared error sense), has a sound statistical foundation that is analyzed in detail. The performance of our approach is experimentally verified on a variety of images and noise levels. The results presented here demonstrate that our proposed method is on par or exceeding the current state of the art, both visually and quantitatively. | 2012 |
|
|
Precision-Aware Self-Quantizing Hardware Architectures for the Discrete Wavelet Transform | This paper presents designs for both bit-parallel (BP) and digit-serial (DS) precision-optimized implementations of the discrete wavelet transform (DWT), with specific consideration given to the impact of depth (the number of levels of DWT) on the overall computational accuracy. These methods thus allow customizing the precision of a multilevel DWT to a given error tolerance requirement and ensuring an energy-minimal implementation, which increases the applicability of DWT-based algorithms such as JPEG 2000 to energy-constrained platforms and environments. Additionally, quantization of DWT coefficients to a specific target step size is performed as an inherent part of the DWT computation, thereby eliminating the need to have a separate downstream quantization step in applications such as JPEG 2000. Experimental measurements of design performance in terms of area, speed, and power for 90-nm complementary metal-oxide-semiconductor implementation are presented. Results indicate that while BP designs exhibit inherent speed advantages, DS designs require significantly fewer hardware resources with increasing precision and DWT level. A four-level DWT with medium precision, for example, while the BP design is four times faster than the digital-serial design, occupies twice the area. In addition to the BP and DS designs, a novel flexible DWT processor is presented, which supports run-time configurable DWT parameters | 2012 |
|
|
Scalable Coding of Encrypted Images | This paper proposes a novel scheme of scalable coding for encrypted images. In the encryption phase, the original pixel values are masked by a modulo-256 addition with pseudorandom numbers that are derived from a secret key. After decomposing the encrypted data into a downsampled subimage and several data sets with a multiple-resolution construction, an encoder quantizes the subimage and the Hadamard coefficients of each data set to reduce the data amount. Then, the data of quantized subimage and coefficients are regarded as a set of bitstreams. At the receiver side, while a subimage is decrypted to provide the rough information of the original content, the quantized coefficients can be used to reconstruct the detailed content with an iteratively updating procedure. Because of the hierarchical coding mechanism, the principal original content with higher resolution can be reconstructed when more bitstreams are received. | 2012 |
|
|
Removing Label Ambiguity in Learning-Based Visual Saliency Estimation | Visual saliency is a useful clue to depict visually important image/video contents in many multimedia applications. In visual saliency estimation, a feasible solution is to learn a “feature-saliency” mapping model from the user data obtained by manually labeling activities or eye-tracking devices. However, label ambiguities may also arise due to the inaccurate and inadequate user data. To process the noisy training data, we propose a multi-instance learning to rank approach for visual saliency estimation. In our approach, the correlations between various image patches are incorporated into an ordinal regression framework. By iteratively refining a ranking model and relabeling the image patches with respect to their mutual correlations, the label ambiguities can be effectively removed from the training data. Consequently, visual saliency can be effectively estimated by the ranking model, which can pop out real targets and suppress real distractors. Extensive experiments on two public image data sets show that our approach outperforms 11 state-of-the-art methods remarkably in visual saliency estimation. | 2012 |
|
|
Robust Multichannel Blind Deconvolution via Fast Alternating Minimization | Blind deconvolution, which comprises simultaneous blur and image estimations, is a strongly ill-posed problem. It is by now well known that if multiple images of the same scene are acquired, this multichannel (MC) blind deconvolution problem is better posed and allows blur estimation directly from the degraded images. We improve the MC idea by adding robustness to noise and stability in the case of large blurs or if the blur size is vastly overestimated. We formulate blind deconvolution as an l1 -regularized optimization problem and seek a solution by alternately optimizing with respect to the image and with respect to blurs. Each optimization step is converted to a constrained problem by variable splitting and then is addressed with an augmented Lagrangian method, which permits simple and fast implementation in the Fourier domain. The rapid convergence of the proposed method is illustrated on synthetically blurred data. Applicability is also demonstrated on the deconvolution of real photos taken by a digital camera | 2012 |
|
|
Scale-Invariant Features for 3-D Mesh Models | In this paper, we present a framework for detecting interest points in 3-D meshes and computing their corresponding descriptors. For that, we propose an intrinsic scale detection scheme per interest point and utilize it to derive two scale-invariant local features for mesh models. First, we present the scale-invariant spin image local descriptor that is a scale-invariant formulation of the spin image descriptor. Second, we adapt the scale-invariant feature transform feature to mesh data by representing the vicinity of each interest point as a depth map and estimating its dominant angle using the principal component analysis to achieve rotation invariance. The proposed features were experimentally shown to be robust to scale changes and partial mesh matching, and they were compared favorably with other local mesh features on the SHREC’10 and SHREC’11 testbeds. We applied the proposed local features to mesh retrieval using the bag-of-features approach and achieved state-of-the-art retrieval accuracy. Last, we applied the proposed local features to register models to scanned depth scenes and achieved high registration accuracy. | 2012 |
|
|
Scene-Oriented Hierarchical Classification of Blurry and Noisy Images | A system for scene-oriented hierarchical classification of blurry and noisy images is proposed. It attempts to simulate important features of the human visual perception. The underlying approach is based on three strategies: extraction of essential signatures captured from a global context, simulating the global pathway; highlight detection based on local conspicuous features of the reconstructed image, simulating the local pathway; and hierarchical classification of extracted features using probabilistic techniques. The techniques involved in hierarchical classification use input from both the local and global pathways. Visual context is exploited by a combination of Gabor filtering with the principal component analysis. In parallel, a pseudo-restoration process is applied together with an affine invariant approach to improve the accuracy in the detection of local conspicuous features. Subsequently, the local conspicuous features and the global essential signature are combined and clustered by a Monte Carlo approach. Finally, clustered features are fed to a self-organizing tree algorithm to generate the final hierarchical classification results. Selected representative results of a comprehensive experimental evaluation validate the proposed system. | 2012 |
|
|
Rotation-Invariant Image and Video Description With Local Binary Pattern Features | In this paper, we propose a novel approach to compute rotation-invariant features from histograms of local noninvariant patterns. We apply this approach to both static and dynamic local binary pattern (LBP) descriptors. For static-texture description, we present LBP histogram Fourier (LBP-HF) features, and for dynamic-texture recognition, we present two rotation-invariant descriptors computed from the LBPs from three orthogonal planes (LBP-TOP) features in the spatiotemporal domain. LBP-HF is a novel rotation-invariant image descriptor computed from discrete Fourier transforms of LBP histograms. The approach can be also generalized to embed any uniform features into this framework, and combining the supplementary information, e.g., sign and magnitude components of the LBP, together can improve the description ability. Moreover, two variants of rotation-invariant descriptors are proposed to the LBP-TOP, which is an effective descriptor for dynamic-texture recognition, as shown by its recent success in different application problems, but it is not rotation invariant. In the experiments, it is shown that the LBP-HF and its extensions outperform noninvariant and earlier versions of the rotation-invariant LBP in the rotation-invariant texture classification. In experiments on two dynamic-texture databases with rotations or view variations, the proposed video features can effectively deal with rotation variations of dynamic textures (DTs). They also are robust with respect to changes in viewpoint, outperforming recent methods proposed for view-invariant recognition of DTs.
|
2012 |
|
|
Solving Inverse Problems With Piecewise Linear Estimators From Gaussian Mixture Models to Structured Sparsity | A general framework for solving image inverse problems with piecewise linear estimations is introduced in this paper. The approach is based on Gaussian mixture models, which are estimated via a maximum a posteriori expectation-maximization algorithm. A dual mathematical interpretation of the proposed framework with a structured sparse estimation is described, which shows that the resulting piecewise linear estimate stabilizes the estimation when compared with traditional sparse inverse problem techniques. We demonstrate that, in a number of image inverse problems, including interpolation, zooming, and deblurring of narrow kernels, the same simple and computationally efficient algorithm yields results in the same ballpark as that of the state of the art. | 2012 |
| TECHNOLOGY : DOT NET
DOMAIN :IEEE TRANSACTIONS ON SOFTWARE ENGINEERING |
| S.NO | TITLES | ABSTRACT | YEAR |
|
|
A Theoretical and Empirical Analysis of the Role of Test Sequence Length in Software Testing for Structural Coverage | In this paper, we analyze the role that the length plays in software testing, in particular branch coverage. We show that, on “difficult” software testing Bench marks, longer test sequences make their testing trivial. Hence, we argue that the choice of the length of the test sequences is very important in software testing. | 2012 |
|
|
Comparing Semi-Automated Clustering Methods for Persona Development | This paper presents an empirical study comparing the performance of existing qualitative and quantitative clustering techniques for the task of identifying personas and grouping system users into those personas. A method based on Factor (Principal Components) Analysis performs better than two other methods which use Latent Semantic Analysis and Cluster Analysis as measured by similarity to expert manually defined clusters | 2012 |
|
|
An Autonomous Engine for Services Configuration and Deployment | This paper proposes to support the configuration and deployment of services with an automated Closed control loop. The automation is enabled by the definition of a generic information model, which captures all the information relevant to the management of the services with the same abstractions, describing the runtime elements, service dependencies and business objectives. | 2012 |
|
|
Automatic Detection of Unsafe Dynamic Component Loadings | In this paper, we present the first automated technique to detect vulnerable and unsafe dynamic component loadings. Our analysis has two phases: 1) apply dynamic binary instrumentation to collect runtime information on component loading and 2) analyze the collected information to detect vulnerable component loadings | 2012 |
| TECHNOLOGY : DOT NET
DOMAIN : IEEE TRANSACTIONS ON GRID AND CLOUD COMPUTING |
| S.NO | TITLES | ABSTRACT | YEAR |
|
|
Using Rules and Data Dependencies for the Recovery of Concurrent Processes in a Service-Oriented Environment | This paper presents a recovery algorithm for service execution failure in the context of concurrent process execution. The recovery algorithm was specifically designed to support a rule-based approach to user-defined correctness in execution environments that support a relaxed form of isolation for service execution. | 2012 |
|
|
Business-OWL (BOWL)—A Hierarchical Task Network Ontology for Dynamic Business Process Decomposition and Formulation | This paper introduces the Business-OWL (BOWL), an ontology rooted in the Web Ontology Language (OWL), and modeled as a Hierarchical Task Network (HTN) for the dynamic formation of business processes. An ontologized extension and augmentation of traditional HTN, BOWL describes business processes as a hierarchical ontology of decomposable business tasks encompassing all possible decomposition permutations | 2012 |
|
|
Detecting And Resolving Firewall Policy Anomalies | The advent of emerging computing technologies such as service-oriented architecture and cloud computing has enabled us to perform business services more efficiently and effectively. | 2012 |
|
|
ABACS: An Attribute-Based Access Control System for Emergency Services over Vehicular Ad Hoc Networks | ABACS for emergency services with security assurance over VANETs. ABACS aims to improve the efficiency of rescues mobilized via emergency Communications over VANETs. ABACS can select the emergency vehicles that can most appropriately deal with an emergency and securely delegate the authority to control traffic facilities to the assigned emergency vehicles. | 2011 |
|
|
Information Theoretic Aspects of Users’ Activity in a Wyner-Like Cellular Model | This paper proposes an application of multiuser information theory to the study of the uplink of a communication system with Randomly activated users. | 2010 |
|
|
Performance Analysis of Cloud Computing Centers Using M/G/m/m+r Queuing Systems | In this paper, we requests, we describe a novel approximate analytical model for performance evaluation of cloud server farms and solve it to obtain accurate estimation of the complete probability distribution of the request response time and other important performance indicators. | 2012 |
|
|
Enabling Secure and Efficient Ranked Keyword Search over Outsourced Cloud Data | In this paper, we define and solve the problem of secure ranked keyword search over encrypted cloud data. Ranked search greatly enhances system usability by enabling search result relevance ranking instead of sending undifferentiated results, and further ensures the file retrieval accuracy | 2012 |
|
|
A Secure Erasure Code-Based Cloud Storage System with Secure Data Forwarding | We propose a threshold proxy re-encryption scheme and integrate it with a decentralized erasure code such that a secure distributed storage system is formulated. The distributed storage system not only supports secure and robust data storage and retrieval, but also lets a user forward his data in the storage servers to another user without retrieving the data back. | 20123 |
|
|
Toward Secure and Dependable Storage Services in Cloud Computing | We propose in this paper a flexible distributed storage integrity auditing mechanism, utilizing the homomorphic token and distributed erasure-coded data. The proposed design allows users to audit the cloud storage with very lightweight communication and computation cost. | 2012 |
|
|
Optimal Multiserver Con?guration for Pro?t Maximization in Cloud Computing | In this paper, we study the problem of optimal multiserver con?guration for pro?t maximization in cloud computing environment. To maximize the pro?t, a service provider should understand both service charges and business costs, and how they are determined by the characteristics of the applications and the con?guration of a multiserver system. | 2012 |
|
|
Enhanced data security model for cloud computing | Cloud Computing becomes the next generation architecture of IT Enterprise. In contrast to traditional solutions, Cloud computing moves the application software and databases to the large data centers, where the management of the data and services may not be fully trustworthy. This unique feature, however, raises many new security challenges which have not been well understood. In cloud computing, both data and software are fully not contained on the user’s computer; Data Security concerns arising because both user data and program are residing in Provider Premises. Clouds typically have a single security architecture but have many customers with different demands. Every cloud provider solves this problem by encrypting the data by using encryption algorithms. This paper investigates the basic problem of cloud computing data security. We present the data security model of cloud computing based on the study of the cloud architecture. We improve data security model for cloud computing. We implement software to enhance work in a data security model for cloud computing. Finally apply this software in the Amazon EC2 Micro instance | 2012 |
|
|
Implementation of MapReduce-based image conversion module in cloud computing environment | In recent years, the rapid advancement of the Internet and the growing number of people using social networking services (SNSs) have facilitated the sharing of multimedia data. However, multimedia data processing techniques such as transcoding and transmoding impose a considerable burden on the computing infrastructure as the amount of data increases. Therefore, we propose a MapReduce-based image-conversion module in cloud computing environment in order to reduce the burden of computing power. The proposed module consists of two parts: a storage system, i.e., Hadoop distributed file system (HDFS) for image data and a MapReduce program with a Java Advanced Imaging (JAI) library for image transcoding. It can process image data in distributed and parallel cloud computing environments, thereby minimizing the computing infrastructure overhead. In this paper, we describe the implementation of the proposed module using Hadoop and JAI. In addition, we evaluate the proposed module in terms of processing time under varying experimental conditions | 2012 |
|
|
VM Management for Cross-Cloud Computing Environment | Cloud computing is the set of distributed computing nodes. The distribution of virtual machine (VM) images to a set of distributed compute nodes in a Cross-Cloud computing environment is main issue considered in this paper. This paper will be dealing with the problem of scheduling virtual machine (VM) images to a set of distributed compute nodes in a Cross-Cloud computing environment. To address this problem, an efficient approach for VM management is proposed and implemented in this paper. The result will be used as an effective scheduling guidance for VM scheduling on cloud computing as well as cross cloud computing environment. | 2012 |
|
|
Securing cloud computing environment against DDoS attacks | Cloud computing is becoming one of the next IT industry buzz word. However, as cloud computing is still in its infancy, current adoption is associated with numerous challenges like security, performance, availability, etc. In cloud computing where infrastructure is shared by potentially millions of users, Distributed Denial of Service (DDoS) attacks have the potential to have much greater impact than against single tenanted architectures. This paper tested the efficiency of a cloud trace back model in dealing with DDoS attacks using back propagation neural network and finds that the model is useful in tackling Distributed Denial of Service attacks. | 2012 |
|
|
Optimization of Resource Provisioning Cost in Cloud Computing | In cloud computing, cloud providers can offer cloud consumers two provisioning plans for computing resources, namely reservation and on-demand plans. In general, cost of utilizing computing resources provisioned by reservation plan is cheaper than that provisioned by on-demand plan, since cloud consumer has to pay to provider in advance. With the reservation plan, the consumer can reduce the total resource provisioning cost. However, the best advance reservation of resources is difficult to be achieved due to uncertainty of consumer’s future demand and providers’ resource prices. To address this problem, an optimal cloud resource provisioning (OCRP) algorithm is proposed by formulating a stochastic programming model. The OCRP algorithm can provision computing resources for being used in multiple provisioning stages as well as a long-term plan, e.g., four stages in a quarter plan and twelve stages in a yearly plan. The demand and price uncertainty is considered in OCRP. In this paper, different approaches to obtain the solution of the OCRP algorithm are considered including deterministic equivalent formulation, sample-average approximation, and Benders decomposition. Numerical studies are extensively performed in which the results clearly show that with the OCRP algorithm, cloud consumer can successfully minimize total cost of resource provisioning in cloud computing environments. | 2012 |
|
|
Cloud intelligent track – Risk analysis and privacy data management in the cloud computing | Cloud computing is a computing platform with the backbone of internet to store, access the data and application which is in the cloud, not in the computer. The biggest issue which should be addressed in cloud computing are security and privacy. Outsourcing data to other companies worries internet clients to think about the privacy data. Most Enterprise executives hesitate to use cloud computing system due to their sensitive enterprise information. This paper provides data integrity and user privacy through cloud intelligent track system. This paper discuss about the previous experiment done on the privacy and data management. The work proposes the Architecture or system which provides intelligent track in Privacy Manager and Risk Manager to address privacy issues which rules the cloud environment. | 2012
|
|
|
Measurement and utilization of customer-provided resources for cloud computing | Recent years have witnessed cloud computing as an efficient means for providing resources as a form of utility. Driven by the strong demands, such industrial leaders as Amazon, Google, and Microsoft have all offered practical cloud platforms, mostly datacenter-based. These platforms are known to be powerful and cost-effective. Yet, as the cloud customers are pure consumers, their local resources, though abundant, have been largely ignored. In this paper, we for the first time investigate a novel customer-provided cloud platform, SpotCloud, through extensive measurements. Complementing data centers, SpotCloud enables customers to contribute/sell their private resources to collectively offer cloud services. We find that, although the capacity as well as the availability of this platform is not yet comparable to enterprise datacenters, SpotCloud can provide very flexible services to customers in terms of both performance and pricing. It is friendly to the customers who often seek to run short-term and customized tasks at minimum costs. However, different from the standardized enterprise instances, SpotCloud instances are highly diverse, which greatly increase the difficulty of instance selection. To solve this problem, we propose an instance recommendation mechanism for cloud service providers to recommend short-listed instances to the customers. Our model analysis and the real-worldexperiments show that it can help the customers to find the best trade off between benefit and cost.
|
2012 |
|
|
Energy-efficient Virtual Machine Consolidation for Cloud Computing | In the presence of rising costs for energy, infrastructure, cooling and power supply, Infrastructure-as-a-Service Cloud computing providers are highly interested in increasing the energy efficiency of their hardware- and software architectures. In this article, a novel approach to virtual machine consolidation for saving energy is presented. It is based on energy-efficient storage migration and live migration of virtual machines to take advantage of the lacking energy-proportionality of commodity hardware. Eucalyptus, an open-source clone of the popular Amazon Elastic Compute Cloud, is used to implement the proposed approach. Several short- and long-term experiments are presented, demonstrating the potential for energy savings in productive Cloud computing environments. Quality-of-service violations during the consolidation process are addressed. | 2012 |
|
|
On energy-aware aggregation of dynamic temporal demand in cloud computing | The proliferation of cloud computing faces social and economic concerns on energy consumption. We present formulations for cloud servers to minimize energy consumption as well as server hardware cost under three different models (homogeneous, heterogeneous, mixed hetero-homogeneous clusters) by considering dynamic temporal demand. To be able to compute optimal configurations for large scale clouds, we then propose static and dynamic aggregation methods, which come at the additional cost on energy consumption; however, they still result in significant savings compared to the scenario when all servers are on during the entire duration. Our studies show that the homogeneous model takes four time less computational time than the heterogeneous model. The dynamic aggregation scheme results in 8% to 40% savings over the static aggregation scheme when the degree of aggregation is high. | 2012 |
|
|
Toward Secure and Dependable Storage Services in Cloud Computing | Cloud storage enables users to remotely store their data and enjoy the on-demand high quality cloud applications without the burden of local hardware and software management. Though the benefits are clear, such a service is also relinquishing users’ physical possession of their outsourced data, which inevitably poses new security risks toward the correctness of the data in cloud. In order to address this new problem and further achieve a secure and dependable cloud storage service, we propose in this paper a flexible distributed storage integrity auditing mechanism, utilizing the homomorphic token and distributed erasure-coded data. The proposed design allows users to audit the cloud storage with very lightweight communication and computation cost. The auditing result not only ensures strong cloud storage correctness guarantee, but also simultaneously achieves fast data error localization, i.e., the identification of misbehaving server. Considering the cloud data are dynamic in nature, the proposed design further supports secure and efficient dynamic operations on outsourced data, including block modification, deletion, and append. Analysis shows the proposed scheme is highly efficient and resilient against Byzantine failure, malicious data modification attack, and even server colluding attacks | 2012
|
|
|
Improving public auditability, data possession in data storage security for cloud computing | Cloud computing is Internet based technology where the users can subscribe high quality of services from data and software that resides solely in the remote servers. This provides many benefits for the users to create and store data in the remote servers thereby utilizing fewer resources in client system. However management of the data and software may not be fully trustworthy which possesses many security challenges. One of the security issues is the data storage security where frequent integrity checking of remotely stored data is carried out. RSA based storage security (RSASS) method uses public auditing of the remote data by improving existing RSA based signature generation. This public key cryptography technique is widely used for providing strong security. Using this RSASS method, the data storage correctness is assured and identification of misbehaving server with high probability is achieved. This method also supports dynamic operation on the data and tries to reduce the server computation time. The preliminary results achieved through RSASS, proposed scheme outperforms with improved security in data storage when compared with the existing methods. | 2012 |
|
|
Comparing efficiency and costs of cloud computing models | Public and private clouds are being adopted as a cost-effective approach for sharing IT resources. Customers acquire and release resources by requesting and returning virtual machines to the cloud. Different service models are proposed for virtual machine resource management. Some public cloud providers follow a t-shirt model for VM resource sizing. A second approach for resource management is based on a time share model. This paper compares the two approaches from the perspective of resource usage for both the service provider and workload owner. Using data from 312 customer applications, we show that the t-shirt model requires 40% more infrastructure than when a finer degree of resource sharing based on time varying resource shares is permitted. | |
|
|
Resource Selection Strategy Based on Propagation Delay in Cloud | Cloud computing is a highly scalable distributed computing platform in which computing resources are offered ‘as a service’ leveraging virtualization. Cloud Computing distributes the computational tasks on the resource pool which consists of massive computers so that the service consumer can gain maximum computation strength, more storage space and software services for its application according to its need. A huge amount of data moves from user to host and hosts to user in the cloud environment. Based on the above two considerations, how to select appropriate host for accessing resources and creating a virtual machine(VM) to execute applications so that execution becomes more efficient and access cost becomes low as far as possible simultaneously is a challenging task. In this paper, a host selection model based on minimum network delay is proposed, the objective is to minimize propagation time of input and output data by selecting nearest host into the network. And finally it minimizes the execution time of cloudlet. | 2012 |