A fast retrieval technique for large graph structures

Abstract

Graphs are a typical and basic data structure for computer algorithms. A two-dimensional array and a list are well-known as for their representation. These data representations have contrasting features for retrieval time and space efficiency. Aho et al. [3] proposed a method for combining the compactness of the list with the fast retrieval of the array. Applications of Aho's scheme were, however, limited to static data structures because the updating algorithm was not given.

By introducing three one-dimensional arrays based on Aho's data structure, called a triple-array structure, this paper proposes a method for updating arcs stored in the triple-array without degrading the worst-case retrieval time complexity 0(1). The triple-array maps arcs into two one-dimensional arrays CHECK and NEXT according to another one-dimensional array BASE. An updating algorithm presented here moves the initial positions of the arcs into other possible positions in the triple-array, by a first-fit strategy which searches the array CHECK starting from the head. For a large graph, the updating algorithm is improved by introducing the criterion of searching the array CHECK locally. Theoretical and experimental observations show that the updating time of the triple-array becomes practical while keeping the worstcase retrieval time complexity 0(1).

Keywords:

• Graph structures
• Worst-case time complexity
• Storing and retrieving
• Data compressing
• Finite automata

C.R.Categories:

• Algorithms
• Performance E.1 Data Structure[Graphs]
• H.3.3[Information search and retrieval]
• F.2.2[Nonnumerical Algorithms and problems]