next up previous
Next: Vector spaces Up: Retrieval models Previous: Retrieval models

Semantic networks

Let tex2html_wrap_inline1227 be a semantic network retrieval model. The set tex2html_wrap_inline1245 consists of objects each of which is a node in a directed graph G with two types of arcs: isa and partof. An isa-arc denotes the subclass-superclass relationship between the nodes it connects; a partof-arcs denotes the part-whole relationship between the nodes (Fitzgerald 1995). Let tex2html_wrap_inline1361 be the tex2html_wrap_inline1363 matrix such that tex2html_wrap_inline1365 if there is an isa-arc from tex2html_wrap_inline1277 and tex2html_wrap_inline1369 , and tex2html_wrap_inline1371 , if there is no such arc. Let tex2html_wrap_inline1373 be a similar matrix for the partof-relationship. An object tex2html_wrap_inline1375 abstracts an object tex2html_wrap_inline1377 iff G has a path of isa-arcs from tex2html_wrap_inline1377 to tex2html_wrap_inline1375 . When tex2html_wrap_inline1375 abstracts tex2html_wrap_inline1377 , tex2html_wrap_inline1375 is an abstraction of tex2html_wrap_inline1377 . An object tex2html_wrap_inline1375 specializes an object tex2html_wrap_inline1377 iff G has a path of isa-arcs from tex2html_wrap_inline1375 to tex2html_wrap_inline1377 . Thus, tex2html_wrap_inline1375 abstracts tex2html_wrap_inline1377 iff tex2html_wrap_inline1377 specializes tex2html_wrap_inline1375 . Any object both abstracts and specializes itself.

Associated with each node is a single set of labels. A label tex2html_wrap_inline1411 is a sequence of elements such that for all i, tex2html_wrap_inline1415 . Thus, labels may contain not only tokens but also object ids. If tex2html_wrap_inline1417 , then tex2html_wrap_inline1419 is the set of labels associated with tex2html_wrap_inline1375 . If tex2html_wrap_inline1277 , and tex2html_wrap_inline1425 , tex2html_wrap_inline1427 . An expectation is a 3-tuple tex2html_wrap_inline1429 such that tex2html_wrap_inline1431 . For example, if tex2html_wrap_inline1433 , then tex2html_wrap_inline1435 , tex2html_wrap_inline1437 , tex2html_wrap_inline1439 , and tex2html_wrap_inline1441 are expectations. Intuitively, an expectation reflects how completed a label is with respect to an object. If tex2html_wrap_inline1443 is an expectation, tex2html_wrap_inline1445 , tex2html_wrap_inline1447 , tex2html_wrap_inline1449 , and key(z) = head(ecseq(z)).

tex2html_wrap_inline1453 , where tex2html_wrap_inline1419 is the set of labels associated with tex2html_wrap_inline1375 , tex2html_wrap_inline1459 , and tex2html_wrap_inline1461 . Note that tex2html_wrap_inline1463 and tex2html_wrap_inline1465 can be empty. For example, if tex2html_wrap_inline1467 , tex2html_wrap_inline1469 . Let tex2html_wrap_inline1279 and tex2html_wrap_inline1277 . The object similarity between tex2html_wrap_inline1375 and tex2html_wrap_inline1477 is tex2html_wrap_inline1479 , where tex2html_wrap_inline1481 , tex2html_wrap_inline1483 , tex2html_wrap_inline1485 completes tex2html_wrap_inline1487 , tex2html_wrap_inline1489 and tex2html_wrap_inline1491 . The object tex2html_wrap_inline1477 activates the object tex2html_wrap_inline1375 iff there exists a label tex2html_wrap_inline1483 and a label tex2html_wrap_inline1481 such that tex2html_wrap_inline1485 completes tex2html_wrap_inline1487 . If there is no tex2html_wrap_inline1481 such that tex2html_wrap_inline1485 completes tex2html_wrap_inline1509 , then tex2html_wrap_inline1511 .

Let [x] be a label associated with a node tex2html_wrap_inline1375 . The token closure of [x], tex2html_wrap_inline1519 , is the set of all token sequences that complete [x]. For example, let tex2html_wrap_inline1523 and tex2html_wrap_inline1525 be two nodes such that tex2html_wrap_inline1527 and tex2html_wrap_inline1529 , where all tex2html_wrap_inline1531 . Then tex2html_wrap_inline1533 . An algorithm for computing token closures is given in Listing 1 of the Appendix. Intuitively, the token closure of a label is the set of all token sequences through which the label can be completed, and, consequently, the label's node activated. For example, the first two elements of tex2html_wrap_inline1193 complete tex2html_wrap_inline1537 associated in tex2html_wrap_inline1539 , thus activating tex2html_wrap_inline1523 . When tex2html_wrap_inline1523 is activated, tex2html_wrap_inline1545 is advanced one element to the right, which allows the rest of the label, i.e., tex2html_wrap_inline1547 to be completed by the last two elements of tex2html_wrap_inline1193 , thus activating tex2html_wrap_inline1525 . The token closure of a node tex2html_wrap_inline1375 , tex2html_wrap_inline1555 , is the union of the token closures of its labels. Thus, the token closure of a node is the set of all token sequences that can possibly activate the node. The union of the token closures of nodes in tex2html_wrap_inline1245 is called tex2html_wrap_inline1245 -closure. Formally, tex2html_wrap_inline1245 -closure tex2html_wrap_inline1563 .


next up previous
Next: Vector spaces Up: Retrieval models Previous: Retrieval models

Vladimir Kulyukin
Fri Oct 29 09:32:57 CDT 1999