Search

Given a directed graph and a node $v$ , the transitive closure (TC) of $v$ is the set of nodes that $v$ can reach in the graph. TC size is very important in many applications but the cost of TC size computation is high in both time and space, which makes computing accurate TC size not applicable to the scenario where we need to know the TC size quickly for large graphs. Considering that existing approaches are either inefficient or inaccurate, we propose an algorithm, namely buTCS, to efficiently make more accurate estimation. Our approach works in linear time and space. The basic idea is to compute a node’s TC size based on that of its out-neighbors and perform a top-down verification. We further propose two optimizations to improve the estimation accuracy. The experimental results on 13 real datasets show that buTCS achieves better estimation on TC size efficiently.

With the development of society, the demand for energy keeps increasing. Solar energy has received widespread concern for its renewable and environmentally friendly advantages. As one of the most efficient solar energy devices, the output power of photovoltaic (PV) cells is easily affected by the external environment. In order to solve the problem of the maximum power output of PV cells, this paper proposed a maximum power point tracking (MPPT) method. Based on the online particle swarm optimization (PSO) variable step length algorithm, the pulse width modulation (PWM) control module parameters are set according to the parameters of the PV cells’ output voltage. By dynamically adjusting the output voltage step of the PV cells online, the output of the PV cells is stabilized near the maximum power point (MPP). The simulation results concluded that the method and model could accurately adjust the output voltage according to the external environment changes in real time and reduce the voltage fluctuation at the MPP, providing a new idea to solve the problem of MPPT of PV cells.

This paper presents a hybrid Semi-parametric model for nonlinear system fault detection. The proposed hybrid model integrates the analytical model and the group method of data handing-type neural network (GMDH neural network) model. The GMDH neural network model is used to correct the modeling error of the analytical model for system fault diagnosis. There are two improvements to the hybrid semi-parametric model. Firstly, the evaluation criteria of the middle layer neurons are improved to improve the structural stability of the GMDH neural networks, especially the comprehensive evaluation of neurons using root mean square error, maximum absolute error, and network complexity function. Secondly, the reasonable threshold parameter is designed to enhance the robustness of the fault detection. The simulation results on a reaction flywheel of a satellite demonstrate that the proposed model is effective.

This paper investigates the task scheduling and attitude planning of single agile earth observation satellite for intensive tasks. We aim to obtain the execution strategy and corresponding attitude path at the same time by the maximization of the total number of imaged tasks together with minimization of the energy cost, where the rectangle strip observation tasks are considered. Denoting the ground task as a time-varying attitude path, the whole collaborative task scheduling and attitude planning problem is modeled in the attitude apace. To prepare for the final solution, we first design a time-dependent mechanism to determinate the start working time, based on which an energy-dependent mechanism is designed to determine the attitude path corresponding for each possible execution strategy. Using the results produced by the mechanisms to construct the evaluation process, we propose a novel pseudospectral cooperative genetic algorithm (PCGA) to obtain the effective execution strategy and attitude path simultaneously. In PCGA, the genetic algorithm is employed to search the optimal solution, while the pseudospectral procedure and cooperative concept are combined into the genetic algorithm framework to further eliminate the uncertainty and obtain a compromise solution between two objectives, respectively. Simulation results demonstrate the effectiveness of proposed model and algorithm.

Given a directed acyclic graph (DAG), a k-hop reachability query u → ?k is used to answer whether there exists a path from u to v with length ≤ k. Answering k-hop reachability queries is a fundamental graph operation and has been extensively studied during the past years. Considering that existing approaches still suffer from inefficiency in practice when processing large graphs, we propose a novel labeling scheme, namely HT, to accelerate k-hop reachability queries answering. HTuses a constrained 2hop distance label to maintain the length of shortest paths between a set of hop nodes and other nodes, and for the remaining reachability information, HT uses a novel topological level to accelerate graph traversal. Further, we propose to enhance HT by two optimization techniques. The experimental results show that compared with the state-of-the-art approaches, HT works best for most graphs when answering k-hop reachability queries with small index size and reasonable index construction time.

