Please use this identifier to cite or link to this item: https://hdl.handle.net/20.500.11851/6888
Title: Indexing Through Laplacian Spectra
Authors: Demirci, Muhammed Fatih
van Leuken, Reinier H.
veltkamp, Remeo C.
Keywords: spectral graph theory
indexing
laplacian spectrum
spectral integral variation
information retrieval
Publisher: Academic Press Inc Elsevier Science
Abstract: With ever growing databases containing multimedia data, indexing has become a necessity to avoid a linear search. We propose a novel technique for indexing multimedia databases in which entries can be represented as graph structures. In our method, the topological structure of a graph as well as that of its subgraphs are represented as vectors whose components correspond to the sorted laplacian eigenvalues of the graph or subgraphs. Given the laplacian spectrum of graph G, we draw from recently developed techniques in the field of spectral integral variation to generate the laplacian spectrum of graph G + e without computing its eigendecomposition, where G + e is a graph obtained by adding edge e to graph G. This process improves the performance of the system for generating the subgraph signatures for 1.8% and 6.5% in datasets of size 420 and 1400, respectively. By doing a nearest neighbor search around the query spectra, similar but not necessarily isomorphic graphs are retrieved. Given a query graph, a voting schema ranks database graphs into an indexing hypothesis to which a final matching process can be applied. The novelties of the proposed method come from the powerful representation of the graph topology and successfully adopting the concept of spectral integral variation in an indexing algorithm. To examine the fitness of the new indexing framework, we have performed a number of experiments using an extensive set of recognition trials in the domain of 2D and 3D object recognition. The experiments, including a comparison with a competing indexing method using two different graph-based object representations, demonstrate both the robustness and efficacy of the overall approach. (C) 2007 Elsevier Inc. All rights reserved.
URI: https://doi.org/10.1016/j.cviu.2007.09.012
https://hdl.handle.net/20.500.11851/6888
ISSN: 1077-3142
1090-235X
Appears in Collections:Bilgisayar Mühendisliği Bölümü / Department of Computer Engineering
Scopus İndeksli Yayınlar Koleksiyonu / Scopus Indexed Publications Collection
WoS İndeksli Yayınlar Koleksiyonu / WoS Indexed Publications Collection

Show full item record



CORE Recommender

SCOPUSTM   
Citations

21
checked on Dec 21, 2024

WEB OF SCIENCETM
Citations

19
checked on Oct 5, 2024

Page view(s)

116
checked on Dec 16, 2024

Google ScholarTM

Check




Altmetric


Items in GCRIS Repository are protected by copyright, with all rights reserved, unless otherwise indicated.