ERA

Download the full-sized PDF of Metric Techniques for High-Dimensional IndexingDownload the full-sized PDF

Analytics

Share

Permanent link (DOI): https://doi.org/10.7939/R3JQ0SX0P

Download

Export to: EndNote  |  Zotero  |  Mendeley

Communities

This file is in the following communities:

Computing Science, Department of

Collections

This file is in the following collections:

Technical Reports (Computing Science)

Metric Techniques for High-Dimensional Indexing Open Access

Descriptions

Author or creator
Digout, Christian
Additional contributors
Subject/Keyword
high-dimensional indexing
Type of item
Computing Science Technical Report
Computing science technical report ID
TR04-19
Language
English
Place
Time
Description
Technical report TR04-19. Despite the proposal of numerous tree-based structures for high-dimensional similarity searches, techniques based on a sequential scan, such as the VA-File, have been shown to be quite effective. In this thesis we present three new access structures which use sequential access patterns to efficiently answer similarity queries for high-dimensional vector and metric data. Two of these access structures are designed to answer range queries, while the third access method is intended for nearest neighbor queries. The three access methods organize preprocessed data and reorder the original data sequentially on disk. At query time, portions of the data are read sequentially to prevent expensive random disk I/Os that prevent many access methods for high-dimensional data and metric data from being efficient. Experimental results show the first two proposed access structures can process range queries up to 24 times faster than the VA-File and up to 69 times faster than a sequential scan of the data set. The third proposed method is designed for nearest neighbor queries and is up to 15 times faster than the VA-File method and more than 40 times faster than a sequential scan of the data set. Unlike the VA-File, the access structures presented in this thesis work in general metric spaces, in addition to vector space (under a metric distance), scale well with increasing the radius of range queries and the number of nearest neighbors retrieved for nearest neighbor queries, and can be easily implemented.
Date created
2004
DOI
doi:10.7939/R3JQ0SX0P
License information
Creative Commons Attribution 3.0 Unported
Rights

Citation for previous publication

Source
Link to related item

File Details

Date Uploaded
Date Modified
2014-05-01T01:23:17.782+00:00
Audit Status
Audits have not yet been run on this file.
Characterization
File format: pdf (Portable Document Format)
Mime type: application/pdf
File size: 471167
Last modified: 2015:10:12 17:32:26-06:00
Filename: TR04-19.pdf
Original checksum: fe216645a942e0d6a607e8637aecc5ba
Well formed: true
Valid: true
Page count: 60
Activity of users you follow
User Activity Date