Search

Many datasets including social media data and bibliographic data can be modeled as graphs. Clustering such graphs is able to provide useful insights into the structure of the data. To improve the quality of clustering, node attributes can be taken into account, resulting in attributed graphs. Existing attributed graph clustering methods generally consider attribute similarity and structural similarity separately. In this paper, we represent attributed graphs as star-schema heterogeneous graphs, where attributes are modeled as different types of graph nodes. This enables the use of personalized pagerank (PPR) as a unified distance measure that captures both structural and attribute similarities. We employ DBSCAN for clustering, and we update edge weights iteratively to balance the importance of different attributes. The rapidly growing volume of data nowadays challenges traditional clustering algorithms, and thus, a distributed method is required. Hence, we adopt a popular distributed graph computing system Blogel, based on which, we develop four exact and approximate approaches that enable efficient PPR score computation when edge weights are updated. To improve the effectiveness of the clustering, we propose a simple yet effective edge weight update strategy based on entropy. In addition, we present a game theory based method that enables trading efficiency for result quality. Extensive experiments on real-life datasets offer insights into the effectiveness and efficiency of our proposals. [ABSTRACT FROM AUTHOR]

Modern surveillance systems rely on coverage overlapping to attain multi-viewing capabilities and to support coverage redundancy. This paper examines the coverage overlapping configurations in visual surveillance systems. This paper proposes a robust dynamic programming framework to optimize visual surveillance sensor coverage overlaps. Based on visual sensor parameters information, and the features of the area to be monitored, this paper uses a deterministic modeling approach to model the sensor coverage in a 2-D space. Then, the minimization and the maximization arrangements of the coverage overlapping are formulated as discrete optimization problems. The obtained solutions from the dynamic programming technique are evaluated with respect to local and global greedy search algorithms. The results reveal the feasibility of the proposed technique compared with the benchmarked optimization methods in terms of the amount of coverage redundancy. [ABSTRACT FROM PUBLISHER]

Permanent magnet localization (PML) is a nascent method of wireless motion tracking that can estimate the 5D state (3D position and 2D orientation) of a cylindrical magnet from its magnetic field. PML is well suited for applications where a wireless tracking is crucial, and in particular for tongue motion which opens up many new interesting applications. To allow its usage outside of a research lab, our tongue tracking system relies on the PML to avoid impeding tongue’s natural motion due to its wireless tracking method and ensure safe use inside the mouth. Our tracking module is embedded in a headset to be portable and simple to use while being affordable by relying on the mass-produced components. The classical implementation of PML has many shortcomings that limit its practicality for real-world applications because it is computationally intensive due to its iterative algorithm, subject to local minimum convergence issues, and sensitive to its initial state and calibration parameters. Additionally, its physical model is an approximation that is only valid in limited tracking conditions. In this paper, we investigated the potential of deep learning to create a PML model for tongue tracking by training a feedforward neural network (3 layers, 100 neurons per layer) on a dataset composed of ∼1.7 million states spanning a volume of $10\times 10\times 10$ cm3. Our PML was validated on 337 000 states in a $4\times 6\times 7$ cm3 volume and tested on 100 000 samples emulating a more natural tongue motion with curves and twists. A fully automated 5D positional stage was engineered by our team to collect these large datasets of the 5D magnet states. Our PML prediction, limited to the magnet’s 3D positions in this paper, reaches positional errors of 1.4 mm (median) and 1.8 mm (Q3). [ABSTRACT FROM AUTHOR]

Graph pattern matching has been extensively investigated on general graphs without time information over decades. Nevertheless, few studies focus on temporal graphs, where a relationship between two vertices takes place at a specific moment and lingers for some time. In this paper, we propose a new notion so-called time-respecting flow graph, in which all paths are time-respecting (i.e., a sequence of contacts with non-decreasing time), and one vertex is distinguished as the root, from which other vertices can be reached via a time-respecting path. Based on this, we explore the problem of time-respecting flow graph pattern matching on temporal graphs. This problem motivates important applications in epidemiology, information diffusion, crime detection, etc. To address it, we present one baseline algorithm as well as two optimized algorithms that utilize several efficient matching strategies and topological sort based technique to boost efficiency. Extensive experimental evaluation using both real and synthetic data sets demonstrates the effectiveness and efficiency of our proposed algorithms. Compared with baseline method, our optimized algorithms could achieve up to three orders of magnitude speedup. [ABSTRACT FROM AUTHOR]

The orbit of the tropical rainfall measuring mission (TRMM) satellite was boosted from 350 to 402.5 km in August 2001 to extend its lifetime by conserving fuel. Since the timing between transmission and reception by the precipitation radar (PR) onboard the TRMM satellite was a fixed constant for measurement from an original altitude of 350 km, the PR encountered a mismatch between the transmitting and receiving beams after the TRMM orbit boost. Although the PR algorithm in TRMM Version 7 employs a correction for the beam mismatch, its error remains as an underestimation of the precipitation estimates near surface in the second half of the swath. This paper aims to mitigate the beam-mismatch correction error in Version 7. The beam-mismatch correction needs to estimate the radar echo that would be measured in the virtual intermediate beam between the beam in question and the previous adjacent beam. The beam-mismatch correction developed in this paper assumes that the surface and precipitation echoes change linearly in the horizontal direction in parallel to the surface between the two beams. The new correction is tested with observational data, indicating that the method improves the accuracy of the correction at off-nadir angles. Statistics of the surface normalized radar cross sections and the bright band peak intensities at off-nadir angles are improved using the method. The asymmetric bias of the precipitation estimates with respect to the scan angle in Version 7 is mitigated by 95.9% over ocean and 72.5% over land with the new correction. [ABSTRACT FROM AUTHOR]

In this paper, we develop a technique to extend any bound for the minimum distance of cyclic codes constructed from its defining sets (ds-bounds) to Abelian (or multivariate) codes through the notion of ${\mathbb B}$ -apparent distance. We also study conditions for an Abelian code to verify that its ${\mathbb B}$ -apparent distance reaches its (true) minimum distance. Then, we construct some codes as an application. [ABSTRACT FROM AUTHOR]

Companies operating large datacenters are focusing on how to reduce the electrical energy costs of operating datacenters. A common way of cost reduction is to perform a dynamic voltage and frequency scaling (DVFS), thereby matching the CPU’s performance and power level to incoming workloads. Another power saving technique is CPU consolidation, which uses the minimum number of CPUs necessary to meet the service request demands and turns OFF the remaining unused CPUs. DVFS has been already extensively studied and verified its effectiveness. On the other hand, it is necessary to study more about the effectiveness of CPU consolidation. Key questions that must be answered are how effectively the CPU consolidation improves the energy efficiency and how to maximize the improvement. These questions are addressed in this paper. After understanding modern power management techniques and developing an appropriate power model, this paper provides an extensive set of hardware-based experimental results and makes suggestions about how to maximize energy efficiency improvement through CPU consolidation. In addition, this paper also presents new online CPU consolidation algorithms, which reduce the energy-delay product up to 13% compared with the Linux default DVFS algorithm. [ABSTRACT FROM AUTHOR]

