Fast Similarity Search for Graphs by Edit Distance

被引：0

作者：

Rachkovskij, D. A. ^{[1
]}

机构：

[1] NAS Ukraine, Int Res & Training Ctr Informat Technol & Syst, Kiev, Ukraine

来源：

CYBERNETICS AND SYSTEMS ANALYSIS | 2019年 / 55卷 / 06期

关键词：

similarity search; graph; edit distance; nearest neighbor; index structure; inverted indexing; LINEAR-PROGRAMMING FORMULATION; INDEX STRUCTURES; BINARY VECTORS; ASSIGNMENT; COMPUTATION; EMBEDDINGS; ALGORITHM; ROBUST; JOINS;

D O I：

10.1007/s10559-019-00213-9

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

This survey article considers index structures for fast similarity search for objects represented by trees and graphs. Edit distance is used as a measure of similarity. The execution of exact similarity search queries is considered. Algorithms based on the filter-and-refine strategy using inverted indexing are mainly presented. Algorithms for exact calculation of the graph edit distance and its lower and upper bounds are also considered.

引用

页码：1039 / 1051

页数：13

共 70 条

[1] A parallel graph edit distance algorithm [J].

Abu-Aisheh, Zeina ;

Raveaux, Romain ;

Ramel, Jean-Yves ;

Martineau, Patrick .

EXPERT SYSTEMS WITH APPLICATIONS, 2018, 94 :41-57

[2] Graph edit distance contest: Results and future challenges [J].

Abu-Aisheh, Zeina ;

Gauzere, Benoit ;

Bougleux, Sebastien ;

Ramel, Jean-Yves ;

Brun, Luc ;

Raveaux, Romain ;

Heroux, Pierre ;

Adam, Sebastien .

PATTERN RECOGNITION LETTERS, 2017, 100 :96-103

[3]

ABUAISHEH Z, PATTERN RECOGNITION

[4]

Ahu Aisheh Z., 2015, 4 INT C PATT REC APP, P271, DOI [DOI 10.5220/0005209202710278, 10.5220/0005209202710278]

[5] Approximating Tree Edit Distance through String Edit Distance [J].

Akutsu, Tatsuya ;

Fukagawa, Daiji ;

Takasu, Atsuhiro .

ALGORITHMICA, 2010, 57 (02) :325-348

[6] SimGNN: A Neural Network Approach to Fast Graph Similarity Computation [J].

Bai, Yunsheng ;

Ding, Hao ;

Bian, Song ;

Chen, Ting ;

Sun, Yizhou ;

Wang, Wei .

PROCEEDINGS OF THE TWELFTH ACM INTERNATIONAL CONFERENCE ON WEB SEARCH AND DATA MINING (WSDM'19), 2019, :384-392

[7]

Berchtold S, 1996, PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON VERY LARGE DATA BASES, P28

[8] A survey on tree edit distance and related problems [J].

Bille, P .

THEORETICAL COMPUTER SCIENCE, 2005, 337 (1-3) :217-239

[9]

Blumenthal D.B., 2018, PATTERN RECOGNITION

[10] Ring Based Approximation of Graph Edit Distance [J].

Blumenthal, David B. ;

Bougleux, Sebastien ;

Gamper, Johann ;

Brun, Luc .

STRUCTURAL, SYNTACTIC, AND STATISTICAL PATTERN RECOGNITION, S+SSPR 2018, 2018, 11004 :293-303

← 1 2 3 4 5 6 7 →