Showing 1–10 of 10 results for author: Gai, L

Minimum sum vertex cover: kernelization and parameterized algorithms

Authors: Yixin Cao, Ling Gai, Jingyi Liu, Jianxin Wang

Abstract: Given an ordering of the vertices of a graph, the cost of covering an edge is the smaller number of its two ends. The minimum sum vertex cover problem asks for an ordering that minimizes the total cost of covering all edges. We consider parameterized complexity of this problem, using the largest cost~$k$ of covering a single edge as the parameter. Note that the first $k$ vertices form a (not neces… ▽ More Given an ordering of the vertices of a graph, the cost of covering an edge is the smaller number of its two ends. The minimum sum vertex cover problem asks for an ordering that minimizes the total cost of covering all edges. We consider parameterized complexity of this problem, using the largest cost~$k$ of covering a single edge as the parameter. Note that the first $k$ vertices form a (not necessarily minimal) vertex cover of the graph, and the ordering of vertices after $k$ is irrelevant. We present a $(k^2 + 2 k)$-vertex kernel and an $O(m + 2^kk! k^4)$-time algorithm for the minimum sum vertex cover problem, where $m$ is the size of the input graph. Since our parameter~$k$ is polynomially bounded by the vertex cover number of the input graph, our results also apply to that parameterization. △ Less

Submitted 14 April, 2024; v1 submitted 27 March, 2024; originally announced March 2024.

Optimizing Ghost Imaging via Analysis and Design of Speckle Patterns

Authors: Xinjian Zhang, Siyuan Song, Xiaoping Ma, Haonan Zhang, Lei Gai, Yongjian Gu, Wendong Li

Abstract: We study the influence rules of the speckle size of light source on ghost imaging, and propose a new type of speckle patterns to improve the quality of ghost imaging. The results show that the image quality will first increase and then decrease with the increase of the speckle size, and there is an optimal speckle size for a specific object. Moreover, by using the random distribution of speckle po… ▽ More We study the influence rules of the speckle size of light source on ghost imaging, and propose a new type of speckle patterns to improve the quality of ghost imaging. The results show that the image quality will first increase and then decrease with the increase of the speckle size, and there is an optimal speckle size for a specific object. Moreover, by using the random distribution of speckle positions, a new type of displacement speckle patterns is designed, and the imaging quality is better than that of the random speckle patterns. These results are of great significances for finding the best speckle patterns suitable for detecting targets, which further promotes the practical applications of ghost imaging. △ Less

Submitted 10 March, 2022; originally announced March 2022.

Practical underwater quantum key distribution based on decoy-state BB84 protocol

Authors: Shanchuan Dong, Yonghe Yu, Shangshuai Zheng, Qiming Zhu, Lei Gai, Wendong Li, Yongjian Gu

Abstract: Polarization encoding quantum key distribution has been proven to be a reliable method to build a secure communication system. It has already been used in inter-city fiber channel and near-earth atmosphere channel, leaving underwater channel the last barrier to conquer. Here we demonstrate a decoy-state BB84 quantum key distribution system over a water channel with a compact system design for futu… ▽ More Polarization encoding quantum key distribution has been proven to be a reliable method to build a secure communication system. It has already been used in inter-city fiber channel and near-earth atmosphere channel, leaving underwater channel the last barrier to conquer. Here we demonstrate a decoy-state BB84 quantum key distribution system over a water channel with a compact system design for future experiments in the ocean. In the system, a multiple-intensity modulated laser module is designed to produce the light pulses of quantum states, including signal state, decoy state and vacuum state. The classical communication and synchronization are realized by wireless optical transmission. Multiple filtering techniques and wavelength division multiplexing are further used to avoid crosstalk of different light. We test the performance of the system and obtain a final key rate of 245.6 bps with an average QBER of 1.91% over a 2.4m water channel, in which the channel attenuation is 16.35dB. Numerical simulation shows that the system can tolerate up to 21.7dB total channel loss and can still generate secure keys in 277.9m Jelov type 1 ocean channel. △ Less

Submitted 9 March, 2022; originally announced March 2022.

Tuning the coherent propagation of organic exciton-polaritons through dark state delocalization

Authors: Raj Pandya, Arjun Ashoka, Kyriacos Georgiou, Jooyoung Sung, Rahul Jayaprakash, Scott Renken, Lizhi Gai, Zhen Shen, Akshay Rao, Andrew Musser

Abstract: While there have been numerous reports of long-range polariton transport at room-temperature in organic cavities, the spatio-temporal evolution of the propagation is scarcely reported, particularly in the initial coherent sub-ps regime, where photon and exciton wavefunctions are inextricably mixed. Hence the detailed process of coherent organic exciton-polariton transport and in particular the rol… ▽ More While there have been numerous reports of long-range polariton transport at room-temperature in organic cavities, the spatio-temporal evolution of the propagation is scarcely reported, particularly in the initial coherent sub-ps regime, where photon and exciton wavefunctions are inextricably mixed. Hence the detailed process of coherent organic exciton-polariton transport and in particular the role of dark states has remained poorly understood. Here, we use femtosecond transient absorption microscopy to directly image coherent polariton motion in microcavities of varying quality factor. We find the transport to be well-described by a model of band-like propagation of an initially Gaussian distribution of exciton-polaritons in real space. The velocity of the polaritons reaches values of ~0.65x10^6 m s-1, substantially lower than expected from the polariton dispersion. Further, we find that the velocity is proportional to the quality factor of the microcavity. We suggest this unexpected link between the quality-factor and polariton velocity and slow coherent transport to be a result of varying admixing between delocalised dark and polariton states. △ Less

Submitted 3 December, 2021; originally announced December 2021.

Untargeted Effects in Organic Exciton-Polariton Transient Spectroscopy: A Cautionary Tale

Authors: Scott Renken, Raj Pandya, Kyriacos Georgiou, Rahul Jayaprakash, Lizhi Gai, Zhen Shen, David G. Lidzey, Akshay Rao, Andrew J Musser

Abstract: Strong light-matter coupling to form exciton- and vibropolaritons is increasingly touted as a powerful tool to alter the fundamental properties of organic materials. It is proposed that these states and their facile tunability can be used to rewrite molecular potential energy landscapes and redirect photophysical pathways, with applications from catalysis to electronic devices. Crucial to their ph… ▽ More Strong light-matter coupling to form exciton- and vibropolaritons is increasingly touted as a powerful tool to alter the fundamental properties of organic materials. It is proposed that these states and their facile tunability can be used to rewrite molecular potential energy landscapes and redirect photophysical pathways, with applications from catalysis to electronic devices. Crucial to their photophysical properties is the exchange of energy between coherent, bright polaritons and incoherent dark states. One of the most potent tools to explore this interplay is transient absorption/reflectance spectroscopy. Previous studies have revealed unexpectedly long lifetimes of the coherent polariton states, for which there is no theoretical explanation. Applying these transient methods to a series of strong-coupled organic microcavities, we recover similar long-lived spectral effects. Based on transfer-matrix modelling of the transient experiment, we find that virtually the entire photoresponse results from photoexcitation effects other than the generation of polariton states. Our results suggest that the complex optical properties of polaritonic systems make them especially prone to misleading optical signatures, and that more challenging high-time-resolution measurements on high-quality microcavities are necessary to uniquely distinguish the coherent polariton dynamics. △ Less

Submitted 12 July, 2021; originally announced July 2021.

Journal ref: J. Chem. Phys. 155, 154701 (2021)

Leveraging Neighborhood Summaries for Efficient RDF Queries on RDBMS

Authors: Lei Gai

Abstract: Using structural informations to summarize graph-structured RDF data is helpful in tackling query performance issues. However, leveraging structural indexes needs to revise or even redesign the internal of RDF systems. Given an RDF dataset that have already been bulk loaded into a relational RDF system, we aim at improving the query performance on such systems. We do so by summarizing neighborhood… ▽ More Using structural informations to summarize graph-structured RDF data is helpful in tackling query performance issues. However, leveraging structural indexes needs to revise or even redesign the internal of RDF systems. Given an RDF dataset that have already been bulk loaded into a relational RDF system, we aim at improving the query performance on such systems. We do so by summarizing neighborhood structures and encoding them into triples which can be managed along side the exist instance data. At query time, we optimally select the effective structural patterns, and adding these patterns to the existing queries to gain an improved query performance. Empirical evaluations shown the effectiveness of our method. △ Less

Submitted 22 January, 2020; originally announced January 2020.

On the origin of blueshifts in organic polariton condensates

Authors: Timur Yagafarov, Denis Sannikov, Anton Zasedatelev, Kyriacos Georgiou, Anton Baranikov, Oleksandr Kyriienko, Ivan Shelykh, Lizhi Gai, Zhen Shen, David G. Lidzey, Pavlos G. Lagoudakis

Abstract: We report on the origin of energy-shifts in organic polariton condensates. The localised nature of Frenkel excitons in molecular semiconductors precludes interparticle Coulomb exchange interactions -the latter being the dominant mechanism for blueshifts in inorganic semiconductor microcavities that bear Wannier-Mott excitons. We examine the contribution of optically induced change of the intracavi… ▽ More We report on the origin of energy-shifts in organic polariton condensates. The localised nature of Frenkel excitons in molecular semiconductors precludes interparticle Coulomb exchange interactions -the latter being the dominant mechanism for blueshifts in inorganic semiconductor microcavities that bear Wannier-Mott excitons. We examine the contribution of optically induced change of the intracavity non-linear refractive index, gain induced frequency-pulling and quenching of the Rabi splitting, as well as the role of polariton-exciton and polariton-polariton scattering in the energy-shift of the polariton mode at condensation threshold in strongly coupled molecular dye microcavities. We conclude that blueshifts in organic polariton condensates arise from the interplay of the saturation of molecular optical transitions and intermolecular energy migration. Our model predicts the commonly observed step-wise increase of both the emission energy and degree of linear polarisation at polariton condensation threshold. △ Less

Submitted 22 May, 2019; v1 submitted 7 May, 2019; originally announced May 2019.

ROSIE: Runtime Optimization of SPARQL Queries Using Incremental Evaluation

Authors: Lei Gai, Wei Chen, Tengjiao Wang

Abstract: Relational databases are wildly adopted in RDF (Resource Description Framework) data management. For efficient SPARQL query evaluation, the legacy query optimizer needs reconsiderations. One vital problem is how to tackle the suboptimal query plan caused by error-prone cardinality estimation. Consider the schema-free nature of RDF data and the Join-intensive characteristic of SPARQL query, determi… ▽ More Relational databases are wildly adopted in RDF (Resource Description Framework) data management. For efficient SPARQL query evaluation, the legacy query optimizer needs reconsiderations. One vital problem is how to tackle the suboptimal query plan caused by error-prone cardinality estimation. Consider the schema-free nature of RDF data and the Join-intensive characteristic of SPARQL query, determine an optimal execution order before the query actually evaluated is costly or even infeasible, especially for complex queries on large-scale data. In this paper, we propose ROSIE, a Runtime Optimization framework that iteratively re-optimize SPARQL query plan according to the actual cardinality derived from Incremental partial query Evaluation. By introducing an approach for heuristic-based plan generation, as well as a mechanism to detect cardinality estimation error at runtime, ROSIE relieves the problem of biased cardinality propagation in an efficient way, and thus is more resilient to complex query evaluation. Extensive experiments on real and benchmark data show that compared to the state-of-the-arts, ROSIE consistently outperformed on complex queries by orders of magnitude. △ Less

Submitted 22 May, 2016; originally announced May 2016.

A partition-based Summary-Graph-Driven Method for Efficient RDF Query Processing

Authors: Lei Gai, Wei Chen, Tengjiao Wang

Abstract: RDF query optimization is a challenging problem. Although considerable factors and their impacts on query efficiency have been investigated, this problem still needs further investigation. We identify that decomposing query into a series of light-weight operations is also effective in boosting query processing. Considering the linked nature of RDF data, the correlations among operations should be… ▽ More RDF query optimization is a challenging problem. Although considerable factors and their impacts on query efficiency have been investigated, this problem still needs further investigation. We identify that decomposing query into a series of light-weight operations is also effective in boosting query processing. Considering the linked nature of RDF data, the correlations among operations should be carefully handled. In this paper, we present SGDQ, a novel framework that features a partition-based Summary Graph Driven Query for efficient query processing. Basically, SGDQ partitions data and models partitions as a summary graph. A query is decomposed into subqueries that can be answered without inter-partition processing. The final results are derived by perform summary graph matching and join the results generated by all matched subqueries. In essence, SGDQ combines the merits of graph match processing and relational join-based query implementation. It intentionally avoids maintain huge intermediate results by organizing sub-query processing in a summary graph driven fashion. Our extensive evaluations show that SGDQ is an effective framework for efficient RDF query processing. Its query performance consistently outperforms the representative state-of-the-art systems. △ Less

Submitted 26 October, 2015; originally announced October 2015.

Comments: 12 pages

Towards Efficient Path Query on Social Network with Hybrid RDF Management

Authors: Lei Gai, Wei Chen, Zhichao Xu, Changhe Qiu, Tengjiao Wang

Abstract: The scalability and exibility of Resource Description Framework(RDF) model make it ideally suited for representing online social networks(OSN). One basic operation in OSN is to find chains of relations,such as k-Hop friends. Property path query in SPARQL can express this type of operation, but its implementation suffers from performance problem considering the ever growing data size and complexity… ▽ More The scalability and exibility of Resource Description Framework(RDF) model make it ideally suited for representing online social networks(OSN). One basic operation in OSN is to find chains of relations,such as k-Hop friends. Property path query in SPARQL can express this type of operation, but its implementation suffers from performance problem considering the ever growing data size and complexity of OSN.In this paper, we present a main memory/disk based hybrid RDF data management framework for efficient property path query. In this hybrid framework, we realize an efficient in-memory algebra operator for property path query using graph traversal, and estimate the cost of this operator to cooperate with existing cost-based optimization. Experiments on benchmark and real dataset demonstrated that our approach can achieve a good tradeoff between data load expense and online query performance. △ Less

Submitted 9 June, 2014; v1 submitted 26 May, 2014; originally announced May 2014.