This paper introduces a bistatic fast backprojection synthetic aperture radar (SAR) algorithm that is available for different bistatic geometries. The proposed algorithm is tested with the bistatic CARABAS-like data, and the results indicate that the algorithm is a good candidate for bistatic SAR data processing. The image quality measurements are quite similar to the referenced values obtained with the bistatic global backprojection algorithm. That is, the peak sidelobe ratio (PSLR) is −13.7 dB in comparison to the referenced PSLR of −13.8 dB. The half-power beamwidths (HPBWs) measured on the cuts in $x$ and $y$ and the direction where the peak sidelobes locate are 2.8, 3.7, and 3.5 m, respectively, which are approximate to the referenced HPBWs. The small differences in the measured results mainly come from the interpolation step of the algorithm. [ABSTRACT FROM AUTHOR]

Hybridization networks represent plausible evolutionary histories of species that are affected by reticulate evolutionary processes. An established computational problem on hybridization networks is constructing the most parsimonious hybridization network such that each of the given phylogenetic trees (called gene trees) is “displayed” in the network. There have been several previous approaches, including an exact method and several heuristics, for this NP-hard problem. However, the exact method is only applicable to a limited range of data, and heuristic methods can be less accurate and also slow sometimes. In this paper, we develop a new algorithm for constructing near parsimonious networks for multiple binary gene trees. This method is more efficient for large numbers of gene trees than previous heuristics. This new method also produces more parsimonious results on many simulated datasets as well as a real biological dataset than a previous method. We also show that our method produces topologically more accurate networks for many datasets. [ABSTRACT FROM PUBLISHER]

In multilateration, distances between an unknown location and several known points are used to determine the location of the unknown point. Papers on algorithms for multilateration, such as time of arrival (TOA), time difference of arrival (TDOA), and angle of arrival (AOA), have proliferated in the literature. These use the same equations, but are often written in a way that hides the underlying geometry and make it difficult to see the similarity in approaches between different papers. This paper provides a review of TOA and AOA-based localization approaches, with a focus on linear positioning algorithms. This paper presents simple and consistent versions of TOA, TDOA, and AOA position equations with intuitive explanations for how those equations relate to the geometry of the localization problem. This perspective can make it easier to implement these algorithms in a way that produces stable results and provides insight into the underlying geometric problem. We also review the literature relating to TDOA and AOA localization algorithms and multistatic radar.

Information-theoretic security is considered in the paradigm of network coding in the presence of wiretappers, who can access one arbitrary edge subset up to a certain size, also referred to as the security level. Secure network coding is applied to prevent the leakage of the source information to the wiretappers. In this paper, we consider the problem of secure network coding when the information rate and the security level can change over time. To efficiently solve this problem, we put forward local-encoding-preserving secure network coding, where a family of secure linear network codes (SLNCs) is called local-encoding-preserving if all the SLNCs in this family share a common local encoding kernel at each intermediate node in the network. We first consider the design of a family of local-encoding-preserving SLNCs for a fixed security level and a flexible rate. A simple approach is presented for efficiently constructing upon an SLNC that exists a local-encoding-preserving SLNC with the same security level and the rate reduced by one. By applying this approach repeatedly, we can obtain a family of local-encoding-preserving SLNCs with a fixed security level and multiple rates. We further consider the design of a family of local-encoding-preserving SLNCs for a fixed rate and a flexible security level. We present a novel and efficient approach for constructing upon an SLNC that exists a local-encoding-preserving SLNC with the same rate and the security level increased by one. Next, we consider the design of a family of local-encoding-preserving SLNCs for a fixed dimension (equal to the sum of rate and security level) and a flexible pair of rate and security level. We propose another novel approach for designing an SLNC such that the same SLNC can be applied for all the rate and security-level pairs with the fixed dimension. Also, two polynomial-time algorithms are developed for efficient implementations of the later two proposed approaches, respectively. Furthermore, we prove that all our three approaches do not incur any penalty on the required field size for the existence of SLNCs in terms of the best known lower bound by Guang and Yeung. Finally, we consider the ultimate problem of designing a family of local-encoding-preserving SLNCs that can be applied to all possible pairs of rate and security level. By combining the constructions of the three families of local-encoding-preserving SLNCs in the paper in suitable ways, we can obtain a family of local-encoding-preserving SLNCs that can be applied for all possible pairs of rate and security level. Three possible such constructions are presented. [ABSTRACT FROM AUTHOR]

People use various online social networks for different purposes. The user information on each social network is usually partial. Thus, matching the users across these multiple online social networks is of great significance for providing new services as well as new insights on user behaviors. Recent research shows that group structure widely exists on social networks, in which members work together with certain purpose and are more influential than individuals on online social networks. Previous works provide outstanding solutions for mapping individuals, but few ones pay attention to the study of groups across multiple social networks. To address the research gap, we first aim to propose an effective method to detect similar group across multiple social networks. The method mainly has three steps, including detecting group structure based on random walks, extracting similarity features, and inferring group similarity using probabilistic graphical model. We evaluate our algorithm on five different types of online social networks. Experimental results show that our method achieves 0.693, 0.779, 0.729 in precision, recall, and ${F}1$ -measure, which significantly surpass the state-of-the-art by 31.4%–44.3%, 17.3%–26.3%, and 25.9%–31.6%, respectively. The outstanding performance of our method demonstrates that our proposal can reach the requirement of detecting similar groups across social networks. In particular, the result of this paper paves the way for the recommendation system, link prediction and information diffusion across sites. [ABSTRACT FROM AUTHOR]

Since the well-established navigation systems such as GPS are ineffective in indoor environments, research into developing novel indoor positioning technologies has emerged in recent years. While several technologies are being investigated, a practical and reliable indoor positioning system is yet to emerge. Indoor positioning using light signals holds a great potential to provide a reliable solution to the indoor positioning problem. This paper presents a comprehensive review of the available literature on light-based indoor positioning systems. The paper establishes a classification based on the design of various light-based indoor positioning (LIP) systems, and discusses their key components including hardware, software and algorithms. The limitations and challenges of the LIP systems are discussed in details, and current published solutions are presented. The review also provides a comparison between LIP systems and other optical positioning systems, and identifies the associated research gaps. Finally, based on the identified gaps, the future research directions in both LIP systems and other optical positioning systems are presented. [ABSTRACT FROM AUTHOR]

