Fast Shortest Path Distance Estimation in Large Networks

We study the problem of preprocessing a large graph so that point-to-point shortest-path queries can be answered very fast. Computing shortest paths is a well studied problem, but exact algorithms do not scale to huge graphs encountered on the web, social networks, and other applications. In this paper we focus on approximate methods for distance estimation, in particular using landmark-based distance indexing. This approach involves selecting a subset of nodes as landmarks and computing (offline) the distances from each node in the graph to those landmarks. At runtime, when the distance between a pair of nodes is needed, we can estimate it quickly by combining the precomputed distances of the two nodes to the landmarks. We prove that selecting the optimal set of landmarks is an NP-hard problem, and thus heuristic solutions need to be employed. Given a budget of memory for the index, which translates directly into a budget of landmarks, different landmark selection strategies can yield dramatically different results in terms of accuracy. A number of simple methods that scale well to large graphs are therefore developed and experimentally compared. The simplest methods choose central nodes of the graph, while the more elaborate ones select central nodes that are also far away from one another. The efficiency of the suggested techniques is tested experimentally using five different real world graphs with millions of edges; for a given accuracy, they require as much as 250 times less space than the current approach in the literature which considers selecting landmarks at random. Finally, we study applications of our method in two problems arising naturally in large-scale networks, namely, social search and community detection.

Index Trees for Efficient Deformable Shape-based Retrieval

An improved method for deformable shape-based image indexing and retrieval is described. A pre-computed index tree is used to improve the speed of our previously reported on-line model fitting method; simple shape features are used as keys in a pre-generated index tree of model instances. In addition, a coarse to fine indexing scheme is used at different levels of the tree to further improve speed while maintaining matching accuracy. Experimental results show that the speedup is significant, while accuracy of shape-based indexing is maintained. A method for shape population-based retrieval is also described. The method allows query formulation based on the population distributions of shapes in each image. Results of population-based image queries for a database of blood cell micrographs are shown.

Authenticated Index Structures for Outsourced Database Systems

In outsourced database (ODB) systems the database owner publishes its data through a number of remote servers, with the goal of enabling clients at the edge of the network to access and query the data more efficiently. As servers might be untrusted or can be compromised, query authentication becomes an essential component of ODB systems. Existing solutions for this problem concentrate mostly on static scenarios and are based on idealistic properties for certain cryptographic primitives. In this work, first we define a variety of essential and practical cost metrics associated with ODB systems. Then, we analytically evaluate a number of different approaches, in search for a solution that best leverages all metrics. Most importantly, we look at solutions that can handle dynamic scenarios, where owners periodically update the data residing at the servers. Finally, we discuss query freshness, a new dimension in data authentication that has not been explored before. A comprehensive experimental evaluation of the proposed and existing approaches is used to validate the analytical models and verify our claims. Our findings exhibit that the proposed solutions improve performance substantially over existing approaches, both for static and dynamic environments.

Authenticated Index Structures for Aggregation Queries in Outsourced Databases

In an outsourced database system the data owner publishes information through a number of remote, untrusted servers with the goal of enabling clients to access and query the data more efficiently. As clients cannot trust servers, query authentication is an essential component in any outsourced database system. Clients should be given the capability to verify that the answers provided by the servers are correct with respect to the actual data published by the owner. While existing work provides authentication techniques for selection and projection queries, there is a lack of techniques for authenticating aggregation queries. This article introduces the first known authenticated index structures for aggregation queries. First, we design an index that features good performance characteristics for static environments, where few or no updates occur to the data. Then, we extend these ideas and propose more involved structures for the dynamic case, where the database owner is allowed to update the data arbitrarily. Our structures feature excellent average case performance for authenticating queries with multiple aggregate attributes and multiple selection predicates. We also implement working prototypes of the proposed techniques and experimentally validate the correctness of our ideas.

Rule Extraction, Fuzzy ARTMAP, and Medical Databases

This paper shows how knowledge, in the form of fuzzy rules, can be derived from a self-organizing supervised learning neural network called fuzzy ARTMAP. Rule extraction proceeds in two stages: pruning removes those recognition nodes whose confidence index falls below a selected threshold; and quantization of continuous learned weights allows the final system state to be translated into a usable set of rules. Simulations on a medical prediction problem, the Pima Indian Diabetes (PID) database, illustrate the method. In the simulations, pruned networks about 1/3 the size of the original actually show improved performance. Quantization yields comprehensible rules with only slight degradation in test set prediction performance.

Efficient building management with IP-based wireless sensor network

