Search

Real graphs often contain edge and node weights, representing, for instance, penalty, distance or uncertainty. We study the problem of keyword search over weighted node-labeled graphs, in which a query consists of a set of keywords and an answer is a subgraph whose nodes contain the keywords. We evaluate answers using three ranking strategies: optimizing edge weights, optimizing node weights, and a bi-objective combination of both node and edge weights. We prove that optimizing node weights and the bi-objective function are NP-hard. We propose an algorithm that optimizes edge weights and has an approximation ratio of two for the unique node enumeration paradigm. To optimize node weights and the bi-objective function, we propose transformations that distribute node weights onto the edges. We then prove that our transformations allow our algorithm to also optimize node weights and the bi-objective function with the same approximation ratio of two. Notably, the proposed transformations are compatible with existing algorithms that only optimize edge weights. We empirically show that in many natural examples, incorporating node weights (both keyword holders and middle nodes) produces more relevant answers than ranking methods based only on edge weights. Extensive experiments over real-life datasets verify the effectiveness and efficiency of our solution. [ABSTRACT FROM AUTHOR]

Subscription-based online newspapers usually offer non-subscribed users a certain number of free articles in a period of time, and then directs them to a page (called paywall) asking for subscription. This approach (also known as metered or fixed paywall) does not consider the user's reading history nor the articles that the user may read in the future, and consequently, it may disengage many potential subscribers. To that end, we propose adaptive paywall mechanisms to make optimal paywall decisions (i.e., showing the article or the paywall) by balancing the benefit of showing the article against that of presenting the paywall. We define the notions of utility and cost which are used to define an objective function for the optimal paywall decision problem. We propose the Lookahead policy (LAP) and QPaywall policy (QP) as two data-driven approaches to solve the adaptive paywall problem. While the LAP method makes paywall decisions on the fly by simulating trajectories of article requests using Monte Carlo sampling, the QP approach is based on reinforcement learning and learns a neural network-based action-value (Q) function for this purpose. We compare advantages of the proposed approaches and discuss the practical considerations of using them in a real environment. Empirical studies on a real dataset from a major newspaper in Canada show that the proposed methods outperform several baseline approaches in terms of various business objectives. [ABSTRACT FROM AUTHOR]