Determining safe and fast routes for first responders is an important issue in a disaster response. Especially when different types of disasters (e.g., toxic plumes, fires, and floods) occur and affect transportation networks simultaneously, special routing strategies (e.g., detour) would be needed to ensure the safety for responders. On the other hand, after disasters happen, a quick response time is required, and the responders should move as fast as possible and even go through certain obstacles to reach the disaster sites to deliver emergency services. In this paper, we study path planning through moving obstacles, taking into account the influence of obstacles on the status of road networks and the speed of rescue vehicles. A set of algorithms is proposed to deal with not only geometries but also the properties of moving obstacles to support route generation. Based on the Dijkstra algorithm, a new routing algorithm is designed and developed, which aims at minimizing the risk while constraining the travel time of routes. We validate our approach with a set of experiments on some navigation cases. The experimental results show the promise of the algorithm in the generation of feasible and safe routes for first responders to pass through moving obstacles. [ABSTRACT FROM AUTHOR]

Disassembly planning aims to perform the optimal disassembly sequence given a used or obsolete product in terms of cost and environmental impact. This paper presents a new multiobjective programming model for the target disassembly sequencing. It proposes an improved multiobjective ant colony algorithm to derive optimal target disassembly sequences. This work also establishes some indices on disassembly scheme evaluation and a fuzzy integral method to evaluate the obtained disassembly scheme. A CNC machine tool example is given to illustrate the proposed models and the effectiveness of the proposed algorithm. Both theoretical and simulation results demonstrate that the proposed approach can perform the quantitative analysis of a disassembly process effectively. Such results can help decision makers select the best plans and sequences when executing a disassembly process of a product. [ABSTRACT FROM AUTHOR]

With advances in geo-positioning technologies and mobile internet, location-based services have attracted much attention, and spatial keyword queries are catching on fast. However, as far as we aware, no prior work considers the temporal information of geo-tagged objects. Temporal information is important in the spatial keyword query because many objects are not always valid. For example, visitors may plan their trips according to the opening time of attractions. In this paper, we identify and solve a novel problem, i.e., the time-aware Boolean spatial keyword query (TABSKQ), which returns the $k$ objects that satisfy users’ spatio-temporal description and textual constraint. We first present pruning strategies and algorithm based on the CIR ^{+} -tree (i.e., the CIR-tree with temporal information). Then, we propose an efficient index structure, called the TA-tree, and its corresponding algorithms, which can prune the search space using both spatio-temporal and textual information. Furthermore, we study an interesting TABSKQ variant, i.e., Joint TABSKQ (JTABSKQ), which aims to process a set of TABSKQs jointly, and extend our techniques to tackle it. Extensive experiments with real datasets offer insight into the performance of our proposed indices and algorithms. [ABSTRACT FROM AUTHOR]

This paper investigates the spectrum fragmentation issue, which undermines the bandwidth efficiency in elastic optical networks. After categorizing the two-dimensional fragmentation problem as the fragmentation and misalignment subproblems, this paper proposes joint routing and spectrum assignment (RSA) algorithms to alleviate the spectral fragmentation in the lightpath provisioning process. The time complexity of the two proposed algorithms are analyzed in detail, and both algorithms can run in 0(kdnC log C) time, where k is the number of the shortest path in the routing algorithm, d is the maximum node degree in the network, n is the number of nodes in the network, and C is the link capacity expressed as the number of spectral slots. Simulation results indicate that the proposed fragmentation-aware (FA) RSA algorithm and the FA algorithm with congestion avoidance (CA) outperform the existing schemes in terms of blocking probability (BP) reduction. Compared with the benchmark iT-shortest-path routing and first-fit assignment (KSP-FF) algorithm, the proposed FA and FA-CA algorithms can achieve a BP reduction of [100%, 4.43%] and [100%, 6.45%], respectively, according to the traffic load in a sample NSFNET topology. [ABSTRACT FROM PUBLISHER]

Due to the emergence of new network applications, current IP lookup engines must support high bandwidth, low lookup latency, and the ongoing growth of IPv6 networks. However, the existing solutions are not designed to address jointly these three requirements. This paper introduces SHIP, an IPv6 lookup algorithm that exploits prefix characteristics to build a data structure designed to meet future application requirements. Based on the prefix length distribution and prefix density, prefixes are first clustered into groups sharing similar characteristics and then encoded in hybrid trie-trees. The resulting memory-efficient and scalable data structure can be stored in low-latency memories and allows the traversal process to be parallelized and pipelined in order to support high packet bandwidth in hardware. In addition, SHIP supports incremental updates. Evaluated on real and synthetic IPv6 prefix tables, SHIP has a logarithmic scaling factor in terms of the number of memory accesses and a linear memory consumption scaling. Compared with other well-known approaches, SHIP reduces the required amount of memory per prefix by 87%. When implemented on a state-of-the-art field-programmable gate array (FPGA), the proposed architecture can support processing 588 million packets per second. [ABSTRACT FROM AUTHOR]

Magnetic surveys are conventionally performed by scanning a domain with a portable scalar magnetic sensor. Unfortunately, scalar magnetometers are expensive, power consuming, and bulky. In many applications, calibrated vector magnetometers can be used to perform magnetic surveys. In recent years, algorithms based on artificial intelligence (AI) achieve state-of-the-art results in many modern applications. In this paper, we investigate an AI algorithm for the classical scalar calibration of magnetometers. A simple, low-cost method for performing a magnetic survey is presented. The method utilizes a low-power consumption sensor with an AI calibration procedure that improves the common calibration methods and suggests an alternative to the conventional technology and algorithms. The setup of the survey system is optimized for quick deployment in situ right before performing the magnetic survey. We present a calibration method based on a procedure of rotating the sensor in the natural earth magnetic field for an optimal time period. This technique can deal with a constant field offset and non-orthogonality issues and does not require any external reference. The calibration is done by finding an estimator that yields the calibration parameters and produces the best geometric fit to the sensor readings. A comprehensive model considering the physical, algorithmic, and hardware properties of the magnetometer of the survey system is presented. The geometric ellipsoid fitting approach is parametrically tested. The calibration procedure reduced the root-mean-square noise from the order of $10^{4}$ nT to less than 10 nT with variance lower than 1 nT in a complete 360° rotation in the natural earth magnetic field. In a realistic survey scheme, the obtained calibration noise is suited to the environmental survey clutter. Implementing this scheme with a modern low-power analog-to-digital convertor and micro-controller results in power consumption lower than 15 mW and calibration duration of few minutes. [ABSTRACT FROM AUTHOR]