Existing Building/Energy Management Systems (BMS/EMS) fail to convey holistic performance to the building manager. A 20% reduction in energy consumption can be achieved by efficiently operated buildings compared with current practice. However, in the majority of buildings, occupant comfort and energy consumption analysis is primarily restricted by available sensor and meter data. Installation of a continuous monitoring process can significantly improve the building systems’ performance. We present WSN-BMDS, an IP-based wireless sensor network building monitoring and diagnostic system. The main focus of WSN-BMDS is to obtain much higher degree of information about the building operation then current BMSs are able to provide. Our system integrates a heterogeneous set of wireless sensor nodes with IEEE 802.11 backbone routers and the Global Sensor Network (GSN) web server. Sensing data is stored in a database at the back office via UDP protocol and can be access over the Internet using GSN. Through this demonstration, we show that WSN-BMDS provides accurate measurements of air-temperature, air-humidity, light, and energy consumption for particular rooms in our target building. Our interactive graphical user interface provides a user-friendly environment showing live network topology, monitor network statistics, and run-time management actions on the network. We also demonstrate actuation by changing the artificial light level in one of the rooms.

DC/DC converter 3D assembly for autonomous sensor nodes

This paper reports on the design and the manufacturing of an integrated DCDC converter, which respects the specificity of sensor node network: compactness, high efficiency in acquisition and transmission modes, and compatibility with miniature Lithium batteries. A novel integrated circuit (ASIC) has been designed and manufactured to provide regulated Voltage to the sensor node from miniaturized, thin film Lithium batteries. Then, a 3D integration technique has been used to integrate this ASIC in a 3 layers stack with high efficiency passives components, mixing the wafer level technologies from two different research institutions. Electrical results have demonstrated the feasibility of this integrated system and experiments have shown significant improvements in the case of oscillations in regulated voltage. However, stability of this output voltage toward the input voltage has still to be improved.

Statistical method of modeling and optimization for wireless sensor nodes with different interconnect technologies and substrates

A comparison study was carried out between a wireless sensor node with a bare die flip-chip mounted and its reference board with a BGA packaged transceiver chip. The main focus is the return loss (S parameter S11) at the antenna connector, which was highly depended on the impedance mismatch. Modeling including the different interconnect technologies, substrate properties and passive components, was performed to simulate the system in Ansoft Designer software. Statistical methods, such as the use of standard derivation and regression, were applied to the RF performance analysis, to see the impacts of the different parameters on the return loss. Extreme value search, following on the previous analysis, can provide the parameters' values for the minimum return loss. Measurements fit the analysis and simulation well and showed a great improvement of the return loss from -5dB to -25dB for the target wireless sensor node.

Design and implementation of the embedded capacitance layers for decoupling of wireless sensor nodes

In this paper, the embedded capacitance material (ECM) is fabricated between the power and ground layers of the wireless sensor nodes, forming an integrated capacitance to replace the large amount of decoupling capacitors on the board. The ECM material, whose dielectric constant is 16, has the same size of the wireless sensor nodes of 3cm*3cm, with a thickness of only 14μm. Though the capacitance of a single ECM layer being only around 8nF, there are two reasons the ECM layers can still replace the high frequency decoupling capacitors (100nF in our case) on the board. The first reason is: the parasitic inductance of the ECM layer is much lower than the surface mount capacitors'. A smaller capacitance value of the ECM layer could achieve the same resonant frequency of the surface mount decoupling capacitors. Simulation and measurement fit this assumption well. The second reason is: more than one layer of ECM material are utilized during the design step to get a parallel connection of the several ECM capacitance layers, finally leading to a larger value of the capacitance and smaller value of parasitic. Characterization of the ECM is carried out by the LCR meter. To evaluate the behaviors of the ECM layer, time and frequency domain measurements are performed on the power-bus decoupling of the wireless sensor nodes. Comparison with the measurements of bare PCB board and decoupling capacitors solution are provided to show the improvement of the ECM layer. Measurements show that the implementation of the ECM layer can not only save the space of the surface mount decoupling capacitors, but also provide better power-bus decoupling to the nodes.

Monitoring the vegetation start of season (SOS) across the island of Ireland using the MERIS global vegetation index