Online deposit-free leasing service has witnessed rapid growth in China and shows a promising market in the future. While eliminating the requirement of a deposit does attract more users to the service, it also lowers the cost for fraudsters. Since the emergence of this service is relatively new, there are few works in literature focusing on detecting fraud transactions in it. Existing efforts mainly fall into hard-coded solutions such as block-listing or scorecard methods, which can be impotent in the face of the diverse fraud tactics, e.g., identity theft, or even suffering concept drift problem as the tactics evolve. In this paper, we contribute Turbo, an efficient graph-based anti-fraud system, to fully exploit the abundant user behavior logs in a real-time manner. Turbo is able to additionally make use of the implicit user relationships beyond the user features in the logs. To capture the user relationships, we first propose a novel algorithm to construct a time-evolving user behavior network called BN. Empirical analysis demonstrates that fraudsters in BN exhibit unique temporal aggregation and homophilic patterns, which inspires us to develop a novel heterogeneous adaptive graph neural network algorithm called HAG. Specifically, in HAG two graph operators are presented to mitigate the over-smoothing problem and make better use of the heterogeneous behavior relations in BN. Extensive experiments on a real-world dataset show that our method outperforms state-of-the-art methods significantly and can give a response in seconds for each detection request.

The battery energy storage system (BESS) has received broad concern with the development of photovoltaic technology. The unknown internal parameters of the battery model in BESS will affect its output, so extract the parameters accurately is essential. In order to extract the parameters of the battery model, an improved JAYA (IJAYA) optimization algorithm is presented. In IJAYA, a self-adaptive weight, an experience-based learning strategy, and a chaotic elite learning method are adopted. The three strategies can increase the probability of obtaining the best solution, enhance the population diversity, and improve the quality of the solution. The 16 A discharging experiment is performed in BESS. The parameters are identified according to the second-order RC equivalent circuit model. The results indicate that the IJAYA algorithm can accurately and effectively extract parameters of the battery model.

Existing Side-Channel Attacks (SCAs) have several limitations and, rather than to be real attack methods, can only be considered to be security evaluation methods. Their limitations are mainly related to the sampling conditions, such as the trigger signal embedded in the source code of the encryption device, and the acquisition device that serves as the encryption-device controller. Apart from it being very difficult for an attacker to add a trigger into the original design before making an attack or to control the encryption device, there is a big gap in the capacity of existing SCAs to pose real threats to cipher devices. In this paper, we propose a new method, the sliding window SCA (SW-SCA), which can be applied in scenarios in which the acquisition device is independent of the encryption device and for which the encryption source code requires no trigger signal or modification. First, we describe the main issues in existing SCAs, then we theoretically analyze the effectiveness and complexity of our proposed SW-SCA -a method that can incorporate a sliding-window mechanism into almost all of the existing non-profiled SCAs. The experimental results for both simulated and physical traces verify the effectiveness of the SW-SCA and the appropriateness of its theoretical complexity.

Answering reachability queries is one of the fundamental graph operations. The existing approaches build indexes and answer reachability queries on a directed acyclic graph (DAG) $$G$$ , which is constructed by coalescing each strongly connected component of the given directed graph $$\mathcal {G}$$ into a node of $$G$$ . Considering that $$G$$ can still be large to be processed efficiently, there are studies to further reduce $$G$$ to a smaller graph. However, these approaches suffer from either inefficiency in answering reachability queries, or cannot scale to large graphs. In this paper, we study DAG reduction to accelerate reachability query processing, which reduces the size of $$G$$ by computing transitive reduction (TR) followed by computing equivalence reduction (ER). For TR, we propose a bottom-up algorithm, namely buTR, which removes from $$G$$ all redundant edges to get the unique smallest DAG $$G^{t}$$ satisfying that $$G^{t}$$ has the same transitive closure as that of $$G$$ . For ER, we propose a divide-and-conquer algorithm, namely linear-ER. Given the result $$G^{t}$$ of TR, linear-ER gets a smaller DAG $$G^{\varepsilon }$$ in linear time based on equivalence relationship between nodes in $$G$$ . Our DAG reduction approaches (TR and ER) significantly improve the cost of time and space and can be scaled to large graphs. Based on the result of DAG reduction, we further propose a graph decomposition-based algorithm to efficiently answer reachability queries. We confirm the efficiency of our approaches by extensive experimental studies for TR, ER, and reachability query processing using 20 real datasets. The complete source code is available for download at https://pan.baidu.com/s/1skHBXXN .

