Top-K Query Processing in Edge-Labeled Graph Data

Edge-labeled graphs have proliferated rapidly over the last decade due to the increased popularity of social networks and the Semantic Web. In social networks, relationships between people are represented by edges and each edge is labeled with a semantic annotation. Hence, a huge single graph can express many different relationships between entities. The Semantic Web represents each single fragment of knowledge as a triple (subject, predicate, object), which is conceptually identical to an edge from subject to object labeled with predicates. A set of triples constitutes an edge-labeled graph on which knowledge inference is performed. Subgraph matching has been extensively used as a query language for patterns in the context of edge-labeled graphs. For example, in social networks, users can specify a subgraph matching query to find all people that have certain neighborhood relationships. Heavily used fragments of the SPARQL query language for the Semantic Web and graph queries of other graph DBMS can also be viewed as subgraph matching over large graphs. Though subgraph matching has been extensively studied as a query paradigm in the Semantic Web and in social networks, a user can get a large number of answers in response to a query. These answers can be shown to the user in accordance with an importance ranking. In this thesis proposal, we present four different scoring models along with scalable algorithms to find the top-k answers via a suite of intelligent pruning techniques. The suggested models consist of a practically important subset of the SPARQL query language augmented with some additional useful features. The first model called Substitution Importance Query (SIQ) identifies the top-k answers whose scores are calculated from matched vertices' properties in each answer in accordance with a user-specified notion of importance. The second model called Vertex Importance Query (VIQ) identifies important vertices in accordance with a user-defined scoring method that builds on top of various subgraphs articulated by the user. Approximate Importance Query (AIQ), our third model, allows partial and inexact matchings and returns top-k of them with a user-specified approximation terms and scoring functions. In the fourth model called Probabilistic Importance Query (PIQ), a query consists of several sub-blocks: one mandatory block that must be mapped and other blocks that can be opportunistically mapped. The probability is calculated from various aspects of answers such as the number of mapped blocks, vertices' properties in each block and so on and the most top-k probable answers are returned. An important distinguishing feature of our work is that we allow the user a huge amount of freedom in specifying: (i) what pattern and approximation he considers important, (ii) how to score answers - irrespective of whether they are vertices or substitution, and (iii) how to combine and aggregate scores generated by multiple patterns and/or multiple substitutions. Because so much power is given to the user, indexing is more challenging than in situations where additional restrictions are imposed on the queries the user can ask. The proposed algorithms for the first model can also be used for answering SPARQL queries with ORDER BY and LIMIT, and the method for the second model also works for SPARQL queries with GROUP BY, ORDER BY and LIMIT. We test our algorithms on multiple real-world graph databases, showing that our algorithms are far more efficient than popular triple stores.

MANIPULATION OF IONS, ELECTRONS, AND PHOTONS IN 2D MATERIALS BY ION INTERCALATION

2D materials have attracted tremendous attention due to their unique physical and chemical properties since the discovery of graphene. Despite these intrinsic properties, various modification methods have been applied to 2D materials that yield even more exciting results. Among all modification methods, the intercalation of 2D materials provides the highest possible doping and/or phase change to the pristine 2D materials. This doping effect highly modifies 2D materials, with extraordinary electrical transport as well as optical, thermal, magnetic, and catalytic properties, which are advantageous for optoelectronics, superconductors, thermoelectronics, catalysis and energy storage applications. To study the property changes of 2D materials, we designed and built a planar nanobattery that allows electrochemical ion intercalation in 2D materials. More importantly, this planar nanobattery enables characterization of electrical, optical and structural properties of 2D materials in situ and real time upon ion intercalation. With this device, we successfully intercalated Li-ions into few layer graphene (FLG) and ultrathin graphite, heavily dopes the graphene to 0.6 x 10^15 /cm2, which simultaneously increased its conductivity and transmittance in the visible range. The intercalated LiC6 single crystallite achieved extraordinary optoelectronic properties, in which an eight-layered Li intercalated FLG achieved transmittance of 91.7% (at 550 nm) and sheet resistance of 3 ohm/sq. We extend the research to obtain scalable, printable graphene based transparent conductors with ion intercalation. Surfactant free, printed reduced graphene oxide transparent conductor thin film with Na-ion intercalation is obtained with transmittance of 79% and sheet resistance of 300 ohm/sq (at 550 nm). The figure of merit is calculated as the best pure rGO based transparent conductors. We further improved the tunability of the reduced graphene oxide film by using two layers of CNT films to sandwich it. The tunable range of rGO film is demonstrated from 0.9 um to 10 um in wavelength. Other ions such as K-ion is also studied of its intercalation chemistry and optical properties in graphitic materials. We also used the in situ characterization tools to understand the fundamental properties and improve the performance of battery electrode materials. We investigated the Na-ion interaction with rGO by in situ Transmission electron microscopy (TEM). For the first time, we observed reversible Na metal cluster (with diameter larger than 10 nm) deposition on rGO surface, which we evidenced with atom-resolved HRTEM image of Na metal and electron diffraction pattern. This discovery leads to a porous reduced graphene oxide sodium ion battery anode with record high reversible specific capacity around 450 mAh/g at 25mA/g, a high rate performance of 200 mAh/g at 250 mA/g, and stable cycling performance up to 750 cycles. In addition, direct observation of irreversible formation of Na2O on rGO unveils the origin of commonly observed low 1st Columbic Efficiency of rGO containing electrodes. Another example for in situ characterization for battery electrode is using the planar nanobattery for 2D MoS2 crystallite. Planar nanobattery allows the intrinsic electrical conductivity measurement with single crystalline 2D battery electrode upon ion intercalation and deintercalation process, which is lacking in conventional battery characterization techniques. We discovered that with a “rapid-charging” process at the first cycle, the lithiated MoS2 undergoes a drastic resistance decrease, which in a regular lithiation process, the resistance always increases after lithiation at its final stage. This discovery leads to a 2- fold increase in specific capacity with with rapid first lithiated MoS2 composite electrode material, compare with the regular first lithiated MoS2 composite electrode material, at current density of 250 mA/g.