Journal article
Optimal Policies to Obtain the Most Join Results
Journal of Theoretical Probability, Vol.20(2), pp.237-256
06/2007
DOI: 10.1007/s10959-007-0063-4
Abstract
Consider two finite or infinite populations, each member of which carries a positive integer valued label. Samples are drawn without replacement. A match is said to occur between two sampled members if they are from different populations and carry the same label. The object is to sample from the two sources in an order that maximizes the number of matches, uniformly across all steps. An optimal strategy is identified in the infinite case. In the finite case, while an optimal policy is shown to not always exist, we identify a policy which beats one that is commonly used. The work is motivated by a database problem in computer science. Many of the results are established through the probabilistic technique of coupling.
Details
- Title: Subtitle
- Optimal Policies to Obtain the Most Join Results
- Creators
- Nariankadu Shyamalkumar - Department of Statistics & Actuarial Science The University of Iowa 241 Schaeffer Hall Iowa City IA 52242 USARalph Russo - Department of Statistics & Actuarial Science The University of Iowa 241 Schaeffer Hall Iowa City IA 52242 USARamon Lawrence - Department of Computer Science University of British Columbia Okanagan Canada
- Resource Type
- Journal article
- Publication Details
- Journal of Theoretical Probability, Vol.20(2), pp.237-256
- Publisher
- Kluwer Academic Publishers-Plenum Publishers; New York
- DOI
- 10.1007/s10959-007-0063-4
- ISSN
- 0894-9840
- eISSN
- 1572-9230
- Language
- English
- Date published
- 06/2007
- Academic Unit
- Statistics and Actuarial Science
- Record Identifier
- 9983985967302771
Metrics
14 Record Views