Nowadays, the manufacturing industries are continuously challenged by achieving high-quality products and clean production in order to remain competitiveness. Surface roughness is one of the important factors in evaluation of the quality of a machined part. Meanwhile, it is vital to correlate energy usage with operations being performed in the production lines for the green and energy-saving manufacturing. A novel surface roughness prediction model based on the energy consumption is proposed. Specific cutting energy consumption (SCEC) and cutting parameters are employed as inputs to the prediction model. Particle swarm optimization-support vector machine (PSO-SVM) is used to predict the surface roughness value in turning. Furthermore, this method is verified by conducting experiments in turning process and compared with the PSO-relevance vector machine (PSO-RVM). Besides, the prediction performance of the energy based model is compared with the model with different combinations of cutting parameters, energy, and vibration features. The result shows that the proposed model obtains the lowest mean relative error and indicates that the model is effective and straightforward for practical implementation.

Energy saving and surface quality are priorities in manufacturing industry with increased sustainability and high-quality consciousness. This paper presents a cooperative optimization approach to choose optimal cutting parameters for energy saving and quality assurance considering the effects of tool wear and cutting parameter combinations at a certain material removal rate. Cutting energy consumption, energy efficiency and surface roughness are optimization objectives and their functions are developed with cutting parameters and tool wear. The multi-objective optimization model is constructed with constraints and solved by NSGA-III. A turning application case is given and the results illustrate the effectiveness of the proposed method.

the rapid development of distributed generation technology has brought a large number of uncertain factors to the power grid. The research of probability distribution model of these uncertain factors has great significance to the planning and operation of the power grid. Taking the uncertainty problem in wind farm as an example, a non-parametric kernel density estimation method for wind power probability density model based on fuzzy ordinal optimization is proposed in this paper. Based on the historical data sample of wind power operation, a non-parametric kernel density estimation model of wind power probability density is established in the method, and then a multi-objective optimization model of bandwidth selection is also constructed. Finally, the fuzzy ordinal optimization is used to solve the bandwidth optimization model. The result of practical examples show that the method is completely driven by the sample data and has no need to perform a priori subjective assumption on the probability density model as in the traditional way. Therefore, it has higher modeling accuracy and stronger applicable ability.

This paper studies the orbital pursuit-evasion-defense problem with the continuous low thrust propulsion. A control strategy for the pursuer is proposed based on the fuzzy comprehensive evaluation and the differential game. First, the system is described by the Lawden&rsquo, s equations, and simplified by introducing the relative state variables and the zero effort miss (ZEM) variables. Then, the objective function of the pursuer is designed based on the fuzzy comprehensive evaluation, and the analytical necessary conditions for the optimal control strategy are presented. Finally, a hybrid method combining the multi-objective genetic algorithm and the multiple shooting method is proposed to obtain the solution of the orbital pursuit-evasion-defense problem. The simulation results show that the proposed control strategy can handle the orbital pursuit-evasion-defense problem effectively.

It is challenging to estimate wind speed of tropical cyclones directly using remote sensing image patterns. This paper approaches the task in two major steps: cyclone category estimation and wind speed regression. A novel framework based on Tensor Convolutional Neural Network (Tensor CNN) is proposed to solve the problem. Not only does the framework combine Tensor analysis for dimensionality reduction and deep neural networks for pattern recognition, the Tensor CNN also provides a unitary and concise mathematical representation form of the two significant models. The proposed framework is able to categorize cyclones by classification based on the Tensor CNN as well as exploit the estimated categories and predict the wind speed by a successive regression model. Experiments are conducted on multispectral imagery acquired by the FY-4 Satellite. Results show that the framework outperforms several classic models in cyclone category estimation and one state-of-the-art method, Deviation Angle Variance Technique (DAVT), in wind speed regression.

