A Plain Indexing Method for Organizing Conceptually
Promiscuous Data
Toyoaki Nishida, Kazuto Koujitani, and Hideaki Takeda
Graduate School of Information Science
Nara Institute of Science and Technology
8916-5 Takayama, Ikoma, Nara 630-01, Japanemail: nishida@is.aist-nara.ac.jp

Abstract

An ability of organizing conceptually promiscuous data into a uniform structure is critical toknowledge navigating systems. In this paper, we
describe a plain indexing method for accumulating diverse information originating from heterogeneous natural information sources. We present a
couple of heuristic techniques: (a) orthogonal decomposition which allows for reorganizing a given
information base into a Cartesian product of primitive concepts, and (b) analogical re nement whichenables further elaboration based on the measurement of similarity. The proposal is implemented and evaluated against sample information
bases containing about a few thousands conceptual units. We discuss the strength and weaknessof the method based on the analysis of experimental results.

Introduction

Most of information people produce and manipulate(such as natural language documents, or images) isconceptually promiscuous in the sense that its semantics is not rigorously de ned or completely agreed
upon. As long term research goals, we aim at (a)designing an inventory of knowledge media (Ste k,1986) with varying degrees of elaboration for accumulating diverse information originating from natural information sources, and (b) constructing a system capable of helping people create, share and explore large knowledge spaces. Towards this end, we
are working on the Knowledgeable Community project(Nishida and Takeda, 1993; Nishida et al., 1994;
Takeda et al., 1995; Nishida et al., 1995) including several small projects such as information gathering andclassi cation (Iwazume et al., 1995), content-based information summarization (Matsuo et al., 1995), andbuilding a knowledge media information base systemcalled CM-2.
In this paper, we describe a plain indexing method
for accumulating diverse information originating fromheterogeneous natural information sources. We present

a couple of heuristic techniques: (a) orthogonal decomposition which allows for reorganizing a given information base into a Cartesian product of primitive
concepts, and (b) analogical re nement which enables
further elaboration based on the measurement of similarity. The proposal is implemented and evaluatedagainst sample information bases containing abouta few thousands conceptual units. We discuss thestrength and weakness of the method based on theanalysis of experimental results.
In what follows, we will rst overview CM-2 and describe the role of a plain indexing method using associational representation. We then present heuristic
techniques for reorganizing CM-2 information bases.
Finally, we show experimental results and make discussion.

Associational Representation in CM-2
Information Base
Architecture of the CM-2 Information Base
SystemCM-2 is a knowledge media information base system

under construction
at Nara Institute of Science andTechnology.1 The design goal of CM-2 is to provide
users with a means of accumulating, sharing, exploring, and re ning conceptually promiscuous information
gathered from vast information sources.
CM-2 consists of a collection of information bases.
Each CM-2 information base is possessed by an individual person or a group (Figure 1). It consists of acollection of workspaces and agents. Each workspaceprovides a particular view of looking at information
stored in the information base through a particular information representation language. Each agent manipulates information representation or/and interact
with the user. The user or agents in CM-2 information
bases can interact with other, or incorporate information from other kinds of information sources connected
to Internet.
1\CM" stands for \Contextual Media" which stands for
our long term theoretical research goal.

information space for a person or a group(a) naive presentation(b) refinement of (a)IJCAI-93

IJCAI-93 & venue

human-oriented
workspace

Franceproblem solving
agent
comuter-oriented

natural language
machine learning

FranceIJCAI-93 & topics
problem solving
natural language
machine learning

protocolIJCAII

Figure 1: The architecture of the CM-2 informationbase system
(a)

(b)

Nara

Nara & temples

the Nara park
deer

Daibutsu

Todai-ji
Kofuku-ji

Todai-ji

Horyu-jiFigure 2: Example of associations in CM-2

