11690157
Graph and Topological Structure Mining on Scientific Articles
In this paper, we investigate a new approach for literature mining. We use frequent subgraph mining, and its generalization topological structure mining, for finding interesting relationships between gene names and other key biological terms from the text of scientific articles. We show how we can find keywords of interest and represent them as nodes of the graphs. We also propose several methods for inserting edges between these nodes. Our study initially focused on comparing: 1) different methods for constructing edges, and 2) patterns found from sub-graph mining and topological structure mining. Subsequently, we analyzed several frequent topological minors reported by our experiments, and explained their scientific significance. Overall, our study shows the following. First, a simple method of constructing edges, which is based on sliding windows, seems to provide the best results. Second, we are able to find much larger number of well-known and meaningful topological patterns with high support values, as compared to sub-graphs. Overall, the frequent topological minors our algorithm found correspond well to known relationships between genes and biological terms. Thus, we believe that topological structure mining can be a very valuable tool for researchers who are not deeply familiar with the existing literature, and want to obtain a quick summary about known relationships among key scientific names or terms.
18844092
Extracting Output Metadata from Scientific Deep Web Data Sources
Increasingly, many data sources appear as online databases, hidden behind query forms, thus forming the deep web. The popularity of this new medium for data dissemination is leading to new problems in data integration. Particularly, to enable data integration from multiple deep web data sources, one needs to obtain the metadata for each of the data sources. Obtaining the metadata, particularly, the output schema, can be very challenging. This is because, given an input query, many deep web data sources only return a subset of the output schema attributes, i.e, the ones that have a non-NULL value for the corresponding input. In this paper, we propose two approaches, which are the sampling model approach and the mixture model approach, respectively, to efficiently obtain an approximately complete set of output schema attributes from a deep web data source. Our experiments show while each of the above two approaches has limitations, a hybrid strategy, where we combine the two approaches, achieves high recall with good precision for most data sources.
19880347
Personality Based Latent Friendship Mining
Methods and apparatus for detecting imperfections in adhesive coatings formed on fingers of beams are disclosed. The present invention relates, in one aspect, to a method for preparing a first work piece for joining with a second work piece. The method involves forming a finger in the first work piece, then applying an adhesive coating on the finger. A determination is made to determine whether the adhesive coating is defective through the used of a sensing mechanism which is arranged to scan across a portion of the finger. In one embodiment, a defect in the adhesive coating on the finger is defined as a void.
15473023
Query Planning for Searching Inter-dependent Deep-Web Databases
Increasingly, many data sources appear as online databases, hidden behind query forms, thus forming what is referred to as the deep web. It is desirable to have systems that can provide a high-level and simple interface for users to query such data sources, and can automate data retrieval from the deep web. However, such systems need to address the following challenges. First, in most cases, no single database can provide all desired data, and therefore, multiple different databases need to be queried for a given user query. Second, due to the dependencies present between the deep-web databases, certain databases must be queried before others. Third, some database may not be available at certain times because of network or hardware problems, and therefore, the query planning should be capable of dealing with unavailable databases and generating alternative plans when the optimal one is not feasible. 
 