Robots are usually equipped with microphones and cameras to perceive and understand the physical world. Though visual object detection technology has achieved great success, the detection in other modalities remains unsolved. In this paper, we establish a novel robotic sound-indicated visual object detection framework, and develop a two-stream weakly-supervised deep learning architecture to connect the visual and audio modalities for localizing the sounding object. A dataset is constructed from the AudioSet to validate the proposed method and some promising applications are demonstrated on robotic platforms.

In this study, the authors study a deep learning model that can convert vision into tactile information, so that different texture images can be fed back to the tactile signal close to the real tactile sensation after training and learning. This study focuses on the classification of different image visual information and its corresponding tactile feedback output mode. A training model of ensembled generative adversarial networks is proposed, which has the characteristics of simple training and stable efficiency of the result. At the same time, compared with the previous methods of judging the tactile output, in addition to subjective human perception, this study also provides an objective and quantitative evaluation system to verify the performance of the model. The experimental results show that the learning model can transform the visual information of the image into the tactile information, which is close to the real tactile sensation, and also verify the scientificity of the tactile evaluation method.

A major aim of separating sound source is to separate the sound of interest out of mixture, such as the sound of objects on the screen. In this paper we put forward a method incorporating sound-indicated object detection and using the detection result to separate the on screen sounds and the off screen ones. After training, the object detection network could recognize which object is sounding just like human learns what object making what sound. And then using the temporal information of sounds in a video segment, we separate out sound of the object that is not shown in the video. At last, experiments are carried out in data from AudioSet and we demonstrate that the method works well in given scenarios.

This paper studies the orbital pursuit-evasion problem with imperfect information, including measurement noise and input delay. The presence of imperfect information will degrade the players’ control performance and lead to mission failure. To solve this problem, a compensation control strategy for the players is proposed. The compensation control strategy consists of two parts: the guaranteed cost strategy and the time delay compensation method. First, a near-optimal feedback strategy called guaranteed cost strategy with perfect information is proposed based on a Lyapunov-like function and matrix analysis theory. Second, a time delay compensation method based on an uncertainty set is proposed to compensate for delayed information. The compensation control strategy is derived by combining the time delay compensation method with the guaranteed cost strategy. While applying this strategy to the game, the input of the strategy is generated by processing the measured data with the state estimation algorithm based on the unscented Kalman filter (UKF). The simulation results show that the proposed strategy can handle the orbital pursuit-evasion problem with imperfect information effectively.

Answering reachability queries is a fundamental graph operation. Considering that the size of the input graph has a great impact on query performance, there are studies focusing on reducing the graph size, such that queries can be answered over a smaller graph. Although the input graph can be compressed significantly by existing approaches, a good compression ratio does not always mean a positive effect on query performance. In this paper, we study graph reduction to accelerate reachability queries answering. We propose a novel graph reduction approach, namely RCN reduction, to compress the input graph into a smaller one. Let a be the compression ratio of the number of nodes in the reduced graph over that of the input graph, we show that based on our approach, the lower bound probability that a query q can be answered in constant time is 1-a^2. We show the difficulties of RCN reduction and propose efficient algorithms to improve the compression ratio. Based on the result of RCN reduction, we further propose a novel labeling scheme to accelerate queries answering. We confirm the efficiency of our approach by extensive experimental results for graph reduction and reachability queries processing using 20 real datasets.

Efficiently answering XML keyword queries has attracted much research effort in the last decade. The key factors resulting in the inefficiency of existing methods are the common-ancestor-repetition (CAR) and visiting-useless-nodes (VUN) problems. To address the CAR problem, we propose a generic top-down processing strategy to answer a given keyword query w.r.t. LCA/SLCA/ELCA semantics. By “ top-down ”, we mean that we visit all common ancestor (CA) nodes in a depth-first, left-to-right order; by “ generic ”, we mean that our method is independent of the query semantics. To address the VUN problem, we propose to use child nodes, rather than descendant nodes to test the satisfiability of a node $v$ w.r.t. the given semantics. We propose two algorithms that are based on either traditional inverted lists or our newly proposed LLists to improve the overall performance. We further propose several algorithms that are based on hash search to simplify the operation of finding CA nodes from all involved LLists. The experimental results verify the benefits of our methods according to various evaluation metrics.

