Optimal Policies to Obtain the Most Join Results

Nariankadu D. Shyamalkumar (), Ralph P. Russo () and Ramon Lawrence ()
Additional contact information
Nariankadu D. Shyamalkumar: The University of Iowa
Ralph P. Russo: The University of Iowa
Ramon Lawrence: University of British Columbia

Journal of Theoretical Probability, 2007, vol. 20, issue 2, 237-256

Abstract: 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.

Keywords: Optimal strategies; Sequential strategies; Greedy policy; Coupling (search for similar items in EconPapers)
Date: 2007
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10959-007-0063-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jotpro:v:20:y:2007:i:2:d:10.1007_s10959-007-0063-4

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10959

DOI: 10.1007/s10959-007-0063-4

Access Statistics for this article

Journal of Theoretical Probability is currently edited by Andrea Monica

More articles in Journal of Theoretical Probability from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().