Index point data using algebraic lattice

Xiangyang Xue; Hangzai Luo; Lide Wu

doi:10.1117/12.373558

23 December 1999 Index point data using algebraic lattice

Xiangyang Xue, Hangzai Luo, Lide Wu

Proceedings Volume 3972, Storage and Retrieval for Media Databases 2000; (1999) https://doi.org/10.1117/12.373558
Event: Electronic Imaging, 2000, San Jose, CA, United States

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 E_g 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 Z_n. 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.

Citation Download Citation

Xiangyang Xue, Hangzai Luo, and Lide Wu "Index point data using algebraic lattice", Proc. SPIE 3972, Storage and Retrieval for Media Databases 2000, (23 December 1999); https://doi.org/10.1117/12.373558

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available