With the continuous improvement of the level of economic development and the increasingly serious environmental problems, countries around the world are focusing more on renewable energy. Wind energy is an important category of renewable energy because of its advantages. However, wind power is very dependent on the climate environment. It operates in an open operating environment, and its communication depends on the network interaction method. With the proposal of the Internet of Everything, the power grid is developing in the direction of information and intelligence. There are more and more attacks, and the security and stability of wind power interface devices have been threatened. As the power grid involves many areas and households, once the power outage occurs, the economic losses will be huge and even cause major security accidents. This paper proposes a deep belief network research of wind power control management unit based on attack recognition to improve the safety and operational reliability of wind power generation.

High energy efficiency has become a critical requirement of companies. An effective energy consumption assessment model for machine tool is presented based on the Extended Stochastic Petri Nets and the analysis approach is also proposed using behavior expression. The energy consumption states and machine tool modes are unified the places of model, and the change information of energy is added to the transitions of model. An actual example, a turn machine tool production processes is addressed and the power and cycle time indicators are discussed.

Tropical cyclone (TC) intensity estimation is vital to disastrous weather forecasting. In this paper, the task is approached as a classification problem, regarding the cyclone intensity levels as the class labels. Multispectral Imagery (MSI) captured by a recently launched satellite, No. 4 meteorological satellite (FY-4) of China, is used as the raw data for classification. To solve the problem, this paper proposes a machine learning framework with three major parts: useable band determination, band-wise classification and fusion. The framework is compatible with arbitrary classifiers for the band-wise classification. Since some band images acquired during night hours contain little useful information, a selector is designed and placed before each band classifier. Moreover, majority voting, a very efficient method, is employed to fuse the band-wise classification results. Experiments demonstrate that Multiple Logistic Regression (MLR), Support Vector Machine (SVM) and Back-Propagation Neural Network (BPNN), each in turn used as the band-wise classifiers, can yield high accuracy in labelling the TC intensity. The results also show the usefulness of the FY-4 data and the potentials of machine learning for automatic and accurate TC intensity estimation.

In this paper, we focus on efficient construction of restricted subtree (RSubtree) results for XML keyword queries on amulticore system. We firstly show that the performance bottlenecks for existing methods lie in 1) computing the set of relevant keyword nodes (RKNs) for each subtree root node, 2) constructing the corresponding RSubtree, and 3) parallel execution. We then propose a two-step generic top-down subtree construction algorithm, which computes SLCA/ELCA nodes in the first step, and parallelly gets RKNs and generates RSubtree results in the second step, where genericmeans that 1) our method can be used to compute different kinds of subtree results, 2) our method is independent of the query semantics; top-down means that our method constructs each RSubtree by visiting nodes of the subtree constructed based on an RKN set level-by-level from left to right, such that to avoid visiting as many useless nodes as possible. The experimental results show that our method is much more efficient than existing ones according to various metrics.

© 2017 ACM. Answering reachability queries is one of the fundamental graph operations. The existing approaches build indexes and answer reachability queries on a directed acyclic graph (DAG) G, which is constructed by coalescing each strongly connected component of the given directed graph G into a node of G. Considering that G can still be large to be processed efficiently, there are studies to further reduceGto a smaller graph. However, these approaches suffer from either inefficiency in answering reachability queries, or cannot scale to large graphs. In this paper, we study DAG reduction to accelerate reachability query processing, which reduces the size of G by computing transitive reduction (TR) followed by computing equivalence reduction (ER). For TR, we propose a bottom-up algorithm, namely buTR, which removes from G all redundant edges to get the unique smallest DAG Gt satisfying that Gt has the same transitive closure as that of G. For ER, we propose a divide-and-conquer algorithm, namely linear-ER. Given the result Gt of TR, linear-ER gets a smaller DAG Gϵ in linear time based on equivalence relationship between nodes in G. Our DAG reduction approaches (TR and ER) significantly improve the cost of time and space, and can be scaled to large graphs. We confirm the efficiency of our approaches by extensive experimental studies for TR, ER, and reachability query processing using 20 real datasets.

