Efficient Processing of Spatial Group Keyword Queries

With the proliferation of geo-positioning and geo-tagging techniques, spatio-textual objects that possess both a geographical location and a textual description are gaining in prevalence, and spatial keyword queries that exploit both location and textual description are gaining in prominence. However, the queries studied so far generally focus on finding individual objects that each satisfy a query rather than finding groups of objects where the objects in a group together satisfy a query.

We define the problem of retrieving a group of spatio-textual objects such that the group's keywords cover the query's keywords and such that the objects are nearest to the query location and have the smallest inter-object distances. Specifically, we study three instantiations of this problem, all of which are NP-hard. We devise exact solutions as well as approximate solutions with provable approximation bounds to the problems. In addition, we solve the problems of retrieving top-k groups of three instantiations, and study a weighted version of the problem that incorporates object weights. We present empirical studies that offer insight into the efficiency of the solutions, as well as the accuracy of the approximate solutions.

ArnT proteins that catalyse the glycosylation of lipopolysaccharide share common features with bacterial N-oligosaccharyltransferases

ArnT is a glycosyltransferase that catalyses the addition of 4-amino-4-deoxy-L-arabinose (L-Ara4N) to the lipid A moiety of the lipopolysaccharide. This is a critical modification enabling bacteria to resist killing by antimicrobial peptides. ArnT is an integral inner membrane protein consisting of 13 predicted transmembrane helices and a large periplasmic C-terminal domain. We report here the identification of a functional motif with a canonical consensus sequence DEXRYAX(5)MX(3)GXWX(9)YFEKPX(4)W spanning the first periplasmic loop, which is highly conserved in all ArnT proteins examined. Site-directed mutagenesis demonstrated the contribution of this motif in ArnT function, suggesting that these proteins have a common mechanism. We also demonstrate that the Burkholderia cenocepacia and Salmonella enterica serovar Typhimurium ArnT C-terminal domain is required for polymyxin B resistance in vivo. Deletion of the C-terminal domain in B. cenocepacia ArnT resulted in a protein with significantly reduced in vitro binding to a lipid A fluorescent substrate and unable to catalyse lipid A modification with L-Ara4N. An in silico predicted structural model of ArnT strongly resembled the tertiary structure of Campylobacter lari PglB, a bacterial oligosaccharyltransferase involved in protein N-glycosylation. Therefore, distantly related oligosaccharyltransferases from ArnT and PglB families operating on lipid and polypeptide substrates, respectively, share unexpected structural similarity that could not be predicted from direct amino acid sequence comparisons. We propose that lipid A and protein glycosylation enzymes share a conserved catalytic mechanism despite their evolutionary divergence.

Entity Linking for Web Search Queries

We consider the problem of linking web search queries to entities from a knowledge base such as Wikipedia. Such linking enables converting a user’s web search session to a footprint in the knowledge base that could be used to enrich the user profile. Traditional methods for entity linking have been directed towards finding entity mentions in text documents such as news reports, each of which are possibly linked to multiple entities enabling the usage of measures like entity set coherence. Since web search queries are very small text fragments, such criteria that rely on existence of a multitude of mentions do not work too well on them. We propose a three-phase method for linking web search queries to wikipedia entities. The first phase does IR-style scoring of entities against the search query to narrow down to a subset of entities that are expanded using hyperlink information in the second phase to a larger set. Lastly, we use a graph traversal approach to identify the top entities to link the query to. Through an empirical evaluation on real-world web search queries, we illustrate that our methods significantly enhance the linking accuracy over state-of-the-art methods.

Sharing services, saving money? Five risks to cost saving when organizations share administrative services

Shared services are a popular reform for governments under financial pressure. The hope is to reduce overheads and increase efficiency by providing support services like HR, finance and procurement once to multiple agencies. Drawing on insights from organization theory and political science, we identify five risks that shared services won’t live up to current expectations. We illustrate each with empirical evidence from the UK, Ireland and further afield, and conclude with suggestions on how to manage these risks.