Structural Induction and Coinduction in a Fibrational Setting

We present a categorical logic formulation of induction and coinduction principles for reasoning about inductively and coinductively defined types. Our main results provide sufficient criteria for the validity of such principles: in the presence of comprehension, the induction principle for initial algebras is admissible, and dually, in the presence of quotient types, the coinduction principle for terminal coalgebras is admissible. After giving an alternative formulation of induction in terms of binary relations, we combine both principles and obtain a mixed induction/coinduction principle which allows us to reason about minimal solutionsX≅σ(X) whereXmay occur both positively and negatively in the type constructor σ. We further strengthen these logical principles to deal with contexts and prove that such strengthening is valid when the (abstract) logic we consider is contextually/functionally complete. All the main results follow from a basic result about adjunctions between “categories of algebras” (inserters).     

COSAR: hybrid reasoning for context-aware activity recognition

Human activity recognition is a challenging problem for context-aware systems and applications. Research in this field has mainly adopted techniques based on supervised learning algorithms, but these systems suffer from scalability issues with respect to the number of considered activities and contextual data. In this paper, we propose a solution based on the use of ontologies and ontological reasoning combined with statistical inferencing. Structured symbolic knowledge about the environment surrounding the user allows the recognition system to infer which activities among the candidates identified by statistical methods are more likely to be the actual activity that the user is performing. Ontological reasoning is also integrated with statistical methods to recognize complex activities that cannot be derived by statistical methods alone. The effectiveness of the proposed technique is supported by experiments with a complete implementation of the system using commercially available sensors and an Android-based handheld device as the host for the main activity recognition module.     

Privacy in geo-social networks: proximity notification with untrusted service providers and curious buddies

A major feature of the emerging geo-social networks is the ability to notify a user when any of his friends (also called buddies) happens to be geographically in proximity. This proximity service is usually offered by the network itself or by a third party service provider (SP) using location data acquired from the users. This paper provides a rigorous theoretical and experimental analysis of the existing solutions for the location privacy problem in proximity services. This is a serious problem for users who do not trust the SP to handle their location data and would only like to release their location information in a generalized form to participating buddies. The paper presents two new protocols providing complete privacy with respect to the SP and controllable privacy with respect to the buddies. The analytical and experimental analysis of the protocols takes into account privacy, service precision, and computation and communication costs, showing the superiority of the new protocols compared to those appeared in the literature to date. The proposed protocols have also been tested in a full system implementation of the proximity service.     

A coarse-grain reconfigurable architecture for multimedia applications supporting subword and floating-point calculations

Signal processors exploiting ASIC acceleration suffer from sky-rocketing manufacturing costs and long design cycles. FPGA-based systems provide a programmable alternative for exploiting computation parallelism, but the flexibility they provide is not as high as in processor-oriented architectures: HDL or C-to-HDL flows still require specific expertise and a hardware knowledge background. On the other hand, the large size of the configuration bitstream and the inherent complexity of FPGA devices make their dynamic reconfiguration not a very viable approach. Coarse-grained reconfigurable architectures (CGRAs) are an appealing solution but they pose implementation problems and tend to be application specific. This paper presents a scalable CGRA which eases the implementation of algorithms on field programmable gate array (FPGA) platforms. This design option is based on two levels of programmability: it takes advantage of performance and reliability provided by state-of-the-art FPGA technology, and at the same time it provides the user with flexibility, performance and ease of reconfiguration typical of standard CGRAs. The basic cell template provides advanced features such as sub-word SIMD integer and floating-point computation capabilities, as well as saturating arithmetic. Multiple reconfiguration contexts and partial run-time reconfiguration capabilities are provided, tackling this way the problem of high reconfiguration overhead typical of FPGAs. Selected instances of the proposed architecture have been implemented on an Altera Stratix II EP2S180 FPGA. On this system, we mapped some common DSP, image processing, 3D graphics and audio compression algorithms in order to validate our approach and to demonstrate its effectiveness by benchmarking the benefits achieved.     

nSPARQL: A navigational language for RDF