Use of Associational Representation in
CM-2 Information BaseIn this paper, we focus on associational representation,
which allows the user to explore a way of articulating
conceptually promiscuous information by aggregating
conceptually relevant information. The basic entities
of associational representation are (a) a unit which represents either a concept or an external datum, and (b)an association which associates a collection of key concepts (hereafter keys) with a collection of units (hereafter values) which is normally reminded of by thegiven keys. Figure 2 shows a couple of associations.
The left says that given a concept \Nara", one may
be reminded of \Todai-ji", \the Nara park", \deer",and \Daibutsu". The right is an example of association with more than one key. It says that \Todaiji", \Kofuku-ji", and \Horyu-ji" are reminded when
\Nara" and \temples" are given as keys.

Conceptual Promiscuity with CM-2
Associational Representation

As suggested by the examples shown in Figure 2, what
is reminded of by a given set of keywords may welldi er from person to person, and people might givedi erent names to the same concept or the same nameto di erent concepts. We call such a phenomenon conceptual promiscuity.
It is our policy to live with conceptual promiscuity, rather than imposing standardization on terminol-

IJCAI-93 & sponsors
IJCAII

Figure 3: Conceptual promiscuity
ogy or conceptualization. Such a \generous mind", as
we believe, will be bene cial to us, for it will foster
creative thinking. On one hand, we have to admit itbecause raw data are already there. We would liketo incorporate them without spending huge amount oftime on reforming them into a well-de ned knowledge
medium and make use of them before their contents
become obsolete. On the other hand, completely wellde ned knowledge medium is not possible as philosophers based on the Wittgenstein doctrine have pointed
out, for our language can at best be de ned connotationally as language games.
In fact, we are experimenting with gathering information from varieties of information sources, suchas research notes, WWW pages, and personal memoranda. It is quite easy to generate associational representations from those raw materials and use them as
indices.
On the other hand, conceptual promiscuity is not desirable from the information retrieval point of view, forit will cause both noise and incompleteness. Compare
two sets of associations in Figure 3. In Figure 3a, thevalue space associated with the concept \IJCAI-95"
is conceptually promiscuous in the sense that entities
of various kinds are mixed up there. In contrast, thevalues of each association in Figure 3b are more coherent. For understanding the domain andutilizing theinformation, the latter is more useful.2

Re ning CM-2 Information BaseIn order to resolve diculty with conceptual promiscuity, we explore a way of using heuristics to suggest
the user how to re ne CM-2 information bases into a
coherent structure, as shown in Figure 4.
2

One may complain about fragmentation of informationin Figure 3b and rather prefer the presentation shown in
Figure 3a. We cope with such complaints by introducing facilities for aggregating information and present it
altogether.

B and a threshold  > 0
huse heuristic rules to diagnose B and produce; given an information baserepeata set of suggestions and associated penalties if
any undesirable portion is foundi;

ifhthe largest penalty is greater than

then

if

then

j(V [fxg]\V [fy g])0V [fx;yg]jpenalty;jV3 [fx;yg]jsuggestion\resolvethedierencebetweenV3[fxg] \ V3[fyg] and V3 [fx; yg],by3 adding z to V[fx; yg]3 if z 62
V3[fx; yg] and z 2 (V [fxg] \V [fyg]) "

 i;

B

h x

as suggested by the diagnosis
with the largest penalty i;elseexit from the loop

for everif

Figure 4: A general procedure of re nement

h for concepts x and y :V3[fxg] \ V3 [fyg] 6= V3 [fx; yg] i333h for two sets of concepts ; ,9z [ z 2 V[ ] ^ z 2 V[ ] ] i



:

then

In this paper, we assume that people implicitly encode a certain kind of conceptual structure into associational representations even though they are not given
an explicit description tool for conceptualization, andwe are able to detect such regularity by some means
such as statistical analysis.
We present a couple of heuristic techniques which
will detect inappropriate associations from CM-2 information base and suggest a possible way of remedying
them. Orthogonal decomposition attempts to decompose a given information base into coherent groups ofassociations, by analyzing how the user intersects associations. Analogical re nement is a less ecient but
more powerful technique for further elaborating information base based on the measurement of similarity.
The details will be given in the next two sections.

