DSpace Repository

Get a Sample for a Discount Sampling-Based XML Data Pricing

Show simple item record

dc.contributor.author TANG, Ruiming en_US
dc.contributor.author AMARILLI, Antoine en_US
dc.contributor.author SENELLART, Pierre en_US
dc.contributor.author BRESSAN, Stéphane en_US
dc.date.accessioned 2014-03-12T08:54:12Z en_US
dc.date.accessioned 2017-01-23T07:00:08Z
dc.date.available 2014-03-12T08:54:12Z en_US
dc.date.available 2017-01-23T07:00:08Z
dc.date.issued 2014-03-12 en_US
dc.identifier.uri http://hdl.handle.net/1900.100/4362 en_US
dc.description.abstract While price and data quality should define the major tradeoff for consumers in data markets, prices are usually prescribed by vendors and data quality is not negotiable. In this paper we study a model where data quality can be traded for a discount. We focus on the case of XML documents and consider completeness as the quality dimension. In our setting, the data provider offers an XML document, and sets both the price of the document and a weight to each node of the document, depending on its potential worth. The data consumer proposes a price. If the proposed price is lower than that of the entire document, then the data consumer receives a sample, i.e., a random rooted subtree of the document whose selection depends on the discounted price and the weight of nodes. By requesting several samples, the data consumer can iteratively explore the data in the document. We show that the uniform random sampling of a rooted subtree with prescribed weight is unfortunately intractable. However, we are able to identify several practical cases that are tractable. The first case is uniform random sampling of a rooted subtree with prescribed size; the second case restricts to binary weights. For both these practical cases we present polynomial-time algorithms and explain how they can be integrated into an iterative exploratory sampling approach. en_US
dc.format.extent 501788 bytes en_US
dc.format.mimetype application/pdf en_US
dc.language.iso en en_US
dc.relation.ispartofseries ;TRA3/2014 en_US
dc.title Get a Sample for a Discount Sampling-Based XML Data Pricing en_US
dc.type Technical Report en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search DSpace


My Account