The Half Space Proximal (HSP) graph is a low out-degree monotonic graph with a wide range of applications in various domains, including combinatorial optimization in strings, enhancing k NN classification, simplifying chemical networks, estimating local intrinsic dimensionality, and generating uniform samples from skewed distributions, among others. However, the linear complexity of finding HSP neighbors of a query limits its scalability, thus motivating approximate indexing which sacrifices accuracy in favor of restricting the test to a small local neighborhood. This compromise leads to the loss of crucial long-range connections which as a result introduce false positives and exclude false negatives, and compromising some of the essential properties of the HSP. To overcome these limitations, this paper proposes a fast and exact algorithm for computing the HSP which enjoys sublinear complexity as demonstrated by extensive experimentation. Our hierarchical approach leverages the triangle inequality applied to pivots to enable efficient HSP search in metric spaces with the Hilbert Exclusion property. A key component of our approach is the concept of the shifted generalized hyperplane between two points, which allows for the invalidation of entire groups of points. Our approach ensures the computation of the exact HSP with efficiency, even for datasets containing hundreds of millions of points.

The computation of a continuous generative model to describe a finite sample of an infinite metric space can prove challenging and lead to erroneous hypothesis, particularly in high-dimensional spaces. In this paper, we follow a different route and define the Hubness Half Space Partitioning graph (HubHSP graph). By constructing this spanning graph over the dataset, we can capture both the geometrical and statistical properties of the data without resorting to any continuity assumption. Leveraging the classical graph-theoretic apparatus, the HubHSP graph facilitates critical operations, including the creation of a representative sample of the original dataset, without relying on density estimation. This representative subsample is essential for a range of operations, including indexing, visualization, and machine learning tasks such as clustering or inductive learning. With the HubHSP graph, we can bypass the limitations of traditional methods and obtain a holistic understanding of our dataset’s properties, enabling us to unlock its full potential.

Approximate Nearest Neighbor (ANN) search is a prevalent paradigm for searching intrinsically high dimensional objects in large-scale data sets. Recently, the permutation-based approach for ANN has attracted a lot of interest due to its versatility in being used in the more general class of metric spaces. In this approach, the entire database is ranked by a permutation distance to the query. Typically, permutations allow the efficient selection of a candidate set of results, but typically to achieve high recall or precision this set has to be reviewed using the original metric and data. This can lead to a sizeable percentage of the database being recalled, along with many expensive distance calculations. To reduce the number of metric computations and the number of database elements accessed, we propose here a re-ranking based on a local embedding using the nSimplex projection. The nSimplex projection produces Euclidean vectors from objects in metric spaces which possess the n-point property. The mapping is obtained from the distances to a set of reference objects, and the original metric can be lower bounded and upper bounded by the Euclidean distance of objects sharing the same set of references. Our approach is particularly advantageous for extensive databases or expensive metric function. We reuse the distances computed in the permutations in the first stage, and hence the memory footprint of the index is not increased. An extensive experimental evaluation of our approach is presented, demonstrating excellent results even on a set of hundreds of millions of objects.

As the number of older adults increases, and with it the demand for dedicated care, geriatric residences face a shortage of caregivers, who themselves experience work overload, stress, and burden. We conducted a long-term field study in three geriatric residences to understand the work conditions of caregivers with the aim of developing technologies to assist them in their work and help them deal with their burdens. From this study, we obtained relevant requirements and insights to design, implement, and evaluate two prototypes for supporting caregivers’ tasks (e.g., electronic recording and automatic notifications) in order to validate the feasibility of their implementation in situ and their technical requirements. The evaluation in situ of the prototypes was conducted for a period of 4 weeks. The results of the evaluation, together with the data collected from 6 months of use, motivated the design of a predictive schedule, which was iteratively improved and evaluated in participative sessions with caregivers. PRESENCE, the predictive schedule we propose, triggers real-time alerts of risky situations (e.g., falls, entering off-limits areas such as the infirmary or the kitchen) and informs caregivers of routine tasks that need to be performed (e.g., medication administration, diaper change, etc.). Moreover, PRESENCE helps caregivers to record caring tasks (such as diaper changes or medication) and well-being assessments (such as the mood) that are difficult to automate. This facilitates caregiver's shift handover and can help to train new caregivers by suggesting routine tasks and by sending reminders and timely information about residents. It can be seen as a tool to reduce the workload of caregivers and medical staff. Instead of trying to substitute the caregiver with an automatic caring system, as proposed by others, we propose our predictive schedule system that blends caregiver assessments and measurements from sensors. We show the feasibility of predicting caregiver tasks and a formative evaluation with caregivers that provides preliminary evidence of its utility.

In this paper we present a novel technique for nearest neighbor searching dubbed neighborhood approximation. The central idea is to divide the database into compact regions represented by a single object, called the reference. To search for nearest neighbors a set of candidate references is first obtained and later enriched with the database objects associated to those references.

The Mexico Research Centre of the Web Intelligence Consortium was established in 2003 motivated by Mexico being selected as the host of the 2nd Atlantic Web Intelligence Conference. It currently has 18 members including faculty and doctoral students from 7 different institutions. The WIC-Mexico includes groups working in the areas of Intelligent Web Information Retrieval, Web Mining and Farming, Knowledge Management, and Agents in Ubiquitous Computing.

The problem of cluster and outlier detection is a classic problem of non-parametric statistics. In recent times the need for cluster analysis in massive multimedia data sets (terabytes of data sampled from a metric space) have demonstrated the need for solutions both in the sense of being capable of automatic clustering metric data and at reasonable speed. Since cluster properties involve the relationship between each pair of data set elements, a good clustering algorithm must examine (in principle) every distance pair and hence has quadratic complexity. An appealing trend to achieve subquadratic complexity is either a) to use an approximation for a classic clustering algorithm or b) to design a new algorithm for clustering. This paper presents a new clustering algorithm performing O(n1+α)distance computations (the operation ofleading complexity), with 0 ⩽ α ⩽ 1 a constant depending on the intrinsic dimension of the sample data. The algorithm can detect outliers in the sample data and, if desired, it can produce a hierarchical structure (a dendogram) pointing to clusters at different resolutions.

A metric space consists of a collection of objects and a distance function defined among them, which satisfies the triangular inequality. The goal is to preprocess the set so that, given a set of objects and a query, one can retrieve those objects close enough to the query. The number of distances computed to achieve this goal is the complexity measure. The problem is very difficult in the so-called high dimensional metric spaces, where the histogram of distances has a large mean and a small variance. A recent survey on methods to index metric spaces has shown that the so-called clustering algorithms are better suited than their competitors, pivot based algorithms, to cope with high dimensional metric spaces. The authors present a new clustering method that achieves much better performance than all the existing data structures. We present analytical and experimental results that support our claims and that give the users the tuning parameters to make optimal use of this data structure.