The aim of this study was to develop a methodology, based on satellite remote sensing, to estimate the vegetation Start of Season (SOS) across the whole island of Ireland on an annual basis. This growing body of research is known as Land Surface Phenology (LSP) monitoring. The SOS was estimated for each year from a 7-year time series of 10-day composited, 1.2 km reduced resolution MERIS Global Vegetation Index (MGVI) data from 2003 to 2009, using the time series analysis software, TIMESAT. The selection of a 10-day composite period was guided by in-situ observations of leaf unfolding and cloud cover at representative point locations on the island. The MGVI time series was smoothed and the SOS metric extracted at a point corresponding to 20% of the seasonal MGVI amplitude. The SOS metric was extracted on a per pixel basis and gridded for national scale coverage. There were consistent spatial patterns in the SOS grids which were replicated on an annual basis and were qualitatively linked to variation in landcover. Analysis revealed that three statistically separable groups of CORINE Land Cover (CLC) classes could be derived from differences in the SOS, namely agricultural and forest land cover types, peat bogs, and natural and semi-natural vegetation types. These groups demonstrated that managed vegetation, e.g. pastures has a significantly earlier SOS than in unmanaged vegetation e.g. natural grasslands. There was also interannual spatio-temporal variability in the SOS. Such variability was highlighted in a series of anomaly grids showing variation from the 7-year mean SOS. An initial climate analysis indicated that an anomalously cold winter and spring in 2005/2006, linked to a negative North Atlantic Oscillation index value, delayed the 2006 SOS countrywide, while in other years the SOS anomalies showed more complex variation. A correlation study using air temperature as a climate variable revealed the spatial complexity of the air temperature-SOS relationship across the Republic of Ireland as the timing of maximum correlation varied from November to April depending on location. The SOS was found to occur earlier due to warmer winters in the Southeast while it was later with warmer winters in the Northwest. The inverse pattern emerged in the spatial patterns of the spring correlates. This contrasting pattern would appear to be linked to vegetation management as arable cropping is typically practiced in the southeast while there is mixed agriculture and mostly pastures to the west. Therefore, land use as well as air temperature appears to be an important determinant of national scale patterns in the SOS. The TIMESAT tool formed a crucial component of the estimation of SOS across the country in all seven years as it minimised the negative impact of noise and data dropouts in the MGVI time series by applying a smoothing algorithm. The extracted SOS metric was sensitive to temporal and spatial variation in land surface vegetation seasonality while the spatial patterns in the gridded SOS estimates aligned with those in landcover type. The methodology can be extended for a longer time series of FAPAR as MERIS will be replaced by the ESA Sentinel mission in 2013, while the availability of full resolution (300m) MERIS FAPAR and equivalent sensor products holds the possibility of monitoring finer scale seasonality variation. This study has shown the utility of the SOS metric as an indicator of spatiotemporal variability in vegetation phenology, as well as a correlate of other environmental variables such as air temperature. However, the satellite-based method is not seen as a replacement of ground-based observations, but rather as a complementary approach to studying vegetation phenology at the national scale. In future, the method can be extended to extract other metrics of the seasonal cycle in order to gain a more comprehensive view of seasonal vegetation development.

Development of miniaturized wireless sensor nodes suitable for building energy management and modelling

Buildings consume 40% of Ireland's total annual energy translating to 3.5 billion (2004). The EPBD directive (effective January 2003) places an onus on all member states to rate the energy performance of all buildings in excess of 50m2. Energy and environmental performance management systems for residential buildings do not exist and consist of an ad-hoc integration of wired building management systems and Monitoring & Targeting systems for non-residential buildings. These systems are unsophisticated and do not easily lend themselves to cost effective retrofit or integration with other enterprise management systems. It is commonly agreed that a 15-40% reduction of building energy consumption is achievable by efficiently operating buildings when compared with typical practice. Existing research has identified that the level of information available to Building Managers with existing Building Management Systems and Environmental Monitoring Systems (BMS/EMS) is insufficient to perform the required performance based building assessment. The cost of installing additional sensors and meters is extremely high, primarily due to the estimated cost of wiring and the needed labour. From this perspective wireless sensor technology provides the capability to provide reliable sensor data at the required temporal and spatial granularity associated with building energy management. In this paper, a wireless sensor network mote hardware design and implementation is presented for a building energy management application. Appropriate sensors were selected and interfaced with the developed system based on user requirements to meet both the building monitoring and metering requirements. Beside the sensing capability, actuation and interfacing to external meters/sensors are provided to perform different management control and data recording tasks associated with minimisation of energy consumption in the built environment and the development of appropriate Building information models(BIM)to enable the design and development of energy efficient spaces.

Longitudinal study of changes in body mass index, anthropometric measures, dietary intake and physical activity in cohorts of school-going Irish adolescents

