Hashing Technique: A New Index Method for High Dimensional Data
| dc.contributor.author | Song, Zhexuan | en_US |
| dc.contributor.author | Roussopoulos, Nick | en_US |
| dc.date.accessioned | 2004-05-31T21:08:38Z | |
| dc.date.available | 2004-05-31T21:08:38Z | |
| dc.date.created | 1999-09 | en_US |
| dc.date.issued | 1999-09-25 | en_US |
| dc.description.abstract | When dimension goes high, sequential scan processing becomes more efficient than most index-based query. In this paper, we propose a new index method for high-dimensional data spaces. This method is based on hashing technique. The basic idea is: First find a hashing function which puts the given d-dimensional space data into a d'-dimensional buckets where d' << d. Then, we use existing index techniques to manage those buckets. We later define some properties of a good hashing function and give four hashing functions. To demonstrate the efficiency of our idea, we experimentally compared our algorithms with sequential scan and Pyramid-Techniques. The results demonstrate that this method outperforms others for skewed data set. It always beats the sequential scan by using only half of elapsed time for range query. However if the data has uniform distribution, Pyramid-Technique is still the best method. | en_US |
| dc.format.extent | 202344 bytes | |
| dc.format.mimetype | application/postscript | |
| dc.identifier.uri | http://hdl.handle.net/1903/509 | |
| dc.language.iso | en_US | |
| dc.relation.isAvailableAt | Digital Repository at the University of Maryland | en_US |
| dc.relation.isAvailableAt | University of Maryland (College Park, Md.) | en_US |
| dc.relation.isAvailableAt | Tech Reports in Computer Science and Engineering | en_US |
| dc.relation.isAvailableAt | Computer Science Department Technical Reports | en_US |
| dc.relation.ispartofseries | UM Computer Science Department; CS-TR-4059 | en_US |
| dc.title | Hashing Technique: A New Index Method for High Dimensional Data | en_US |
| dc.type | Technical Report | en_US |