Keyword search over XML data has attracted a lot of research efforts in the last decade, where one of the fundamental research problems is how to efficiently answer a given keyword query w.r.t. a certain query semantics. We found that the key factor resulting in the inefficiency for existing methods is that they all heavily suffer from the common-ancestor-repetition problem. In this paper, we propose a novel form of inverted list, namely the IDList; the IDList for keyword $$k$$ consists of ordered nodes that directly or indirectly contain $$k$$ . We then show that finding keyword query results based on the smallest lowest common ancestor and exclusive lowest common ancestor semantics can be reduced to ordered set intersection problem, which has been heavily optimized due to its application in areas such as information retrieval and database systems. We propose several algorithms that exploit set intersection in different directions and with or without using additional indexes. We further propose several algorithms that are based on hash search to simplify the operation of finding common nodes from all involved IDLists. We have conducted an extensive set of experiments using many state-of-the-art algorithms and several large-scale datasets. The results demonstrate that our proposed methods outperform existing methods by up to two orders of magnitude in many cases.

In this paper, we focus on efficient processing of XML keyword queries based on smallest lowest common ancestor (SLCA) semantics. For a given query Q with m keywords, we propose to use stable matches as the basis for SLCA computation, where each stable match M consists of m nodes that belong to the m distinct keyword inverted lists of Q. M satisfies that no other lowest common ancestor (LCA) node of Q can be found to be located after the first node of M and be a descendant of the LCA of M, based on which the operation of locating a stable match can skip more useless nodes. We propose two stable match based algorithms for SLCA computation, i.e., BSLCA and HSLCA. BSLCA processes two keyword inverted lists each time from the shortest to the longest, while HSLCA processes all keyword inverted lists in a holistic way to avoid the problem of redundant computation invoked by BSLCA. Our extensive experimental results verify the performance advantages of our methods according to various evaluation metrics.

In this paper, we focus on efficient construction of tightest matched subtree (TMSubtree) results, for keyword queries on extensible markup language (XML) data, based on smallest lowest common ancestor (SLCA) semantics. Here, "matched" means that all nodes in a returned subtree satisfy the constraint that the set of distinct keywords of the subtree rooted at each node is not subsumed by that of any of its sibling nodes, while "tightest" means that no two subtrees rooted at two sibling nodes can contain the same set of keywords. Assume that d is the depth of a given TMSubtree, m is the number of keywords of a given query Q. We proved that if d ≤ m, a matched subtree result has at most 2m! nodes; otherwise, the size of a matched subtree result is bounded by (d - m + 2)m!. Based on this theoretical result, we propose a pipelined algorithm to construct TMSubtree results without rescanning all node labels. Experiments verify the benefits of our algorithm in aiding keyword search over XML data.

We investigate the limitations of existing XML search methods and propose a new semantics, related relationship, to effectively capture meaningful relationships of data elements from XML data in the absence of structural constraints. Then we make an extension to XPath by introducing a new axis, related axis, to specify the related relationship between query nodes so as to enhance the flexibility of XPath. We propose to reduce the cost of computing the related relationship by a new schema summary that summarizes the related relationship from the original schema without any loss. Based on this schema summary, we introduce two indices to improve the performance of query processing. Our algorithm shows that the evaluation of most queries can be equivalently transformed into just a few selection and value join operations, thus avoids the costly structural join operations. The experimental results show that our method is effective and efficient in terms of comparing the effectiveness of the related relationship with existing keyword search semantics and comparing the efficiency of our evaluation methods with existing query engines.

