skip to main content

Title: Semantically Diverse Path Search
Location-Based Services are often used to find proximal Points of Interest PoI - e.g., nearby restaurants and museums, police stations, hospitals, etc. - in a plethora of applications. An important recently addressed variant of the problem not only considers the distance/proximity aspect, but also desires semantically diverse locations in the answer-set. For instance, rather than picking several close-by attractions with similar features - e.g., restaurants with similar menus; museums with similar art exhibitions - a tourist may be more interested in a result set that could potentially provide more diverse types of experiences, for as long as they are within an acceptable distance from a given (current) location. Towards that goal, in this work we propose a novel approach to efficiently retrieve a path that will maximize the semantic diversity of the visited PoIs that are within distance limits along a given road network. We introduce a novel indexing structure - the Diversity Aggregated R-tree, based on which we devise efficient algorithms to generate the answer-set - i.e., the recommended locations among a set of given PoIs - relying on a greedy search strategy. Our experimental evaluations conducted on real datasets demonstrate the benefits of proposed methodology over the baseline more » alternative approaches. « less
; ; ;
Award ID(s):
Publication Date:
Journal Name:
21st {IEEE} International Conference on Mobile Data Management, {MDM} 2020, Versailles, France, June 30 - July 3, 2020
Page Range or eLocation-ID:
69 to 78
Sponsoring Org:
National Science Foundation
More Like this
  1. One of the most popular applications of Location Based Services (LBS) is recommending a Point of Interest (POI) based on user's preferences and geo-locations. However, the existing approaches have not tackled the problem of jointly determining: (a) a sequence of POIs that can be traversed within certain budget (i.e., limit on distance) and simultaneously provide a high-enough diversity; and (b) recommend the best origin (i.e., the hotel) for a given user, so that the desired route of POIs can be traversed within the specified constraints. In this work, we take a first step towards identifying this new problem and formalizing it as a novel type of a query. Subsequently, we present naïve solutions and experimental observations over a real-life datasets, illustrating the trade-offs in terms of (dis)associating the initial location from the rest of the POIs.
  2. Context has been recognized as an important factor to consider in personalized recommender systems. Particularly in location-based services (LBSs), a fundamental task is to recommend to a mobile user where he/she could be interested to visit next at the right time. Additionally, location-based social networks (LBSNs) allow users to share location-embedded information with friends who often co-occur in the same or nearby points-of-interest (POIs) or share similar POI visiting histories, due to the social homophily theory and Tobler’s first law of geography. So, both the time information and LBSN friendship relations should be utilized for POI recommendation. Tensor completion has recently gained some attention in time-aware recommender systems. The problem decomposes a user-item-time tensor into low-rank embedding matrices of users, items and times using its observed entries, so that the underlying low-rank subspace structure can be tracked to fill the missing entries for time-aware recommendation. However, these tensor completion methods ignore the social-spatial context information available in LBSNs, which is important for POI recommendation since people tend to share their preferences with their friends, and near things are more related than distant things. In this paper, we utilize the side information of social networks and POI locations to enhance themore »tensor completion model paradigm for more effective time-aware POI recommendation. Specifically, we propose a regularization loss head based on a novel social Hausdorff distance function to optimize the reconstructed tensor. We also quantify the popularity of different POIs with location entropy to prevent very popular POIs from being over-represented hence suppressing the appearance of other more diverse POIs. To address the sensitivity of negative sampling, we train the model on the whole data by treating all unlabeled entries in the observed tensor as negative, and rewriting the loss function in a smart way to reduce the computational cost. Through extensive experiments on real datasets, we demonstrate the superiority of our model over state-of-the-art tensor completion methods.« less
  3. Diversity is an important principle in data selection and summarization, facility location, and recommendation systems. Our work focuses on maximizing diversity in data selection, while offering fairness guarantees. In particular, we offer the first study that augments the Max-Min diversification objective with fairness constraints. More specifically, given a universe 𝒰 of n elements that can be partitioned into m disjoint groups, we aim to retrieve a k-sized subset that maximizes the pairwise minimum distance within the set (diversity) and contains a pre-specified k_i number of elements from each group i (fairness). We show that this problem is NP-complete even in metric spaces, and we propose three novel algorithms, linear in n, that provide strong theoretical approximation guarantees for different values of m and k. Finally, we extend our algorithms and analysis to the case where groups can be overlapping.
  4. We address the problem of maintaining the correct answer-sets to the Conditional Maximizing Range-Sum (C-MaxRS) query in spatial data streams. Given a set of (possibly weighted) 2D point objects, the traditional MaxRS problem determines an optimal placement for an axes-parallel rectangle r so that the number – or, the weighted sum – of objects in its interior is maximized. In many practical settings, the objects from a particular set – e.g., restaurants – can be of distinct types – e.g., fast-food, Asian, etc. The C-MaxRS problem deals with maximizing the overall sum, given class-based existential constraints, i.e., a lower bound on the count of objects of interests from particular classes. We first propose an efficient algorithm to the static C-MaxRS query, and extend the solution to handle dynamic (data streams) settings. Our experiments over datasets of up to 100,000 objects show that the proposed solutions provide significant efficiency benefits.
  5. One of the most urgent contemporary tasks for taxonomists and evolutionary biologists is to estimate the number of species on earth. Recording alpha diversity is crucial for protecting biodiversity, especially in areas of elevated species richness, which coincide geographically with increased anthropogenic environmental pressures - the world’s so-called biodiversity hotspots. Although the distribution of Puddle frogs of the genus Occidozyga in South and Southeast Asia includes five biodiversity hotspots, the available data on phylogeny, species diversity, and biogeography are surprisingly patchy. Samples analyzed in this study were collected throughout Southeast Asia, with a primary focus on Sundaland and the Philippines. A mitochondrial gene region comprising ~ 2000 bp of 12S and 16S rRNA with intervening tRNA Valine and three nuclear loci (BDNF, NTF3, POMC) were analyzed to obtain a robust, time-calibrated phylogenetic hypothesis. We found a surprisingly high level of genetic diversity within Occidozyga, based on uncorrected p-distance values corroborated by species delimitation analyses. This extensive genetic diversity revealed 29 evolutionary lineages, defined by the > 5% uncorrected p-distance criterion for the 16S rRNA gene, suggesting that species diversity in this clade of phenotypically homogeneous forms probably has been underestimated. The comparison with results of other anuran groups leads tomore »the assumption that anuran species diversity could still be substantially underestimated in Southeast Asia in general. Many genetically divergent lineages of frogs are phenotypically similar, indicating a tendency towards extensive morphological conservatism. We present a biogeographic reconstruction of the colonization of Sundaland and nearby islands which, together with our temporal framework, suggests that lineage diversification centered on the landmasses of the northern Sunda Shelf. This remarkably genetically structured group of amphibians could represent an exceptional case for future studies of geographical structure and diversification in a widespread anuran clade spanning some of the most pronounced geographical barriers on the planet (e.g., Wallace’s Line). Studies considering gene flow, morphology, ecological and bioacoustic data are needed to answer these questions and to test whether observed diversity of Puddle frog lineages warrants taxonomic recognition.« less