For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Efficient Incremental Query Processing via Vantage Point Filtering in Dynamic Multi-Dimensional Index Structures
Byung-Gon KIM Sam Hyuk NOH DoSoon PARK Haechull LIM Jaeho LEE
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2001/06/01
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Papers Selected from 2000 International Technical Conference on Circuits/Systems, Computers and Communications (ITC-CSCC 2000))
multi-dimensional index structure, VP filtering, incremental query, k-NNQ, range query,
Full Text: PDF>>
Efficient query processing in multi-dimensional indexing structures is an important issue for multimedia data applications. In this paper, we propose incremental k-nearest neighbor query (k-NNQ) and range query algorithms for R-tree based structures. The novel aspect of these algorithms is that they make use of the notion of VP filtering, a concept borrowed from the MVP-tree. The filtering notion allows for delaying of computational overhead until absolutely necessary. By so doing, we attain considerable performance benefits while paying insignificant overhead during the construction of the index structure. We implemented our algorithms and carried out experiments to demonstrate the capability and usefulness of our method. Results show that improvements range from 8% to 23% in response time for the experimental environment that we considered.