In this paper, a new method is proposed to identify and classify the data obtained by the sensor network (SN) for the detection of mines. This method is used for the identification of antitank and antipersonnel mines and classification of buried objects within a target region. In this paper, a mobile SN is used to detect mines and some other objects buried and creating magnetic anomaly in and around the region where they are found, with the behavior of the individual sensors swarming onto the area under which a mine or any other object is buried. The process of collecting data by the SN and modeling it mathematically are explained in detail. The SN is modeled as a fictitious two-dimensional spatial impulse sampler. This paper is motivated by clearing the territories of mine fields to open them to agriculture. It is very important because, currently, in some countries, very fertile territories around the borders are covered by buried mines. The approach is basically based on magnetic anomaly measurements, which directly tackles the subregions corresponding to buried objects whether they represent objects that are separately located or occluded by other objects. It is based on a new developed method that is called “the back-most object detection and identification algorithm.” This method is fully automatic, and there is no human intervention throughout the process. In this paper, classification of objects is based on their well-known shapes and dimensions. Therefore, there is no need for sophisticated learning algorithms to achieve classification. The experimental results are given both for detection and identification of a single mine and classification of a number of mines and any other objects that have a potential of giving false alarms in a target region. [ABSTRACT FROM AUTHOR]

Recently, an important set of high dimensional signals (HDS) applications has successfully implemented compressive sensing (CS) sensors in which their efficiency depends on physical elements that perform a binary codification over the HDS. The structure of the binary codification is crucial as it determines the HDS sensing matrices. For a correct reconstruction, this class of matrices drastically differs from the dense or i.i.d. assumptions usually made in CS. Therefore, current CS matrix design algorithms are impractical. This paper proposes a novel strategy to design structured, sparse, and binary HDS measurement matrices based on promoting linear independence between rows by minimizing the number of its zero singular values. The design constraints lead to keep uniform both, the number of non-zero elements per row and also the number of non-zero elements per column. An algorithm based on an optimal selection of non-zero entries positions is developed to implement this strategy. Simulations show that the proposed optimization improves the quality of the reconstructed HDS in up to 8 dB of PSNR compared with non-optimized matrices. [ABSTRACT FROM AUTHOR]

Dedicated short-range communication (DSRC) technology has been adopted by the IEEE community to enable safety and nonsafety applications for vehicular ad hoc networks. To better serve these two classes of applications, the DSRC standard divides the bandwidth into seven channels. One channel, which is called the control channel (CCH), serves safety applications, and the other six channels, which are called service channels, serve nonsafety applications. The DSRC standard specifies a channel-switching scheme to allow vehicles to alternate between these two classes of applications. The standard also recommends that vehicles should visit the CCH every 100 ms, which is called the synchronization interval (SI), to send and receive their status messages. It is highly desirable that these status messages be delivered to the neighboring vehicles reliably and within an acceptable delay bound. It is obvious that increasing the time share of the CCH from the SI will increase the reliability of safety applications. In this paper, we propose two algorithms to optimize the length of the control channel interval (CCI) such that nonsafety applications have a fair share of the SI interval. One algorithm, which is called optimal channel access, is proposed to allow vehicles to access the channel with a derived optimal probability such that the successful transmission rate is maximized. The second algorithm, which is called the mobility- and topology-aware algorithm, is an adaptive scheme proposed to change the DSRC parameters based on the road and network conditions to allow the coexistence of safety and nonsafety applications on the DSRC. Vehicles will execute both algorithms in a distributed manner to achieve a high success rate within the selected CCI interval. The simulation results show that using the two new algorithms keeps the CCI below half of the SI in all scenarios while maintaining a high success rate for safety messages. This will give nonsafety applications the opportunity to work in the second half of the SI interval without jeopardizing the critical safety applications. [ABSTRACT FROM AUTHOR]

The collective spatial keyword query (CSKQ), an important variant of spatial keyword queries, aims to find a set of the objects that collectively cover users' queried keywords, and those objects are close to the query location and have small inter-object distances. Existing works only focus on the CSKQ problem in the Euclidean space, although we observe that, in many real-life applications, the closeness of two spatial objects is measured by their road network distance. Thus, existing methods cannot solve the problem of network-based CSKQ efficiently. In this paper, we study the problem of collective spatial keyword query processing on road networks, where the objects are located on a predefined road network. We first prove that this problem is NP-complete, and then we propose two approximate algorithms with provable approximation bounds and one exact algorithm, for supporting CSKQ on road networks efficiently. Extensive experiments using real datasets demonstrate the efficiency and accuracy of our presented algorithms. [ABSTRACT FROM PUBLISHER]

Given a geo-textual dataset $\mathbb {O}$ O , a set $\varphi$ φ of keywords, a query object $q \in \mathbb {O}$ q ∈ O , and an integer $k$ k , a reverse top- $k$ k keyword-based location query returns the influence zone $\mathcal {R}$ R of $q$ q such that $q$ q belongs to the result of a top- $k$ k spatial keyword query with query keywords $\varphi$ φ and any location in $\mathcal {R}$ R as arguments. For a query object $q$ q , the influence zone of $q$ q varies for different keywords $\varphi$ φ . Users may be interested in identifying the maximum influence zone of the query object. To this end, in this paper, we study the problem called MaxiZone that finds the keyword set maximizing the influence zone of a specified query object. The MaxiZone problem has many real-life applications, e.g., a business owner would like to identify the maximum influence zone so as to attract as many customers as possible. A straightforward way to tackle the MaxiZone problem is to compute the influence zone for every candidate keyword set. Obviously, this is infeasible if there are a large number of candidate keyword sets. We propose a more efficient index-centric algorithm together with a series of optimizations as well as a sampling-based algorithm, to facilitate the query processing. Moreover, we extend the proposed algorithms to address a variant of MaxiZone problem called $\tau$ τ -MaxiZone problem, which finds top- $\tau$ τ keyword sets having the maximum influence zones. Extensive empirical study using real-world datasets demonstrates the effectiveness and efficiency of our proposed algorithms. [ABSTRACT FROM AUTHOR]

This paper presents a fast fuzzy logic control algorithm for a Takagi–Sugeno–Kang fuzzy controller, which is applied to integrated \textLED drivers with the purpose of getting a good dynamic response and the reduction in the low-frequency (120 Hz) ripple. The algorithm uses the high-speed mathematical engine of a digital signal controller \text(DSC) that is capable to achieve fast multiplications during a common one-cycle instruction. Therefore, the execution time of the controller is improved with the use of a \textDSC. A scaling procedure is included in the program in order to use and to improve the accuracy of the multiplications and divisions in the \textDSC mathematical engine. A low-range \textDSC was used to program the proposed controller; therefore, the cost is affordable for \textLED driver applications. The fuzzy control curve was approximated to the sliding mode control \text(SMC) curve with the purpose of getting some of the good advantages of the \textSMC strategy like a good dynamic performance. The proposed controller is used to regulate the \textLED current. Simulation and experimental results are shown [ABSTRACT FROM PUBLISHER]

