NDLI: An efficient technique for nearest-neighbor query processing on the SPY-TEC

Content Provider	IEEE Xplore Digital Library
Author	Dong-Ho Lee Hyoung-Joo Kim
Copyright Year	1989
Abstract	The SPY-TEC (spherical pyramid-technique) was proposed as a new indexing method for high-dimensional data spaces using a special partitioning strategy that divides a d-dimensional data space into 2d spherical pyramids. In the SPY-TEC, an efficient algorithm for processing hyperspherical range queries was introduced with a special partitioning strategy. However, the technique for processing k-nearest-neighbor queries, which are frequently used in similarity search, was not proposed. In this paper, we propose an efficient algorithm for processing nearest-neighbor queries on the SPY-TEC by extending the incremental nearest-neighbor algorithm. We also introduce a metric that can be used to guide an ordered best-first traversal when finding nearest neighbors on the SPY-TEC. Finally, we show that our technique significantly outperforms the related techniques in processing k-nearest-neighbor queries by comparing it to the R*-tree, the X-tree, and the sequential scan through extensive experiments.
Sponsorship	IEEE IEEE Comput. Soc. Tech. Committee on Data Eng IEEE Computer Society
Starting Page	1472
Ending Page	1486
Page Count	15
File Size	1491668
File Format	PDF
ISSN	10414347
Volume Number	15
Issue Number	6
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2003-11-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Nearest neighbor searches Indexing Partitioning algorithms Query processing Multidimensional systems Multimedia databases Costs Spatial databases Information retrieval Data mining
Content Type	Text
Resource Type	Article
Subject	Information Systems Computational Theory and Mathematics Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Visible Reverse k-Nearest Neighbor Query Processing in Spatial Databases

Batch Nearest Neighbor Search for Video Retrieval

Ranked Reverse Nearest Neighbor Search

Continuous Nearest Neighbor Queries over Sliding Windows

Efficient Processing of Metric Skyline Queries

Probabilistic Reverse Nearest Neighbor Queries on Uncertain Data

Incremental Evaluation of Visible Nearest Neighbor Queries

On the dimensionality curse and the self-similarity blessing

Reverse Nearest Neighbors Search in Ad Hoc Subspaces

An efficient technique for nearest-neighbor query processing on the SPY-TEC

Similar Documents

Visible Reverse k-Nearest Neighbor Query Processing in Spatial Databases

Batch Nearest Neighbor Search for Video Retrieval

Ranked Reverse Nearest Neighbor Search

Continuous Nearest Neighbor Queries over Sliding Windows

Efficient Processing of Metric Skyline Queries

Probabilistic Reverse Nearest Neighbor Queries on Uncertain Data

Incremental Evaluation of Visible Nearest Neighbor Queries

On the dimensionality curse and the self-similarity blessing

Reverse Nearest Neighbors Search in Ad Hoc Subspaces

An efficient technique for nearest-neighbor query processing on the SPY-TEC