Orthogonal Decomposition of CM-2
Information BaseLet us rst introduce some notations and relations.
Given an association with keys fk1 ; : : : ; km g and values fv1 ; : : : ; vn g, we denoteV[fk1 ; : : : ; km g] = fv1 ; : : : ; vn g.
Given a set of keys fk1; : : : ; km g, we de ne the extended value V3 [fk1 ; : : : ; km g] as follows:
V3[fk1 ; : :[: ; km g]=
V[fk1 ; : : : ; km g [ fkm+1 ; : : : ; kn g],
km+1 ;:::;knwhere m < n, ki 6= kj whenever i 6= j . For example,

V3 [f\IJCAI-93"g]= V[f\IJCAI-93"g [ f\venue"g][ V[f\IJCAI-93"g [ f\topics"g][ V[f\IJCAI-93"g [ f\sponsors"g]= f \France"; \problem solving";\knowledge representation";\machine learning"; \IJCAII"gpenalty1;
suggestion\remove z from V[ ]."Figure 5: Diagnosis rules for orthogonal decompositionin Figure 3b. Extended values provide a means forlooking at the entire picture of entities comprising agiven set of keys.
Given a unit x, we de ne the extended keys K3[x] as
K3[x] = ffk1 ; : : : ; km g j x 2 V3[fk1 ; : : : ; km g]g:
Two set of keys fx1 ; : : : ; xm g and fy1 ; : : : ; yn g are
orthogonal to each other (with respect to the associations of information base at3 that situation), if
theirassociated values, i.e., V [fx1 ; : : : ; xm g] andV3 [fy1 ; : : : ; yn g], have a non-empty intersection. For
instance, the key f\IJCAI-93"g is orthogonal to thekeys f\venue"g, f\topics"g, and f\sponsors"g, in Figure 3b, forV3[f\IJCAI-93"g] \ V3 [f\venue"g]= f\France"; \problem solving"; : : : ; g\ f\France"g= f\France"g 6= fg.
Orthogonal decomposition is a technique of re ning
CM-2 information base using diagnosis rules shown in
Figure 5.
Example of the application of orthogonal decomposition is illustrated in Figure 6.

Limitation of Orthogonal Decomposition

Orthogonal decomposition is easy and useful, but limited in several ways. First, it cannot make preference.
For example, the set of associations in Figure 3b can
not be derived from the association shown in Figure 3aeven if those shown in Figure 7 are added, for there
is no way of deriving the fact that concepts \venue",\sponsors", and \topics" are used for referring to more
specialized concepts \countries", \organizations", and\AI", respectively.

parks

Nara

Kyoto

Todai-ji the Nara park
deer
Daibutsu

Gion
Kinkaku-ji
Ginkaku-ji
the Maruyama park

Murou-ji

templesrhododendron

flowers

Kinkaku-ji Ginkaku-ji
Todai-ji Eihei-ji

Nara

the Central park
the Nara park
the Maruyama park

peony cherry blossom
rhododendron
azaleaNara & temples
Todai-ji

Kyoto & temples
Kinkaku-ji Ginkaku-ji

Murou-ji & flowers
rhododendron

templesEihei-jiNara & parks
the Nara Park

Kyoto & parks
the Maruyama park

Murou-ji
Nara

parks
the Central park

Nara
deer

Kyoto

flowers
peony

Gion

DaibtsuazaleaFigure 6: Orthogonal decomposition of CM-2 information baseAI
problem solving

knowledge representation
machine learningknowledge discovery
countries

organizations

Japan Canada
U.S.A.
Franceand y, we de ne the similarity Sim[x; y] as shown in
Figure 8. Basedon that de nition, we de ne the key
similarity Sim3 [ ; ] between keys and as the sumof maximal pairwise similarities of units in and .
Namely,Sim3[ ; 2]
3
= max 4

AAAI

IEEE

Figure 7: Some associations
Furthermore, orthogonal decomposition may sometimes lead to useless association. For example, although\$1.00" 2 V[f\the fare"; \the toll bridge A"]
and\$1.00" 2 V[f\the price"; \the burger"g];
it is not useful to keep association\$1.00" 2 V[f \the fare"; \the toll bridge A";\the price"; \the burger" g]:In the next section, we propose a solution for theformer problem. The latter will be discussed later inthis paper.
Analogical Re nement of CM-2

Information Base

Analogical re nement is based on the measurement ofsimilarity. Given a couple of non-orthogonal keys x

X max[Sim[x; y]]; X max[Sim[x; y]]5

x2 y2

IJCAII

y2 x2

For concepts x, y, and a threshold  > 0, we denotex  y if Sim[x; y ]  . Similarly, for keys , , and athreshold ,  if Sim3[ ; ]  .
The analogical re nement heuristic suggests to re nea CM-2 information base according to the following
diagnosis rule:if

x 2 V3 [ ],y 2 V3 [ [ fag], andx 62 V3 [ [ fag]thenpenalty Sim[x; y ] + Sim3 [ ; ]suggestion
add x to V[ [ fag] .

In other words, the above rule will cause
the concept
x to be added to V[ [ fag] if x 2 V3 [ ],  , andx  y for some y 2 V3 [ [ fag].
For example, suppose a set of associations are given
as shown in Figure 9, resulting from putting together
associations shown in Figure 3b and Figure 7. Consider
now the association shown in Figure 10 is added tothose shown in Figure 9.
Similarities are computed as partly shown in Table 1
and a new associations will be created as shown in
Figure 11. For example, as

x and y, we de ne the similarity Sim[x; y] between x and y from three perspectives
Sim(a) [x; y ] + Sim(b) [x; y ] + Sim(c) [x; y ]2 [0; 1].
Sim[x; y ] =Given a couple of non-orthogonal keys
and let it:x; ySim(a) [] measures the similarity between
is as follows:3x and y by comparing concepts in V3 [fxg] and those in V3 [fyg]. The de nitionx; y] = jV3 [fxg][1 V3 [fyg]j3
3
1( jfz j z 2 V [fxg] ^ z 2 V [fy g]gj
+ j fz j z 2 V3 [fxg] 0 V3 [fyg] ^ 9u[ u 2 V3 [fy g] ^ (K3 [z ] \ K3 [u] 6= fg) ]g j
+ j fz j z 2 V3 [fy g] 0 V3 [fxg] ^ 9u[ u 2 V3 [fxg] ^ (K3 [z ] \ K3 [u] 6= fg) ]g j).
Sim(b) [x;y ] measures the rate of common keys of associations containing x and y as values. Namely,
3
3
jfz j z 2 K [x] ^ z 2 K [y ]gj(b).
Sim [x; y ] =33
jK [x] [ K [y ]jSim(c) [x; y ] measures the rate of keys orthogonal both to x and to y . Thus,jfz j hz is orthogonal to xi ^ hz is orthogonal to y igj(c).
Sim [x; y] =jfz j hz is orthogonal to xig [ fz j hz is orthogonal to y igj
(a)

Sim

[

Figure 8: De ning similarity between concepts
IJCAI-93 & venue
FranceIJCAI-93 & sponsors

IJCAI-93 & topics
problem solving
natural language
machine learning

IJCAII
KDD-95
1995 knowledge discovery
CanadaprivacyAAAIknowledge representation

Figure 9: The set of associations resulting from putting
together associations shown in Figure 3b and Figure 7
K3 [\Canada"] = ff\countries"g; f\KDD-95"gg
K3[\Japan"] = ff\countries"ggso,Sim(b) [\Canada"; \Japan"]jff\countries"ggj= jff\countries"
g; f\KDD-95"ggj
KDD-95
1995 knowledge discovery
CanadaprivacyAAAIknowledge representation

Figure 10: An association added to the associations
shown in Figure 9x

Table 1: Part of similarities computed for associations
shown in Figure 10, Figure 3b, and Figure 7\Canada"\France"\knowledge representation\knowledge discovery"\AAAI"\KDD-95"y\Japan"\U.S.A."\problem solving"\machine learning"\IJCAII"\IJCAI-93"

Sim[

x; y]

1 1 1
3 2
1 1
3 1 2
1 1
3 1 3
1 1
3 1 3
1 1
3 1 3
1 8
3 1 11= 12 .
On the other hand, as
V3[\Canada"] = V3[\Japan"] = fg
and no keys have intersection with keys f\Canada"gor f\Japan"g, soSim(b) [\Canada"; \Japan"]= Sim(c) [\Canada"; \Japan"]= 0:Hence,
Sim[\Canada"; \Japan"]= 13 1 Sim(a)[\Canada"; \Japan"]= 31 1 12 :Using the similarities,\KDD-95"  \IJCAI-93"\knowledge representation"  \problem solving"KDD-95
1995 privacy
KDD-95 & venue
CanadaKDD-95 & topics
knowledge representation
knowledge discovery
KDD-95 & sponsors
AAAI

Figure 11: New contexts resulting from adding a context shown in Figure 10 to those shown in Figure 3b
and Figure 7

Ikoma park

flowers

cherry blossom

cherry blossom

tickets

open

rhododendron
anirissimilarIkoma park & flowers

Ayameike park
similarcherry blossom

roller coarster
boats
iris

we will obtain\knowledge representation"
2 V[f\KDD-95"; \topics"g]
The results obtained are conceptually more wellstructured than those obtained solely by orthogonal
decomposition.

Experiments

We have implemented a kernel of CM-2 on top of Common Lisp and tcl/tk. We are evaluating CM-2 against
accumulating various kinds of information such as research memoranda, technical surveys, regional guide,
personal diary, and so on. Besides testing against thesesmall examples and the examples described so far, wehave made a couple of experiments with a nontrivial
scale.
We have manually constructed a CM2 information base for regional guide of Nara, Japan.
It contains about 1,850 concepts and 870 associations.
As a result of orthogonal decomposition, CM-2 has produced 212 revisions, about 80 of which have been founduseful. Others are uninteresting. On the other hand,the analogical re nement heuristic has generated 65
suggestions, 20 of which are found useful.
There are several interesting suggestions. For example, from \cherry blossom" 2 V[f\Ikoma park"g] and,\cherry blossom" 2 V[f\ owers"g], we obtained\cherry blossom" 2 V[f\Ikoma park"; \ owers"g];from which we in turn obtained\iris" 2 V[f\Ayameike park"; \ owers"g]based on\iris" 2 V[f\Ayameike park"g];\Ikoma park"  \Ayameike park"; and\cherry blossom"  \iris";as shown in Figure 12.
Experiment 1

Ayameike park & flowers
iris

Figure 12: An interesting suggestion obtained by orthogonal decomposition and analogical re nement
Experiment 2
We have gathered WWW pages in
the Kansai (west) area of Japan and have generated
associational representations using a simple keyword
extraction and text analysis program. As a result,
we have obtained about 700 concepts and 230 associations. CM-2 has proposed 1130 and 230 revisions
using the orthogonal decomposition and analogical renement heuristics. About 230 and 12 proposals by
orthogonal decomposition and analogical re nement
heuristics, respectively, are found useful.

Discussion

This work is complementary to recent work on information gathering from heterogeneous sources on
Internet (Levy et al., 1994; Armstrong et al., 1995;
Balabanovi'c and Shoham, 1995; Li, 1995). Instead of
focusing on the strategies and heuristics for information gathering, we concentrate on how to classify information obtained from multiple information sources
and integrate it into personal information base.
The basic recognition behind this research is atrade-o between the bene t from conceptually wellstructured information space and the cost for organizing information space. The more organized is theinformation space, the more utilities can a navigator
provide, while the higher cost we have to pay. When
we look at vast information from various information
sources accessible through a global computer network,
it seems almost impossible to design a well-de ned conceptual structure on which information is accumulated.
Our approach is to provide a framework of information representation with a low structural facilities
and to facilitate raw information from vast information sources to be incorporated without much laborand gradually re ned and elaborated as more insights
are obtained.

How successful is our approach? Our early experiments have ended up in very promising results as far
as a half of our goal is concerned. Members of ourgroup have been able to use associational representation to accumulate varieties of information taken fromvast information sources and access relevant information.
However, it turned out that there is much space toimprove as for the other half of our goal: to use heuristics to semi-automatically introduce
conceptual structure into the information base.3 Unfortunately, therate of useful suggestions from the heuristics, being
less than 30%, seems to be too low, though we havenot evaluated how well the given set of sample associations is conceptually structured from the beginning.
To improve the quality of heuristics, we are currently
looking at introduction of other kinds of heuristics anda domain knowledge.
One possibility is introducing a notion of signi canceof association. Given a set of keys , we may ask
the user to specify either is signi cant or not (i.e.,
insigni cant), depending on whether thinking about
makes sense to the user or not, respectively.
If the user
has explicitly given the contents of V3[ ], is taken tobe signi cant. The user may well reserve the remark
about the signi cance of the keys . In such a case,is called signi cance-unknown. Using this convention,
we can avoid thinking about such associations as\$1.00" 2 V[f \the fare"; \the toll bridge A";\the price"; \the burger"g]:
Or, we might use the following kind of heuristic
and store \hindsight" as a more structured conceptual
structure.
ifh V3 [fx; y g] does not make sense, or
the userassert thatV3 [fx; yg] 6= (V3[fxg] \ V3[fyg]) ithen
8z [ z 2 (V3 [fxg] \ V3 [fy g])! :hz isa xi ^ :hz isa y i ].
Further research is open for future.

Conclusion

In this paper, we have proposed an approach to accumulating diverse information using a plain indexing
method. We have given a couple of heuristic techniques, orthogonal decomposition and analogical renement, for re ning the conceptual structure of information base. We have discussed the strength andweakness of the method based on the analysis of experimental results.
3

Hu man and Steier (Hu man and Steier, 1995) propose a similar method using heuristic join to combine datafrom multiple structured sources.

References

Armstrong, Robert; Freitag, Dayne; Joachims,
Thorsten; and Mitchell, Tom 1995. WebWatcher:
A learning apprentice for the World Wide Web. In

Working Notes of the AAAI Spring Symposium on Information Gathering from Heterogeneous, Distributed
Environments. 6{12.

Balabanovi'c, Marko and Shoham, Yoav 1995. Learning information retrieval agents: Experiments with
automated web browsing. In Working Notes of the
AAAI Spring Symposium on Information Gatheringfrom Heterogeneous, Distributed Environments. 13{
18.
Hu man, Scott B. and Steier, David 1995. Heuristic
joins to integrate structured heterogeneous data. In

Working Notes of the AAAI Spring Symposium on Information Gathering from Heterogeneous, Distributed
Environments. 74{77.

Iwazume, Michiaki; Takeda, Hideaki; and Nishida,Toyoaki 1995. Ontology-based approach to information gathering and text categorization. (to be presented at ISDL'95).
Levy, Alon Y.; Sagiv, Yehoshua; and Srivasava, Divesh 1994. Towards e cient information gathering
agents. In Working Notes of the AAAI Spring Symposium on Software Agents. 64{70.
Li, Wen-Syan 1995. Knowledge gathering and matching in heterogeneous databases. In Working Notes of
the AAAI Spring Symposium on Information Gathering from Heterogeneous, Distributed Environments.
116{121.
Matsuo, Toshiyuki; Takeda, Hideaki; and Nishida,Toyoaki 1995. An application of knowledge medium
to semi-automated summarization of technical papers
in metallurgy. In JSAI Annual Convention Records.
15-07 (in Japanese).
Nishida, Toyoaki and Takeda, Hideaki 1993. Towards
the knowledgeable community. In Proceedings International Conference on Building and Sharing ofVery-Large Scale Knowledge Bases '93 (KB&KS '93).
Ohmsha, Ltd. 157{166.
Nishida, Toyoaki; Takeda, Hideaki; and Iino, Kenji
1994. Mediation in the knowledgeable community. In
Working Notes of the AAAI Spring Symposium on
Software Agents.
Nishida, Toyoaki; Takeda, Hideaki; Iino, Kenji; andNishiki, Masanobu 1995. A knowledge media approach to ontology development. In Mars, N.J.I.,
editor 1995, Towards Very Large Knowledge Bases:
Knowledge Building & Knowledge Sharing 1995. IOS
Press. 84{94.
Ste k, Mark 1986. The next knowledge medium. AI
Magazine 7(1):34{46.
Takeda, Hideaki; Iino, Kenji; and Nishida, Toyoaki
1995. Ontology-supported agent communication. In
Working Notes of the AAAI Spring Symposium on Information Gathering from Heterogeneous, Distributed
Environments. AAAI. 160{165.