A methodology for automatic incipient broken rotor bar detection in induction motors (IMs) is presented. Sparse representations of signals are applied as a diagnosis technique. The novelty of this technique is that it can analyze the frequency spectra from vibration signals even when the differences among signals are small. This representation allows decomposing or reconstructing signals through a trained dictionary that has learned the features of one specific group/class. The main feature of this paper is the use of overcomplete dictionaries trained from sets of signals with faults to be detected. In this way, trained dictionaries perform the decomposition of signals using the orthogonal matching pursuit (OMP) algorithm. The decomposition is evaluated and classified by error-based criteria and a majority decision classifier, allowing the detection of early damage, ranging from 1 mm to one broken bar. The detection is performed by the decomposition of vibration signals from three axes ( ${x}$ , ${y}$ , and ${z}$ ) of IMs under three load conditions (unloaded, half loaded, and three-fourths loaded) and different levels of damage (healthy or 0 mm, 1–9 mm, and one broken bar). These signals are processed by the Fourier transform and the spectrum obtained is evaluated by the OMP algorithm. Finally, the retrieved information is evaluated and the diagnosis is given. All algorithms are developed in MATLAB software and the detection accuracy is higher than 90% for damages as small as 1 mm. [ABSTRACT FROM AUTHOR]

The rapid progress of invasive therapeutic options for cardiac arrhythmias increases the need for accurate diagnostics. The surface electrocardiogram (ECG) is still the standard of noninvasive diagnostics but lacks atrial signal resolution. By contrast, esophageal electrocardiography (EECG) yields atrial signals of high amplitude and with a high signal-to-noise ratio. Esophageal electrocardiography has become fast and safe, but the mechanical constraints of esophageal measuring catheters and the “random” motion of the catheter inside the subject's esophagus limit the spatial resolution of EECG signals. In this paper, we propose a method to estimate the electrical field projected onto the esophagus with an increased spatial resolution, using commonly available esophageal catheters. In a first step, we estimate the time-varying catheter position, and in a second step, we estimate the projected electrical field with enhanced spatial resolution. The proposed algorithm comprises several consecutive optimization steps, where each intermediate step produces not just a single point estimate, but a cost function over multiple solutions, which reduces the information loss at each processing step. We conclude with examples from a clinical trial, where the fields of cardiac arrhythmias are presented as two-dimensional contour plots. [ABSTRACT FROM AUTHOR]

In 10nm technology node, self-aligned double patterning (SADP) and triple patterning lithography (TPL) allow us to achieve minimum wiring pitch of around 45nm. While metal layers can be printed by SADP, via layer manufacturing requires TPL to maintain design rules. SADP-aware detailed routing is proposed to ensure decomposability of metal layer patterns. However, its routing solution does not automatically guarantee TPL decomposable via layers. Vias have an inherently low reliability and via failure causes a great yield loss. Double via insertion (DVI) is an effective means to increase yield by reducing via failures. With the restriction of SADP design rules and consideration of TPL decomposability for via layers, DVI becomes a more challenging problem. In this paper, we consider DVI and via layer TPL manufacturability simultaneously in SADP-aware detailed routing. Both spacer-is-metal and spacer-is-dielectric types of SADP are considered. Furthermore, we tackle the TPL-aware DVI in postrouting stage. Both ILP and high-performance heuristic solutions are proposed. The experimental results demonstrate our router can obtain 100% routability and TPL decomposable via layers with reduced dead via count. Meanwhile, compared with the ILP approach to solve TPL-aware DVI problem, the heuristic approach can achieve similar solution quality and significant speedup. [ABSTRACT FROM PUBLISHER]

Nanopore sensors provide an innovative platform for rapid and label-free biomolecule detection. The analytical information extracted from resistive pulse sensing (RPS) measurement, though powerful has several limitations. To address these challenges, various signal conditioning algorithms have been researched which include efficient clustering and classification of data, applying probabilistic models to reduce information overlap and also leveraging transient analysis of ionic current instead of the steady state RPS measurement. Additionally, as the current is typically in few picoampere regime with high transition rates, its faithful measurement requires precision instrumentation like a patch clamp amplifier with low noise and high bandwidth. However, for practical deployment of such systems, it is necessary to develop portable electronic interface. Significant efforts have been directed globally to develop on-chip customized integrated circuits with low noise, high bandwidth amplifiers. Thus, it is absolutely timely and pertinent to conduct a review on the various signal processing schemes and electronic interfaces for single biomolecule identification using nanopores which will enable to comprehend the current status for its deployment as a commercial platform for genomics and ultrasensitive detection. To the best of our knowledge, the data extraction methodologies and electronic interface schemes for nanopores have not yet been summarized. In this paper, a comprehensive review emphasizing the signal processing algorithms for DNA sequencing and protein identification in complex analyte using functionalized and non-functionalized nanopores has been presented along with the on-chip low noise electronic interfaces required for field deployable measurement. [ABSTRACT FROM AUTHOR]

Consider a set $S$ of nodes in the plane such that the unit-disk graph G(S)$ spanning all nodes is connected. Each node in S$ is equipped with a directional antenna with beam-width \theta = \pi / 2$ . The objective of the directional antenna orientation (AO) problem concerning symmetric connectivity is to determine an orientation of the antennas with a minimum transmission power range r=O(1)$ such that the induced symmetric communication graph is connected. Another related problem is the AO and power assignment (AOPA) problem whose objective is to assign each node u \in S is minimized, where $\beta \geq 1$ is the distance-power gradient (typically $2 \leq \beta \leq 5$ ). In this paper, we study both problems by first proving that they are NP-hard. We then propose two algorithms for the AO problem that orient the antennas to yield a symmetric connected communication graph where the transmission power ranges are bounded by 9 and 7, respectively, which are currently the best results for this problem. We also propose constant-factor approximation algorithms for the AOPA problem where our constants are smaller than Aschner et al’s. Finally, we study the performance of our algorithms through simulations. [ABSTRACT FROM PUBLISHER]

