k-Nearest neighbor searching in hybrid spaces |
| |
| Affiliation: | 1. Michigan State University, East Lansing, MI, United States;2. University of Michigan - Dearborn, Dearborn, MI, United States;1. Laboratory for Studies in Research Evaluation, Institute for System Analysis and Computer Science (IASI-CNR), National Research Council of Italy, Istituto di Analisi dei Sistemi e Informatica, Consiglio Nazionale delle Ricerche, Via dei Taurini 19, 00185 Roma, Italy;2. University of Rome “Tor Vergata”, and Institute for System Analysis and Computer Science, National Research Council of Italy, Dipartimento di Ingegneria dell’Impresa, Università degli Studi di Roma “Tor Vergata”, Via del Politecnico 1, 00133 Roma, Italy;3. National Research Council of Italy, Istituto di Analisi dei Sistemi e Informatica, Consiglio Nazionale delle Ricerche, Via dei Taurini 19, 00185 Roma, Italy |
| |
| Abstract: | Little work has been reported in the literature to support k-nearest neighbor (k-NN) searches/queries in hybrid data spaces (HDS). An HDS is composed of a combination of continuous and non-ordered discrete dimensions. This combination presents new challenges in data organization and search ordering. In this paper, we present an algorithm for k-NN searches using a multidimensional index structure in hybrid data spaces. We examine the concept of search stages and use the properties of an HDS to derive a new search heuristic that greatly reduces the number of disk accesses in the initial stage of searching. Further, we present a performance model for our algorithm that estimates the cost of performing such searches. Our experimental results demonstrate the effectiveness of our algorithm and the accuracy of our performance estimation model. |
| |
| Keywords: | Hybrid data space Nearest neighbor search Similarity search Spatial indexing Information retrieval |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
