Publication Type
Journal Article
Version
acceptedVersion
Publication Date
8-2014
Abstract
In this paper we study a novel query type, called direct neighbor query. Two objects in a dataset are direct neighbors (DNs) if a window selection may exclusively retrieve these two objects. Given a source object, a DN search computes all of its direct neighbors in the dataset. The DNs define a new type of affinity that differs from existing formulations (e.g., nearest neighbors, nearest surrounders, reverse nearest neighbors, etc.) and finds application in domains where user interests are expressed in the form of windows, i.e., multi-attribute range selections. Drawing on key properties of the DN relationship, we develop an I/O optimal processing algorithm for data indexed with a spatial access method. In addition to plain DN search, we also study its K -DN and all-DN variants. The former relaxes the DN condition – two objects are K -DNs if a window query may retrieve them and only up to K−1 other objects – whereas the all-DN variant computes the DNs of every object in the dataset. Using real, large-scale data, we demonstrate the efficiency and practicality of our approach, and show that it vastly outperforms a competitor constructed from previous work.
Keywords
Direct neighbors, Window query, Low-dimensional search
Discipline
Databases and Information Systems | Numerical Analysis and Scientific Computing
Publication
Information Systems
Volume
44
First Page
73
Last Page
92
ISSN
0306-4379
Identifier
10.1016/j.is.2014.03.003
Publisher
Elsevier
Citation
ZHANG, Jilian; MOURATIDIS, Kyriakos; and PANG, Hwee Hwa.
Direct Neighbor Search. (2014). Information Systems. 44, 73-92.
Available at: https://ink.library.smu.edu.sg/sis_research/2218
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Additional URL
http://dx.doi.org/10.1016/j.is.2014.03.003
Included in
Databases and Information Systems Commons, Numerical Analysis and Scientific Computing Commons