Share Email Print

Proceedings Paper

Index point data using algebraic lattice
Author(s): Xiangyang Xue; Hangzai Luo; Lide Wu
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper Abstract

In this paper, we propose a new method for indexing large amounts of points in high-dimensional space. The basic principle is as follows: Data points or feature vectors extracted from objects are first quantized into lattice points by using lattice vector quantization. Inverted file is adopted to organize those lattice points. Fast retrieval is implemented by sing the good properties of algebraic lattice. We first tested the indexing performance for range query by using lattice Eg and Hash. The initial experimental result show our method has good indexing performance. However, we found, Hash has to search the inverted file for a large amounts of lattice points if query window is bigger or dimension is high. To solve this problem, we use Trie instead of Hash and propose Tire Parallel Search Algorithm to fast access the inverted file. Further experiments have been done for n-dimensional data point by using lattice Zn. The results show the proposed index structure owns many good properties such as low CPU cost and low I/O cost in comparison to R-tree.

Paper Details

Date Published: 23 December 1999
PDF: 11 pages
Proc. SPIE 3972, Storage and Retrieval for Media Databases 2000, (23 December 1999); doi: 10.1117/12.373558
Show Author Affiliations
Xiangyang Xue, Fudan Univ. (China)
Hangzai Luo, Fudan Univ. (China)
Lide Wu, Fudan Univ. (China)

Published in SPIE Proceedings Vol. 3972:
Storage and Retrieval for Media Databases 2000
Minerva M. Yeung; Boon-Lock Yeo; Charles A. Bouman, Editor(s)

© SPIE. Terms of Use
Back to Top
Sign in to read the full article
Create a free SPIE account to get access to
premium articles and original research
Forgot your username?