This paper considers query planning in the context of a deep-web integration system. We have developed a dynamic query planner to generate an efficient query order based on the database dependencies. Our query planner is able to select the topKquery plans. We also develop cost models suitable for query planning for deep web mining. Our implementation and evaluation has been made in the context of a bioinformatics system, SNPMiner. We have compared our algorithm with a naive algorithm and the optimal algorithm. We show that for the 30 queries we used, our algorithm outperformed the naive algorithm and obtained very similar results as the optimal algorithm. Our experiments also show the scalability of our system with respect to the number of data sources involved and the number of query terms.
9156262
SEEDEEP: A System for Exploring and Querying Scientific Deep Web Data Sources
A recent and emerging trend in scientific data dissemination involves online databases that are hidden behind query forms, thus forming what is referred to as the deep web . In this paper, we propose SEEDEEP, a System for Exploring and quErying scientific DEEP web data sources. SEEDEEP is able to automatically mine deep web data source schemas, integrate heterogeneous data sources, answer cross-source keyword queries, and incorporates features like caching and fault-tolerance. Currently, SEEDEEP integrates 16 deep web data sources in the biological domain. We demonstrate how an integrated model for correlated deep web data sources is constructed, how a complex cross-source keyword query is answered efficiently and correctly, and how important performance issues are addressed.
6932857
SNPMiner: A Domain-Specific Deep Web Mining Tool
In this paper, we propose a novel query-oriented, mediator-based biological data querying tool, SNPMiner. The system searches and queries single nucleotide polymorphisms (SNPs) data from eight widely used web accessible databases. The system provides a domain-specific search utility, which can access and collect data from the deep web. This is a web-based system, so any user can use the system by accessing our server from their own computers. The system includes three important components, which are the Web server interface, the dynamic query planner, and the Web page parser. The Web server interface can provide end users a unified and friendly interface. The dynamic query planner can automatically schedule an efficient query order on all available databases according to user's query request. The Web page parser analyzes the layout of HTML files and extracts desired data from those files. The final results of the query are organized in a tabular format, which can be reviewed by a biological researcher.
28610096
A New Neighborhood Based on Improvement Graph for Robust Graph Coloring Problem
In this paper, we propose a new neighborhood structure based on the improvement graph for solving the Robust Graph Coloring Problem, an interesting extension of classical graph coloring Different from the traditional neighborhood where the color of only one vertex is modified, the new neighborhood involves several vertices In addition, the questions of how to select the modified vertices and how to modify them are modelled by an improvement graph and solved by a Dynamic Programming method The experimental results clearly show that our new improvement graph based k-exchange cycle neighborhood improves the accuracy significantly, especially for large scale heuristic search.
327315
A Survey on Vehicle Routing Problem with Loading Constraints
In the classical Vehicle Routing Problem (VRP), a fleet of vehicles is available to serve a set of customers with known demand. Each customer is visited by exactly one vehicle as well as the objective is to minimize the total distance or the total charge incurred. Recent years have seen increased attention on VRP integrated with additional loading constraints, known as 2L-CVRP or 3L-CVRP. In this paper we present a survey of the state-of-the-art on 2L-CVRP/3L-CVRP.
27183053
Improved GRASP with Tabu Search for Vehicle Routing with Both Time Window and Limited Number of Vehicles
8682866
Soft Error Rates with Inertial and Logical Masking
We analyze the neutron induced soft error rate (SER). An induced error pulse is modeled by two parameters, probability of occurrence and probability density function of the pulse width. We calculate failures in time (FIT) rates for ISCAS85 benchmark circuits. A comparison with measured SER for SRAMs shows better relevance of our work over other published work. Our CPU times are reasonable; benchmark circuit C1908 with 880 gates requires only 1.14seconds. Further, we study the influence of circuit topology on SER. We find that for some circuits with many levels of logic there exists a critical single event transient (SET) width. For smaller induced pulse width the SER depends not on the size of the circuit but only on the gates near the output, and only those need to be protected. For an inverter chain in TMSC035 technology, the critical width is between 25ps and 50ps. For a shallow circuit, e.g., a ripple-carry adder, the critical SET width may not exist.
20112388
The shortest route cut and fill problem in linear topological structure
In this paper, we study the Shortest Route Cut and Fill (SRCF) problem where a fleet of vehicles with fixed capacities travel between cut and fill points to finish all cut and fill requirements so that the travel time of the fleet is minimized. We state and classify the SRCF problem and present a complete view of its computational complexities with NP-hardness proof for the basic linear topological structure. Moreover, a simple cycle-based optimization method is proposed to solve the SRCF in linear time complexity, for the version of single vehicle in linear structure without time window constraint.