As huge volumes of data are organized or exported in tree-structured form, it is quite necessary to extract useful information from these data collections using effective and efficient query processing methods. A natural way of retrieving desired information from XML documents is using twig pattern (TP), which is, actually, the core component of existing XML query languages. Twig pattern possesses the inherent feature that query nodes on the same path have concrete precedence relationships. It is this feature that makes it infeasible in many actual scenarios. This has driven the requirement of relaxing the complete specification of a twig pattern to express more flexible semantic constraints in a single query expression. In this paper, we focus on query evaluation of partially specified twig pattern (PSTP) queries, through which we can reap the most flexibility of specifying partial semantic constraints in a query expression. We propose an extension to XPath through introducing two Samepath axes to support partial semantic constraints in a concise but effective way. Then we propose a stack based algorithm, pTwigStack, to process a PSTP holistically without deriving the concrete twig patterns and then processing them one by one. Further, we propose two DTD schema based optimization methods to improve the performance of pTwigStack algorithm. Our experimental results on various datasets indicate that our method performs significantly better than existing ones when processing PSTPs.

XML has been used extensively in many applications as a de facto standard for information representation and exchange over internet. Huge volumes of data are organized or exported in tree-structured form and the desired information can be got by traversing the whole tree structure using a twig pattern query. A new definition, Extended Solution Extension, is proposed in this paper to check the usefulness of an element from both forward and backward directions. Then a novel Extended Solution Extension based algorithm, TwigStack+, is also proposed to reduce the query processing cost, simply because it can check whether other elements can be processed together with the current one. Compared with existing methods, query evaluation cost can be largely reduced. The experimental results on various datasets indicate that the proposed algorithm performs significantly better than the existing ones.

Numerous mobility solutions have been proposed in the past, but none of them have been widely deployed today. To address the deployment difficulty in previous work, we propose an end-system-based mobility solution for IPv6 (EMIPv6). In our design, we adhere to the end-to-end principle (Saltzer et al., 1984) by directly performing connection maintenance and data packet delivery between the two communicating hosts. And we leverage distributed hash table-based peer-to-peer (P2P) systems to carry out self-organized, scalable, and robust name lookup for mobile hosts. When the mobility messages such as address updates cannot be delivered directly between the end hosts (e.g., due to firewalls, network address translators, or simultaneous movement), we propose a distributed subscription/notification (S/N) service on top of the previously introduced P2P overlay to deliver them. This leads to a complete end-system solution with small handoff latency and efficient packet delivery. Our simulation results showed that our scheme achieves small name resolution latency by considering host heterogeneity into the design. We have implemented EMIPv6-based end-systems. The experiments in our testbed demonstrated that a complete end-system-based mobility solution is technically feasible and is easy to deploy in the real world without the need of introducing new network components.

Traditional software architecture models, such as: Object-oriented, Service-oriented, Agent-oriented, have been confronting the challenges in more and more complex distributed computing situations, e.g. pervasive computing, Internet of things, smart-city, etc. Organization-oriented architecture model is proposed to attempt to improve the abstraction and design capability of software architecture in the pervasive computing environment, and then enhance the efficiency of architecture model reuse. The description language of organization-oriented architecture is based on the WRIGHT * and CSP.

In this paper, we focus on efficient constructing of matched subtree (MSubtree) results for keyword queries on XML data. We firstly show that the performance bottlenecks for existing methods lie in (1) computing the set of relevant keyword nodes (RKNs) for each subtree root node, (2) constructing the corresponding MSubtrees, and (3) parallel execution. We then propose a two-step generic top-down subtree construction algorithm, which computes SLCA/ELCA nodes in the first step, and parallelly gets RKNs and generates MSubtree results in the second step, where generic means that (1) our method can be used to compute different kinds of subtree results, (2) our method is independent of the query semantics; top-down means that our method constructs each MSubtree by visiting nodes of the subtree constructed based on an RKN set level-by-level from left to right, such that to avoid visiting as many useless nodes as possible.

Recently, XML keyword search has attracted much attention and has become a popular paradigm for information retrieval over XML data. Because of its convenience, users don't need to know a complex query language or the underlying data schema. However, due to the inherent ambiguity, a keyword query usually corresponds to a large number of results that may be classified into different types, or different search intentions, among which only a few meet users' search intentions.

