GQP: A Framework for Scalable and Effective Graph Query-based Pricing

Data is increasingly being bought and sold online, and data market platforms have emerged to facilitate these activities. However, current mechanisms for pricing data mainly focus on traditional relational data. In this paper, we propose a framework GQP for pricing graph data on the data market platform. Specifically, given a set of graph price points and a graph query, we can efficiently compute the price of the query based on the graph price points. We first identify an important property (called arbitrage-free) GQP should satisfy with, such that GQP can effectively price the graph query. We then study the exact pricing problem (NP-completeness) and develop an efficient approximation algorithm to solve the problem. We also study the approximate pricing when the query cannot be answered by price points exactly. Furthermore, to avoid the expensive computing cost of updating graph price points, we study the dynamic query pricing and propose novel solutions to reuse the computed graph price points to reduce the computational complexity. Finally, we use real-life data and synthetic data to experimentally verify that the proposed algorithms are able to effectively and efficiently price large graph data based on the framework GQP.