Efficient Algorithms for Answering the m-Closest Keywords Query

As an important type of spatial keyword query, the m-closest keywords (mCK) query finds a group of objects such that they cover all query keywords and have the smallest diameter, which is defined as the largest distance between any pair of objects in the group. The query is useful in many applications such as detecting locations of web resources. However, the existing work does not study the intractability of this problem and only provides exact algorithms, which are computationally expensive.

In this paper, we prove that the problem of answering mCK queries is NP-hard. We first devise a greedy algorithm that has an approximation ratio of 2. Then, we observe that an mCK query can be approximately answered by finding the circle with the smallest diameter that encloses a group of objects together covering all query keywords. We prove that the group enclosed in the circle can answer the mCK query with an approximation ratio of 2 over 3. Based on this, we develop an algorithm for finding such a circle exactly, which has a high time complexity. To improve efficiency, we propose another two algorithms that find such a circle approximately, with a ratio of 2 over √3 + ε. Finally, we propose an exact algorithm that utilizes the group found by the 2 over √3 + ε)-approximation algorithm to obtain the optimal group. We conduct extensive experiments using real-life datasets. The experimental results offer insights into both efficiency and accuracy of the proposed approximation algorithms, and the results also demonstrate that our exact algorithm outperforms the best known algorithm by an order of magnitude.

Relocation, reproduction and remaining alive in the orb-web spider

When mortality is high, animals run a risk if they wait to accumulate resources for improved reproduction so they may trade-off the time of reproduction with number and size of offspring. Animals may attempt to improve food acquisition by relocation, even in 'sit and wait' predators. We examine these factors in an isolated population of an orb-web spider Zygiella x-notata. The population was monitored for 200 days from first egg laying until all adults had died. Large females produced their first clutch earlier than did small females and there was a positive correlation between female size and the number and size of eggs produced. Many females, presumably without eggs, abandoned their web site and relocated their web position. This is presumed because female Zygiella typically guard their eggs. In total, c. 25% of females reproduced but those that relocated were less likely to do so, and if they did, they produced the clutch at a later date than those that remained. When the date of lay was controlled there was no effect of relocation on egg number but relocated females produced smaller eggs. The data are consistent with the idea that females in resource-poor sites are more likely to relocate. Relocation seems to be a gamble to find a more productive site but one that achieves only a late clutch of small eggs and few achieve that.

Food-web structure in low- and high-dimensional trophic niche spaces

A question central to modelling and, ultimately, managing food webs concerns the dimensionality of trophic niche space, that is, the number of independent traits relevant for determining consumer-resource links. Food-web topologies can often be interpreted by assuming resource traits to be specified by points along a line and each consumer's diet to be given by resources contained in an interval on this line. This phenomenon, called intervality, has been known for 30 years and is widely acknowledged to indicate that trophic niche space is close to one-dimensional. We show that the degrees of intervality observed in nature can be reproduced in arbitrary-dimensional trophic niche spaces, provided that the processes of evolutionary diversification and adaptation are taken into account. Contrary to expectations, intervality is least pronounced at intermediate dimensions and steadily improves towards lower- and higher-dimensional trophic niche spaces.

A Web-Service Based Approach for Software Sharing

A Web-service based approach is presented which enables geographically dispersed users to share software resources over the Internet. A service-oriented software sharing system has been developed, which consists of shared applications, client applications and three types of services: application proxy service, proxy implementation service and application manager service. With the aids of the services, the client applications interact with the shared applications to implement a software sharing task. The approach satisfies the requirements of copyright protection and reuse of legacy codes. In this paper, the role of Web-services and the architecture of the system are presented first, followed by a case study to illustrate the approach developed.

Phylogeny versus body size as determinants of food web structure

Food webs are the complex networks of trophic interactions that stoke the metabolic fires of life. To understand what structures these interactions in natural communities, ecologists have developed simple models to capture their main architectural features. However, apparently realistic food webs can be generated by models invoking either predator-prey body-size hierarchies or evolutionary constraints as structuring mechanisms. As a result, this approach has not conclusively revealed which factors are the most important. Here we cut to the heart of this debate by directly comparing the influence of phylogeny and body size on food web architecture. Using data from 13 food webs compiled by direct observation, we confirm the importance of both factors. Nevertheless, phylogeny dominates in most networks. Moreover, path analysis reveals that the size-independent direct effect of phylogeny on trophic structure typically outweighs the indirect effect that could be captured by considering body size alone. Furthermore, the phylogenetic signal is asymmetric: closely related species overlap in their set of consumers far more than in their set of resources. This is at odds with several food web models, which take only the view-point of consumers when assigning interactions. The echo of evolutionary history clearly resonates through current food webs, with implications for our theoretical models and conservation priorities.

JISC Workshop Report: E-Research Resources, Tools and Methods for Historic Place Name Analysis

A substantial amount of the 'critical mass' of digital data available to scholarship contains place-names, and it is now recognised that spatial and temporal data points, including place-names, are a vital part of the e-research infrastructure that supports the use, re-use and advanced analysis of data using ICT tools and methods. Place-names can also be linked semantically to contribute to the web of data, and to enrich content through linking existing data, and identifying new collections for digitization to strategically enhance existing digital collections. However, existing e-projects rely on modern gazetteers limiting them to the modern and the near-contemporary. This workshop explored how to further integrate the wealth of historical place-name scholarship, and the resulting digital resources generated within UK academia, so enabling integration of local knowledge over much longer periods.

Stressed Web Environments as Strategic Games: Risk Profiles and Weltanschauung

We consider the behaviour of a set of services in a stressed web environment where performance patterns may be difficult to predict. In stressed environments the performances of some providers may degrade while the performances of others, with elastic resources, may improve. The allocation of web-based providers to users (brokering) is modelled by a strategic non-cooperative angel-daemon game with risk profiles. A risk profile specifies a bound on the number of unreliable service providers within an environment without identifying the names of these providers. Risk profiles offer a means of analysing the behaviour of broker agents which allocate service providers to users. A Nash equilibrium is a fixed point of such a game in which no user can locally improve their choice of provider – thus, a Nash equilibrium is a viable solution to the provider/user allocation problem. Angel daemon games provide a means of reasoning about stressed environments and offer the possibility of designing brokers using risk profiles and Nash equilibria.