QoS routing plays a critical role in providing QoS support in the Internet. Most existing QoS routing algorithms employ the strategy of unidirectional search in route selection. Bidirectional search has been recognized as an effective strategy for fast route acquisition in identifying the shortest path connecting a pair of nodes. However, its efficiency has not been well established in the context of route selection subject to multiple additive constraints, which is in general NP-Complete. In this paper, we study how to employ bidirectional search to support efficient QoS routing subject to multiple additive constraints. The major contributions in this paper are as follows. First, we propose a k shortest path algorithm using bidirectional search, whose complexity is deduced to be O(\sqrtk\vert V \vert\lg (\vert V \vert) + k\vert E\vert), where \vert V \vert and \vert E \vert represent the number of nodes and links in the network, respectively. Second, we show that bidirectional search can significantly accelerate the convergence of several existing QoS routing algorithms. Third, we propose a novel cost-effective bidirectional multi-constrained routing algorithm, which can greatly alleviate the forwarding state scalability issue by supporting stateless QoS routing in IP networks via IP tunneling or constraints-based alternate routing in MPLS networks via label stacks. It has the fastest known on-line running time O(\vert V\vert). Theoretical and simulation results are given to demonstrate the high performance of our proposed algorithm in identifying QoS-satisfied paths and also in efficient resource utilization as compared with existing algorithms. [ABSTRACT FROM PUBLISHER]

We consider a set of transmitter-receiver pairs, or links, that share a wireless medium and address the problem of emptying backlogged queues with given initial size at the transmitters in minimum time. The problem amounts to determining activation subsets of links, and their time durations, to form a minimum-time schedule. Scheduling in wireless networks has been studied under various formulations before. In this paper, we present fundamental insights and solution characterizations that include: 1) showing that the complexity of the problem remains high for any continuous and increasing rate function; 2) formulating and proving sufficient and necessary optimality conditions of two baseline scheduling strategies that correspond to emptying the queues using one-at-a-time or all-at-once strategies; and 3) presenting and proving the tractability of the special case in which the transmission rates are functions only of the cardinality of the link activation sets. These results are independent of physical-layer system specifications and are valid for any form of rate function. We then develop an algorithmic framework for the solution to this problem. The framework encompasses exact as well as sub-optimal, but fast, scheduling algorithms, all under a unified principle design. Through computational experiments, we finally investigate the performance of several specific algorithms from this framework. [ABSTRACT FROM AUTHOR]

Multilayer coating stack-up on an aircraft is a primary defense against corrosion, abrasion, and degradation. The correct coating thickness on an aircraft cannot only provide better protection against environmental impact during flight, but also minimize the reflected electromagnetic signature. Instrumentation to estimate the characteristics of an aircraft's coating stack-up can help to minimize or eliminate the need for coating stripping and reapplying during manufacturing and regular maintenance. This paper investigates the feasibility of using a customized 4 mm penetration depth concentric fringing electric field sensor and a dielectric spectroscopy meter to independently and simultaneously measure the functional coating layer thickness and the coating loading (percentage of silicone with iron oxide filler) on an aircraft. The results show that the sensor capacitance is more sensitive to the variation in coating loading than in coating thickness. Furthermore, this paper demonstrates that the functional coating layer loading and thickness measurement algorithm has been used to successfully estimate the functional coating layer thickness and loading on an aircraft. The currently achievable measurement accuracy for the functional coating layer thickness is ~ 0.1 mm, and the coating loading is ~ 1.5%. [ABSTRACT FROM PUBLISHER]

Temporal event sequence alignment has been used in many domains to visualize nuanced changes and interactions over time. Existing approaches align one or two sentinel events. Overview tasks require examining all alignments of interest using interaction and time or juxtaposition of many visualizations. Furthermore, any event attribute overviews are not closely tied to sequence visualizations. We present Sequence Braiding, a novel overview visualization for temporal event sequences and attributes using a layered directed acyclic network. Sequence Braiding visually aligns many temporal events and attribute groups simultaneously and supports arbitrary ordering, absence, and duplication of events. In a controlled experiment we compare Sequence Braiding and IDMVis on user task completion time, correctness, error, and confidence. Our results provide good evidence that users of Sequence Braiding can understand high-level patterns and trends faster and with similar error. A full version of this paper with all appendices; the evaluation stimuli, data, and analysis code; and source code are available at $\text{osf.io}/\mathrm{mq}2\mathrm{wt}$ . [ABSTRACT FROM AUTHOR]

In this paper we study from an algorithmic perspective the problem of finding the peak value of a bandlimited signal. This problem plays an important role in the design and optimization of communication systems. We show that the peak value problem, i.e., computing the peak value of a bandlimited signal from its samples, can be solved algorithmically if oversampling is used. Without oversampling this is not possible. There exist bandlimited signals, for which the sequence of samples is computable, but the signal itself is not. This problem is directly related to the question whether there is a link between computability in the digital domain and the analog domain, and hence to a fundamental signal processing problem. We show that there is an asymmetry between continuous-time and discrete-time computability. Further, we study the decay behavior of computable bandlimited signals, which describes the concentration of the signals in the time domain, and, for locally computable bandlimited signals, we analyze if it is always possible to decide algorithmically whether the peak value is smaller than a given threshold. [ABSTRACT FROM AUTHOR]

With the proliferation of GPS-enabled smart devices and increased availability of wireless network, spatial crowdsourcing (SC) has been recently proposed as a framework to automatically request workers (i.e., smart device carriers) to perform location-sensitive tasks (e.g., taking scenic photos, reporting events). In this paper, we study a destination-aware task assignment problem that concerns the optimal strategy of assigning each task to proper worker such that the total number of completed tasks can be maximized whilst all workers can reach their destinations before deadlines after performing assigned tasks. Finding the global optimal assignment turns out to be an intractable problem since it does not imply optimal assignment for individual worker. Observing that the task assignment dependency only exists amongst subsets of workers, we utilize tree-decomposition technique to separate workers into independent clusters and develop an efficient depth-first search algorithm with progressive bounds to prune non-promising assignments. In order to make our proposed framework applicable to more scenarios, we further optimize the original framework by proposing strategies to reduce the overall travel cost and allow each task to be assigned to multiple workers. Extensive empirical studies verify that the proposed technique and optimization strategies perform effectively and settle the problem nicely. [ABSTRACT FROM AUTHOR]

The vertical profile of atmospheric CO2 is of great scientific significance in identifying carbon sinks and sources, and estimating CO2 emissions or uptakes. Differential absorption Light Detection And Ranging (DIAL), has been widely accepted as the most promising technique to sense atmospheric CO2. The classical method to retrieve measurements, generated from range-resolved detection, is derived from differentiating the measured column content, but its performance in dealing with aerosol backscatter signals is poor. To address this issue, this paper proposes a derivative method, which is based on Chebyshev fitting to the measured differential absorption optical depth. We created a performance evaluation model to assess the performance of the proposed method. Simulations revealed that the error of a single CO2 profile in data retrieval can be reduced to less than 4 ppm in 6000 m. The precision of long-term mean CO2 profile is expected to be less than 1 ppm. We believe that this novel method can be used in other applications also, e.g., trace gas measurements collected using DIAL, especially when the signal-to-noise-ratio of received signal is small. [ABSTRACT FROM PUBLISHER]

