<?xml version="1.0" encoding="UTF-8"?>
<modsCollection xmlns="http://www.loc.gov/mods/v3">
<mods ID="dobre-2024-efficient">
    <titleInfo>
        <title>Efficient Dependency Tree Sampling Without Replacement</title>
    </titleInfo>
    <name type="personal">
        <namePart type="given">Bogdan</namePart>
        <namePart type="family">Dobre</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <originInfo>
        <dateIssued>2024-06</dateIssued>
    </originInfo>
    <typeOfResource>text</typeOfResource>
    <relatedItem type="host">
        <titleInfo>
            <title>Findings of the Association for Computational Linguistics: NAACL 2024</title>
        </titleInfo>
        <name type="personal">
            <namePart type="given">Kevin</namePart>
            <namePart type="family">Duh</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <name type="personal">
            <namePart type="given">Helena</namePart>
            <namePart type="family">Gomez</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <name type="personal">
            <namePart type="given">Steven</namePart>
            <namePart type="family">Bethard</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <originInfo>
            <publisher>Association for Computational Linguistics</publisher>
            <place>
                <placeTerm type="text">Mexico City, Mexico</placeTerm>
            </place>
        </originInfo>
        <genre authority="marcgt">conference publication</genre>
    </relatedItem>
    <abstract>In the context of computational models of dependency syntax, most dependency treebanks have the restriction that any valid dependency tree must have exactly one edge coming out of the root node in addition to respecting the spanning tree constraints. Many algorithms for dependency tree sampling were recently proposed, both for sampling with and without replacement.In this paper we propose a new algorithm called Wilson Reject SWOR for the case of sampling without replacement by adapting the Wilson Reject algorithm originally created for sampling with replacement and combining it with a Trie data structure. Experimental results indicate the efficiency of our approach in the scenario of sampling without replacement from dependency graphs with random weights.</abstract>
    <identifier type="citekey">dobre-2024-efficient</identifier>
    <identifier type="doi">10.18653/v1/2024.findings-naacl.47</identifier>
    <location>
        <url>https://aclanthology.org/2024.findings-naacl.47</url>
    </location>
    <part>
        <date>2024-06</date>
        <extent unit="page">
            <start>736</start>
            <end>741</end>
        </extent>
    </part>
</mods>
</modsCollection>

%0 Conference Proceedings
%T Efficient Dependency Tree Sampling Without Replacement
%A Dobre, Bogdan
%Y Duh, Kevin
%Y Gomez, Helena
%Y Bethard, Steven
%S Findings of the Association for Computational Linguistics: NAACL 2024
%D 2024
%8 June
%I Association for Computational Linguistics
%C Mexico City, Mexico
%F dobre-2024-efficient
%X In the context of computational models of dependency syntax, most dependency treebanks have the restriction that any valid dependency tree must have exactly one edge coming out of the root node in addition to respecting the spanning tree constraints. Many algorithms for dependency tree sampling were recently proposed, both for sampling with and without replacement.In this paper we propose a new algorithm called Wilson Reject SWOR for the case of sampling without replacement by adapting the Wilson Reject algorithm originally created for sampling with replacement and combining it with a Trie data structure. Experimental results indicate the efficiency of our approach in the scenario of sampling without replacement from dependency graphs with random weights.
%R 10.18653/v1/2024.findings-naacl.47
%U https://aclanthology.org/2024.findings-naacl.47
%U https://doi.org/10.18653/v1/2024.findings-naacl.47
%P 736-741

Markdown (Informal)

[Efficient Dependency Tree Sampling Without Replacement](https://aclanthology.org/2024.findings-naacl.47) (Dobre, Findings 2024)

• Efficient Dependency Tree Sampling Without Replacement (Dobre, Findings 2024)

ACL

• Bogdan Dobre. 2024. Efficient Dependency Tree Sampling Without Replacement. In Findings of the Association for Computational Linguistics: NAACL 2024, pages 736–741, Mexico City, Mexico. Association for Computational Linguistics.