Publikation:

Pivot Selection Techniques for Proximity Searching in Metric Spaces

Lade...
Vorschaubild

Dateien

prl03.pdf
prl03.pdfGröße: 181.2 KBDownloads: 744

Datum

2003

Autor:innen

Bustos Cárdenas, Benjamin Eugenio
Navarro, Gonzalo
Chávez, Edgar

Herausgeber:innen

Kontakt

ISSN der Zeitschrift

Electronic ISSN

ISBN

Bibliografische Daten

Verlag

Schriftenreihe

Auflagebezeichnung

ArXiv-ID

Internationale Patentnummer

Angaben zur Forschungsförderung

Projekt

Open Access-Veröffentlichung
Open Access Green
Core Facility der Universität Konstanz

Gesperrt bis

Titel in einer weiteren Sprache

Publikationstyp
Zeitschriftenartikel
Publikationsstatus
Published

Erschienen in

Pattern recognition letters. 2003, 24(14), pp. 2357-2366. Available under: doi: 10.1016/S0167-8655(03)00065-5

Zusammenfassung

With few exceptions, proximity search algorithms in metric spaces based on the use of pivots select them at random among the objects of the metric space. However, it is well known that the way in which the pivots are selected can drastically affect the performance of the algorithm. Between two sets of pivots of the same size, better chosen pivots can largely reduce the search time. Alternatively, a better chosen small set of pivots (requiring much less space) can yield the same efficiency as a larger, randomly chosen, set. We propose an efficiency measure to compare two pivot sets, combined with an optimization technique that allows us to select good sets of pivots. We obtain abundant empirical evidence showing that our technique is effective, and it is the first that we are aware of in producing consistently good results in a wide variety of cases and in being based on a formal theory. We also show that good pivots are outliers, but that selecting outliers does not ensure that good pivots are selected.

Zusammenfassung in einer weiteren Sprache

Fachgebiet (DDC)
004 Informatik

Schlagwörter

Metric databases, range queries, pivot based indexing, nearest neighbour search

Konferenz

Rezension
undefined / . - undefined, undefined

Forschungsvorhaben

Organisationseinheiten

Zeitschriftenheft

Zugehörige Datensätze in KOPS

Zitieren

ISO 690BUSTOS CÁRDENAS, Benjamin Eugenio, Gonzalo NAVARRO, Edgar CHÁVEZ, 2003. Pivot Selection Techniques for Proximity Searching in Metric Spaces. In: Pattern recognition letters. 2003, 24(14), pp. 2357-2366. Available under: doi: 10.1016/S0167-8655(03)00065-5
BibTex
@article{BustosCardenas2003Pivot-5525,
  year={2003},
  doi={10.1016/S0167-8655(03)00065-5},
  title={Pivot Selection Techniques for Proximity Searching in Metric Spaces},
  number={14},
  volume={24},
  journal={Pattern recognition letters},
  pages={2357--2366},
  author={Bustos Cárdenas, Benjamin Eugenio and Navarro, Gonzalo and Chávez, Edgar}
}
RDF
<rdf:RDF
    xmlns:dcterms="http://purl.org/dc/terms/"
    xmlns:dc="http://purl.org/dc/elements/1.1/"
    xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
    xmlns:bibo="http://purl.org/ontology/bibo/"
    xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
    xmlns:foaf="http://xmlns.com/foaf/0.1/"
    xmlns:void="http://rdfs.org/ns/void#"
    xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > 
  <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/5525">
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T15:56:13Z</dcterms:available>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/5525/1/prl03.pdf"/>
    <dc:contributor>Bustos Cárdenas, Benjamin Eugenio</dc:contributor>
    <dc:creator>Navarro, Gonzalo</dc:creator>
    <dcterms:issued>2003</dcterms:issued>
    <dcterms:abstract xml:lang="eng">With few exceptions, proximity search algorithms in metric spaces based on the use of pivots select them at random among the objects of the metric space. However, it is well known that the way in which the pivots are selected can drastically affect the performance of the algorithm. Between two sets of pivots of the same size, better chosen pivots can largely reduce the search time. Alternatively, a better chosen small set of pivots (requiring much less space) can yield the same efficiency as a larger, randomly chosen, set. We propose an efficiency measure to compare two pivot sets, combined with an optimization technique that allows us to select good sets of pivots. We obtain abundant empirical evidence showing that our technique is effective, and it is the first that we are aware of in producing consistently good results in a wide variety of cases and in being based on a formal theory. We also show that good pivots are outliers, but that selecting outliers does not ensure that good pivots are selected.</dcterms:abstract>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:creator>Bustos Cárdenas, Benjamin Eugenio</dc:creator>
    <dcterms:title>Pivot Selection Techniques for Proximity Searching in Metric Spaces</dcterms:title>
    <dc:rights>Attribution-NonCommercial-NoDerivs 2.0 Generic</dc:rights>
    <dc:creator>Chávez, Edgar</dc:creator>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/5525/1/prl03.pdf"/>
    <dcterms:bibliographicCitation>First publ. in: Pattern recognition letters 24 (2003), 14, pp. 2357-2366</dcterms:bibliographicCitation>
    <dc:format>application/pdf</dc:format>
    <dc:contributor>Navarro, Gonzalo</dc:contributor>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dc:contributor>Chávez, Edgar</dc:contributor>
    <dc:language>eng</dc:language>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T15:56:13Z</dc:date>
    <dcterms:rights rdf:resource="http://creativecommons.org/licenses/by-nc-nd/2.0/"/>
    <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/5525"/>
  </rdf:Description>
</rdf:RDF>

Interner Vermerk

xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter

Kontakt
URL der Originalveröffentl.

Prüfdatum der URL

Prüfungsdatum der Dissertation

Finanzierungsart

Kommentar zur Publikation

Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Begutachtet
Diese Publikation teilen