Record |
Author |
Pau Riba; Josep Llados; Alicia Fornes; Anjan Dutta |
Title |
Large-scale Graph Indexing using Binary Embeddings of Node Contexts |
Type |
Conference Article |
Year |
2015 |
Publication |
10th IAPR-TC15 Workshop on Graph-based Representations in Pattern Recognition |
Abbreviated Journal |
|
Volume |
9069 |
Issue |
|
Pages |
208-217 |
Keywords |
Graph matching; Graph indexing; Application in document analysis; Word spotting; Binary embedding |
Abstract |
Graph-based representations are experiencing a growing usage in visual recognition and retrieval due to their representational power in front of classical appearance-based representations in terms of feature vectors. Retrieving a query graph from a large dataset of graphs has the drawback of the high computational complexity required to compare the query and the target graphs. The most important property for a large-scale retrieval is the search time complexity to be sub-linear in the number of database examples. In this paper we propose a fast indexation formalism for graph retrieval. A binary embedding is defined as hashing keys for graph nodes. Given a database of labeled graphs, graph nodes are complemented with vectors of attributes representing their local context. Hence, each attribute counts the length of a walk of order k originated in a vertex with label l. Each attribute vector is converted to a binary code applying a binary-valued hash function. Therefore, graph retrieval is formulated in terms of finding target graphs in the database whose nodes have a small Hamming distance from the query nodes, easily computed with bitwise logical operators. As an application example, we validate the performance of the proposed methods in a handwritten word spotting scenario in images of historical documents. |
Address |
Beijing; China; May 2015 |
Corporate Author |
|
Thesis |
|
Publisher |
Springer International Publishing |
Place of Publication |
|
Editor |
C.-L.Liu; B.Luo; W.G.Kropatsch; J.Cheng |
Language |
|
Summary Language |
|
Original Title |
|
Series Editor |
|
Series Title |
|
Abbreviated Series Title |
LNCS |
Series Volume |
|
Series Issue |
|
Edition |
|
ISSN |
0302-9743 |
ISBN |
978-3-319-18223-0 |
Medium |
|
Area |
|
Expedition |
|
Conference |
GbRPR |
Notes |
DAG; 600.061; 602.006; 600.077 |
Approved |
no |
Call Number |
Admin @ si @ RLF2015a |
Serial |
2618 |
Permanent link to this record |