The prevalence of obesity worldwide has increased dramatically over the last few decades. Poor dietary habits and low levels of exercise in adolescence are often maintained into adulthood where they can impact on the incidence of obesity and chronic diseases. A 3-year longitudinal study of anthropometric, dietary and exercise parameters was carried out annually (2005 - 2007) in 3 Irish secondary schools. Anthropometric measurements were taken in each year and analysed longitudinally. Overweight and obesity were at relatively low levels in these adolescents. Height, weight, BMI, waist and hip circumferences and TST increased significantly over the 3 years. Waist-to-hip ratio (WHR) decreased significantly over time. Boys were significantly taller than girls across the 3 years. A 3-day weighed food diary was used to assess food intake by the adolescents. Analysis of dietary intake data was determined using WISP©. Mean daily energy and nutrient intakes were reported. Mean daily energy and macronutrient intakes were analysed longitudinally. The adolescents’ diet was characterised by relatively high saturated fat intakes and insufficient fruit and vegetable consumption. The dietary pattern did not change significantly over the 3 years. Boys consumed more energy than girls over the study period. A validated questionnaire was used to assess physical activity and sedentary activity levels. Boys were substantially more active and had higher energy expenditure estimates than girls throughout the study. A significant longitudinal decrease in physical activity levels among the adolescents was observed. Both genders spent more than the recommended amount of time (hrs/day) pursing sedentary activities. The dietary pattern in these Irish adolescents is relatively poor. Of additional concern is the overall longitudinal decrease in physical activity levels. Promoting consumption of a balanced diet and increased exercise levels among adolescents will help to reduce future public health care costs due to weight-related diseases.

Evaluation of HER2, p53, bcl-2, topoisomerase II-alpha, heat shock proteins 27 and 70 in primary breast cancer and metastatic ipsilateral axillary lymph nodes.

BACKGROUND: Breast cancer is a heterogeneous disease. Predictive biological markers (BM) of responsiveness to therapy need to be identified. Evaluation of BM is mainly done at the primary site. However, in the adjuvant therapy of breast cancer, the main goal is control of micrometastases. It is still unknown whether heterogeneity in the expression of BM between the primary site and its micrometastases exists. OBJECTIVE: To evaluate the expression of some BM with potential predictive value from the primary breast cancer site and metastatic ipsilateral axillary lymph nodes. PATIENTS AND METHODS: Focality (percentage of positive cells) and intensity staining scores were evaluated for each marker. Freshly cut sections (4 microm) from embedded blocks of breast cancer fixed in formalin or bouin were put onto superfrost slides (Menzel-Gläser). Protein expression was evaluated immunohistochemically (IHC) using monoclonal antibodies against: topo II-alpha (clone KiS1, 1 microg/ml, Roche) with a trypsine pre-treatment (P); HSP27 (clone G3.1, 1/60, Biogenex), HSP70 (clone BRM.22, 1/80, Biogenex) and HER2 (clone CB11, 1/40, Novocastra; without P); p53 (clone D07, 1/750, Dako) and bcl-2 (clone 124, 1/60, Dako) with citrate buffer as P. RESULTS: Overall, the percentage of discordant marker status in the primary tumour and its metastatic lymph nodes was 2% for HER2, 6% for p53, 15% for bcl-2, 19% for topoisomerase II-alpha, 24% for HSP27 and 30% for HSP70. For the subgroup of patients with positive BM in the primary tumour, the percentage of discordance was 6% for HER2, 7% for p53, 14% for bcl-2, 19% for HSP70, 21% for topoisomerase II-alpha and 36% for HSP27. For the subgroup of patients with positive BM in the lymph nodes, the percentage of discordance was 9% for bcl-2, 15% for HER2 and p53, 21% for topoisomerase II-alpha, 22% for HSP27 and 25% for HSP70. CONCLUSIONS: 1) No biological marker had 100% concordant results. 2) Although some discordant cases might be explained by the limitations of the IHC technique, future studies aiming to evaluate the predictive value of BM in the adjuvant therapy of breast cancer should take into account a possible difference in BM expression between the primary and the metastatic sites.

Separating the scattering and absorption coefficients using the real and imaginary parts of the refractive index with low-coherence interferometry.

We present an analytical method that yields the real and imaginary parts of the refractive index (RI) from low-coherence interferometry measurements, leading to the separation of the scattering and absorption coefficients of turbid samples. The imaginary RI is measured using time-frequency analysis, with the real part obtained by analyzing the nonlinear phase induced by a sample. A derivation relating the real part of the RI to the nonlinear phase term of the signal is presented, along with measurements from scattering and nonscattering samples that exhibit absorption due to hemoglobin.

Measurements of nonlinear refractive index in scattering media.

We have recently developed a spectral re-shaping technique to simultaneously measure nonlinear refractive index and nonlinear absorption. In this technique, the information about the nonlinearities is encoded in the frequency domain, rather than in the spatial domain as in the conventional Z-scan method. Here we show that frequency encoding is much more robust with respect to scattering. We compare spectral re-shaping and Z-scan measurements in a highly scattering environment and show that reliable spectral re-shaping measurements can be performed even in a regime that precludes standard Z-scans.