In this paper, we focus on efficient keyword query processing for XML data based on the SLCA and ELCA semantics. We propose a novel form of inverted lists for keywords which include IDs of nodes that directly or indirectly contain a given keyword. We propose a family of efficient algorithms that are based on the set intersection operation for both semantics. We show that the problem of SLCA/ELCA computation becomes finding a set of nodes that appear in all involved inverted lists and satisfy certain conditions. We also propose several optimization techniques to further improve the query processing performance. We have conducted extensive experiments with many alternative methods. The results demonstrate that our proposed methods outperform previous methods by up to two orders of magnitude in many cases.

In this paper, we focus on efficient processing of a given XML keyword query based on SLCA semantics. We assign to each node an ID that equals to its visiting order when traversing the XML document in deep-first order, based on which we construct two kinds of indexes. The first index is an inverted list L of IDDewey labels for each keyword k, where each IDDewey label l ∈ L represents a node v that directly contains k, l consists of node IDs corresponding to all nodes on the path from the document root to v. The second index is a hash table, which records, for each pair of node v and keyword k, the number of occurrence of k in the subtree rooted at v. Based on the two indexes, we propose an algorithm, namely TDHS, that takes the shortest inverted IDDewey label list as the working list and computes all SLCA results in a top-down manner based on hash search. Compared with existing methods, our method achieves the worst case time complexity of \(O(m\cdot|L^{ID}_1|)\) for a given keyword query Q, where \(|L^{ID}_1|\) is the number of distinct node IDs in the shortest inverted IDDewey label list of Q. Our experimental results verify the performance advantages of our method according to various evaluation metrics.

In this paper, we focus on efficient construction of tightest matched subtree (TMSubtree) results for keyword queries on XML data based on SLCA semantics, where "matched" means that all nodes in a returned subtree satisfy the constraint that the set of distinct keywords of the subtree rooted at each node is not subsumed by that of any of its sibling node, while "tightest" means that no two subtrees rooted at two sibling nodes can contain the same set of keywords. Assume that d is the depth of a given TMSubtree, m is the number of keywords of a given query Q, we proved that if d≤m, a matched subtree result has at most 2m! nodes; otherwise, the size of a matched subtree result is bounded by (d−m+2)m!. Based on this theoretical result, we propose a pipelined algorithm to construct TMSubtree results without rescanning all node labels. Experiments verify the benefits of our algorithm in aiding keyword search over XML data.

In this paper, we focus on efficient processing of a given XML keyword query based on SLCA semantics. We propose an efficient algorithm that processes all nodes in the set of inverted Dewey label lists in a top-down way. Specifically, our method recursively divides the set of initial Dewey label lists into a set of minimum nontrivial blocks (MNBlocks), where a block consists of a set of Dewey label lists and corresponds to an XML tree. The "minimum" means that for a given block, none of its sub-blocks corresponds to a subtree that contains all keywords of the given query; the "nontrivial" means that no block can contain an empty list. Based on these MNBlocks, our method produces all qualified results by directly outputting the LCA node of all nodes in each MNBlock as a qualified SLCA node. During processing, our method can intelligently prune useless keyword nodes according to the distribution of all nodes in a given block. Our experimental results verify the performance advantages of our method according to various evaluation metrics.

We investigated the problem of finding from a collection of strings those similar to a given query string based on edit distance, for which the critical operation is merging inverted lists of grams generated from the collection of strings. We present an efficient algorithm to accelerate the merging operation.

Keyword search is a user-friendly way to query XML data,such that users do not need to understand the complex syntax of structured query languages and the complex structural information of the underlying XML data.However,existing semantics suffer from limited expressiveness, thus users cannot obtain desired information in many cases.We propose an entity-based semantics,namely ELCEA,to capture users'search intension by supporting additionally the semantics of "NOT".We verified the effectiveness of ELCEA by conducting rich experiment according to different metrics.

We investigate the expressiveness of existing XML keyword search semantics and propose Meaningful Connected Network (MCN) as a new semantics to capture meaningful relationships of the given keywords from XML documents. Our evaluation method adopts a two-step strategy to compute all MCNs. In the first step, we identify a set of query patterns from a new schema summary; in the second step, all query patterns are processed based on two efficient indices, partial path index and entity path index. The experimental results show that our method is both effective and efficient.