Document (#8237)

Author

Dillenburg, J.F.
Nelson, P.C.

Title

Perimeter search

Source

Artificial intelligence. 65(1994) no.1, S.165-178

Year

1994

Abstract

Presents a technique for improving heuristic search efficiency. This admissible technique is referred to as perimeter search since it relies on a perimeter of nodes around the goal. The perimeter is generated by a breadth-first search from the goal to all nodes at a given depth d. The path back to the goal along with each perimeter node's state descriptor are stored in a table. The search then proceeds normally from the start node on the perimeter. If a match is found, the search can terminate with the path being formed with the path from the start to the perimeter node together with the previously stored path from the perimeter node to the goal. Both analytical and experimental results are presented to show that perimeter search is more efficient than IDA* and A* in terms of time complexity and number of nodes expanded for two problem domains

Similar documents (author)

1. Nelson, M.J.: Correlation of term usage and term indexing frequencies (1988) 5.02

   5.020828 = sum of:
     5.020828 = weight(author_txt:nelson in 651) [ClassicSimilarity], result of:
       5.020828 = score(doc=651,freq=1.0), product of:
         0.99999994 = queryWeight, product of:
           8.033325 = idf(docFreq=38, maxDocs=44218)
           0.12448145 = queryNorm
         5.0208282 = fieldWeight in 651, product of:
           1.0 = tf(freq=1.0), with freq of:
             1.0 = termFreq=1.0
           8.033325 = idf(docFreq=38, maxDocs=44218)
           0.625 = fieldNorm(doc=651)
   

2. Nelson, M.G.: Catalogers as librarians (1986) 5.02

   5.020828 = sum of:
     5.020828 = weight(author_txt:nelson in 2880) [ClassicSimilarity], result of:
       5.020828 = score(doc=2880,freq=1.0), product of:
         0.99999994 = queryWeight, product of:
           8.033325 = idf(docFreq=38, maxDocs=44218)
           0.12448145 = queryNorm
         5.0208282 = fieldWeight in 2880, product of:
           1.0 = tf(freq=1.0), with freq of:
             1.0 = termFreq=1.0
           8.033325 = idf(docFreq=38, maxDocs=44218)
           0.625 = fieldNorm(doc=2880)
   

3. Nelson, T.H.: ¬A file structure for the complex, the changing, and the indeterminate (1965) 5.02

   5.020828 = sum of:
     5.020828 = weight(author_txt:nelson in 4468) [ClassicSimilarity], result of:
       5.020828 = score(doc=4468,freq=1.0), product of:
         0.99999994 = queryWeight, product of:
           8.033325 = idf(docFreq=38, maxDocs=44218)
           0.12448145 = queryNorm
         5.0208282 = fieldWeight in 4468, product of:
           1.0 = tf(freq=1.0), with freq of:
             1.0 = termFreq=1.0
           8.033325 = idf(docFreq=38, maxDocs=44218)
           0.625 = fieldNorm(doc=4468)
   

4. Nelson, M.J.: ¬The design of a hypertext interface for information retrieval (1991) 5.02

   5.020828 = sum of:
     5.020828 = weight(author_txt:nelson in 4805) [ClassicSimilarity], result of:
       5.020828 = score(doc=4805,freq=1.0), product of:
         0.99999994 = queryWeight, product of:
           8.033325 = idf(docFreq=38, maxDocs=44218)
           0.12448145 = queryNorm
         5.0208282 = fieldWeight in 4805, product of:
           1.0 = tf(freq=1.0), with freq of:
             1.0 = termFreq=1.0
           8.033325 = idf(docFreq=38, maxDocs=44218)
           0.625 = fieldNorm(doc=4805)
   

5. Nelson, S.J.: From meaning to term : semantic locality in the UMLS metathesaurus (1992) 5.02

   5.020828 = sum of:
     5.020828 = weight(author_txt:nelson in 5611) [ClassicSimilarity], result of:
       5.020828 = score(doc=5611,freq=1.0), product of:
         0.99999994 = queryWeight, product of:
           8.033325 = idf(docFreq=38, maxDocs=44218)
           0.12448145 = queryNorm
         5.0208282 = fieldWeight in 5611, product of:
           1.0 = tf(freq=1.0), with freq of:
             1.0 = termFreq=1.0
           8.033325 = idf(docFreq=38, maxDocs=44218)
           0.625 = fieldNorm(doc=5611)
   

Similar documents (content)

1. Rada, R.: Hypertext writing and document reuse : the role of a semantic net (1990.) 0.14

   0.13878454 = sum of:
     0.13878454 = product of:
       0.86740345 = sum of:
         0.014094275 = weight(abstract_txt:with in 5911) [ClassicSimilarity], result of:
           0.014094275 = score(doc=5911,freq=1.0), product of:
             0.060141988 = queryWeight, product of:
               1.6425582 = boost
               2.4997334 = idf(docFreq=9868, maxDocs=44218)
               0.014647494 = queryNorm
             0.23435001 = fieldWeight in 5911, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               2.4997334 = idf(docFreq=9868, maxDocs=44218)
               0.09375 = fieldNorm(doc=5911)
         0.02694235 = weight(abstract_txt:from in 5911) [ClassicSimilarity], result of:
           0.02694235 = score(doc=5911,freq=2.0), product of:
             0.07352408 = queryWeight, product of:
               1.8161288 = boost
               2.7638826 = idf(docFreq=7577, maxDocs=44218)
               0.014647494 = queryNorm
             0.36644253 = fieldWeight in 5911, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               2.7638826 = idf(docFreq=7577, maxDocs=44218)
               0.09375 = fieldNorm(doc=5911)
         0.5329507 = weight(abstract_txt:node in 5911) [ClassicSimilarity], result of:
           0.5329507 = score(doc=5911,freq=3.0), product of:
             0.42682907 = queryWeight, product of:
               3.789566 = boost
               7.689554 = idf(docFreq=54, maxDocs=44218)
               0.014647494 = queryNorm
             1.2486279 = fieldWeight in 5911, product of:
               1.7320508 = tf(freq=3.0), with freq of:
                 3.0 = termFreq=3.0
               7.689554 = idf(docFreq=54, maxDocs=44218)
               0.09375 = fieldNorm(doc=5911)
         0.29341614 = weight(abstract_txt:path in 5911) [ClassicSimilarity], result of:
           0.29341614 = score(doc=5911,freq=1.0), product of:
             0.45513332 = queryWeight, product of:
               4.518572 = boost
               6.8766055 = idf(docFreq=123, maxDocs=44218)
               0.014647494 = queryNorm
             0.64468175 = fieldWeight in 5911, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               6.8766055 = idf(docFreq=123, maxDocs=44218)
               0.09375 = fieldNorm(doc=5911)
       0.16 = coord(4/25)
   

2. Vocht, L. De: Exploring semantic relationships in the Web of Data : Semantische relaties verkennen in data op het web (2017) 0.12

   0.122135825 = sum of:
     0.122135825 = product of:
       0.38167447 = sum of:
         0.01703725 = weight(abstract_txt:match in 4232) [ClassicSimilarity], result of:
           0.01703725 = score(doc=4232,freq=1.0), product of:
             0.097754724 = queryWeight, product of:
               1.047058 = boost
               6.373877 = idf(docFreq=204, maxDocs=44218)
               0.014647494 = queryNorm
             0.1742857 = fieldWeight in 4232, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               6.373877 = idf(docFreq=204, maxDocs=44218)
               0.02734375 = fieldNorm(doc=4232)
         0.009192096 = weight(abstract_txt:with in 4232) [ClassicSimilarity], result of:
           0.009192096 = score(doc=4232,freq=5.0), product of:
             0.060141988 = queryWeight, product of:
               1.6425582 = boost
               2.4997334 = idf(docFreq=9868, maxDocs=44218)
               0.014647494 = queryNorm
             0.15283991 = fieldWeight in 4232, product of:
               2.236068 = tf(freq=5.0), with freq of:
                 5.0 = termFreq=5.0
               2.4997334 = idf(docFreq=9868, maxDocs=44218)
               0.02734375 = fieldNorm(doc=4232)
         0.0124248825 = weight(abstract_txt:from in 4232) [ClassicSimilarity], result of:
           0.0124248825 = score(doc=4232,freq=5.0), product of:
             0.07352408 = queryWeight, product of:
               1.8161288 = boost
               2.7638826 = idf(docFreq=7577, maxDocs=44218)
               0.014647494 = queryNorm
             0.16899066 = fieldWeight in 4232, product of:
               2.236068 = tf(freq=5.0), with freq of:
                 5.0 = termFreq=5.0
               2.7638826 = idf(docFreq=7577, maxDocs=44218)
               0.02734375 = fieldNorm(doc=4232)
         0.06500807 = weight(abstract_txt:technique in 4232) [ClassicSimilarity], result of:
           0.06500807 = score(doc=4232,freq=8.0), product of:
             0.1503706 = queryWeight, product of:
               1.8365313 = boost
               5.5898643 = idf(docFreq=448, maxDocs=44218)
               0.014647494 = queryNorm
             0.432319 = fieldWeight in 4232, product of:
               2.828427 = tf(freq=8.0), with freq of:
                 8.0 = termFreq=8.0
               5.5898643 = idf(docFreq=448, maxDocs=44218)
               0.02734375 = fieldNorm(doc=4232)
         0.047751654 = weight(abstract_txt:stored in 4232) [ClassicSimilarity], result of:
           0.047751654 = score(doc=4232,freq=2.0), product of:
             0.19432576 = queryWeight, product of:
               2.0877671 = boost
               6.3545527 = idf(docFreq=208, maxDocs=44218)
               0.014647494 = queryNorm
             0.24572992 = fieldWeight in 4232, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               6.3545527 = idf(docFreq=208, maxDocs=44218)
               0.02734375 = fieldNorm(doc=4232)
         0.0464126 = weight(abstract_txt:goal in 4232) [ClassicSimilarity], result of:
           0.0464126 = score(doc=4232,freq=1.0), product of:
             0.3026788 = queryWeight, product of:
               3.684876 = boost
               5.6078424 = idf(docFreq=440, maxDocs=44218)
               0.014647494 = queryNorm
             0.15333945 = fieldWeight in 4232, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               5.6078424 = idf(docFreq=440, maxDocs=44218)
               0.02734375 = fieldNorm(doc=4232)
         0.098268226 = weight(abstract_txt:search in 4232) [ClassicSimilarity], result of:
           0.098268226 = score(doc=4232,freq=19.0), product of:
             0.22538671 = queryWeight, product of:
               4.2064433 = boost
               3.6580524 = idf(docFreq=3098, maxDocs=44218)
               0.014647494 = queryNorm
             0.43599832 = fieldWeight in 4232, product of:
               4.358899 = tf(freq=19.0), with freq of:
                 19.0 = termFreq=19.0
               3.6580524 = idf(docFreq=3098, maxDocs=44218)
               0.02734375 = fieldNorm(doc=4232)
         0.08557971 = weight(abstract_txt:path in 4232) [ClassicSimilarity], result of:
           0.08557971 = score(doc=4232,freq=1.0), product of:
             0.45513332 = queryWeight, product of:
               4.518572 = boost
               6.8766055 = idf(docFreq=123, maxDocs=44218)
               0.014647494 = queryNorm
             0.18803218 = fieldWeight in 4232, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               6.8766055 = idf(docFreq=123, maxDocs=44218)
               0.02734375 = fieldNorm(doc=4232)
       0.32 = coord(8/25)
   

3. Bressan, M.; Peserico, E.: Choose the damping, choose the ranking? (2010) 0.12

   0.11935226 = sum of:
     0.11935226 = product of:
       0.74595165 = sum of:
         0.03657971 = weight(abstract_txt:analytical in 2563) [ClassicSimilarity], result of:
           0.03657971 = score(doc=2563,freq=1.0), product of:
             0.10248924 = queryWeight, product of:
               1.0721141 = boost
               6.5264034 = idf(docFreq=175, maxDocs=44218)
               0.014647494 = queryNorm
             0.35691267 = fieldWeight in 2563, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               6.5264034 = idf(docFreq=175, maxDocs=44218)
               0.0546875 = fieldNorm(doc=2563)
         0.008221661 = weight(abstract_txt:with in 2563) [ClassicSimilarity], result of:
           0.008221661 = score(doc=2563,freq=1.0), product of:
             0.060141988 = queryWeight, product of:
               1.6425582 = boost
               2.4997334 = idf(docFreq=9868, maxDocs=44218)
               0.014647494 = queryNorm
             0.13670418 = fieldWeight in 2563, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               2.4997334 = idf(docFreq=9868, maxDocs=44218)
               0.0546875 = fieldNorm(doc=2563)
         0.1934724 = weight(abstract_txt:nodes in 2563) [ClassicSimilarity], result of:
           0.1934724 = score(doc=2563,freq=2.0), product of:
             0.3561458 = queryWeight, product of:
               3.4615963 = boost
               7.0240583 = idf(docFreq=106, maxDocs=44218)
               0.014647494 = queryNorm
             0.5432393 = fieldWeight in 2563, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               7.0240583 = idf(docFreq=106, maxDocs=44218)
               0.0546875 = fieldNorm(doc=2563)
         0.50767785 = weight(abstract_txt:node in 2563) [ClassicSimilarity], result of:
           0.50767785 = score(doc=2563,freq=8.0), product of:
             0.42682907 = queryWeight, product of:
               3.789566 = boost
               7.689554 = idf(docFreq=54, maxDocs=44218)
               0.014647494 = queryNorm
             1.1894172 = fieldWeight in 2563, product of:
               2.828427 = tf(freq=8.0), with freq of:
                 8.0 = termFreq=8.0
               7.689554 = idf(docFreq=54, maxDocs=44218)
               0.0546875 = fieldNorm(doc=2563)
       0.16 = coord(4/25)
   

4. Falquet, G.; Guyot, J.; Nerima, L.: Languages and tools to specify hypertext views on databases (1999) 0.11

   0.10666197 = sum of:
     0.10666197 = product of:
       0.6666373 = sum of:
         0.011745229 = weight(abstract_txt:with in 3968) [ClassicSimilarity], result of:
           0.011745229 = score(doc=3968,freq=1.0), product of:
             0.060141988 = queryWeight, product of:
               1.6425582 = boost
               2.4997334 = idf(docFreq=9868, maxDocs=44218)
               0.014647494 = queryNorm
             0.19529167 = fieldWeight in 3968, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               2.4997334 = idf(docFreq=9868, maxDocs=44218)
               0.078125 = fieldNorm(doc=3968)
         0.015875932 = weight(abstract_txt:from in 3968) [ClassicSimilarity], result of:
           0.015875932 = score(doc=3968,freq=1.0), product of:
             0.07352408 = queryWeight, product of:
               1.8161288 = boost
               2.7638826 = idf(docFreq=7577, maxDocs=44218)
               0.014647494 = queryNorm
             0.21592833 = fieldWeight in 3968, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               2.7638826 = idf(docFreq=7577, maxDocs=44218)
               0.078125 = fieldNorm(doc=3968)
         0.27638912 = weight(abstract_txt:nodes in 3968) [ClassicSimilarity], result of:
           0.27638912 = score(doc=3968,freq=2.0), product of:
             0.3561458 = queryWeight, product of:
               3.4615963 = boost
               7.0240583 = idf(docFreq=106, maxDocs=44218)
               0.014647494 = queryNorm
             0.7760561 = fieldWeight in 3968, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               7.0240583 = idf(docFreq=106, maxDocs=44218)
               0.078125 = fieldNorm(doc=3968)
         0.36262703 = weight(abstract_txt:node in 3968) [ClassicSimilarity], result of:
           0.36262703 = score(doc=3968,freq=2.0), product of:
             0.42682907 = queryWeight, product of:
               3.789566 = boost
               7.689554 = idf(docFreq=54, maxDocs=44218)
               0.014647494 = queryNorm
             0.84958375 = fieldWeight in 3968, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               7.689554 = idf(docFreq=54, maxDocs=44218)
               0.078125 = fieldNorm(doc=3968)
       0.16 = coord(4/25)
   

5. Scholer, F.; Williams, H.E.; Turpin, A.: Query association surrogates for Web search (2004) 0.10

   0.100398526 = sum of:
     0.100398526 = product of:
       0.4183272 = sum of:
         0.016610263 = weight(abstract_txt:with in 2236) [ClassicSimilarity], result of:
           0.016610263 = score(doc=2236,freq=2.0), product of:
             0.060141988 = queryWeight, product of:
               1.6425582 = boost
               2.4997334 = idf(docFreq=9868, maxDocs=44218)
               0.014647494 = queryNorm
             0.27618414 = fieldWeight in 2236, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               2.4997334 = idf(docFreq=9868, maxDocs=44218)
               0.078125 = fieldNorm(doc=2236)
         0.015875932 = weight(abstract_txt:from in 2236) [ClassicSimilarity], result of:
           0.015875932 = score(doc=2236,freq=1.0), product of:
             0.07352408 = queryWeight, product of:
               1.8161288 = boost
               2.7638826 = idf(docFreq=7577, maxDocs=44218)
               0.014647494 = queryNorm
             0.21592833 = fieldWeight in 2236, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               2.7638826 = idf(docFreq=7577, maxDocs=44218)
               0.078125 = fieldNorm(doc=2236)
         0.06566807 = weight(abstract_txt:technique in 2236) [ClassicSimilarity], result of:
           0.06566807 = score(doc=2236,freq=1.0), product of:
             0.1503706 = queryWeight, product of:
               1.8365313 = boost
               5.5898643 = idf(docFreq=448, maxDocs=44218)
               0.014647494 = queryNorm
             0.43670815 = fieldWeight in 2236, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               5.5898643 = idf(docFreq=448, maxDocs=44218)
               0.078125 = fieldNorm(doc=2236)
         0.09647291 = weight(abstract_txt:stored in 2236) [ClassicSimilarity], result of:
           0.09647291 = score(doc=2236,freq=1.0), product of:
             0.19432576 = queryWeight, product of:
               2.0877671 = boost
               6.3545527 = idf(docFreq=208, maxDocs=44218)
               0.014647494 = queryNorm
             0.49644944 = fieldWeight in 2236, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               6.3545527 = idf(docFreq=208, maxDocs=44218)
               0.078125 = fieldNorm(doc=2236)
         0.13260742 = weight(abstract_txt:goal in 2236) [ClassicSimilarity], result of:
           0.13260742 = score(doc=2236,freq=1.0), product of:
             0.3026788 = queryWeight, product of:
               3.684876 = boost
               5.6078424 = idf(docFreq=440, maxDocs=44218)
               0.014647494 = queryNorm
             0.43811268 = fieldWeight in 2236, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               5.6078424 = idf(docFreq=440, maxDocs=44218)
               0.078125 = fieldNorm(doc=2236)
         0.09109263 = weight(abstract_txt:search in 2236) [ClassicSimilarity], result of:
           0.09109263 = score(doc=2236,freq=2.0), product of:
             0.22538671 = queryWeight, product of:
               4.2064433 = boost
               3.6580524 = idf(docFreq=3098, maxDocs=44218)
               0.014647494 = queryNorm
             0.4041615 = fieldWeight in 2236, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               3.6580524 = idf(docFreq=3098, maxDocs=44218)
               0.078125 = fieldNorm(doc=2236)
       0.24 = coord(6/25)