This paper applies a physical inversion approach to retrieve geophysical properties from the single instrumental field-of-view (FOV) spectral radiances measured by the Infrared Atmospheric Sounding Interferometer (IASI) under all-sky conditions. We demonstrate the use of a principal-component-based radiative transfer model (PCRTM) and a physical inversion methodology to simultaneously retrieve cloud radiative and microphysical properties along with atmospheric thermodynamic parameters. By using a fast parameterization scheme, the PCRTM can include the cloud scattering properties simulation in radiative transfer calculations without incurring much more computational cost. The computational speed achieved for a single FOV forward simulation under cloudy skies is similar to that normally achieved for clear skies. The retrieval algorithm introduced herein adopts a novel cloud phase determination scheme, to stabilize and/or constrain retrieval iterations, based on characteristics of the reflectance and transmittance of ice and water clouds. A modified Gaussian-Newton minimization technique is employed in the iterative inversion process in order to overcome a highly nonlinear cost function introduced by the cloud parameters. We carry out a rigorous error analysis for the retrieval of temperature, moisture, ozone (O3), and carbon monoxide (CO) from IASI measurements under cloudy-sky conditions. Our algorithm is applied to real IASI observations. Retrieval results are validated using European Center for Medium-Range Weather Forecasting data and collocated Lidar/Radar measurements, and the dependence of retrieval accuracy on cloud optical depth is illustrated. [ABSTRACT FROM PUBLISHER]

In this paper, we study path planning for first responders in the presence of uncertain moving obstacles. To support the path planning, in our research we use hazard simulation to provide the predicted information of moving obstacles. A major problem in using hazard simulation is that the simulation results may involve uncertainty due to model errors or noise in the real measurements. To address this problem, we provide an approach to handle the uncertainty in the information of moving obstacles, and apply it to the case of toxic plumes. Our contribution consists of two parts: 1) a spatial data model that supports the representation of uncertain obstacles from hazard simulations and their influence on the road network and 2) a modified A* algorithm that can deal with the uncertainty and generate fast and safe routes passing though the obstacles. The experimental results show the routing capability of our approach and its potential for the application to real disasters. [ABSTRACT FROM PUBLISHER]

Given two object sets Q and O, a metric similarity join finds similar object pairs according to a certain criterion. This operation has a wide variety of applications in data cleaning and data mining, to name but a few. However, the rapidly growing volume of data nowadays challenges traditional metric similarity join methods, and thus, a distributed method is required. In this paper, we adopt a popular distributed framework, namely, MapReduce, to support scalable metric similarity joins. To ensure the load balancing, we present two sampling based partition methods. One utilizes the pivot and the space-filling curve mappings to cluster the data into one-dimensional space, and then selects high quality centroids to enable equal-sized partitions. The other uses the KD-tree partitioning technique to equally divide the data after the pivot mapping. To avoid unnecessary object pair evaluation, we propose a framework that maps the two involved object sets in order, where the range-object filtering, the double-pivot filtering, the pivot filtering, and the plane sweeping techniques are utilized for pruning. Extensive experiments with both real and synthetic data sets demonstrate that our solutions outperform significantly existing state-of-the-art competitors. [ABSTRACT FROM AUTHOR]

Knowledge acquisition is an iterative process. Most previous work has focused on bootstrapping techniques based on syntactic patterns, that is, each iteration finds more syntactic patterns for subsequent extraction. However, syntactic bootstrapping is incapable of resolving the inherent ambiguities in the syntactic patterns. The precision of the extracted results is thus often poor. On the other hand, semantic bootstrapping bootstraps directly on knowledge rather than on syntactic patterns, that is, it uses existing knowledge to understand the text and acquire more knowledge. It has been shown that semantic bootstrapping can achieve superb precision while retaining good recall. Nonetheless, the working mechanism of semantic bootstrapping remains elusive. In this paper, we present a detailed analysis of semantic bootstrapping from a theoretical perspective. We show that the efficiency and effectiveness of semantic bootstrapping can be theoretically guaranteed. Our experimental evaluation results substantiate the theoretical analysis. [ABSTRACT FROM PUBLISHER]

The analytical study of grounding systems is only possible for basic electrodes, i.e., hemispherical and spherical electrodes, rods, and horizontal wires. However, it is normal practice to employ more complex earthing systems, such as grounding grids integrated with rods, in order to obtain lower resistances to ground and improve the electrical safety of substations. This paper introduces a semianalytical (or seminumerical) method, consisting of an analytical approach integrated with a numerical solution, to study grounding grids of complex geometry and their effects on non stratified soils. The algorithm that was created and realized with MATLAB allows the determination of all the quantities of interest for the design and the analysis of such grounding systems, i.e., ground resistance, ground potentials, and distribution of the ground-fault current along the grid's components (i.e., horizontal wires and rods). The model is based on the assumption that conductors forming grids have very small radii if compared with their lengths and that the wires can be considered equipotential cylindrical elements. A verification of the proposed algorithm through a finite-element method has been also carried out to confirm the validity of the results. Exemplary calculations of the ground resistance of grids are included in this paper. [ABSTRACT FROM AUTHOR]

Role assignment is a critical task in role-based collaboration. It has three steps, i.e., agent evaluation, group role assignment, and role transfer, where group role assignment is a time-consuming process. This paper clarifies the group role assignment problem (GRAP), describes a general assignment problem (GAP), converts a GRAP to a GAP, proposes an efficient algorithm based on the Kuhn–Munkres (K-M) algorithm, conducts numerical experiments, and analyzes the solutions' performances. The results show that the proposed algorithm significantly improves the algorithm based on exhaustive search. The major contributions of this paper include formally defining the GRAPs, giving a general efficient solution for them, and expanding the application scope of the K-M algorithm. This paper offers an efficient enough solution based on the K-M algorithm that outperforms significantly the exhaustive search approach. [ABSTRACT FROM PUBLISHER]

The problem of data sampling and collection in wireless sensor networks (WSNs) is becoming critical as larger networks are being deployed. Increasing network size poses significant data collection challenges, for what concerns sampling and transmission coordination as well as network lifetime. To tackle these problems, in-network compression techniques without centralized coordination are becoming important solutions to extend lifetime. In this paper, we consider a scenario in which a large WSN, based on ZigBee protocol, is used for monitoring (e.g., building, industry, etc.). We propose a new algorithm for in-network compression aiming at longer network lifetime. Our approach is fully distributed: each node autonomously takes a decision about the compression and forwarding scheme to minimize the number of packets to transmit. Performance is investigated with respect to network size using datasets gathered by a real-life deployment. An enhanced version of the algorithm is also introduced to take into account the energy spent in compression. Experiments demonstrate that the approach helps finding an optimal tradeoff between the energy spent in transmission and data compression. [ABSTRACT FROM PUBLISHER]

