Aufgrund von Vorbereitungen auf eine neue Version von KOPS, können derzeit keine Publikationen eingereicht werden. (Due to preparations for a new version of KOPS, no publications can be submitted currently.)
Type of Publication: | Contribution to a conference collection |
URI (citable link): | http://nbn-resolving.de/urn:nbn:de:bsz:352-opus-70648 |
Author: | Berchtold, Stefan; Böhm, Christian; Keim, Daniel A.; Kriegel, Hans-Peter |
Year of publication: | 1997 |
Conference: | the sixteenth ACM SIGACT-SIGMOD-SIGART symposium, May 11, 1997 - May 15, 1997, Tucson, Arizona, United States |
Published in: | Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems - PODS '97. - New York, New York, USA : ACM Press, 1997. - pp. 78-86. - ISBN 0-89791-910-6 |
DOI (citable link): | https://dx.doi.org/10.1145/263661.263671 |
Summary: |
In this paper, we present a new cost model for nearest neighbor search in high-dimensional data space. We first analyze different nearest neighbor algorithms, present a generalization of an algorithm which has been originally proposed for Quadtrees [13], and show that this algorithm is optimal. Then, we develop a cost model which - in contrast to previous models - takes boundary effects into account and therefore also works in high dimensions. The advantages of our model are in particular: Our model works for data sets with an arbitrary number of dimensions and an arbitrary number of data points, is applicable to different data distributions and index structures, and provides accurate estimates of the expected query execution time. To show the practical relevance and accuracy of our model, we perform a detailed analysis using synthetic and real data. The results of applying our model to Hilbert and X-tree indices show that it provides a good estimation of the query performance, which is considerably better than the estimates by previous models especially for highdimensional data.
|
Subject (DDC): | 004 Computer Science |
Keywords: | Nearest Neighbor Search, Cost Model, Multidimensional Searching, Multidimensional Index Structures, High-Dimensional Data Space |
Link to License: | Attribution-NonCommercial-NoDerivs 2.0 Generic |
BERCHTOLD, Stefan, Christian BÖHM, Daniel A. KEIM, Hans-Peter KRIEGEL, 1997. A Cost Model for Nearest Neighbor Search in High-Dimensional Data Space. the sixteenth ACM SIGACT-SIGMOD-SIGART symposium. Tucson, Arizona, United States, May 11, 1997 - May 15, 1997. In: Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems - PODS '97. New York, New York, USA:ACM Press, pp. 78-86. ISBN 0-89791-910-6. Available under: doi: 10.1145/263661.263671
@inproceedings{Berchtold1997Model-5738, title={A Cost Model for Nearest Neighbor Search in High-Dimensional Data Space}, year={1997}, doi={10.1145/263661.263671}, isbn={0-89791-910-6}, address={New York, New York, USA}, publisher={ACM Press}, booktitle={Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems - PODS '97}, pages={78--86}, author={Berchtold, Stefan and Böhm, Christian and Keim, Daniel A. and Kriegel, Hans-Peter} }
<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/rdf/resource/123456789/5738"> <dc:creator>Keim, Daniel A.</dc:creator> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <dc:contributor>Böhm, Christian</dc:contributor> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <dc:rights>Attribution-NonCommercial-NoDerivs 2.0 Generic</dc:rights> <dc:creator>Berchtold, Stefan</dc:creator> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T15:59:42Z</dc:date> <dc:language>eng</dc:language> <dc:format>application/pdf</dc:format> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T15:59:42Z</dcterms:available> <dcterms:rights rdf:resource="http://creativecommons.org/licenses/by-nc-nd/2.0/"/> <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/5738"/> <dc:contributor>Kriegel, Hans-Peter</dc:contributor> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/5738/1/PODS97.pdf"/> <dc:creator>Böhm, Christian</dc:creator> <dc:creator>Kriegel, Hans-Peter</dc:creator> <dcterms:abstract xml:lang="eng">In this paper, we present a new cost model for nearest neighbor search in high-dimensional data space. We first analyze different nearest neighbor algorithms, present a generalization of an algorithm which has been originally proposed for Quadtrees [13], and show that this algorithm is optimal. Then, we develop a cost model which - in contrast to previous models - takes boundary effects into account and therefore also works in high dimensions. The advantages of our model are in particular: Our model works for data sets with an arbitrary number of dimensions and an arbitrary number of data points, is applicable to different data distributions and index structures, and provides accurate estimates of the expected query execution time. To show the practical relevance and accuracy of our model, we perform a detailed analysis using synthetic and real data. The results of applying our model to Hilbert and X-tree indices show that it provides a good estimation of the query performance, which is considerably better than the estimates by previous models especially for highdimensional data.</dcterms:abstract> <dcterms:bibliographicCitation>First publ. in: Proceedings / ACM PODS Symposium on Principles of Database Systems, Tucson, AZ, 1997, pp. 78-86</dcterms:bibliographicCitation> <dc:contributor>Berchtold, Stefan</dc:contributor> <dcterms:title>A Cost Model for Nearest Neighbor Search in High-Dimensional Data Space</dcterms:title> <dc:contributor>Keim, Daniel A.</dc:contributor> <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/5738/1/PODS97.pdf"/> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dcterms:issued>1997</dcterms:issued> </rdf:Description> </rdf:RDF>
PODS97.pdf | 1391 |