DocumentCode :
264248
Title :
Scalable proximity indexing with the list of clusters
Author :
Tellez, Eric S. ; Chavez, Edgar ; Ortiz Bejar, Jose
Author_Institution :
INFOTEC, Aguascalientes, Mexico
fYear :
2014
fDate :
5-7 Nov. 2014
Firstpage :
1
Lastpage :
6
Abstract :
In a wide spectrum of computer applications, the central problem is to satisfy proximity queries in a database of abstract objects under a given distance. That is, to find objects near a given query. Above certain size-threshold, a sequential scan of the database is too costly to be of use and an index should be used. When the intrinsic dimension of a collection is too high, most metric indexes will perform as bad as an exhaustive scan of the database, as part of the curse of dimensionality. Among the available metric indexes, under high intrinsic dimension, two indexes perform better than others, these are the List of Clusters and AESA; however, they hold a quadratic preprocessing time. In most setups LC is preferred over AESA since the latter needs a quadratic amount of memory while LC use a linear amount. In this paper we tackle the major drawback of the LC, which is the construction time. More detailed, the core of our contribution is the parallelization of the preprocessing and searching algorithms, taking advantage of the capabilities of modern multi-core computer architectures. We did extensive experimentation and report peak efficiencies of 45% to 70% in construction time for our testing datasets (close to 3.5 and 6 times speedup, for our eight core testing hardware). We also reformulated range and nearest neighbor search algorithms ending up with a very high efficiency speedup of 45% and 85% for range queries retrieving 0.01% and 0.02% of the database respectively in real world datasets.
Keywords :
database indexing; multiprocessing systems; parallel algorithms; query processing; search problems; AESA; LC; abstract object database; computer applications; construction time; core testing hardware; curse of dimensionality; high-intrinsic dimension; intrinsic dimension; list-of-clusters; metric indexes; multicore computer architectures; nearest neighbor search algorithms; parallelization; peak efficiencies; preprocessing algorithms; proximity queries; quadratic memory; quadratic preprocessing time; range query retrieval; range search algorithms; real world datasets; scalable proximity indexing; Clustering algorithms; Color; Indexes; Measurement; Parallel algorithms; Search problems; Metric Indexes; Parallel Algorithms; Parallel Metric Indexes; Proximity Searching; Query by Content; Scalable Pattern Recognition;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Power, Electronics and Computing (ROPEC), 2014 IEEE International Autumn Meeting on
Conference_Location :
Ixtapa
Type :
conf
DOI :
10.1109/ROPEC.2014.7036336
Filename :
7036336
Link To Document :
بازگشت