This paper presents a new insulator diagnosis algorithm that is applied to the measured voltage and resistance values of an insulator string to detect faulty insulators. Under normal conditions of low pollution and low humidity, the distribution voltages of a sound insulator string show a U-shaped distribution, and its insulation resistances show very high values of above 20 G\Omega. The inspection data measured in the field, however, showed that in high pollution or high humidity environments, the voltage distribution has sawtooth shapes and offsets in comparison with those of other strings, and its insulation resistances are greatly decreased. For these reasons, the commonly used algorithms tend to yield incorrect results under these conditions. In order to solve this problem, we propose a new diagnosis algorithm that can precisely detect faulty insulators from the measured data, regardless of the environmental conditions. We confirmed its effectiveness through live-line field tests in actual power transmission lines. [ABSTRACT FROM PUBLISHER]

In many real applications, graph data is subject to uncertainties due to incompleteness and imprecision of data. Mining such uncertain graph data is semantically different from and computationally more challenging than mining conventional exact graph data. This paper investigates the problem of mining uncertain graph data and especially focuses on mining frequent subgraph patterns on an uncertain graph database. A novel model of uncertain graphs is presented, and the frequent subgraph pattern mining problem is formalized by introducing a new measure, called expected support. This problem is proved to be NP-hard. An approximate mining algorithm is proposed to find a set of approximately frequent subgraph patterns by allowing an error tolerance on expected supports of discovered subgraph patterns. The algorithm uses efficient methods to determine whether a subgraph pattern can be output or not and a new pruning method to reduce the complexity of examining subgraph patterns. Analytical and experimental results show that the algorithm is very efficient, accurate, and scalable for large uncertain graph databases. To the best of our knowledge, this paper is the first one to investigate the problem of mining frequent subgraph patterns from uncertain graph data. [ABSTRACT FROM AUTHOR]

We present a fast bottom-up algorithm to compute all fixpoints of a fuzzy closure operator in a finite set over a finite chain of truth degrees, along with the partial order on the set of all fixpoints. Fuzzy closure operators appear in several areas of fuzzy logic and its applications, including formal concept analysis (FCA) that we use as a reference area of application in this paper. Several problems in FCA, such as computing all formal concepts from data with graded attributes or computing non-redundant bases of all attribute dependencies, can be reduced to the problem of computing fixpoints of particular fuzzy closure operators associated with the input data. The development of a general algorithm that is applicable, in particular, to these problems is the ultimate purpose of this paper. We present the algorithm, its theoretical foundations, and experimental evaluation. [ABSTRACT FROM AUTHOR]

Packet classification is the core mechanism that enables many networking services on the Internet such as firewall packet filltering and traffic accounting. Using ternary content addressable memories (TCAMs) to perform high-speed packet classification has become the de facto standard in industry. TCAMs classify packets in constant time by comparing a packet with all classification rules of ternary encoding in parallel. Despite their high speed, TCAMs suffer from the well-known range expansion problem. As packet classification rules usually have fields specified as ranges, converting such rules to TCAM-compatible rules may result in an explosive increase in the number of rules. This is not a problem if TCAMs have large capacities. Unfortunately, TCAMs have very limited capacity, and more rules mean more power consumption and more heat generation for TCAMs. Even worse, the number of rules in packet classifiers has been increasing rapidly with the growing number of services deployed on the Internet. In this paper, we consider the following problem: given a packet classifier, how can we generate another semantically equivalent packet classifier that requires the least number of TCAM entries? In this paper, we propose a systematic approach, the TCAM Razor, that is effective, efficient, and practical. In terms of effectiveness, TCAM Razor achieves a total compression ratio of 29.0%, which is significantly better than the previously published best result of 54%. In terms of efficiency, our TCAM Razor prototype runs in seconds, even for large packet classifiers. Finally, in terms of practicality, our TCAM Razor approach can be easily deployed as it does not require any modification to existing packet classification systems, unlike many previous range encoding schemes. [ABSTRACT FROM AUTHOR]

Hardware/software (HW/SW) partitioning is one of the key challenges in HW/SW codesign. This paper presents efficient algorithms for the HW/SW partitioning problem, which has been proved to be NP-hard. We reduce the HW/SW partitioning problem to a variation of knapsack problem that is approximately solved by searching 1D solution space, instead of searching 2D solution space in the latest work cited in this paper, to reduce time complexity. Three heuristic algorithms are proposed to determine suitable partitions to satisfy HW/SW partitioning constraints. We have shown that the time complexity for partitioning a graph with n nodes and m edges is significantly reduced from O(dx ⋅ dy ⋅ n³) to O(n log n + d ⋅ (n + m)), where d and dx ⋅ dy are the number of the fragments of the searched 1D solution space and the searched 2D solution space, respectively. The lower bound on the solution quality is also proposed based on the new computing model to show that it is comparable to that reported in the literature. Moreover, empirical results show that the proposed algorithms produce comparable and often better solutions when compared to the latest algorithm while reducing the time complexity significantly. [ABSTRACT FROM AUTHOR]

Light-trail is proposed as a candidate to carry IP traffic over wavelength-division multiplexing optical networks given its capability of enabling high-speed provisioning and accommodating multigranularity traffic. In a light-trail, the optical shutters at the start node and the end node are configured to be in OFF state and the optical shutters at the intermediate nodes are configured to be in ON state. Thus, an optical bus is formed, allowing traffic multiplexing without the state change of any optical shutter. This, however, limits the system throughput and also makes it impossible to implement a fully distributed medium access control (MAC) protocol to assure quality of service (QoS) in a light-trail. With the recent development on ultrafast optical shutter, we propose an improved light-trail architecture, called opportunistic hyperchannel in this paper. In an opportunistic hyperchannel, an intermediate node can dynamically control its optical shutter which makes it possible to design a fully distributed QoS assuring MAC protocol. We then present a QoS assuring distributed dynamic scheduling protocol, namely, minimum source round robin (minSrcRR) protocol, for opportunistic hyperchannels. Theoretical analysis on the effectiveness of the proposed QoS assuring protocol and the worst-case delay bound are also derived in this paper. The simulation results quantitatively demonstrate the advantage of opportunistic hyperchannels and the effectiveness of minSrcRR protocol. [ABSTRACT FROM AUTHOR]