Navigational features have been largely recognized as fundamental for graph database query languages. This fact has motivated several authors to propose RDF query languages with navigational capabilities. In this paper, we propose the query language nSPARQL that uses nested regular expressions to navigate RDF data. We study some of the fundamental properties of nSPARQL and nested regular expressions concerning expressiveness and complexity of evaluation. Regarding expressiveness, we show that nSPARQL is expressive enough to answer queries considering the semantics of the RDFS vocabulary by directly traversing the input graph. We also show that nesting is necessary in nSPARQL to obtain this last result, and we study the expressiveness of the combination of nested regular expressions and SPARQL operators. Regarding complexity of evaluation, we prove that given an RDF graph G and a nested regular expression E, this problem can be solved in time O(|G||E|).     

A spline framework for estimating the EEG surface laplacian using the Euclidean metric

This letter develops a framework for EEG analysis and similar applications based on polyharmonic splines. This development overcomes a basic problem with the method of splines in the Euclidean setting: that it does not work on low-degree algebraic surfaces such as spherical and ellipsoidal scalp models. The method's capability is illustrated through simulations on the three-sphere model and using empirical data.     

Shape-sensitive MLS deformation

This work presents methods for deforming meshes in a shape-sensitive way using Moving Least Squares (MLS) optimization. It extends an approach for deforming space (Cuno et al. in Proceedings of the 27th Computer Graphics International Conference, pp. 115–122, 2007) by showing how custom distance metrics may be used to achieve deformations which preserve the overall mesh shape. Several variant formulations are discussed and demonstrated, including the use of geodesic distances, distances constrained to paths contained in the mesh, the use of skeletons, and a reformulation of the MLS scheme which makes it possible to affect the bending behavior of the deformation. Finally, aspects of the implementation of these techniques in parallel architectures such as GPUs (graphics processing units) are described and compared with CPU-only implementations.     

New simple and efficient heuristics for the uncapacitated single allocation hub location problem

Hub-and-spoke networks are widely studied in the area of location theory. They arise in several contexts, including passenger airlines, postal and parcel delivery, and computer and telecommunication networks. Hub location problems usually involve three simultaneous decisions to be made: the optimal number of hub nodes, their locations and the allocation of the non-hub nodes to the hubs. In the uncapacitated single allocation hub location problem (USAHLP) hub nodes have no capacity constraints and non-hub nodes must be assigned to only one hub. In this paper, we propose three variants of a simple and efficient multi-start tabu search heuristic as well as a two-stage integrated tabu search heuristic to solve this problem. With multi-start heuristics, several different initial solutions are constructed and then improved by tabu search, while in the two-stage integrated heuristic tabu search is applied to improve both the locational and allocational part of the problem. Computational experiments using typical benchmark problems (Civil Aeronautics Board (CAB) and Australian Post (AP) data sets) as well as new and modified instances show that our approaches consistently return the optimal or best-known results in very short CPU times, thus allowing the possibility of efficiently solving larger instances of the USAHLP than those found in the literature. We also report the integer optimal solutions for all 80 CAB data set instances and the 12 AP instances up to 100 nodes, as well as for the corresponding new generated AP instances with reduced fixed costs.     

Distance browsing in distributed multimedia databases

The state of the art of searching for non-text data (e.g., images) is to use extracted metadata annotations or text, which might be available as a related information. However, supporting real content-based audiovisual search, based on similarity search on features, is significantly more expensive than searching for text. Moreover, such search exhibits linear scalability with respect to the dataset size, so parallel query execution is needed.In this paper, we present a Distributed Incremental Nearest Neighbor algorithm (DINN) for finding closest objects in an incremental fashion over data distributed among computer nodes, each able to perform its local Incremental Nearest Neighbor (local-INN) algorithm. We prove that our algorithm is optimum with respect to both the number of involved nodes and the number of local-INN invocations. An implementation of our DINN algorithm, on a real P2P system called MCAN, was used for conducting an extensive experimental evaluation on a real-life dataset.The proposed algorithm is being used in two running projects: SAPIR and NeP4B.