Affiliations: CICESE-Ciencias de la Computación, Carr. Ensenada-Tijuana No. 3918, Zona Playitas, C.P. 22860, Ensenada, Baja California, México
Correspondence:
[*]
Corresponding author. Edgar Chávez, CICESE-Ciencias de la Computación, Carr. Ensenada-Tijuana No. 3918,
Zona Playitas, C.P. 22860, Ensenada, Baja California, México. Tel.: +52 646 1750500;
elchavez@cicese.mx
Abstract: Many multimedia objects accept an abstract representation as point sets, or point clouds, in the plane. Searching for objects in a collection is traduced to searching for matching point clouds. In this paper algorithms and data structures are given for indexing and searching point clouds. The indexes are implemented using off-the-shelf, popular, software components. Experimental tests were performed on large databases, including a synthetic database of 10 million point clouds (1000 points per cloud) and the MIR Flickr-1M database, which contains 1 million high-resolution images. The performance of the proposed indexes was evaluated according to: Average search time, construction time, recall@k, memory usage and performance under insertions and deletions. A thorough comparison was performed between the fastest method available in the literature and a repertoire of implementations. The most competitive index is three orders of magnitude faster than the state of the art, in the image database, with recall @ 1 ≥0.989 for 20% insertions and deletions.
Keywords: Point cloud search, similarity search index, multimedia indexing
